We propose a method for low-rank semidefinite programming in application to the semidefinite relaxation of unconstrained binary quadratic problems. The method improves an existing solution of the semidefinite programming relaxation to achieve a lower rank solution. This procedure is computationally efficient as it does not require projecting on the cone of positive-semidefinite matrices. Its performance in terms of objective improvement and rank reduction is tested over multiple graphs of large-scale Gset graph collection and over binary optimization problems from the Biq Mac collection.
Firstly, the existence of low-rank solutions is used in Burer and Monteiro method @cite_26 . It is based on the factorization @math , where @math is an arbitrary matrix of size @math . This problem is non-convex, though it requires much less computations and performs well in practice. However, finding the minimum rank solution of multiple runs of the algorithm with different @math (one increments @math until resulting point satisfies particular conditions) might be computationally ineffective.
@cite_26
2143075842
We propose a new method for robust PCA -- the task of recovering a low-rank matrix from sparse corruptions that are of unknown value and support. Our method involves alternating between projecting appropriate residuals onto the set of low-rank matrices, and the set of sparse matrices; each projection is non-convex but easy to compute. In spite of this non-convexity, we establish exact recovery of the low-rank matrix, under the same conditions that are required by existing methods (which are based on convex optimization). For an @math input matrix ( @math , our method has a running time of @math per iteration, and needs @math iterations to reach an accuracy of @math . This is close to the running time of simple PCA via the power method, which requires @math per iteration, and @math iterations. In contrast, existing methods for robust PCA, which are based on convex optimization, have @math complexity per iteration, and take @math iterations, i.e., exponentially more iterations for the same accuracy. Experiments on both synthetic and real data establishes the improved speed and accuracy of our method over existing convex implementations.