Low-rank matrix approximations have been used in many applications, because they provide compact representations of the data and reveal the underlying structure. This dissertation is concerned with applications of low-rank approximations in optimization problems. Motivation comes from a recent effort in designing radiotherapy treatment plans for patients with cancer. The problem was formulated as a second-order cone program. Due to the size of the problem, low-rank matrices were used in order to create a computationally tractable approximation. This work is an attempt to theoretically explain the success of low-rank approximations in such problems. The main vehicle for this analysis is a stylized optimization problem with randomly sampled ellipsoidal constraints. We consider two different matrix approximations, one based on the Singular Value Decomposition and one based on column sampling, and apply them to the matrices in the stylized problem. We provide results about the probability distributions of the optimal values of these problems as well as their relative difference. Since the focus is on problems with large number of constraints, we provide asymptotic results, when the number of constraints tends to infinity. We finally compare the performance of the two approximations and discuss the implications of our results.
展开▼
