Rank-Sparsity Incoherence for Matrix Decomposition
From MaRDI portal
Publication:3093595
DOI10.1137/090761793zbMATH Open1226.90067arXiv0906.2220OpenAlexW3104624268MaRDI QIDQ3093595FDOQ3093595
Authors: Venkat Chandrasekaran, Sujay Sanghavi, Pablo A. Parrilo, Alan S. Willsky 
Publication date: 18 October 2011
Published in: SIAM Journal on Optimization (Search for Journal in Brave)
Abstract: 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. Such a problem arises in a number of applications in model and system identification, and is NP-hard in general. In this paper we consider a convex optimization formulation to splitting the specified matrix into its components, by minimizing a linear combination of the norm and the nuclear norm of the components. We develop a notion of emph{rank-sparsity incoherence}, expressed as an uncertainty principle between the sparsity pattern of a matrix and its row and column spaces, and use it to characterize both fundamental identifiability as well as (deterministic) sufficient conditions for exact recovery. Our analysis is geometric in nature, with the tangent spaces to the algebraic varieties of sparse and low-rank matrices playing a prominent role. When the sparse and low-rank matrices are drawn from certain natural random ensembles, we show that the sufficient conditions for exact recovery are satisfied with high probability. We conclude with simulation results on synthetic matrix decomposition problems.
Full work available at URL: https://arxiv.org/abs/0906.2220
Recommendations
- Simultaneous pursuit of sparseness and rank structures for matrix decomposition
- Optimal rank-sparsity decomposition
- Rank Detection Methods for Sparse Matrices
- A new model for sparse and low-rank matrix decomposition
- A sparsity for decomposing a symmetric matrix
- Sparsity and incoherence in orthogonal matching pursuit
- Incoherence-Optimal Matrix Completion
- Low-Rank Matrix Completion in the Presence of High Coherence
- scientific article; zbMATH DE number 6142618
- High Dimensional Low Rank Plus Sparse Matrix Decomposition
ranksparsitysemidefinite programmingconvex relaxationuncertainty principlematrix decompositionnuclear norm minimization\(\ell _1\) norm minimization
Convex programming (90C25) Approximation methods and heuristics in mathematical programming (90C59) Semidefinite programming (90C22) System identification (93B30)
Cited In (only showing first 100 items - show all)
- Sharp recovery bounds for convex demixing, with applications
- Two-stage convex relaxation approach to low-rank and sparsity regularized least squares loss
- Compressive principal component pursuit
- Low-rank matrix completion via preconditioned optimization on the Grassmann manifold
- Noisy matrix decomposition via convex relaxation: optimal rates in high dimensions
- Augmented Lagrangian alternating direction method for matrix separation based on low-rank factorization
- Outlier detection in networks with missing links
- A partially parallel splitting method for multiple-block separable convex programming with applications to robust PCA
- Two-stage convex relaxation approach to least squares loss constrained low-rank plus sparsity optimization problems
- Discussion: Latent variable graphical model selection via convex optimization
- Multi-stage convex relaxation method for low-rank and sparse matrix separation problem
- Structural identifiability in low-rank matrix factorization
- Super-resolution of point sources via convex programming
- Low-rank matrix recovery with composite optimization: good conditioning and rapid convergence
- On conic QPCCs, conic QCQPs and completely positive programs
- Rejoinder: Latent variable graphical model selection via convex optimization
- An ADM-based splitting method for separable convex programming
- Relations among some low-rank subspace recovery models
- Spectral operators of matrices
- Discussion: Latent variable graphical model selection via convex optimization
- On the complexity of robust PCA and \(\ell_1\)-norm low-rank matrix approximation
- Noisy matrix completion: understanding statistical guarantees for convex relaxation via nonconvex optimization
- Symmetric alternating direction method with indefinite proximal regularization for linearly constrained convex optimization
- Accelerated Alternating Projections for Robust Principal Component Analysis
- An alternating minimization method for robust principal component analysis
- Regularized high dimension low tubal-rank tensor regression
- Discussion: Latent variable graphical model selection via convex optimization
- Median filtering-based methods for static background extraction from surveillance video.
- Robust low-rank matrix estimation
- Multigrid with Rough Coefficients and Multiresolution Operator Decomposition from Hierarchical Information Games
- Convex optimization for the planted \(k\)-disjoint-clique problem
- Sparse + low-energy decomposition for viscous conservation laws
- A generalized inexact Uzawa method for stable principal component pursuit problem with nonnegative constraints
- Parameterized low-rank binary matrix approximation
- A modified alternating projection based prediction-correction method for structured variational inequalities
- Splitting methods with variable metric for Kurdyka-Łojasiewicz functions and general convergence rates
- Scalable robust matrix recovery: Frank-Wolfe meets proximal methods
- Optimal rank-sparsity decomposition
- TILT: transform invariant low-rank textures
- Two proposals for robust PCA using semidefinite programming
- Alternating proximal gradient method for convex minimization
- Asymptotic performance of PCA for high-dimensional heteroscedastic data
- The convex geometry of linear inverse problems
- A sparse decomposition of low rank symmetric positive semidefinite matrices
- Compressed sensing and matrix completion with constant proportion of corruptions
- A new model for sparse and low-rank matrix decomposition
- Large covariance estimation through elliptical factor models
- Matrix rigidity and the ill-posedness of robust PCA and matrix completion
- A customized Douglas-Rachford splitting algorithm for separable convex minimization with linear constraints
- Efficient algorithms for robust and stable principal component pursuit problems
- Bridging convex and nonconvex optimization in robust PCA: noise, outliers and missing data
- Applications of gauge duality in robust principal component analysis and semidefinite programming
- Similarity preserving low-rank representation for enhanced data representation and effective subspace learning
- New classes of matrix decompositions
- Finding approximately rank-one submatrices with the nuclear norm and \(\ell_1\)-norm
- Fast global convergence of gradient methods for high-dimensional statistical recovery
- An alternating direction method with increasing penalty for stable principal component pursuit
- Statistical inference of semidefinite programming
- Structural Identifiability in Low-Rank Matrix Factorization
- Proximity point algorithm for low-rank matrix recovery from sparse noise corrupted data
- An approximation theory of matrix rank minimization and its application to quadratic equations
- Robust principal component pursuit via inexact alternating minimization on matrix manifolds
- An augmented Lagrangian based parallel splitting method for separable convex minimization with applications to image processing
- Robust computation of linear models by convex relaxation
- Latent variable graphical model selection via convex optimization
- A unified framework for high-dimensional analysis of \(M\)-estimators with decomposable regularizers
- Compressed sensing of low-rank plus sparse matrices
- Adaptive estimation of the copula correlation matrix for semiparametric elliptical copulas
- Main effects and interactions in mixed and incomplete data frames
- Robust Matrix Decomposition With Sparse Corruptions
- A distributed Douglas-Rachford splitting method for multi-block convex minimization problems
- An introduction to a class of matrix cone programming
- Robust matrix completion
- Decomposition into low-rank plus additive matrices for background/foreground separation: a review for a comparative evaluation with a large-scale dataset
- Interpreting latent variables in factor models via convex optimization
- An extragradient-based alternating direction method for convex minimization
- Guaranteed recovery of planted cliques and dense subgraphs by convex relaxation
- Compressive total variation for image reconstruction and restoration
- Robust principal component analysis using facial reduction
- An adaptation for iterative structured matrix completion
- A proximal fully parallel splitting method for stable principal component pursuit
- Models and algorithms for low-rank and sparse matrix optimization problems
- Robust covariance estimation for approximate factor models
- Blind source separation with outliers in transformed domains
- Convex graph invariant relaxations for graph edit distance
- Recovering low-rank and sparse matrix based on the truncated nuclear norm
- Bayesian sparse covariance decomposition with a graphical structure
- Recovery of simultaneous low rank and two-way sparse coefficient matrices, a nonconvex approach
- Implicit regularization in nonconvex statistical estimation: gradient descent converges linearly for phase retrieval, matrix completion, and blind deconvolution
- Adaptive estimation in structured factor models with applications to overlapping clustering
- Linear convergence of descent methods for the unconstrained minimization of restricted strongly convex functions
- Deformable groupwise image registration using low-rank and sparse decomposition
- Discussion: Latent variable graphical model selection via convex optimization
- Hierarchical subspace identification of directed acyclic graphs
- Stochastic model-based minimization of weakly convex functions
- Rank-one and sparse matrix decomposition for dynamic MRI
- Robust CUR Decomposition: Theory and Imaging Applications
- Unbiased risk estimates for matrix estimation in the elliptical case
- Non-convex matrix completion and related problems via strong duality
- Complex best \(r\)-term approximations almost always exist in finite dimensions
This page was built for publication: Rank-Sparsity Incoherence for Matrix Decomposition
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3093595)
