PaperlayerView exact revision on arXiv

Source-linked AI summary

Corrupted Sensing: Novel Guarantees for Separating Structured Signals

Rina Foygel, Lester Mackey

arXiv:1305.2524v2cs.ITmath.ITmath.OCstat.ML

TL;DR

Corrupted sensing asks how to recover a structured signal from measurements that may also contain structured corruption. The paper analyzes penalized and constrained convex programs using geometric complexity measures, and reports recovery conditions whose simulated thresholds closely match observed phase transitions.

  • Problem

    Corrupted sensing asks whether a structured signal can be recovered when measurements contain unknown structured corruption.

    Source: §I · p. 1

  • Method

    The paper analyzes penalized and constrained convex programs for separating signal and corruption, using Gaussian complexity and Gaussian distance to characterize recovery.

    Source: §III · p. 5, B. Phase transitions from penalized… · p. 13, §VI · p. 14

  • Results

    The simulations show close agreement between theoretical recovery bounds and the sharp phase transitions observed in practice.

    Source: §VI · p. 14

  • Takeaways & Limitations

    The analysis provides conditions for exact signal recovery from structured corruption and stable recovery when unstructured noise is added.

    Source: §VI · p. 14

Abstract

from arXiv · show

We study the problem of corrupted sensing, a generalization of compressed sensing in which one aims to recover a signal from a collection of corrupted or unreliable measurements. While an arbitrary signal cannot be recovered in the face of arbitrary corruption, tractable recovery is possible when both signal and corruption are suitably structured. We quantify the relationship between signal recovery and two geometric measures of structure, the Gaussian complexity of a tangent cone and the Gaussian distance to a subdifferential. We take a convex programming approach to disentangling signal and corruption, analyzing both penalized programs that trade off between signal and corruption complexity, and constrained programs that bound the complexity of signal or corruption when prior information is available. In each case, we provide conditions for exact signal recovery from structured corruption and stable signal recovery from structured corruption with added unstructured noise. Our simulations demonstrate close agreement between our theoretical recovery bounds and the sharp phase transitions observed in practice. In addition, we provide new interpretable bounds for the Gaussian complexity of sparse vectors, block-sparse vectors, and low-rank matrices, which lead to sharper guarantees of recovery when combined with our results and those in the literature.

I. INTRODUCTION

Corrupted sensing seeks to recover a structured signal when measurements include structured corruption, extending compressed sensing beyond trustworthy measurements. The paper formulates convex methods and recovery conditions for structured signal-corruption pairs, with scope including noise and both under- and overcomplete settings.

I. INTRODUCTION

  • Corrupted sensing extends compressed sensing by seeking structured-signal recovery despite unknown structured corruption in the measurements.The paper frames recovery as possible when both signal and corruption are suitably structured.Source: §I · p. 1

A. Problem formulation and methodology

  • The analysis treats signal and corruption complexity through norms and considers bounded unstructured noise whose size controls estimation error.The signal and corruption are fixed independently of the Gaussian measurement matrix; the noise need not be independent and may be chosen adversarially.Source: A. Problem formulation and methodology · p. 2
  • The paper analyzes penalized convex programs that trade off signal and corruption penalties, and constrained programs that use prior bounds on either complexity.Its results cover exact recovery and stable recovery with noise, in both high-dimensional (n < p) and overcomplete (n ≥ p) settings.Source: A. Problem formulation and methodology · p. 2

B. Roadmap

  • The introduction previews applications to secure, robust channel coding and simulations that closely match theoretical recovery bounds to observed phase transitions.The paper’s roadmap also identifies further applications in Section IV and simulated-data experiments in Section V.Source: B. Roadmap · pp. 2–3

II. CONVEX GEOMETRY

The paper uses convex-geometric quantities to describe structured-vector complexity and connect it to recovery. Tangent cones capture descent directions, while Gaussian complexity and optimized Gaussian distance provide measures used in recovery bounds.

B. Tangent cones and normal cones

  • The tangent cone at a point contains directions along which the norm does not increase, and the normal cone is its polar and the conic hull of the subdifferential.The paper illustrates these cones for the ℓ1 and ℓ2 norms at x = (1, 0).Source: B. Tangent cones and normal cones · p. 3, Figure 1 · p. 4

C. Gaussian complexity and Gaussian distance

  • Gaussian complexity and Gaussian distance are the two geometric measures the paper adopts to quantify structured-vector complexity.The Gaussian squared complexity is defined for a set, and the Gaussian distance is the square root of the Gaussian squared distance.Source: C. Gaussian complexity and Gaussian… · p. 3
  • The optimized Gaussian distance to the scaled subdifferential faithfully approximates the Gaussian complexity of the tangent cone.The paper relates the measures through Propositions 1 and 2.Source: C. Gaussian complexity and Gaussian… · p. 4
  • For sparse vectors, the new closed-form Gaussian-complexity bound is tighter than the prior bound when s ≥ 0.07 · p and is below p for every s < p.The new closed-form bound closely approximates the optimal squared-distance bound across a wide range of sparsity levels, while the prior bound dominates it only in the extreme sparsity regime.Source: C. Gaussian complexity and Gaussian… · pp. 4–5
  • Under the ℓ2 norm, the tangent cone is a half-space with Gaussian complexity approximately √p regardless of signal structure, whereas sparse vectors have smaller complexity under ℓ1.The paper notes that this reduction in geometric complexity is critical to recovery in the presence of corruption.Source: B. Tangent cones and normal cones · p. 3, C. Gaussian complexity and Gaussian… · p. 5

D. Structured vectors and structure-inducing norms

The paper pairs structure-inducing norms with signal classes and gives constrained recovery guarantees based on signal and corruption geometry.

D. Structured vectors and structure-inducing norms

  • Sparse, low-rank, binary, and block-sparse signals are paired with the ℓ1, trace, ℓ∞, and ℓ1/ℓ2 norms, respectively.These norms are identified as having low complexity for their associated signal classes.Source: D. Structured vectors and… · p. 5
  • Tables I and II give bounds for tangent-cone complexity and scaled subdifferential distance across structured settings.The estimates support analysis of constrained and penalized recovery, respectively.Source: D. Structured vectors and… · p. 5

III. RECOVERY FROM CORRUPTED GAUSSIAN MEASUREMENTS

  • The recovery analysis describes signal and corruption through their respective tangent cones.The cones are defined at the true structured signal and corruption.Source: §III · p. 5

A. Recovery via constrained optimization

  • Constrained procedures recover exactly without noise and stably with noise when the measurement count exceeds a success threshold.The theorem gives a high-probability guarantee for either constrained program.Source: A. Recovery via constrained optimization · pp. 5, 7

B. Recovery via penalized optimization

The paper gives penalized recovery conditions and a proof strategy, then applies its theory to binary signals with sparse corruption. The binary result extends beyond noiseless, equal-dimension settings.

B. Recovery via penalized optimization

  • Penalized recovery has sufficient conditions for exact and stable recovery, with λ set as the ratio of corruption and signal distance scalings.The theorem also reports a high-probability guarantee above a success threshold.Source: B. Recovery via penalized optimization · p. 7
  • The penalized threshold is nearly right empirically, but a visible asymmetry remains because only the signal is Gaussian-modulated.The paper contrasts this with a symmetric model in which both signal and corruption are independently Gaussian-modulated.Source: B. Recovery via penalized optimization · p. 7

C. Proof overview

  • The proof bounds the joint estimation error by lower-bounding a measurement quantity over perturbations allowed by the recovery procedure.The resulting lower bound is applied to the estimator error to control its ℓ2 norm.Source: C. Proof overview · p. 7

A. Binary recovery from sparse corruption and unstructured noise

  • Under Corollary 1’s measurement condition, the recovered binary signal equals the sign of the estimated signal with high probability.The corollary assumes a binary signal and corruption supported on at most n·γ entries.Source: A. Binary recovery from sparse… · p. 8
  • For binary signals with sparse corruption, the noiseless recovery condition holds when the corruption proportion γ is below 19.3%.The result also allows dense unstructured noise and measurement counts n different from p.Source: A. Binary recovery from sparse… · p. 8

B. General penalized recovery from block-sparse corruption and unstructured noise

The penalized recovery results cover entrywise- and block-sparse corruption, including a dense-corruption regime with an arbitrary specified upper bound on corruption. For sparse signals with entrywise corruption, the analysis gives explicit trade-offs between signal and corruption sparsity.

B. General penalized recovery from block-sparse corruption and unstructured noise

  • The analysis extends to structured signals recovered from block-sparse corruption, a setting the authors identify as previously unanalyzed.Corollary 2 also covers entrywise-sparse corruption.Source: B. General penalized recovery from… · p. 8
  • For dense block or entrywise corruption, Corollary 2 gives exact recovery in the noiseless case and stable recovery with unstructured noise under its stated conditions.The result allows the corruption proportion γ to range anywhere in (0, 1), with at most a γ fraction of corrupted blocks.Source: B. General penalized recovery from… · pp. 8–9
  • The guarantees use a penalty parameter tied to the corruption bound, while the stated choice does not require prior knowledge of signal sparsity.The parameter is given as λ = μk(1−γ)/t_sig for t_sig ≥ 0; the result is parameterized by γ.Source: B. General penalized recovery from… · pp. 8–9
  • When x⋆ has at most s nonzero entries and v⋆ is entrywise sparse (k = 1), s log(p/s) + s measurements suffice, with high probability, for exact or stable recovery, respectively.The result also provides an explicit trade-off between the signal and corruption sparsity levels.Source: B. General penalized recovery from… · p. 9
  • The paper leaves an adversarial extension for future work, although it says the analysis can be adapted by measuring the Gaussian complexity of the ℓ1 unit ball.The contrasted setting permits the signal and corruption to be selected with knowledge of the measurement matrix.Source: B. General penalized recovery from… · p. 9

C. Penalized recovery when signal and corruption are both extremely sparse

For extremely sparse signal and corruption, the penalized analysis gives a recovery guarantee without knowing their sparsity levels. The paper also contrasts its assumptions and guarantees with prior work, and reports synthetic experiments in which theoretical constrained-recovery thresholds closely match observed phase transitions.

C. Penalized recovery when signal and corruption are both extremely sparse

  • For extremely sparse signals and corruption, the analysis gives high-probability recovery with λ = 1 without knowing either sparsity level.The measurement bound is reported in terms of log(p+n) and the two sparsity levels; the noiseless case recovers a result of Laska et al..Source: C. Penalized recovery when signal and… · pp. 9–10
  • The paper says its sparse-signal, sparse-corruption analysis has explicit small constants, stable recovery under unstructured noise, and a more general structural treatment than the compared result.It also notes a similar result for block-sparse signals and corruption, without giving its details.Source: C. Penalized recovery when signal and… · p. 10

1) Sparse signal recovery from sparse corruption:

  • For sparse signal recovery from sparse corruption, the authors contrast their deterministic-vector Gaussian-measurement analysis with prior results relying on random signs, supports, or matrix incoherence.They state that their framework also covers arbitrary structured signals and corruption vectors.Source: 1) Sparse signal recovery from sparse… · p. 10

2) Structured signal recovery from structured corruption:

  • Against related structured-recovery work, this paper permits noisy observations, sample sizes above or below p, and penalized optimization, but does not give high-probability failure bounds.The cited comparison includes settings with n = p, noiseless observations, and exactly known signal or corruption complexity.Source: 2) Structured signal recovery from… · p. 10

V. EXPERIMENTAL EVALUATION

  • The synthetic evaluation tests constrained and penalized recovery across structured signals and corruptions, with and without noise, using CVX to solve the convex programs.Its stated aims include comparing constrained-theory predictions with empirical behavior and evaluating penalty settings suggested by Theorem 2.Source: §V · p. 10

A. Phase transitions from constrained recovery

  • Theoretical thresholds closely match observed constrained-recovery phase transitions for binary signals with sparse corruption, sparse signals with sparse corruption, and sparse signals with block-sparse corruption.For block-sparse corruption, the comparison also plots the threshold for using ℓ1 on both components rather than exploiting block structure.Source: A. Phase transitions from constrained… · pp. 11, 13, Figure 3 · p. 12, Figure 4 · p. 12

B. Phase transitions from penalized recovery

The simulations compare penalized recovery with constrained recovery and test stable recovery under unstructured noise. The conclusion identifies gaps in matching the two theories, handling unknown noise levels, and extending results beyond Gaussian measurements.

B. Phase transitions from penalized recovery

  • Three penalty choices yield empirical phase transitions nearly as good as constrained recovery without prior knowledge of the signal or corruption norms.With λ = 1, high-probability recovery is reported when neither signal nor corruption is overly dense.Source: B. Phase transitions from penalized… · p. 13

C. Stable recovery error

  • Across signal lengths and measurement counts, distance-rescaled recovery errors converge to a common value, as Theorem 1 predicts.Absolute error curves vary with signal length; the experiment averages errors over 20 iterations.Source: C. Stable recovery error · p. 14

VI. CONCLUSIONS AND FUTURE WORK

  • Penalized recovery performs nearly as well empirically as constrained recovery, suggesting its theory could be sharpened to match constrained guarantees more closely.The conclusion also identifies analysis of a fully penalized program without a known noise bound as a practical direction.Source: §VI · p. 16
  • Stable-recovery analysis assumes only bounded ℓ2 noise, while extension to non-Gaussian measurements remains an open question.The authors anticipate improved estimation-error bounds under sub-Gaussian or sub-exponential noise assumptions.Source: §VI · p. 16

APPENDIX A TANGENT CONE COMPLEXITY BOUNDS

The appendix develops bounds on Gaussian complexity and Gaussian distance for structured signals. These estimates include new results for block-sparse vectors and low-rank matrices, and inform recovery guarantees and penalty choices.

APPENDIX A TANGENT CONE COMPLEXITY BOUNDS

  • The appendix collects tangent-cone complexity and scaled-subdifferential distance bounds for structured vectors and matrices.The distance bounds provide subdifferential scalings used to choose penalties; the authors relate these bounds to tangent-cone complexity.Source: Appendix A · p. 17, A. Fundamentals · p. 17

B. Sparse vectors

  • For sparse vectors, Proposition 3 yields a second Gaussian-distance bound, extending the sparse-vector estimates used to bound complexity.The supplied passage identifies this bound as arising from the general treatment of block-sparse vectors.Source: B. Sparse vectors · p. 17

C. Block-sparse vectors

  • For vectors supported on at most s of m blocks of size k, Proposition 4 gives two Gaussian-distance estimates; exploiting blocks can require fewer recovery measurements than element-wise sparsity estimates.The comparison states that the block-size factor approaches 1 as k grows, whereas the element-wise factor is μ_1^2.Source: C. Block-sparse vectors · p. 17

D. Binary vectors

E. Low-rank matrices

  • For rank-at-most-r matrices with m1 ≥ m2, Proposition 5 provides a new Gaussian-distance estimate based on the trace-norm subdifferential.The paper contrasts this with an existing tangent-cone complexity bound of 3r(m1 + m2 − r).Source: E. Low-rank matrices · p. 19

F. Proof of subdifferential distance bound

The appendix relates distance to a norm subdifferential with the Gaussian complexity of its tangent cone. It also applies the paper’s recovery results in several corollaries.

F. Proof of subdifferential distance bound

G. Relating Gaussian distance and Gaussian complexity

  • Under weak decomposability, Proposition 1 relates Gaussian distance to Gaussian complexity through concentration and a Lipschitz bound for the projection scale.The projection scale t_g is identified as a Lipschitz function of the Gaussian vector.Source: G. Relating Gaussian distance and… · p. 20

A. Corollaries

  • For binary-signal recovery, the corollary’s argument yields exact recovery by taking the sign of the estimate under its stated probability bound.The supplied proof passage gives probability at least 1 − e^−(μn−2δ√n−τ)^2/2.Source: A. Corollaries · p. 21

B. Scaling for sparse signal and dense corruption

The corollary gives a recovery-error guarantee for a sparse signal under dense corruption. The main analysis derives error bounds for constrained and penalized estimation from an ℓ2 noise bound.

B. Scaling for sparse signal and dense corruption

A. Main idea

  • An ℓ2 bound on noise underlies the estimation-error guarantee for the constrained recovery problem.Source: A. Main idea · pp. 22–23
  • The penalized recovery program likewise yields an estimation-error bound for its feasible solution.Source: A. Main idea · p. 23

B. Preliminaries

The preliminaries set up Gaussian comparison and concentration bounds used in both recovery settings. The constrained lower-bound argument combines Gaussian-complexity estimates with auxiliary bounds on Gaussian norms.

B. Preliminaries

  • The preliminary lemma relates the minimum of ∥Φa + b∥2 over Ω to a second Gaussian functional.Its stated setting uses a Gaussian measurement matrix and independent standard Gaussian vectors.Source: B. Preliminaries · p. 23
  • Gaussian comparison and concentration bounds are the stated main ingredients for deriving the constrained and penalized results.The proof roadmap applies lower bounds to different sets for the two settings, then combines them with a probability bound.Source: B. Preliminaries · p. 23

C. Lower bound: constrained setting

  • The constrained proof distinguishes two cases before asserting a common resulting bound.The supplied passage does not state the bound's formula.Source: C. Lower bound: constrained setting · p. 24
  • The constrained lower-bound argument uses a Gaussian-norm fluctuation bound and an inequality for nonnegative a, b with a2 + b2 ≤ C2.The section says these steps, together with Lemma 5, yield the desired lower bound, but the bound itself is not included in the supplied passages.Source: C. Lower bound: constrained setting · p. 24

D. Lower bound: penalized setting

The penalized-setting lower-bound proof uses a Gaussian comparison argument and bounds involving the signal and corruption parameters. Theorem 4 specifies the penalty ratio as λ = tcor/tsig.

D. Lower bound: penalized setting

  • Theorem 4 sets the penalized parameter to λ = tcor/tsig for tsig, tcor ≥ 0.The supplied passage gives the theorem's parameterization but not its bound.Source: D. Lower bound: penalized setting · p. 24
  • The proof lower-bounds a weighted sum of ∥a∥2 and ∥b∥2 using positive parts of Gaussian inner products.The displayed inequality uses weights dsig and dcor and vectors g and h.Source: D. Lower bound: penalized setting · p. 25
  • The expectation step invokes Lemma 7 for the Gaussian norm and Lemma 8 to bound the expectations of dsig and dcor.The section identifies these as ingredients in its penalized lower-bound derivation.Source: D. Lower bound: penalized setting · p. 25

APPENDIX D PROOFS FOR LEMMAS

The appendix supplies auxiliary Gaussian-process, concentration, and geometric arguments used in the paper's lower bounds. Its proof fragments also establish a Lipschitz property for a projection-related quantity and reduce one matrix bound to a submatrix.

APPENDIX D PROOFS FOR LEMMAS

  • A lower bound for E[∥Γ∥∗] can be reduced to one for a Gaussian submatrix Υ because ∥Γ∥∗ ≥ ∥Υ∥∗.The passage specifies that Υ is an m1 × k submatrix with i.i.d. Gaussian entries.Source: Appendix D · p. 26
  • The projection-related quantity tg is 1/∥w0∥2-Lipschitz in g under the stated assumption (27).The proof identifies tg·w as a projection onto a convex cone and uses nonexpansiveness of projection.Source: Appendix D · p. 26
  • The appendix invokes a concentration bound for 1-Lipschitz functions and a separate estimate for the fluctuation of ∥h∥2 around √n.The supplied passages name Ledoux's bound and state the Gaussian norm estimate, though the latter's right-hand side is incomplete.Source: Appendix D · pp. 26, 28
  • The Gaussian comparison lemma applies to the measurement matrix setting and relates the minimum over Ω to a second Gaussian functional.The proof constructs centered Gaussian processes and invokes Gordon's theorem for their comparison.Source: Appendix D · pp. 26–27
  • The proof of Lemma 8 begins by equating the expected distances of g and −g to A and bounding them by r.The supplied fragment does not state the lemma's full conclusion.Source: Appendix D · p. 28

Related papers

Loading 1305.2524v2…