Source-linked AI summary
Compressed Sensing and Matrix Completion with Constant Proportion of Corruptions
Xiaodong Li
TL;DR
The paper studies recovery of sparse signals and low-rank matrices when unknown data entries are arbitrarily corrupted. It develops tractable recovery guarantees using generalized restricted-isometry arguments and golfing-scheme dual certificates, including exact recovery under positive corruption proportions.
Problem
The paper addresses efficient and accurate recovery of signals when some entries of the data vector are totally corrupted and their locations are unknown.
Method
The proofs use a generalized restricted-isometry argument for compressed sensing and golfing-scheme constructions of dual certificates for the other models.
Results
The theorems establish exact or high-probability recovery for compressed sensing and matrix completion with corrupted measurements or entries under stated sparsity, sampling, and model conditions.
Takeaways & Limitations
The results extend tractable recovery guarantees to settings with a positive proportion of corrupted observations, while improving a prior compressed-sensing condition by a factor of µ in the general sensing model.
Takeaways & Limitations
The matrix-completion analysis is restricted to noiseless data, and the general-sensing result leaves open cases with fixed supports and signs.
Abstract
from arXiv · showhide
We improve existing results in the field of compressed sensing and matrix completion when sampled data may be grossly corrupted. We introduce three new theorems. 1) In compressed sensing, we show that if the m \times n sensing matrix has independent Gaussian entries, then one can recover a sparse signal x exactly by tractable \ell1 minimimization even if a positive fraction of the measurements are arbitrarily corrupted, provided the number of nonzero entries in x is O(m/(log(n/m) + 1)). 2) In the very general sensing model introduced in "A probabilistic and RIPless theory of compressed sensing" by Candes and Plan, and assuming a positive fraction of corrupted measurements, exact recovery still holds if the signal now has O(m/(log^2 n)) nonzero entries. 3) Finally, we prove that one can recover an n \times n low-rank matrix from m corrupted sampled entries by tractable optimization provided the rank is on the order of O(m/(n log^2 n)); again, this holds when there is a positive fraction of corrupted samples.
1 Introduction
The paper studies exact recovery of sparse signals and low-rank matrices when measurements or samples contain unknown gross corruptions. It develops tractable convex-optimization guarantees under Gaussian, general, and stochastic matrix-completion models.
- Compressed sensing with corruptions: Unknown corrupted entries are modeled additively as y = Ax + f, with the goal of efficiently recovering both the original signal and corruption.The model covers applications including clipping and sensor-network recording errors.
- Matrix completion with corruptions: Corrupted matrix completion recovers a low-rank matrix from nearly minimally many samples even when a constant proportion of sampled entries is corrupted.The guarantee uses a stochastic sampling model and assumptions on the rank, sampling rate, incoherence, and random support.
- Compressed sensing with corruptions: A positive fraction of corruptions is tolerated for Gaussian sensing while preserving the standard compressed-sensing sparsity order ∥x∥0 ≤ αm/(log(n/m) + 1).Theorem 1.1 allows ∥f∥0 ≤ αm and provides a noise-dependent error bound; in the noiseless case this yields exact recovery.
- General sensing matrices: General sensing matrices support exact recovery with probability at least 1 − Cn^-3 when the signal sparsity and corruption level satisfy the theorem’s µ-dependent conditions.For some DFT-type models, µ can be constant, making the tolerated corruption proportion constant.
- Comparison and contributions: The matrix-completion result improves prior stochastic-sampling requirements by several logarithmic factors, while requiring random support when the rank is large.The comparison also notes that the sampling-rate requirement is optimal even for clean matrix completion.
- Proof techniques: The proof of the Gaussian result generalizes restricted isometry, while the other two theorems use golfing-scheme dual-certificate constructions.The paper introduces sufficient optimality conditions suited to the golfing scheme.
2 A Proof of Theorem 1.1
The proof establishes recovery for sparse signals and sparse corruptions by generalizing RIP to the augmented matrix [A, I] and showing its mixed RIP constant is sufficiently small with high probability.
- Generalized RIP: The generalized RIP constant δ_s1,s2 controls vectors with sparse signal and corruption components simultaneously.It is defined through uniform norm preservation for supports of sizes s1 and s2.
- Recovery condition: Under the resulting RIP condition, the optimization solution recovers the original signal and corruption variables, including the noisy case covered by the theorem.The proof analyzes the error variables Δx and Δf using the optimization constraint and block decompositions of their supports.
- Probabilistic bounds: The Gaussian matrix lemmas control the restricted sensing and cross-term norms, while a union bound makes the bounds uniform over supports.The resulting probability is at least 1 − 2 exp((δ^2/2 − α1 − α2)m).
- Generalized RIP: The proof bounds the augmented matrix Φ = [A, I] on supports of the signal and corruption vectors.The norm expansion separates the sensing term, corruption term, and their cross-term.
- Recovery condition: δ_2s1,2s2 < 1/9 holds with probability at least 1 − Ce^−cm when α is sufficiently small.This is the central probabilistic estimate used to invoke the recovery lemma.
3 A Proof of Theorem 1.2
The proof of Theorem 1.2 constructs an inexact dual vector with the golfing scheme, then uses concentration and independence bounds to certify exact recovery under the general sensing model.
- Golfing scheme: The golfing scheme partitions the uncorrupted measurements into l = ⌊log2 n + 1⌋ independent blocks.The partition is deterministic and therefore preserves independence among the resulting sensing submatrices.
- Golfing scheme: The constructed certificate is analyzed recursively using concentration inequalities and the supporting lemmas for the sensing model.Hoeffding’s and Bernstein’s inequalities control the relevant inner products and coordinatewise quantities.
- Certificate bounds: The certificate’s residual norm contracts across golfing iterations, reaching a bound such as ∥p_l∥_2 ≤ 1/4 with high probability.The contraction follows from the blockwise estimates and the sparsity condition.
- Comparison and assumptions: The proof incurs an extra logarithmic factor because it separately bounds the corruption-sign term and requires an infinity-norm bound on the certificate.These requirements also lead to the random-sign assumptions on the signal.
4 A Proof of Theorem 1.3
The proof of Theorem 1.3 uses a golfing-scheme dual certificate for corrupted matrix completion, with an equivalent sampling model and recursive norm control yielding exact recovery.
- Sampling model: The proof replaces the original sampling model with an equivalent model that introduces auxiliary independent sets and random sign variables.The joint distribution of observed and corrupted supports is unchanged, while the auxiliary variables simplify the proof.
- Tangent-space decomposition: The tangent-space projectors provide the decomposition used to control low-rank and orthogonal components of matrix errors.The proof uses P_T X = UU*X + XVV* − UU*XVV* and P_T⊥X = (I − UU*)X(I − VV*).
- Recovery conclusion: Under these bounds, the optimization solution satisfies (L̂, Ŝ) = (L, S).The recovery conclusion appears after the certificate construction and error argument.
- Golfing scheme: The golfing scheme splits Γ′ into l = ⌊5 log n + 1⌋ independent Bernoulli blocks and recursively constructs certificate components.The block probabilities are chosen so that q ≥ Cρ/log(n).
- Certificate bounds: The recursive construction contracts the Frobenius norm of the tangent-space residual while concentration lemmas control the remaining certificate terms.The proof invokes sampling and matrix concentration bounds under sufficiently large Cρ and sufficiently small Cs.