Rank-Sparsity Incoherence for Matrix Decomposition
By Venkat Chandrasekaran, Sujay Sanghavi, Pablo A. Parrilo, Alan S. Willsky. SIAM Journal on Optimization, 2009
1,149 citations recorded by the source corpus.
Suppose we are given a matrix that is formed by adding an unknown sparse matrix to an unknown low-rank matrix. Our goal is to decompose the given matrix into its sparse and low-rank components. Suc...
Subfields: Applied Mathematics, Computational Mathematics, Computational Mechanics
View Paper: https://www.semanticscholar.org/paper/e194ea3ba83d58ed0cf3e74a02064bf062408dd5
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Applied Mathematics
- Martin J. Wainwright
- Yudong Chen
- Prateek Jain
- Constantine Caramanis
- Thierry Bouwmans
- Sujay Sanghavi
- Marcelo Pereyra
- René Vidal
In Computational Mathematics
- Martin J. Wainwright
- Sahand N. Negahban
- Yudong Chen
- Alekh Agarwal
- Dacheng Tao
- Tianyi Zhou
- Constantine Caramanis
- Marcelo Pereyra
In Computational Mechanics
- Martin J. Wainwright
- Prateek Jain
- E.J. Candes
- René Vidal
- Thierry Bouwmans
- Sahand N. Negahban
- Zhouchen Lin
- Yudong Chen
Citations in the corpus
- The Emergence of Organizing Structure in Conceptual Representation (2016, background): “…learning sparse networks or sparse Gaussian graphical models, either without latent variables (Banerjee et al., 2008; Hutchinson, 1989; Lake & Tenenbaum, 2010; Schvaneveldt, Durso, & Dearholt, 1989) or without fully recovering a latent topology (Chandrasekaran, Sanghavi, Parrilo, & Willsky, 2011).”
- Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees (2015, methodology): “One line of work concerns the setting where the non-zero entries of S∗ are randomly located [19, 22], whereas another line of work focuses on deterministic models [20, 35, 1].”
- Robust Subspace Learning: Robust PCA, Robust Subspace Tracking, and Robust Subspace Recovery (2017, methodology): “The same program was introduced and studied in parallel [5] and later work [6] as an S+LR solution.”
- Augmented Lagrangian alternating direction method for matrix separation based on low-rank factorization (2014, background): “It has been shown in [3, 9, 10, 21, 44] that, under some suitable conditions, the solution to problem (1) can be found by solving the convex optimization problem:”
- Exact Recoverability From Dense Corrupted Observations via $\ell _{1}$-Minimization (2011, background): “Consequently, our error bound in Theorem 4 loses a √ n vis-a-vis over the ideal bound achieved via the oracle help.”
- Robust Computation of Linear Models by Convex Relaxation (2012, result): “We do not make comparisons with the rank–sparsity decomposition [14], which was also considered for robust linear modeling in [11].”
- Recovering Low-Rank and Sparse Components of Matrices from Incomplete and Noisy Observations (2011, background): “Hence, in [9], it has been shown that the task of recovering low-rank and sparse components, which is NP hard, can be accurately accomplished in the probabilistic sense via solving the following nuclear-norm-and l 1 -norm-involved convex relaxation problem: min A,E A * + τ E 1 s.t.”
- Alternating Direction Algorithms for 1-Problems in Compressive Sensing (2009, methodology): “A more recent application of the ADM approach is to the problem of decomposing a given matrix into a sum of a low-rank matrix and a sparse matrix simultaneously using ℓ 1 -norm and nuclear-norm regularizations (see [11]).”
- Low-rank matrix recovery from errors and erasures (2011, methodology): “Specialization to the errors-only case provides an order improvement over the previous deterministic results in [13], and matches the scaling of [14] but with a much simpler proof.”
- Stable Principal Component Pursuit (2010, background): “It has been shown in [3], under surprisingly broad conditions, the above convex program exactly recovers L0 and S0. Readers are also referred to [ 4 ] which proposed to solve the same problem but with different exact recovery conditions.”
- Hidden Talents of the Variational Autoencoder. (2017, methodology): “ A number of celebrated results have stipulated conditions [6, 7] whereby global solutions of the convex relaxation into nuclear and `1 norm components given by min L,S √ n · rank ‖L‖∗ + ‖S‖1, s.”
- Proximal Markov chain Monte Carlo algorithms (2013, methodology): “…used to find the maximis-ers of posterior distributions that are log-concave and often non-smooth and very high dimensional (Afonso et al. 2011; Agarwal et al. 2012; Candès and Tao 2009; Candès et al. 2011; Chandrasekaran and Jordan 2013; Chandrasekaran et al. 2011; Pesquet and Pustelnik 2012).”