Low-rank matrix completion using alternating minimization
By Prateek Jain, Praneeth Netrapalli, Sujay Sanghavi. 2012
1,135 citations recorded by the source corpus.
Alternating minimization represents a widely applicable and empirically successful approach for finding low-rank matrices that best fit the given data. For example, for the problem of low-rank matrix completion, this method is believed to be one of the most accurate and efficient, and formed a major component of the winning entry in the Netflix Challenge [17]. In the alternating minimization approach, the low-rank target matrix is written in a bi-linear form, i.e. X = UV†; the algorithm then alternates between finding the best U and the best V. Typically, each alternating step in isolation is convex and tractable. However the overall problem becomes non-convex and is prone to local minima. In fact, there has been almost no theoretical understanding of when this approach yields a good result. In this paper we present one of the first theoretical analyses of the performance of alternating minimization for matrix completion, and the related problem of matrix sensing. For both these problems, celebrated recent results have shown that they become well-posed and tractable once certain (now standard) conditions are imposed on the problem. We show that alternating minimization also succeeds under similar conditions. Moreover, compared to existing results, our paper shows that alternating minimization guarantees faster (in particular, geometric) convergence to the true matrix, while allowing a significantly simpler analysis.
Subfields: Computational Mechanics, Computer Vision and Pattern Recognition, Mathematical Optimization, Numerical Methods & Scientific Computing
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
- Martin J. Wainwright
- Jason D. Lee
- Prateek Jain
- Francis R. Bach
- Michael I. Jordan
- E.J. Candes
- Rong Ge
- Yuxin Chen
In Computer Vision and Pattern Recognition
- Luc Van Gool
- Dacheng Tao
- Lei Zhang
- Ming-Hsuan Yang
- Trevor Darrell
- Xiaogang Wang
- Chunhua Shen
- Andrew Zisserman
In Mathematical Optimization
- Prateek Jain
- Jason D. Lee
- Moritz Hardt
- Srinadh Bhojanapalli
- Rong Ge
- Sébastien Bubeck
- Yuanzhi Li
- Sujay Sanghavi
In Numerical Methods & Scientific Computing
- Srinadh Bhojanapalli
- Rong Ge
- Prateek Jain
- Moritz Hardt
- Justin P. Haldar
- Sébastien Bubeck
- Stephen J. Wright
- Yuxin Chen
Citations in the corpus
- Recovery guarantee of weighted low-rank approximation via alternating minimization (2016, methodology): “The spectrum assumption on the weight matrix is a natural generalization of the randomness assumption typically made in matrix completion scenario (e.g., [Candes and Plan, 2010, Jain et al., 2013, Hardt, 2014]).”
- Data Poisoning Attacks on Factorization-Based Collaborative Filtering (2016, methodology): “(2) and (3) provably approximate the true underlying data matrix M under certain conditions [6, 2].”
- Taming the Wild: A Unified Analysis of Hogwild!-Style Algorithms (2015, background): “[4] require that the matrix A satisfy a coherence bound [10].”
- Coordinate descent algorithms (2015, methodology): “When the observations satisfy a restricted isometry property (an assumption commonly made in compressed sensing; see [46, Definition 3.1] for a definition that applies to matrix completion), the block CD approach of Jain, Netrapalli, and Sanghavi [21, Algorithm 1] converges to a solution.”
- Learning a Text-Video Embedding from Incomplete and Heterogeneous Data (2018, background): “In the matrix completion theory, a low rank approximation of the matrix [40] can be performed to fill the missing values.”
- Recovery Guarantees for One-hidden-layer Neural Networks (2017, background): “This direction is popular for many non-convex problems including matrix completion/sensing (Jain et al., 2013; Hardt, 2014; Sun & Luo, 2015; Balcan et al., 2017), mixed linear regression (Zhong et al.”
- Escaping From Saddle Points - Online Stochastic Gradient for Tensor Decomposition (2015, background): “For a functionf : Rd → R,∇f and∇2f denote its gradient vector and Hessian matrix.”
- Adversarial Attacks and Defences: A Survey (2018, methodology): “The two most popular algorithms used for factorization-based collaborative filtering are alternating minimization [64] and nuclear norm minimization [38].”
- Guaranteed Matrix Completion via Non-Convex Factorization (2014, background): “Index Terms —Matrix completion, matrix factorization, nonconvex optimization, alternating minimization, SGD, perturbation analysis.”
- Learning Sparsely Used Overcomplete Dictionaries via Alternating Minimization (2013, background): “More interestingly, our work extends a growing body of recent literature on analysis of alternating minimization methods for a variety of nonconvex factorization problems [15, 24], where global in addition to local results are being established with D ow nl oa de d 09 /2 0/ 17 to 1 31 .”
- Convex Optimization: Algorithms and Complexity (2014, methodology): “Jain et al. [2013] and references therein), neural networks optimization, etc. With respect to (ii) the most glaring omissions include (a) heuristics (the only heuristic briefly discussed here is the non-linear conjugate gradient in Section 2.4), (b) methods for distributed systems, and (c) adaptivi”
- Complete dictionary recovery over the sphere (2015, result): “The particular geometry of this problem does not demand any clever initialization, in contrast with most recent approaches to analyzing nonconvex recovery of structured signals [9–11, 13, 18–30].”
- Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees (2015, background): “Under the above Gaussian example, it can be shown the condition on the initial solution is satisfied if n % dr2κ4 log d and σ is small enough [36, 37].”
- Universal Matrix Completion (2014, methodology): “Concurrently other algorithms were shown to recover incoherent matrices using O ( nr log( n )) (or worse) samples such as: SVD followed by descent on Grassmanian manifold (Keshavan et al., 2010), alternating minimization (Jain et al., 2012).”
- New Algorithms for Learning Incoherent and Overcomplete Dictionaries (2013, methodology): “This analysis is inspired by recent work on analyzing alternating minimization for the matrix completion problem [34, 32], and we obtain algorithms whose running time and sample complexity depends on log 1 /ǫ .”
- Exploiting Shared Representations for Personalized Federated Learning (2021, methodology): “We adapt the argument from Lemma 4.5 in [Jain et al., 2013] to compute the update for W t +1 , and borrow heavily from their notation.”
- Learning One-hidden-layer ReLU Networks via Gradient Descent (2018, methodology): “It is worth noting that the gradient descent algorithm shown in Algorithm 1 does not require any resampling (a.k.a., sample splitting) procedure (Jain et al., 2013) compared with the gradient Algorithm 1 Gradient Descent Input: empirical loss function L N ; step size η ; iteration number T ;…”
- Global Optimality of Local Search for Low Rank Matrix Recovery (2016, background): “Figure 1: The plots in this figure compare the success probability of gradient descent between (left) random and (center) SVD initialization (suggested in [15]), for problem (2), with increasing number of samples m and various values of rank r.”
- Simple, Efficient, and Neural Algorithms for Sparse Coding (2015, background): “This adds to the recent literature on analyzing alternating minimization Jain et al. (2013); Hardt (2013); Netrapalli et al. (2013, 2014) but these work in a setting where there is a convex program that is known to work too, and in our setting, the only known convex program runs in time exponential…”
- Alternating Minimization Algorithms for Hybrid Precoding in Millimeter Wave MIMO Systems (2016, methodology): “has been successfully applied to many applications such as matrix completion [14], phase retrieval [36], image reconstruction [37], blind deconvolution [38] and non-negative matrix”