Rank-Sparsity Incoherence for Matrix Decomposition

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 ${\ell }_1$ 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.

Cited by in corpus (95)

• The Convex Geometry of Linear Inverse Problems
• Latent variable graphical model selection via convex optimization
• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Robust Subspace Learning: Robust PCA, Robust Subspace Tracking, and Robust Subspace Recovery
• A Unified Framework for High-Dimensional Analysis of M-Estimators with Decomposable Regularizers
• Noisy matrix decomposition via convex relaxation: Optimal rates in high dimensions
• Decomposition into Low-rank plus Additive Matrices for Background/Foreground Separation: A Review for a Comparative Evaluation with a Large-Scale Dataset
• Robust Spectral Compressed Sensing via Structured Matrix Completion
• Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution
• Incoherence-Optimal Matrix Completion
• Splitting methods with variable metric for KL functions
• OptShrink: An algorithm for improved low-rank signal matrix denoising by optimal, data-driven singular value shrinkage
• An Online Algorithm for Separating Sparse and Low-dimensional Signal Sequences from their Sum
• Coherence Pursuit: Fast, Simple, and Robust Principal Component Analysis
• Dynamic Anomalography: Tracking Network Anomalies via Sparsity and Low Rank
• An Overview of Robust Subspace Recovery
• On Identification of Distribution Grids
• Robust PCA as Bilinear Decomposition with Outlier-Sparsity Regularization
• Recovery of Low-Rank Plus Compressed Sparse Matrices with Application to Unveiling Traffic Anomalies
• Two Proposals for Robust PCA using Semidefinite Programming
• Recursive Recovery of Sparse Signal Sequences from Compressive Measurements: A Review
• Robust computation of linear models by convex relaxation
• High Dimensional Low Rank plus Sparse Matrix Decomposition
• In-network Sparsity-regularized Rank Minimization: Algorithms and Applications
• Low-rank and Adaptive Sparse Signal (LASSI) Models for Highly Accelerated Dynamic Imaging
• Low Rank and Structured Modeling of High-dimensional Vector Autoregressions
• Corrupted Sensing: Novel Guarantees for Separating Structured Signals
• Asymptotic performance of PCA for high-dimensional heteroscedastic data
• Static and Dynamic Robust PCA and Matrix Completion: A Review
• Scalable Robust Matrix Recovery: Frank-Wolfe Meets Proximal Methods
• Randomized Robust Subspace Recovery for High Dimensional Data Matrices
• Rapid Robust Principal Component Analysis: CUR Accelerated Inexact Low Rank Estimation
• Error Bounded Foreground and Background Modeling for Moving Object Detection in Satellite Videos
• Parametric Bilinear Generalized Approximate Message Passing
• Beyond Low Rank + Sparse: Multi-scale Low Rank Matrix Decomposition
• Iterative Grassmannian Optimization for Robust Image Alignment
• Identification of Successive "Unobservable" Cyber Data Attacks in Power Systems Through Matrix Decomposition
• Identifying Outliers in Large Matrices via Randomized Adaptive Compressive Sampling
• Convexity in source separation: Models, geometry, and algorithms
• Improved Sparse Low-Rank Matrix Estimation
• Improved Graph Clustering
• Subspace-Orbit Randomized Decomposition for Low-rank Matrix Approximation
• Low-Rank Positive Semidefinite Matrix Recovery from Corrupted Rank-One Measurements
• Robust CUR Decomposition: Theory and Imaging Applications
• Load curve data cleansing and imputation via sparsity and low rank
• Low-complexity modeling of partially available second-order statistics: theory and an efficient matrix completion algorithm
• Robust PCA with Partial Subspace Knowledge
• Joint community and anomaly tracking in dynamic networks
• Dynamic Network Cartography
• On the Complexity of Robust PCA and ${\ell }_1$-norm Low-Rank Matrix Approximation
• Provable Dynamic Robust PCA or Robust Subspace Tracking
• Diagonal and Low-Rank Matrix Decompositions, Correlation Matrices, and Ellipsoid Fitting
• Adaptive estimation of the copula correlation matrix for semiparametric elliptical copulas
• Robust Low-rank Matrix Completion via an Alternating Manifold Proximal Gradient Continuation Method
• Structured and Unstructured Outlier Identification for Robust PCA: A Non iterative, Parameter free Algorithm
• Robust Alignment for Panoramic Stitching via an Exact Rank Constraint
• Structured Gradient Descent for Fast Robust Low-Rank Hankel Matrix Completion
• 21cm Signal Recovery via the Robust Principle Component Analysis
• Fast Algorithms for Demixing Sparse Signals from Nonlinear Observations
• SILVar: Single Index Latent Variable Models
• DOA Estimation in Partially Correlated Noise Using Low-Rank/Sparse Matrix Decomposition
• Practical Matrix Completion and Corruption Recovery using Proximal Alternating Robust Subspace Minimization
• Estimating Differential Latent Variable Graphical Models with Applications to Brain Connectivity
• A Dictionary-Based Generalization of Robust PCA with Applications to Target Localization in Hyperspectral Imaging
• A large covariance matrix estimator under intermediate spikiness regimes
• Latent Variable Time-varying Network Inference
• Robust Tensor CUR Decompositions: Rapid Low-Tucker-Rank Tensor Recovery with Sparse Corruption
• A Dictionary-Based Generalization of Robust PCA Part II: Applications to Hyperspectral Demixing
• Fast Robust Subspace Tracking via PCA in Sparse Data-Dependent Noise
• Rank-One Network: An Effective Framework for Image Restoration
• Closed-Form, Provable, and Robust PCA via Leverage Statistics and Innovation Search
• Rejoinder: Latent variable graphical model selection via convex optimization
• Low Rank Matrix Recovery with Simultaneous Presence of Outliers and Sparse Corruption
• Best Pair Formulation & Accelerated Scheme for Non-convex Principal Component Pursuit
• Low Rank plus Sparse Decomposition of ODFs for Improved Detection of Group-level Differences and Variable Correlations in White Matter
• Low-Rank Inducing Norms with Optimality Interpretations
• Semi-blind Source Separation via Sparse Representations and Online Dictionary Learning
• How Does the Low-Rank Matrix Decomposition Help Internal and External Learnings for Super-Resolution
• A Dictionary Based Generalization of Robust PCA
• Interpreting Latent Variables in Factor Models via Convex Optimization
• Quantized Corrupted Sensing with Random Dithering
• Automated Defect Localization via Low Rank Plus Outlier Modeling of Propagating Wavefield Data
• Exact Camera Location Recovery by Least Unsquared Deviations
• Decomposition and Completion of Sum-of-Squares Matrices
• Target-based Hyperspectral Demixing via Generalized Robust PCA
• Accelerating Ill-conditioned Hankel Matrix Recovery via Structured Newton-like Descent
• Accelerating Permutation Testing in Voxel-wise Analysis through Subspace Tracking: A new plugin for SnPM
• Bounded Simplex-Structured Matrix Factorization: Algorithms, Identifiability and Applications
• Discussion: Latent variable graphical model selection via convex optimization
• Discussion: Latent variable graphical model selection via convex optimization
• High-dimensional Asymptotics of VAEs: Threshold of Posterior Collapse and Dataset-Size Dependence of Rate-Distortion Curve
• Differential covariance: A new method to estimate functional connectivity in fMRI
• Adaptive Reference-Guided Estimation of Principal Component Subspace in High Dimensions
• Operational Non-identifiability of Single-epoch Low-rank RFI Mitigation: Controlled Failure-mode Analysis and HERA Evidence
• Applications of gauge duality in robust principal component analysis and semidefinite programming