Local Search Algorithms for Rank-Constrained Convex Optimization

We propose greedy and local search algorithms for rank-constrained convex optimization, namely solving$\underset{\mathrm{rank}(A)\leq r^*}{\min}\, R(A)$given a convex function $R:\mathbb{R}^{m\times n}\rightarrow \mathbb{R}$ and a parameter $r^*$.These algorithms consist of repeating two steps: (a) adding a new rank-1 matrix to $A$ and (b) enforcing the rank constraint on $A$. We provide a tight theoretical analysis showing thatif the \emph{rank-restricted} condition number of $R$ is $\kappa$,a solution $A$ with rank $O(r^*\cdot \min\{\kappa \log \frac{R(\mathbf{0}) - R(A^*)}{\eps}, \kappa^2\})$ and $R(A) \leq R(A^*) + \eps$can be recovered, where $A^*$ is the optimal solution. This significantly generalizesassociated results on sparse convex optimization, as well as rank-constrained convex optimizationfor smooth functions. We then introduce new practical variants of these algorithms that have superior runtime and recover better solutions in practice.We demonstrate the versatility of these methods on a wide range of applications involvingmatrix completion and robust principal component analysis.