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)- Guaranteed recovery of planted cliques and dense subgraphs by convex relaxation
- Exact camera location recovery by least unsquared deviations
- Mixture augmented Lagrange multiplier method for tensor recovery and its applications
- Alternating direction and Taylor expansion minimization algorithms for unconstrained nuclear norm optimization
- Compressive total variation for image reconstruction and restoration
- Accelerating ill-conditioned Hankel matrix recovery via structured Newton-like descent
- Sharp recovery bounds for convex demixing, with applications
- Rank-deficient spectral factorization and wavelets completion problem
- Two-stage convex relaxation approach to low-rank and sparsity regularized least squares loss
- scientific article; zbMATH DE number 7415093 (Why is no real title available?)
- Robust principal component analysis using facial reduction
- Latent Gaussian and Hüsler-Reiss graphical models with Golazo penalty
- An adaptation for iterative structured matrix completion
- A proximal fully parallel splitting method for stable principal component pursuit
- Low-rank matrix completion via preconditioned optimization on the Grassmann manifold
- Compressive principal component pursuit
- Noisy matrix decomposition via convex relaxation: optimal rates in high dimensions
- Two-stage convex relaxation approach to least squares loss constrained low-rank plus sparsity optimization problems
- Outlier detection in networks with missing links
- Augmented Lagrangian alternating direction method for matrix separation based on low-rank factorization
- A partially parallel splitting method for multiple-block separable convex programming with applications to robust PCA
- Robust covariance estimation for approximate factor models
- Convex graph invariant relaxations for graph edit distance
- Models and algorithms for low-rank and sparse matrix optimization problems
- Extremal graphical modeling with latent variables via convex optimization
- An efficient semi-proximal ADMM algorithm for low-rank and sparse regularized matrix minimization problems with real-world applications
- scientific article; zbMATH DE number 6982332 (Why is no real title available?)
- Structural identifiability in low-rank matrix factorization
- Multi-stage convex relaxation method for low-rank and sparse matrix separation problem
- Discussion: Latent variable graphical model selection via convex optimization
- Blind source separation with outliers in transformed domains
- A separable surrogate function method for sparse and low-rank matrices decomposition
- An Algebraic Estimator for Large Spectral Density Matrices
- Isolated calmness of solution mappings and exact recovery conditions for nuclear norm optimization problems
- Recovering low-rank and sparse matrix based on the truncated nuclear norm
- Low-rank matrix recovery with composite optimization: good conditioning and rapid convergence
- Bayesian sparse covariance decomposition with a graphical structure
- On conic QPCCs, conic QCQPs and completely positive programs
- Super-resolution of point sources via convex programming
- Recovery of simultaneous low rank and two-way sparse coefficient matrices, a nonconvex approach
- Rejoinder: Latent variable graphical model selection via convex optimization
- Implicit regularization in nonconvex statistical estimation: gradient descent converges linearly for phase retrieval, matrix completion, and blind deconvolution
- An ADM-based splitting method for separable convex programming
- Adaptive estimation in structured factor models with applications to overlapping clustering
- Spectral operators of matrices
- Relations among some low-rank subspace recovery models
- Symmetric alternating direction method with indefinite proximal regularization for linearly constrained convex optimization
- Discussion: Latent variable graphical model selection via convex optimization
- On the complexity of robust PCA and \(\ell_1\)-norm low-rank matrix approximation
- Linear convergence of descent methods for the unconstrained minimization of restricted strongly convex functions
- Noisy matrix completion: understanding statistical guarantees for convex relaxation via nonconvex optimization
- Accelerated Alternating Projections for Robust Principal Component Analysis
- Regularized high dimension low tubal-rank tensor regression
- An alternating minimization method for robust principal component analysis
- Deformable groupwise image registration using low-rank and sparse decomposition
- Phaselift is robust to a constant fraction of arbitrary errors
- Robust low-rank matrix estimation
- Discussion: Latent variable graphical model selection via convex optimization
- Hierarchical subspace identification of directed acyclic graphs
- Discussion: Latent variable graphical model selection via convex optimization
- Median filtering-based methods for static background extraction from surveillance video.
- Rank-one and sparse matrix decomposition for dynamic MRI
- Stochastic model-based minimization of weakly convex functions
- Multigrid with Rough Coefficients and Multiresolution Operator Decomposition from Hierarchical Information Games
- Nonlinear network-based quantitative trait prediction from biological data
- Kronecker-structured covariance models for multiway data
- Convex optimization for the planted \(k\)-disjoint-clique problem
- Sparse + low-energy decomposition for viscous conservation laws
- Robust CUR Decomposition: Theory and Imaging Applications
- Unbiased risk estimates for matrix estimation in the elliptical case
- Complex best \(r\)-term approximations almost always exist in finite dimensions
- Parameterized low-rank binary matrix approximation
- A generalized inexact Uzawa method for stable principal component pursuit problem with nonnegative constraints
- Robust dimension reduction
- A customized inertial proximal alternating minimization for SVD-free robust principal component analysis
- A modified alternating projection based prediction-correction method for structured variational inequalities
- Non-convex matrix completion and related problems via strong duality
- Generalized asymmetric forward-backward-adjoint algorithms for convex-concave saddle-point problem
- Ising models with latent conditional Gaussian variables
- An \(\ell_{\infty}\) eigenvector perturbation bound and its application
- Splitting methods with variable metric for Kurdyka-Łojasiewicz functions and general convergence rates
- Scalable robust matrix recovery: Frank-Wolfe meets proximal methods
- Low-rank/sparse-inverse decomposition via Woodbury
- Simple heuristics yield provable algorithms for masked low-rank approximation
- Optimal rank-sparsity decomposition
- Toward Interpretable Deep Generative Models via Causal Representation Learning
- Multiple Change Point Detection in Reduced Rank High Dimensional Vector Autoregressive Models
- Large factor model estimation by nuclear norm plus _1 norm penalization
- Active-learning-driven surrogate modeling for efficient simulation of parametric nonlinear systems
- TILT: transform invariant low-rank textures
- High-dimensional asymptotics of VAEs: threshold of posterior collapse and dataset-size dependence of rate-distortion curve
- Two proposals for robust PCA using semidefinite programming
- Matrix completion with noisy entries and outliers
- A non-monotone alternating Newton-like directional method for low-rank and sparse matrix compressive recovery
- Exact guarantees on the absence of spurious local minima for non-negative rank-1 robust principal component analysis
- Linear models based on noisy data and the Frisch scheme
- Spectral operators of matrices: semismoothness and characterizations of the generalized Jacobian
- Topology identification under spatially correlated noise
- Matrix optimization based Euclidean embedding with outliers
- Robust Causal Structure Learning with Some Hidden Variables
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)
