PaperlayerView exact revision on arXiv

Source-linked AI summary

Exact recoverability from dense corrupted observations via $L_1$ minimization

Nam H. Nguyen, Trac. D. Tran

arXiv:1102.1227v3cs.ITmath.ITmath.STstat.TH

TL;DR

The paper studies recovery of sparse signals from incomplete measurements corrupted by unknown, potentially unbounded sparse errors. It uses ℓ1 minimization and establishes exact recovery even when nearly all measurements are corrupted, alongside stable recovery with bounded-energy dense noise.

  • Problem

    The paper asks whether sparse signals can be recovered from incomplete measurements when unknown sparse errors may have arbitrarily large magnitudes.

    Source: §I · p. 1

  • Method

    The paper uses ℓ1 minimization to recover a sparse signal and sparse error jointly from measurements selected from an orthogonal matrix.

    Source: §I · p. 2

  • Results

    The analysis guarantees exact recovery even when nearly all measurements are grossly corrupted, and stable recovery when bounded-energy dense noise is also present.

    Source: B. Exact recovery as measurements are… · p. 3, §VIII · p. 16

  • Takeaways & Limitations

    The paper concludes that compressed sensing can be generalized to incomplete measurements corrupted by sparse errors while retaining robustness to additional small dense noise.

    Source: §VIII · p. 16

    The authors conjecture the signal-sparsity bound is optimal near-total corruption, but establishing this for suborthogonal matrices remains open.

    Source: §VIII · p. 16

Abstract

from arXiv · show

This paper confirms a surprising phenomenon first observed by Wright \textit{et al.} \cite{WYGSM_Face_2009_J} \cite{WM_denseError_2010_J} under different setting: given $m$ highly corrupted measurements $y = A_{\Omega \bullet} x^{\star} + e^{\star}$, where $A_{\Omega \bullet}$ is a submatrix whose rows are selected uniformly at random from rows of an orthogonal matrix $A$ and $e^{\star}$ is an unknown sparse error vector whose nonzero entries may be unbounded, we show that with high probability $\ell_1$-minimization can recover the sparse signal of interest $x^{\star}$ exactly from only $m = C \mu^2 k (\log n)^2$ where $k$ is the number of nonzero components of $x^{\star}$ and $\mu = n \max_{ij} A_{ij}^2$, even if nearly 100% of the measurements are corrupted. We further guarantee that stable recovery is possible when measurements are polluted by both gross sparse and small dense errors: $y = A_{\Omega \bullet} x^{\star} + e^{\star}+ \nu$ where $\nu$ is the small dense noise with bounded energy. Numerous simulation results under various settings are also presented to verify the validity of the theory as well as to illustrate the promising potential of the proposed framework.

I. INTRODUCTION

The paper extends compressed sensing to orthogonal-row measurements corrupted by unknown sparse errors, including errors of arbitrarily large magnitude. It analyzes exact and stable recovery, motivates the model through applications, and states conditions and qualifications on the guarantees.

I. INTRODUCTION

  • Orthogonal-row measurements address practical limits of fully random matrices, while extended ℓ1 minimization targets unknown, arbitrarily large sparse errors and can accommodate bounded dense noise.The paper identifies partial Fourier and structurally random matrices as promising alternatives and presents the combination of gross sparse errors and small dense noise as a technical contribution.Source: §I · p. 2

A. Motivational applications

  • Inpainting, sensor networks, and joint source-channel coding illustrate settings where the model handles unknown corruptions without requiring known missing-pixel locations or a corruption-probability model.For inpainting, the method estimates both corrupted locations and magnitudes; for joint source-channel coding, the paper contrasts its approach with needing a probabilistic corruption model.Source: A. Motivational applications · p. 2

B. Notations and organization of the paper

  • The paper reserves T and S for signal and error supports, defines k=|T| and s=|S|, and uses standard vector norms and a stated meaning of high probability.The paper defines high probability as an event occurring with probability at least 1−cn^-1.Source: B. Notations and organization of the… · p. 3

A. Sparse model

  • The proof model assumes independently uniform signs on the signal support and a uniformly sampled error support; random signal signs are sufficient, not necessary, since an extra log n factor handles arbitrary signs.The random-sign assumption is used for proof convenience.Source: A. Sparse model · p. 3

B. Exact recovery as measurements are corrupted by sparse noise

  • With high probability, the theorem guarantees exact signal and error recovery under random measurement and error supports, even when error magnitudes are arbitrary.For γ close to one, the paper allows error support approaching a constant fraction of the measurements; its parameter λ balances the signal and error ℓ1 terms.Source: B. Exact recovery as measurements are… · pp. 3–4
  • The exact-recovery guarantee is for a fixed sparse signal, not uniformly for all sparse signals; the authors also identify an open question for other orthogonal sensing matrices.They note that Fourier matrices permit a result for all signals supported on T, while whether the result extends to other orthogonal sensing matrices remains open.Source: B. Exact recovery as measurements are… · p. 3

C. Stable recovery as measurements are corrupted by both dense and sparse errors

The paper extends recovery guarantees to observations with both arbitrarily large sparse errors and bounded-energy dense noise, then considers errors sparse in an arbitrary orthogonal basis. It also situates these results against prior recovery frameworks and describes how the signal and error sparsity levels inform the regularization parameter.

C. Stable recovery as measurements are corrupted by both dense and sparse errors

  • m ≥ C1µ^2 max{γ/(1−γ)^2 k(log n)^2, k log n, (log n)^2} suffices for stable recovery with gross sparse errors and bounded-energy dense noise.The theorem states that the reconstruction error is optimal up to a √n factor relative to an oracle that knows the signal and error supports.Source: C. Stable recovery as measurements are… · pp. 4–5
  • For signals approximated by a k-sparse vector, the recovery error separates into a dense-noise term and an approximation-error term.The approximation term measures the distance from x⋆ to its best k-sparse approximation.Source: C. Stable recovery as measurements are… · p. 5

D. When error is sparsified under an arbitrary basis

  • When the error is sparse after an orthogonal transform D, the prior guarantees still apply, with µ interpreted as the mutual incoherence between AΩ• and D.Lower incoherence means fewer measurements are required for stable recovery.Source: D. When error is sparsified under an… · p. 5

E. Contribution and connections to previous works

  • Unlike the Gaussian-matrix setting of Wright and Ma, the paper studies suborthogonal measurements and combines gross sparse errors with dense noise.It also distinguishes its underdetermined, sparse-input setting from Candès and Tao, whose coding matrix is overcomplete.Source: E. Contribution and connections to… · p. 6
  • The regularization parameter λ balances the signal and error ℓ1 norms, with the stated sparsity relationship making signal recovery more constrained as errors become denser.When the error fraction is unknown, the paper gives a good-for-all parameter choice.Source: E. Contribution and connections to… · p. 6

III. STRUCTURE OF OUR PROOF

The proof uses Bernoulli sampling to exploit independence, then reduces exact recovery to constructing a dual certificate. It builds that certificate through a least-squares component and a companion signal component.

A. Bernoulli model and derandomization technique

  • Bernoulli sampling makes measurement and error locations independent for the proof, and derandomization transfers the recovery probability to fixed error signs.The argument relates failure under uniform sampling to failure under Bernoulli sampling.Source: A. Bernoulli model and derandomization… · pp. 6–7

B. Dual certificate

  • A dual certificate satisfying the lemma’s conditions makes every feasible perturbation no better than the true pair, yielding exact recovery.The feasible perturbations obey f = −AΩ•h.Source: B. Dual certificate · p. 7

C. Dual certification constructions

  • The certificate construction sets w(e) by least squares, choosing the minimum-ℓ2-norm solution before constructing v(x).The construction aims for w(e) to meet the required ℓ∞-norm condition.Source: C. Dual certification constructions · p. 8

J•AJT (A∗

The dual-certificate argument establishes conditions for exact, unique recovery and bounds the dual vectors with high probability. Auxiliary results use near-orthogonality between selected support and its complement to help distinguish the true support.

J•AJT (A∗

  • The construction of v(x) satisfies three identity relations through the orthogonality of A.The passage states that AS•v(x) = 0 and AΩc•v(x) = 0.Source: J•AJT (A∗ · p. 8
  • Lemmas 3 and 4 imply that the convex program has an exact and unique solution.The lemmas establish ℓ∞-norm bounds for the dual vectors v(x) and w(e).Source: J•AJT (A∗ · p. 8

A. Important auxiliary lemmas

  • Lemma 5 is used to bound ∥AJcT∥, while Proposition 1 gives a high-probability bound when m − s ≥ 4C0µk log n.The cited literature is,,.Source: A. Important auxiliary lemmas · p. 8
  • A near-orthogonality lemma separates AS0T from AS0T c, helping identify the true support of x⋆.The lemma assumes a random subset S0 and a lower bound on ρ0; its stated success probability is at least 1 − 3n−1.Source: A. Important auxiliary lemmas · p. 9

B. Proof of Lemma 3

  • The proof of Lemma 3 uses concentration bounds and a union bound to establish its stated high-probability control when m − s satisfies a logarithmic lower bound.The supplied proof passage gives the condition m − s ≥ Cµ max{k, log n} log n.Source: B. Proof of Lemma 3 · p. 9

C. Proof of Lemma 4

The proof of Lemma 4 first seeks a spectral-norm bound for AST. It invokes Lemma 5 and rewrites a condition using ηρ = s/n.

1) Preliminary results:

  • A spectral-norm bound for ∥AST∥ is needed to establish the bounds in Lemma 4.The proof invokes Lemma 5 to obtain the bound with high probability.Source: 1) Preliminary results · pp. 9–10

ST AST

  • The proof uses ηρ = s/n to rewrite the condition on s.The supplied passage gives the resulting lower bound only in truncated form.Source: ST AST · p. 10
  • The rewritten condition includes a factor µk log n and a dependence on ϵ, but the supplied inequality is incomplete.Source: ST AST · p. 10

2) Main proofs:

The proof constructs w(e) and bounds its terms to control the dual vector. It handles cases according to the size of S and concludes with an ℓ∞-norm bound under stated size conditions.

2) Main proofs:

  • Hoeffding’s inequality bounds terms involving sgn(e⋆S), using the random-sign assumption on the errors.A term is controlled when s ≤ Cγm.Source: 2) Main proofs · p. 10
  • The proof divides the analysis into two cases according to the size of S.The supplied passages do not specify the case split thresholds.Source: 2) Main proofs · p. 10
  • The proof bounds V by 1/(4λ) when s ≤ Cγm and k ≤ C′γm/(µ log n).It obtains the bound by controlling component terms and applying the triangle inequality.Source: 2) Main proofs · p. 11

AJT A∗

The proof bounds the spectral norm of W using concentration arguments, then uses feasibility and orthogonality to bound recovery error under dense noise. The resulting measurement-space error is at most 2σ.

AJT (A∗

  • Hoeffding’s inequality is used to estimate terms in the spectral-norm bound for W.The proof also conditions on events established earlier and applies a union bound.Source: AJT (A∗ · p. 11

A. Proof of Theorem 3

  • ∥AΩ•(bx − x⋆)∥2 ≤ 2σ follows because both the optimal solution and x⋆ satisfy the residual bound σ.The proof then seeks a bound on ∥bx − x⋆∥2.Source: A. Proof of Theorem 3 · p. 11
  • The proof splits the bound on ∥AΩc•g∥2 into two terms and invokes Lemma 2 for perturbations with AΩ•h = 0.Here g = bx − x⋆.Source: A. Proof of Theorem 3 · p. 11

B. Proof of Theorem 4

The proof bounds the reconstruction residuals for both the signal and error components. It separates terms associated with unreliable and trustworthy measurements and uses a perturbation lemma and noise bound in the analysis.

B. Proof of Theorem 4

  • The proof controls both residual components, g(x) and g(e), for the optimal solution pair.It then bounds terms M1 and M2 to complete the argument.Source: B. Proof of Theorem 4 · p. 12, 1) Bound M2 · p. 13
  • The analysis distinguishes unreliable measurement locations S from trustworthy locations J, with Ω = S ∪ J.The sum to be bounded is handled through bounds for M1 and M2.Source: B. Proof of Theorem 4 · p. 12

1) Bound M2:

  • For M2, the proof uses optimality, triangle inequalities, and a perturbation bound, with the dense-noise component bounded by σ.It converts between ℓ1 and ℓ2 norms when deriving the bound.Source: 1) Bound M2 · pp. 12–13

VI. ORACLE INEQUALITIES

The section compares Theorem 4’s reconstruction error with an oracle estimator that knows the signal and sparse-noise supports. The oracle uses least-squares projection, and the stated adversarial-noise error bound for Theorem 4 loses a √n factor relative to the oracle bound.

VI. ORACLE INEQUALITIES

  • The oracle estimator uses least-squares projection after separating measurements into corrupted locations S and unaffected locations J.The oracle is given the locations of the nonzero signal coefficients and sparse errors.Source: §VI · p. 13
  • The oracle error bound for e⋆ is stated under the condition m ≥ μk log n.The section concludes with oracle bounds for the signal and error.Source: §VI · p. 14
  • Theorem 4’s adversarial-noise error bound loses a √n factor relative to the ideal bound achieved with oracle help.The oracle is assumed to know the locations of the signal and sparse-noise nonzeros.Source: §VI · pp. 13–14

VII. NUMERICAL EXPERIMENTS

The experiments recast the observation model as a conventional ℓ1 program and use a Homotopy solver. They recommend a parameter choice intended as a general-purpose setting and report that simulations with varying noise produce RMS errors close to the oracle’s.

VII. NUMERICAL EXPERIMENTS

  • The observation model is recast as a conventional ℓ1 program using z⋆ = [x⋆T, λe⋆T]T and B = [AΩ• 1 λI].The noisy version is expressed with residual bounded by σ.Source: §VII · p. 14
  • The experiments use the Homotopy solver and recommend a general-purpose λ choice that permits up to 25% corrupted measurements under the stated theorems.When the signal is known to be very sparse, reducing λ is said to help retrieve the signal with more corrupted measurements.Source: §VII · p. 14

A. Exact recovery from grossly corrupted measurements

The paper analyzes exact recovery of sparse signals from grossly corrupted measurements and stable recovery when small dense noise is also present. Simulations test these guarantees, including an image-recovery example, while the conclusion identifies a boundary that remains conjectural.

A. Exact recovery from grossly corrupted measurements

  • Perfect recovery persists with 25% of measurements grossly perturbed, and the observed sparsity level scales proportionally with m(log n)^(3/2).The simulations use Fourier rows and report agreement with the theory, including for relatively small problem sizes.Source: A. Exact recovery from grossly… · p. 14, Figure 1 · p. 14

B. Stable recovery from both dense and sparse corrupted measurements

C. Experiments with images

VIII. DISCUSSION AND CONCLUSION

  • The analysis establishes exact recovery under a significant fraction of gross sparse errors and stable recovery with both gross sparse errors and small dense noise, including approximately sparse signals.For the dense-noise case, the recovery error is within a constant fraction of the dense noise level.Source: §VIII · p. 16
  • The authors conjecture the sparsity bound is optimal near-total corruption, but establishing a matching result for suborthogonal matrices remains open.They state that a related result for Gaussian measurement matrices will appear in upcoming work.Source: §VIII · p. 16
  • The conclusion relates the signal-recovery phenomenon to exact recovery of grossly corrupted low-rank matrices.The cited low-rank results allow almost all entries to be arbitrarily perturbed under a rank condition.Source: §VIII · p. 16

IX. APPENDIX

The appendix proof uses dual-vector and concentration arguments to establish recovery bounds. For approximately sparse signals, the resulting bound includes both dense-noise level and the signal’s tail outside its support.

  • The proof of the corollary applies a dual-vector condition to perturbation pairs satisfying f = −A_Ω•h.The argument uses the relation to bound the objective under perturbations.Source: §IX · p. 16
  • For approximately sparse signals, the recovery bound includes a term proportional to the signal mass outside its support.The displayed bound is √n(1 + λ)σ + 2∥x⋆_Tᶜ∥₁.Source: §IX · p. 16
  • A concentration argument bounds a supremum of sums of independent random variables using Talagrand’s result.The appendix defines the variables from Bernoulli selectors and uses their independence and variance bounds.Source: §IX · pp. 16–17

Related papers

Loading 1102.1227v3…