Fixed point and Bregman iterative methods for matrix rank minimization
By Shiqian Ma, Donald Goldfarb, Lifeng Chen. 2009
1,120 citations recorded by the source corpus.
The linearly constrained matrix rank minimization problem is widely applicable in many fields such as control, signal processing and system identification. The tightest convex relaxation of this problem is the linearly constrained nuclear norm minimization. Although the latter can be cast as a semidefinite programming problem, such an approach is computationally expensive to solve when the matrices are large. In this paper, we propose fixed point and Bregman iterative algorithms for solving the nuclear norm minimization problem and prove convergence of the first of these algorithms. By using a homotopy approach together with an approximate singular value decomposition procedure, we get a very fast, robust and powerful algorithm, which we call FPCA (Fixed Point Continuation with Approximate SVD), that can solve very large matrix rank minimization problems (the code can be downloaded from http://www.columbia.edu/~sm2756/FPCA.htm for non-commercial use). Our numerical results on randomly generated and real matrix completion problems demonstrate that this algorithm is much faster and provides much better recoverability than semidefinite programming solvers such as SDPT3. For example, our algorithm can recover 1000 × 1000 matrices of rank 50 with a relative error of 10−5 in about 3 min by sampling only 20% of the elements. We know of no other method that achieves as good recoverability. Numerical experiments on online recommendation, DNA microarray data set and image inpainting problems demonstrate the effectiveness of our algorithms.
Subfields: Computational Mathematics, Computational Mechanics, Numerical Analysis
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Computational Mathematics
In Computational Mechanics
- Wotao Yin
- Prateek Jain
- E.J. Candes
- Peter Richtárik
- Francis R. Bach
- Martin J. Wainwright
- Yin Zhang
- B. Recht
In Numerical Analysis
- Francis R. Bach
- Wotao Yin
- Jieping Ye
- Mark W. Schmidt
- Peter Richtárik
- Michael I. Jordan
- Paul Tseng
- E.J. Candes
Citations in the corpus
- Guaranteed Matrix Completion via Non-Convex Factorization (2014, background): “Index Terms —Matrix completion, matrix factorization, nonconvex optimization, alternating minimization, SGD, perturbation analysis.”
- Interior-Point Method for Nuclear Norm Approximation with Application to System Identification (2009, methodology): “Recently, a new class of first-order algorithms for the nuclear norm minimization problem (1.7) has been proposed, extending Bregman iterative algorithms for largescale l1-norm minimization [ 28 , 5]. Again each iteration involves a singular value decomposition of X. The complexity can be further re”
- 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].”
- A Gradient Descent Algorithm on the Grassman Manifold for Matrix Completion (2009, methodology): “…Singular Value Thresholding (SVT) [7], Accelerated Proximal Gradient (APG) algo-rithm [30], Fixed Point Continuation with Approximate SVD (FPCA) [22], Atomic Decomposition for Minimum Rank Approximation ( ADMiRA ) [21], Soft-Impute [23], Subspace Evolution and Transfer (SET) [13], Singular…”
- Robust principal component analysis? (2009, background): “Since S 0 and S 0 have the same distribution, the theorem follows.”
- Guaranteed Rank Minimization via Singular Value Projection (2009, methodology): “[20], Toh and Yun [25], while Ji and Ye [13] use Nesterov’s gradient descent methods for opti mizing the trace-norm.”
- On the Linear Convergence of the Proximal Gradient Method for Trace Norm Regularization (2013, methodology): “Currently, a popular method for solving (1) is the proximal gradient method (PGM), which exploits the composite nature of the objective function F and certain smoothness properties of the loss function f [8, 19, 11].”
- Robust Matrix Completion via Joint Schatten p-Norm and lp-Norm Minimization (2012, methodology): “In order to demonstrate the effectiveness of the proposed method, we compare the performance of the proposed method against the following two matrix completion methods: Fixed Point Continuation (FPC) method [12] and Accelerated Proximal Gradient singular value thresholding (APG) method [9], which ar”
- Parallel stochastic gradient algorithms for large-scale matrix completion (2013, methodology): “Keywords Matrix completion · Incremental gradient methods · Parallel computing · Multicore Mathematics Subject Classification 90C06 · 90C25 · 90C15”
- A Unified Primal-Dual Algorithm Framework Based on Bregman Iteration (2010, methodology): “Note that this is a simplified version of the fixed point continuation (FPC) method with Bregman iterations in [39], where a dynamic parameter μ is used in addition to the Bregman iterations.”
- Optimal selection of reduced rank estimators of high-dimensional matrices (2010, methodology): “Alternatively, Bregman iterative algorithms can be developed; see Ma et al. (2009) for a detailed description of the main idea.”
- Low-Rank Matrix Recovery via Efficient Schatten p-Norm Minimization (2012, methodology): “Several methods (Toh and Yun 2009; Ji and Ye 2009; Liu, Sun, and Toh 2009; Ma, Goldfarb, and Chen 2009; Mazumder, Hastie, and Tibshirani 2009) recently have been published to solve this kind of trace norm minimization problem.”
- The Power of Convex Relaxation: Near-Optimal Matrix Completion (2009, background): “d we don’t even need the +1 in this case). 7 Discussion Interestingly, there is an emerging literature on the development of ecient algorithms for solving the nuclear-norm minimization problem (1.3) [6,17]. For instance, in [6], the authors show that the singular-value thresholding algorithm can sol”
- A unified approach to error bounds for structured convex optimization problems (2015, background): “…: R m × n → R m × n is the so-called matrix shrinkage operator defined as follows: Given a matrix X ∈ R m × n , S 1 ( X ) ∈ R m × n is the matrix obtained by taking any SVD of X and replacing the singular value σ i ( X ) by max σ i ( X ) − 1 , 0 , for i = 1 , . . . , m ; see, e.g. , [20, Theorem 3].”
- Accelerated dynamic MRI exploiting sparsity and low-rank structure: k-t SLR (2011, positive): “Most of the existing convex matrix recovery algorithms are based on iterative singular value thresholding [14], [22], [23].”