Source-linked AI summary
Rank-Sparsity Incoherence for Matrix Decomposition
Venkat Chandrasekaran, Sujay Sanghavi, Pablo A. Parrilo, Alan S. Willsky
TL;DR
The paper addresses recovery of unknown sparse and low-rank components from their sum, a problem that is generally NP-hard and can be ill-posed. It develops a convex ℓ1-plus-nuclear-norm relaxation and rank-sparsity incoherence conditions based on tangent spaces. The resulting deterministic conditions guarantee exact recovery in suitable cases, hold with high probability for certain random ensembles, and are supported by simulations.
Problem
Recover unknown sparse and low-rank matrices from C = A⋆ + B⋆ without knowing their support or rank, despite possible non-identifiability and NP-hardness.
Method
Minimize a weighted combination of the ℓ1 norm and nuclear norm subject to A + B = C, analyzing tangent spaces through rank-sparsity incoherence.
Results
µ(A⋆)ξ(B⋆) < 1/6 is sufficient for unique exact recovery over a range of γ, and the condition holds with high probability for certain natural random ensembles.
Takeaways & Limitations
Rank-sparsity incoherence characterizes fundamental identifiability and provides deterministic sufficient conditions for exact recovery by the convex program.
Takeaways & Limitations
The paper notes that more efficient special-purpose algorithms than a general-purpose SDP solver remain an open research question.
Abstract
from arXiv · showhide
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.
1. Introduction.
The paper studies decomposing a matrix into unknown sparse and low-rank components, an ill-posed and generally NP-hard problem. It proposes a convex ℓ1-plus-nuclear-norm formulation and uses rank-sparsity incoherence to characterize identifiability and exact recovery.
- Motivation: Sparse-plus-low-rank decomposition supports applications including statistical model selection, system identification, and complexity theory.The components can represent graphical structure and latent variables, sparse impulse responses and low model order, or matrix rigidity.
- Identifiability: Without additional assumptions, a unique sparse-plus-low-rank decomposition may not exist because the low-rank component can itself be sparse.Another ambiguity occurs when sparse support is concentrated in one column and cancels corresponding low-rank entries.
- Rank-Sparsity Incoherence: Rank-sparsity incoherence is an uncertainty principle relating a matrix’s sparsity pattern to the row and column spaces of its low-rank component.The analysis uses tangent spaces to the varieties of sparse and low-rank matrices, quantified by µ and ξ.
- Rank-Sparsity Incoherence: For every nonzero matrix, ξ(M)µ(M) ≥ 1, so tangent-space diffuseness and diffuse sparse-support spectra cannot both be arbitrarily strong.This uncertainty principle helps characterize fundamental identifiability.
- Convex Relaxation: The proposed convex program minimizes a combination of the ℓ1 norm and nuclear norm subject to A + B = C, with γ trading off sparsity and low rank.The problem is convex and can be rewritten as a semidefinite program.
- Exact Recovery: If µ(A⋆)ξ(B⋆) < 1/6, the convex program uniquely recovers the sparse and low-rank components for a range of γ.The condition depends on the sparse support and low-rank row/column spaces, not on nonzero entry values or singular values; natural random ensembles satisfy it with high probability.
2. Applications.
The paper applies sparse-plus-low-rank decomposition to latent-variable graphical models, matrix rigidity, system identification, and optics. These applications use sparse structure to represent localized or direct effects and low rank to represent latent structure, low model order, or coherent imaging.
- Statistical Model Selection: In latent-variable graphical models, the observed information matrix can decompose into a sparse graphical component and a low-rank latent-variable component.The low-rank term has rank equal to the number of latent variables, so decomposition reveals both observed graphical structure and latent effects.
- Complexity Theory: For matrix rigidity, the SDP can compute rigidity for certain sufficiently low-rigidity matrices and certify the entries changed to obtain lower rank.Rigidity is the smallest number of entries changed to reduce a matrix’s rank below a specified level.
- System Identification: In system identification, sparse and low-rank Hankel components represent sparse impulse responses and systems with small model order.The decomposition provides a simpler system description, and Hankel structure can be imposed as an additional constraint.
- Optics: In optics, low-pass coherent imaging systems correspond to system matrices with small rank.The paper introduces an optics application based on approximating the Hopkins-integral operator by a finite positive semidefinite matrix.
- Scope: The analysis is presented for square n × n matrices, while the authors state that it extends to rectangular matrices by replacing n with max(n1, n2).This is a stated scope convention for simplifying notation.
3. Rank-Sparsity Incoherence.
The paper frames sparse-plus-low-rank decomposition as potentially ill-posed and studies identifiability through tangent spaces associated with sparse and low-rank varieties. It derives an uncertainty principle and connects incoherence conditions to exact recovery.
- 3.1. Identifiability issues: Sparse-plus-low-rank decomposition may lack a unique solution when the low-rank component is itself sparse.The paper therefore seeks conditions ensuring unique decomposition.
- 3.1. Identifiability issues: Identifiability can also fail when a sparse component alters a low-rank matrix without changing the resulting matrix’s rank or column space.The paper controls this issue using a sparsity-pattern quantity µ(A⋆).
- 3.2. Tangent-space identifiability: The analysis represents sparse and rank-constrained matrices as algebraic varieties and compares their tangent spaces at the components.The low-rank tangent space contains matrices sharing the component’s row or column space, while the sparse tangent space reflects its support.
- 3.2. Tangent-space identifiability: Unique recovery given the tangent spaces holds exactly when the sparse and low-rank tangent spaces intersect only at the zero matrix.A nonzero intersection permits adding and subtracting the same matrix from the two components, violating uniqueness.
- 3.3. Rank-sparsity uncertainty principle: For any nonzero matrix, µ(M)ξ(M) ≥ 1, so no matrix can simultaneously have diffuse sparse-tangent spectra and diffuse low-rank-tangent elements.Small µ(A⋆) and ξ(B⋆) instead imply transverse tangent spaces and support exact recovery from the known spaces.
4. Exact Decomposition Using Semidefinite Programming.
The paper derives geometric and dual-certificate conditions ensuring that the convex sparse-plus-low-rank decomposition program uniquely recovers both components. A rank-sparsity incoherence condition yields deterministic guarantees, with corollaries covering bounded-degree sparse matrices, incoherent low-rank matrices, and random ensembles.
- Optimality conditions: A dual matrix Q certifies unique optimality when its projections satisfy the low-rank and sparse subgradient conditions, with strict bounds on orthogonal projections.Proposition 2 combines tangent-space transversality with projection equalities and strict inequalities involving γ, the sign pattern, and UV′.
- Sufficient conditions: The convex program exactly recovers (A⋆, B⋆) when μ(A⋆)ξ(B⋆) < 1/6 for an appropriate range of γ.The proof constructs Q in the direct sum of the tangent spaces and controls its projections onto the orthogonal complements.
- Identifiability: The sparse and low-rank tangent spaces must intersect trivially for unique decomposition, while their incoherence quantities provide a sufficient transversality condition.If μ(A⋆) and ξ(B⋆) are small, the tangent spaces intersect transversally; this is the identifiability requirement underlying exact recovery.
- Concrete classes: Sparse matrices with bounded row and column degree and low-rank matrices with incoherent row and column spaces satisfy deterministic exact-decomposition conditions.Corollary 3 gives a γ range in terms of degmax(A⋆) and inc(B⋆), with 3 inc(B⋆)/degmax(A⋆) guaranteed inside that range.
- Random ensembles: Under random sparsity and random orthogonal models, the semidefinite program uniquely recovers the sparse and low-rank components with high probability.For rank k<n, recovery remains possible even when the sparse support is super-linear in n; related contemporaneous work improves the bound under more specialized assumptions.
- Matrix rigidity: For certain low-rigidity matrices, solving the semidefinite program recovers the composing components and certifies the matrix’s rigidity despite general NP-hardness.A matrix with sparse support O(n log n) and low-rank component of rank εn has rigidity R_M(εn)=O(n log n) and admits high-probability recovery.
5. Simulation Results.
Simulations evaluate the SDP on synthetic sparse-plus-low-rank matrices and show reliable recovery when sparsity and rank are sufficiently limited. A parameter-stability experiment further examines how to select the trade-off parameter without knowing its valid range.
- Recovery experiments: Random 25 × 25 matrices are generated with m-sparse and rank-k components, and the SDP attempts to recover both from their sum.The sparse support and values, and the low-rank factors, are sampled from the stated random models.
- Recovery experiments: Success is declared when the normalized Frobenius recovery error tolγ is below 10^-3, with success rates averaged over 10 experiments for each m and k.The figure reports recovery probability across different sparsity levels and ranks.
- Recovery experiments: The recovery probability is highest for sufficiently sparse A⋆ and sufficiently low-rank B⋆, and decreases as the tested sparsity or rank becomes less favorable.Figure 5.1 encodes probability one as white and probability zero as black.
- Parameter selection: The trade-off parameter can be explored through a compact reparameterization t ∈ [0, 1], corresponding one-to-one with γ.This makes it possible to inspect solution stability over a bounded parameter range.
- Parameter selection: For a 25 × 25 example with a 25-sparse A⋆ and rank-2 B⋆, difft is near zero in three parameter regions, including regimes where one component absorbs the entire sum.The observable stability measure is compared with the unavailable recovery error tol_t.
6. Discussion.
The discussion identifies computational efficiency and noisy or finite-sample approximate decomposition as directions beyond the paper’s exact-recovery treatment.
- Future directions: A special-purpose solver exploiting the structure of the SDP could be more efficient than a general-purpose SDP solver.The paper presents this as an open problem for future research.
- Future directions: Applications such as model selection also raise the problem of approximately decomposing matrices under noise or finite-sample effects.This extends the discussion beyond exact decomposition.
Appendix A. SDP formulation.
Appendix A rewrites the nuclear- and spectral-norm terms using semidefinite representations, yielding an SDP formulation of the sparse-plus-low-rank decomposition constraint.
- SDP reformulation: The spectral norm has a semidefinite characterization, which supports expressing the low-rank surrogate within an SDP.The appendix combines this representation with the nuclear-norm characterization.
- SDP reformulation: Duality provides an SDP characterization of the nuclear norm through auxiliary matrix variables and a trace objective.The displayed trace expression is part of the semidefinite representation.
- SDP reformulation: Combining these norm representations rewrites the convex program as a semidefinite program subject to A + B = C.The equality preserves the required decomposition of the observed matrix.
- Notation: The vector 1_n denotes the all-ones vector used in the SDP formulation.This notation specifies the meaning of the auxiliary vector appearing in the formulation.
Appendix B. Proofs.
The appendix proves recovery and identifiability results by combining tangent-space geometry, projection bounds, and subgradient dual certificates. It also derives bounds for the incoherence quantities governing sparse and low-rank interactions.
- Identifiability: A trivial intersection between the sparse tangent space Ω(A⋆) and the low-rank tangent space T(B⋆) is established as a necessary condition for unique decomposition.A nonzero matrix in the intersection could be shifted between the two components without changing their sum.
- Dual certificate: The proof of SDP optimality constructs a dual matrix Q satisfying the ℓ1 and nuclear-norm subgradient conditions simultaneously.These conditions certify that (A⋆, B⋆) is an optimum before uniqueness is established.
- Dual certificate: Under strict projection bounds, any nonzero feasible perturbation increases the objective, proving that the recovered decomposition is unique.The argument uses Ω ∩ T = {0} together with strict complement projections.
- Exact recovery: The theorem proof uses μ(A⋆)ξ(B⋆) < 1/6 to construct a dual certificate whose projections onto Ω^c and T^⊥ satisfy the required bounds.The certificate is uniquely split across the direct sum Ω ⊕ T.
- Technical bounds: The appendix repeatedly applies projection and norm inequalities to control the off-support and orthogonal-complement components of the dual certificate.These bounds connect the definitions of μ and ξ to the subgradient inequalities needed for exact recovery.
- Incoherence bounds: Bounds for μ(A) relate sparse-support geometry to maximum and minimum row or column degree, while ξ(B) is bounded using the row and column spaces of B.The low-rank bound uses projections associated with the singular vectors and the tangent-space operator.