Compressive Principal Component Pursuit

John Wright; Arvind Ganesh; Kerui Min; Yi Ma

Source-linked AI summary

Compressive Principal Component Pursuit

John Wright, Arvind Ganesh, Kerui Min, Yi Ma

arXiv:1202.4596v1Feb 21, 2012cs.IT

TL;DR

The paper asks whether low-rank and sparse matrices can be jointly recovered from substantially fewer linear measurements than their ambient matrix entries when both components are small. It develops a certificate-based convex recovery analysis under uniformly random measurements and proves exact recovery under suitable conditions, with measurement requirements commensurate with the components’ degrees of freedom.

Problem
When low-rank and sparse components are small, the ambient number of observations may greatly exceed their intrinsic degrees of freedom; the paper asks whether both can be recovered from fewer linear measurements.
Method
The paper constructs an optimality certificate for Compressive Principal Component Pursuit by combining compressive-measurement analysis with existing Principal Component Pursuit recovery analyses.
Results
Under suitable conditions, the convex optimization uniquely recovers (L0, S0) from compressive measurements, and small rank and sparsity permit correspondingly small measurement dimensions.
Takeaways & Limitations
The analysis supports compressive recovery of superpositions of low-complexity components and suggests analogous results for generalized norms built from decomposable terms.
Takeaways & Limitations
The main measurement theorem assumes Q is chosen uniformly at random, whereas transformation-determined measurements require deterministic conditions because they cannot be modeled as random projections.

Abstract

from arXiv · show

We consider the problem of recovering a target matrix that is a superposition of low-rank and sparse components, from a small set of linear measurements. This problem arises in compressed sensing of structured high-dimensional signals such as videos and hyperspectral images, as well as in the analysis of transformation invariant low-rank recovery. We analyze the performance of the natural convex heuristic for solving this problem, under the assumption that measurements are chosen uniformly at random. We prove that this heuristic exactly recovers low-rank and sparse terms, provided the number of observations exceeds the number of intrinsic degrees of freedom of the component signals by a polylogarithmic factor. Our analysis introduces several ideas that may be of independent interest for the more general problem of compressed sensing and decomposing superpositions of multiple structured signals.

1 Introduction

The paper studies whether low-rank and sparse matrices can be simultaneously recovered from highly compressive random measurements using a natural convex program. It establishes near-optimal recovery guarantees and extends the analysis to decompositions involving multiple structured components.

Motivation: The problem is motivated by structured signals including video foreground and background, videos, textures, and hyperspectral datacubes.Small measurement sets could support new sensing architectures for these signals.
Compressive RPCA: CPCP seeks to recover low-rank L0 and sparse S0 from D = P_Q[L0 + S0] using nuclear-norm plus ℓ1-norm minimization.The measurement subspace Q must be incoherent with both components for simultaneous recovery.
Compressive RPCA: With random measurements, the convex program is expected to recover both components when rank and sparsity are sufficiently low.Figure 1 studies success probability as a function of rank and sparse-entry percentage, including a regime using half the matrix entries as measurements.
Transformed RPCA: For transformed RPCA, the measurement operator is determined by the data and transformation group rather than freely chosen or modeled as random.This motivates seeking deterministic conditions verifiable from the given data.
Main result: The recovery bound is close to the intrinsic lower bound, differing by only a polylogarithmic factor.The result concerns random measurements and exactly recovers the desired low-rank and sparse pair with very high probability.
Generalization: The analysis also targets decompositions of observations into multiple incoherent low-complexity components encouraged by decomposable norms.The framework encompasses PCP, Outlier Pursuit, and Morphological Component Analysis, with measurement requirements governed by intrinsic degrees of freedom up to polylog(m).

2 Models and Main Results

The paper formulates compressive recovery of low-rank and sparse components through a convex program and establishes exact recovery under random-subspace measurements and structural assumptions.

Proof strategy: The proof uses a certificate-construction procedure that converts optimality for Principal Component Pursuit into optimality for the compressive problem.This modularly separates the compressive-measurement analysis from the underlying low-rank and sparse recovery analysis.
Modeling assumptions: The decomposition can be ambiguous because a matrix may simultaneously appear low-rank and sparse.Meaningful recovery therefore requires incoherence of the low-rank term and a sparse-term model that prevents it from looking low-rank.
Measurement model: The measurement subspace Q is sampled uniformly from q-dimensional subspaces, equivalently as the span of q independent Gaussian matrices.This distribution is rotationally invariant and is assumed independent of the sparse signs.
Convex program: Compressive Principal Component Pursuit minimizes nuclear norm plus weighted ℓ1 norm subject to matching the projected observation.The formulation is equivalent to the displayed program because the measurement subspace has full rank almost surely.
Main recovery theorem: Under incoherence, iid Bernoulli-Rademacher sparsity, and random measurements, the convex program uniquely recovers (L0, S0) with λ = 1/√m.The theorem assumes m ≥ n, rank r, bounded sparsity probability ρ, and gives success probability at least 1 − Cm^-9.
Measurement complexity: When rank and sparsity are small, the required measurement dimension is correspondingly small and nearly matches the intrinsic degrees-of-freedom lower bound.The paper notes that the rank and sparsity bounds essentially match those known for fully observed PCP.

3 Relationship to the Literature

The paper places compressive low-rank and sparse recovery alongside prior specialized and general frameworks, emphasizing nearly optimal exact-recovery guarantees for sums of structured regularizers.

Fully observed recovery: Earlier low-rank and sparse decomposition results primarily study fully observed matrices, so they are not directly comparable to this compressive setting.The paper positions its analysis as a way to transform fully observed optimality certificates into certificates for compressive recovery.
Greedy compressive methods: A prior greedy algorithm for compressive foreground-background separation performs well numerically, but its theoretical behavior and guarantees remain open.Its objective constrains rank and sparsity while fitting projected measurements.
General frameworks: General structured-recovery frameworks analyze low-complexity signals, while related sparse-low-rank work obtains tight noisy-estimation results under assumptions that preclude exact recovery.These approaches differ from the exact-recovery objective considered here.
Regularizer geometry: Gaussian-measurement analyses relate recovery to atomic-norm geometry or decomposable regularizers, but the present quotient norm is an infimal convolution of two decomposable terms.Its subdifferential has useful properties, although decomposability in the cited sense does not appear to hold.
Paper contribution: The paper generalizes decomposable-regularizer analysis to sums and obtains nearly optimal measurement bounds for exact recovery of multiple low-complexity components.It argues that these results provide theoretical justification for robust principal component analysis with highly compressive measurements.

4 General Certificate Upgrades

This section develops certificate conditions for compressive decomposition with decomposable regularizers, showing how fully observed optimality certificates can be upgraded under random measurements. The required measurement dimension scales with intrinsic degrees of freedom up to a logarithmic factor.

General decomposition framework: The compressive decomposition program generalizes Principal Component Pursuit, Outlier Pursuit, and Morphological Component Analysis through sums of structure-inducing norms.Each component uses a regularizer suited to structures such as sparsity, rank-deficiency, or structured sparsity.
General decomposition framework: A decomposable norm represents its subdifferential at X using a subspace T, a matrix S, and a dual-norm constraint on the orthogonal complement.The framework includes the ℓ1 and nuclear norms and sums of block ℓp norms.
Exact certificates: If the component tangent subspaces and Q⊥ are independent, a dual certificate satisfying projected equalities and strict dual-norm bounds proves unique optimality.Lemma 4.2 requires PTiΛ = λiSi, ∥PT⊥(i)Λ∥* < λi, and PQ⊥Λ = 0.
Inexact certificates: An inexact certificate relaxes the projected equalities by α while imposing a dual-norm bound β, and sufficiently small α and β still certify unique optimality.The compressive version adds the measurement constraint PQ⊥Λ = 0; the component norms must also majorize the Frobenius norm.
Random measurement upgrade: O(log2 m) oversampling beyond dim(T1 + ··· + Tτ) suffices for certificate upgrading with very high probability under a random subspace Q.The theorem requires dim(Q) ≥ CQ · dim(T1 + ··· + Tτ) · log2 m and gives probability at least 1−C2·τ·m−9.
Random measurement upgrade: The expected dual norms νi suggest choosing relative regularization weights according to λi ∝ νi.This recommendation is stated as consistent within logarithmic factors with earlier suggestions.

5 Key Probabilistic Lemmas

This section establishes probabilistic lemmas for the golfing-scheme analysis, using Gaussian operators, subspace projections, covering arguments, and concentration inequalities. These results control approximation and dual norms needed for certificate upgrading.

Random operator control: Lemma 5.1 analyzes a random Gaussian semidefinite operator A generated from independent Gaussian matrices and its range relative to a fixed subspace.The operator is represented as A = PγΣj=1 Hj⟨Hj, ·⟩, with R = range(A).
Random operator control: The first probabilistic lemma follows from a covering argument for controlling the random operator on a fixed subspace.The proof is supplied in Appendix B before the key certificate-upgrade lemma is introduced.
Dual-norm control: Lemma 5.2 controls the dual norm of the constructed certificate for any norm majorizing the Frobenius norm.It defines ν as the expected dual norm of an iid Gaussian matrix and applies to a fixed subspace S and matrix M.
Dual-norm control: Orthogonal projections of iid Gaussian matrices are probabilistically independent, enabling separate control of components on S and S⊥.This independence simplifies bounds on inner products involving the projected Gaussian operators.
Concentration analysis: The analysis bounds Gaussian suprema through comparison with a second Gaussian process and Lipschitz concentration.Slepian’s inequality and Gaussian Lipschitz concentration are used to obtain the stated estimates.
Concentration analysis: The resulting estimates are combined with t = √20 log m and rescaling by mnγ to complete the probabilistic bound.The estimate holds unconditionally after conditioning arguments are removed.

6 Proof of Lemma 4.5: Upgrade to Exact Certificate

This section proves that an inexact dual certificate can be corrected into an exact certificate when the relevant subspaces are sufficiently independent. The proof solves linear systems in the sum of tangent subspaces and enforces the measurement constraint with a minimum-norm correction.

Subspace linear systems: Lemma 6.1 bounds the Frobenius norm of a solution to simultaneous projection equations over independent subspaces.Vectorization converts the system into a matrix equation whose solution norm is controlled by the smallest singular value.
Subspace linear systems: The smallest singular value is bounded using pairwise projection overlaps, ensuring solvability when the subspaces are sufficiently separated.The bound follows from the eigenvalues of the block Gram matrix formed by orthonormal bases of the subspaces.
Certificate correction: Starting from an inexact certificate, the proof solves PTiΔ = λiSi − PTiΛ̂ and obtains a correction Δ0 in T1 + ··· + Tτ.The correction has a controlled Frobenius norm because the tangent subspaces are independent.
Certificate correction: A minimum-Frobenius-norm correction Δ⋆ is then chosen to satisfy the additional Q⊥ projection constraint.The system is feasible because T1 + ··· + Tτ and Q⊥ are independent, and it can be represented by a Neumann series.
Certificate correction: Setting Λ = Λ̂ + Δ⋆ enforces the required projected equalities, while norm comparisons control the remaining dual-norm terms.Because each regularizer majorizes the Frobenius norm, its dual norm is bounded below by the Frobenius norm.
Certificate correction: Under the stated hypotheses, the corrected certificate satisfies the exact optimality conditions, making the target solution uniquely optimal.The final dual-norm quantity is strictly smaller than one, completing the proof of Lemma 4.5.

7 Proof of Theorem 2.1: Compressive PCP Recovery

The proof establishes exact recovery for compressive PCP by upgrading an existing PCP dual certificate and verifying measurement, certificate, and probability conditions. It concludes that the target pair is uniquely optimal with failure probability polynomially small in m.

Certificate construction: The PCP certificate uses the nuclear and ℓ1 norms, with regularization parameters λ1 = 1 and λ2 = 1/√m.Both norms majorize the Frobenius norm, as required by the general certificate theorem.
Proof strategy: The proof reduces compressive PCP recovery to constructing an inexact certificate that satisfies the optimality conditions for the measured problem.Existing PCP certificates are upgraded to certificates compatible with the compressive measurements.
Measurement geometry: The random support obeys dim(Ω + T) < 3 · (ρmn + mr), ensuring the measurement-subspace dimension condition on the support event EΩ.The support size is controlled using Bernstein’s inequality.
Certificate construction: With probability at least 1 − C2m−10, an inexact PCP certificate exists and satisfies ∥PT PΩ∥ < 1/2.Conditioning on this event and the support event allows the certificate to be refined for compressive PCP.
Recovery conclusion: The refined certificate satisfies the required properties, making (L0, S0) the unique optimal solution to the compressive PCP problem.The proof combines the optimality conditions, certificate upgrade, and measurement bounds before consolidating failure probabilities.
Recovery conclusion: Correct recovery occurs with probability at least 1 − C9m−9 for sufficiently large m.The bound is obtained by combining the probabilities of the measurement, PCP-certificate, and upgrade events.

A Proof of Lemma 4.2: Optimality Conditions

The lemma proves uniqueness by showing that every nonzero feasible perturbation strictly increases the objective. The argument uses decomposable norms, subgradients, and independence of the component tangent spaces and the measurement nullspace.

Optimality argument: For any feasible perturbation, subgradients of the component norms provide a lower bound on the change in the objective.The perturbation preserves the measurement constraint, so the corresponding measurement term vanishes.
Optimality argument: If any perturbation has a nonzero component outside its tangent space, decomposability makes the objective strictly increase.The component norms’ decomposability separates tangent-space and orthogonal components.
Uniqueness: If all perturbations lie in the tangent spaces, independence of those spaces and Q⊥ rules out a nonzero feasible perturbation.Thus, the only feasible perturbation entirely contained in the tangent spaces is zero.
Uniqueness: Therefore, every feasible nonzero perturbation has higher objective value, proving that x⋆ is the unique optimal solution.This establishes the lemma’s uniqueness conclusion under the stated independence and decomposability conditions.

B Proof of Lemma 5.1: Operator Approximations

The operator approximation proof controls a random measurement operator on a subspace using a finite net, Gaussian concentration, and a union bound. The resulting approximation holds with the stated high probability when the measurement dimension scales with the subspace dimension.

Net argument: A 1/4-net of the unit ball restricted to S has size at most exp(dim(S) log 12).The net reduces uniform operator control to finitely many fixed-vector concentration bounds.
Concentration: Gaussian and spherical concentration bounds control the projected norm for each net point.The proof applies tail bounds to the resulting random coordinates before taking a union bound.
Random operator model: After vectorization, the random operator is represented by an mn × γ Haar-distributed orthonormal-column matrix.Orthogonal invariance identifies fixed-vector projections with coordinate restrictions of a uniformly random unit vector.
Concentration: Choosing t = 1/32 and taking a union bound yields an intermediate error bound of at most 1/16.The constants are selected so that the net cardinality is absorbed by the available concentration exponent.
Conclusion: When γ > C1dim(S), the required operator approximation holds with the desired probability.The measurement dimension must exceed the subspace dimension by a sufficiently large constant factor.