Guaranteed Rank Minimization via Singular Value Projection

摘要: Minimizing the rank of a matrix subject to affine constraints is fundamental problem with many important applications in machine learning and statistics. In this paper we propose simple fast algorithm SVP (Singular Value Projection) for minimization under (ARMP) show that recovers minimum solution satisfy restricted isometry property (RIP). Our method guarantees geometric convergence rate even presence noise requires strictly weaker assumptions on RIP constants than existing methods. We also introduce Newton-step our framework speed-up substantial empirical gains. Next, address practically application ARMP - low-rank completion, which defining do not directly obey RIP, hence hold. However, provide partial progress towards proof exact recovery by showing more observe empirically incoherent matrices from an almost optimal number uniformly sampled entries. demonstrate algorithms outperform methods, such as those [5, 18, 14], completion order magnitude are robust sampling schemes. particular, results SVP-Newton significantly performs impressively realistic power-law scheme problem.