Rank-Sparsity Incoherence for Matrix Decomposition
From MaRDI portal
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.
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
Cited in
(only showing first 100 items - show all)- Latent variable graphical model selection via convex optimization
- Main effects and interactions in mixed and incomplete data frames
- Asymptotic performance of PCA for high-dimensional heteroscedastic data
- Multi-view low-rank dictionary learning for image classification
- A partially isochronous splitting algorithm for three-block separable convex minimization problems
- Symmetric alternating direction method with indefinite proximal regularization for linearly constrained convex optimization
- Painless breakups -- efficient demixing of low rank matrices
- Multi-stage convex relaxation method for low-rank and sparse matrix separation problem
- Statistical inference of semidefinite programming
- Robust covariance estimation for approximate factor models
- Practical matrix completion and corruption recovery using proximal alternating robust subspace minimization
- The convex geometry of linear inverse problems
- TILT: transform invariant low-rank textures
- Compressed sensing and matrix completion with constant proportion of corruptions
- Discussion: Latent variable graphical model selection via convex optimization
- Rejoinder: Latent variable graphical model selection via convex optimization
- An ADM-based splitting method for separable convex programming
- Two proposals for robust PCA using semidefinite programming
- Robust low-rank matrix estimation
- A proximal fully parallel splitting method for stable principal component pursuit
- Matrix optimization based Euclidean embedding with outliers
- Bridging convex and nonconvex optimization in robust PCA: noise, outliers and missing data
- Low-rank matrix recovery with composite optimization: good conditioning and rapid convergence
- An adaptation for iterative structured matrix completion
- A unified framework for nonconvex nonsmooth sparse and low-rank decomposition by majorization-minimization algorithm
- Convex graph invariant relaxations for graph edit distance
- Alternating DC algorithm for partial DC programming problems
- Deformable groupwise image registration using low-rank and sparse decomposition
- Regularized high dimension low tubal-rank tensor regression
- Trading off \(1\)-norm and sparsity against rank for linear models using mathematical optimization: \(1\)-norm minimizing partially reflexive ah-symmetric generalized inverses
- Complex best \(r\)-term approximations almost always exist in finite dimensions
- Pairwise sparse + low-rank models for variables of mixed type
- Implicit regularization in nonconvex statistical estimation: gradient descent converges linearly for phase retrieval, matrix completion, and blind deconvolution
- Compressive total variation for image reconstruction and restoration
- A multi-objective memetic algorithm for low rank and sparse matrix decomposition
- Adaptive estimation in structured factor models with applications to overlapping clustering
- Parameterized low-rank binary matrix approximation
- Robust principal component analysis using facial reduction
- Outlier detection in networks with missing links
- Sparse trace norm regularization
- Recovering low-rank and sparse matrix based on the truncated nuclear norm
- Recovery of simultaneous low rank and two-way sparse coefficient matrices, a nonconvex approach
- A large covariance matrix estimator under intermediate spikiness regimes
- Mixture augmented Lagrange multiplier method for tensor recovery and its applications
- Alternating direction and Taylor expansion minimization algorithms for unconstrained nuclear norm optimization
- Similarity preserving low-rank representation for enhanced data representation and effective subspace learning
- Low-rank matrix completion via preconditioned optimization on the Grassmann manifold
- Splitting methods with variable metric for Kurdyka-Łojasiewicz functions and general convergence rates
- Robust computation of linear models by convex relaxation
- Rank-one and sparse matrix decomposition for dynamic MRI
- Variational analysis of the Ky Fan k-norm
- Unbiased risk estimates for matrix estimation in the elliptical case
- Alternating proximal gradient method for convex minimization
- Unique decomposition and a new model for the ground moving target indication problem
- PO-MOESP subspace identification of directed acyclic graphs with unknown topology
- Spectral operators of matrices
- A generalized inexact Uzawa method for stable principal component pursuit problem with nonnegative constraints
- Large covariance estimation through elliptical factor models
- Convex optimization for the planted \(k\)-disjoint-clique problem
- Proximity point algorithm for low-rank matrix recovery from sparse noise corrupted data
- A customized Douglas-Rachford splitting algorithm for separable convex minimization with linear constraints
- Efficient algorithms for robust and stable principal component pursuit problems
- An introduction to a class of matrix cone programming
- A modified alternating projection based prediction-correction method for structured variational inequalities
- Robust principal component pursuit via inexact alternating minimization on matrix manifolds
- Phaselift is robust to a constant fraction of arbitrary errors
- Proximal Markov chain Monte Carlo algorithms
- Bayesian sparse covariance decomposition with a graphical structure
- Adaptive estimation of the copula correlation matrix for semiparametric elliptical copulas
- Robust recovery of low-rank matrices with non-orthogonal sparse decomposition from incomplete measurements
- Nonsmooth rank-one matrix factorization landscape
- Kronecker-structured covariance models for multiway data
- Compressed sensing of low-rank plus sparse matrices
- Two-stage convex relaxation approach to least squares loss constrained low-rank plus sparsity optimization problems
- Linear models based on noisy data and the Frisch scheme
- Linear convergence of descent methods for the unconstrained minimization of restricted strongly convex functions
- Scalable robust matrix recovery: Frank-Wolfe meets proximal methods
- Active subspace: toward scalable low-rank learning
- Multigrid with Rough Coefficients and Multiresolution Operator Decomposition from Hierarchical Information Games
- On conic QPCCs, conic QCQPs and completely positive programs
- An augmented Lagrangian based parallel splitting method for separable convex minimization with applications to image processing
- Differential covariance: a new method to estimate functional connectivity in fMRI
- Applications of gauge duality in robust principal component analysis and semidefinite programming
- Rank-deficient spectral factorization and wavelets completion problem
- Scalable low-rank representation
- Low-rank and sparse multi-task learning
- New classes of matrix decompositions
- Structural Identifiability in Low-Rank Matrix Factorization
- Sharp recovery bounds for convex demixing, with applications
- An approximation theory of matrix rank minimization and its application to quadratic equations
- Noisy matrix decomposition via convex relaxation: optimal rates in high dimensions
- Low-rank inducing norms with optimality interpretations
- scientific article; zbMATH DE number 6982332 (Why is no real title available?)
- An \(\ell_{\infty}\) eigenvector perturbation bound and its application
- Low-rank/sparse-inverse decomposition via Woodbury
- Super-resolution of point sources via convex programming
- Using side information to reliably learn low-rank matrices from missing and corrupted observations
- Robust PCA by manifold optimization
- Stochastic model-based minimization of weakly convex functions
- Accelerated Alternating Projections for Robust Principal Component Analysis
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)
