Guaranteed Rank Minimization via Singular Value Projection

By Prateek Jain, Raghu Meka, Inderjit S. Dhillon. Neural Information Processing Systems, 2009

576 citations recorded by the source corpus.

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

Subfields: Computational Mechanics, Signal Processing

View Paper: https://www.semanticscholar.org/paper/ebd660b8df9d7f9cd044c63778c15c39cdd072ed

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Signal Processing

Citations in the corpus

Sparse Local Embeddings for Extreme Multi-label Classification (2015, methodology): “However, using the Singular Value Projection (SVP) method [20], a popular matrix completion method, we can guarantee convergence to a local minima.”
The Power of Normalization: Faster Evasion of Saddle Points (2016, methodology): “…interpretation, Gradient Descent (GD) and its numerous variants are often the method of choice in large-scale optimization tasks, including neural network optimization Bengio (2009), ranking Burges et al. (2005), matrix completion Jain et al. (2010), and reinforcement learning Sutton et al. (1999).”
Understanding the Sparsity: Augmented Matrix Factorization with Sampled Constraints on Unobservables (2014, methodology): “To speed up the process of rank minimization, [16] proposed the Singular Value Projection (SVP) algorithm for matrix completion with affine constraints.”
Solving a low-rank factorization model for matrix completion by a nonlinear successive over-relaxation algorithm (2012, methodology): “…and Applied Mathematics, Rice University, Houston, TX 77005, USA e-mail: wotao.yin@rice.edu Y. Zhang e-mail: yzhang@rice.edu Keywords Matrix completion · Alternating minimization · Nonlinear GS method · Nonlinear SOR method Mathematics Subject Classification 65K05 · 90C06 · 93C41 · 68Q32”
Tight Oracle Inequalities for Low-Rank Matrix Recovery From a Minimal Number of Noisy Random Measurements (2011, background): “Several different algorithms have been proposed, with many drawing their roots from standard compressive sensing techniques [3], [4], [6], [8], [9], [11], [14]–[16].”
Differentially Private Matrix Completion, Revisited (2017, methodology): “Moreover, the algorithm forms a foundation for more sophisticated algorithms like alternating minimization [21], singular value projection [25] and singular value thresholding [6].”
Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview (2018, background): “Another popular approach to solve (88) is singular value projection (SVP) [75], [110], [111].”
Sparse Bayesian Methods for Low-Rank Matrix Estimation (2011, methodology): “For matrix completion, singular value thresholding [25] an d projection methods [26] are attractive in terms of computation, while they nearly optimize (2).”
Provable Inductive Matrix Completion (2013, background): “Of these above mentioned low-rank matrix estimation problems, the most relevant problems to ours are those of matrix completion [2, 5, 8] and general matrix sensing [1, 9, 10].”
Scaled Gradients on Grassmann Manifolds for Matrix Completion (2012, methodology): “We use the beststep sizes that we found for SVP and GROUSE.”
Global Optimality of Local Search for Low Rank Matrix Recovery (2016, background): “Subsequent work established similar guarantees also for the noisy and approximate case [14, 6].”
On critical points of quadratic low-rank matrix optimization problems (2020, methodology): “Other sufficient conditions in the literature for guaranteed recovery of rank-k matrices using different approaches include δ2k < 1/3 (Jain et al., 2010) for the singular value projection (iterative hard thresholding (IHT)) algorithm, and even δ2k 1/2 (Cai & Zhang, 2013) for nuclear norm minimizatio”
Low-rank matrix completion using alternating minimization (2012, methodology): “Speci.cally, we initialize the i-th stage of our algorithm using one step of the SVP algorithm [10] (see Step 4 of Algorithm 3).”
Dropping Convexity for Faster Semi-definite Optimization (2015, methodology): “Impact of avoiding low-rank projections on the PSD cone: In this experiment, we compare factored gradient descent with a variant of the Singular Value Projection ( SVP ) algorithm [41, 8] 23 .”
Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees (2015, methodology): “It can be avoided by using a more sophisticated initialization procedures—for instance, one based on a few iterations of the singular value projection (SVP) algorithm [36].”
Subgradient Methods for Sharp Weakly Convex Functions (2018, background): “For smooth problem formulations, the term “local search” almost universally refers to gradient descent or a close variant thereof; see e.g. [1,2,4,6,20,21,23,37].”
An Overview of Low-Rank Matrix Recovery From Incomplete Observations (2016, background): “A variation of the program above makes this connection clearer.”