Improved Approximation Algorithms for Low-Rank Problems Using Semidefinite Optimization
This work addresses optimization challenges in machine learning and data analysis, offering incremental improvements over prior methods for problems like matrix completion and reduced-rank regression.
The authors tackled low-rank optimization problems by developing a relax-then-round strategy using semidefinite optimization, achieving provably near-optimal solutions with a multiplicative approximation ratio that is never worse than specified bounds and demonstrating improved scalability through matrix size reductions.
Inspired by the impact of the Goemans-Williamson algorithm on combinatorial optimization, we construct an analogous relax-then-round strategy for low-rank optimization problems. First, for orthogonally constrained quadratic optimization problems, we derive a semidefinite relaxation and a randomized rounding scheme that obtains provably near-optimal solutions, building on the blueprint from Goemans and Williamson for the Max-Cut problem. For a given $n \times m$ semi-orthogonal matrix, we derive a purely multiplicative approximation ratio for our algorithm, and show that it is never worse than $\max(2/(πm), 1/(π(\log (2m)+1)))$. We also show how to compute a tighter constant for a finite $(n,m)$ by solving a univariate optimization problem. We then extend our approach to generic low-rank optimization problems by developing new semidefinite relaxations that are both tighter and more broadly applicable than those in prior works. Although our original proposal introduces large semidefinite matrices as decision variables, we show that most of the blocks in these matrices can be safely omitted without altering the optimal value, hence improving the scalability of our approach. Using several examples (including matrix completion, basis pursuit, and reduced-rank regression), we show how to reduce the size of our relaxation even further. Finally, we numerically illustrate the effectiveness and scalability of our relaxation and sampling scheme on orthogonally constrained quadratic optimization and matrix completion problems.