PaperlayerView exact revision on arXiv

Source-linked AI summary

Recovery of Sparsely Corrupted Signals

Christoph Studer, Patrick Kuppinger, Graeme Pope, Helmut Bölcskei

arXiv:1102.1621v4cs.IT

TL;DR

The paper asks how to recover sparse signals corrupted by noise that is sparse in another general dictionary. It develops an uncertainty-relation-based framework with deterministic guarantees and practical algorithms across different support-knowledge settings, showing that recovery depends on sparsity, coherence, and support information.

  • Problem

    Sparse recovery under structured corruption needs guarantees for signal and noise represented in two general dictionaries, including redundant or incomplete dictionaries.

  • Method

    The paper derives a novel uncertainty relation for general dictionaries and uses it to construct coherence-based recovery guarantees and practical algorithms.

  • Results

    The guarantees cover four levels of support knowledge and permit perfect recovery independently of the corruption’s ℓ2-norm under the stated structured-noise conditions.

  • Takeaways & Limitations

    Recovery performance is governed jointly by signal and corruption sparsity, dictionary coherences, and how much support information is available.

Abstract

from arXiv · show

We investigate the recovery of signals exhibiting a sparse representation in a general (i.e., possibly redundant or incomplete) dictionary that are corrupted by additive noise admitting a sparse representation in another general dictionary. This setup covers a wide range of applications, such as image inpainting, super-resolution, signal separation, and recovery of signals that are impaired by, e.g., clipping, impulse noise, or narrowband interference. We present deterministic recovery guarantees based on a novel uncertainty relation for pairs of general dictionaries and we provide corresponding practicable recovery algorithms. The recovery guarantees we find depend on the signal and noise sparsity levels, on the coherence parameters of the involved dictionaries, and on the amount of prior knowledge about the signal and noise support sets.

I. INTRODUCTION

The paper studies recovery of sparse signals corrupted by noise that is sparse in a second general dictionary, covering applications from clipping and impulse noise to inpainting and signal separation. It develops recovery guarantees and practical algorithms for varying levels of support knowledge.

  • Problem setup: The model represents measurements as z = Ax + Be, with sparse signal coefficients x and sparse corruption coefficients e in possibly redundant or incomplete dictionaries.The corruption support and values may be arbitrary and can depend on x or A.
  • Applications: Clipping, impulse noise, narrowband interference, inpainting, super-resolution, and signal separation fit within the sparse-corruption framework.Examples use identity or Fourier dictionaries for particular corruption types, while signal separation jointly extracts sparse components.
  • Contributions: The paper establishes deterministic guarantees based on signal and noise sparsity, dictionary coherence, and available support information.The considered cases range from knowing both supports to knowing neither support.

II. REVIEW OF RELEVANT PREVIOUS RESULTS

Prior work covers sparse recovery with noiseless or unstructured noise and some special structured-noise settings, but does not systematically address deterministic recovery with two general dictionaries and support information. The paper motivates a general uncertainty-relation approach to this gap.

  • Noiseless recovery: Noiseless sparse recovery uses ℓ0 minimization, with basis pursuit and OMP providing tractable alternatives under coherence-based conditions.OMP greedily selects dictionary columns correlated with the current residual.
  • Unstructured noise: For unstructured noise, BPDN provides an error bound proportional to the noise ℓ2-norm, while perfect recovery is generally impossible.The relevant sufficient conditions also depend on the smallest nonzero signal magnitude.
  • Structured noise: A direct concatenated-dictionary formulation gives sufficient recovery conditions but ignores separate dictionary coherences and prior support knowledge.The paper argues that exploiting these structural aspects yields less restrictive thresholds.
  • Prior structured-noise results: Existing structured-noise guarantees include special cases such as Fourier-plus-identity dictionaries, ONB corruption models, and probabilistic settings.Results for two general deterministic dictionaries with support information were identified as missing from the literature.
  • Motivation: The paper is inspired by an uncertainty relation for Fourier and identity bases and extends the direction to general dictionaries.This relation forms the basis for the paper’s structured-noise recovery guarantees.

III. A GENERAL UNCERTAINTY RELATION FOR ϵ-CONCENTRATED VECTORS

The paper introduces an uncertainty relation for vectors that are approximately concentrated on selected supports in two general dictionaries. It extends prior perfectly sparse relations and identifies both equality examples and the computational difficulty of finding them.

  • General relation: The new uncertainty relation applies to ϵ-concentrated coefficient vectors represented by the same signal in two general dictionaries.It depends on the dictionaries’ individual and mutual coherence parameters and the selected support sizes.
  • Definitions: ϵ-concentration requires most ℓ1 mass to lie on a specified set, with perfect concentration corresponding to exact sparsity.The definition uses ∥P_Rr∥1 ≥ (1−ϵ_R)∥r∥1.
  • Connections: For perfectly concentrated vectors, the relation reduces to a previously reported uncertainty relation and generalizes results for orthonormal bases and square dictionaries.The extension covers pairs that may be redundant or incomplete.
  • Equality case: A Fourier-plus-identity comb signal provides a special case attaining the uncertainty relation with equality.Its coefficient supports have equal size and are perfectly concentrated when the relevant divisibility condition holds.
  • Computational complexity: Finding equality-achieving representations for arbitrary general dictionaries is NP-hard.The paper reduces the search to an ℓ0 minimization problem equivalent to a known NP-hard problem.

IV. RECOVERY OF SPARSELY CORRUPTED SIGNALS

Using the uncertainty relation, the paper derives coherence-based recovery conditions for sparse signals and sparse corruptions under four levels of support knowledge. Known supports enable direct or projected recovery, while the conditions depend on sparsity and dictionary coherence rather than corruption energy.

  • Recovery cases: Recovery guarantees cover known supports for both x and e, one known support, known sparsity cardinality, and no support information.The guarantees target perfect recovery of x and, when appropriate, e.
  • Recovery conditions: The conditions depend on nx, ne, and the coherences µa, µb, and µm, rather than on the ℓ2-norm of Be.Thus the structured corruption may have arbitrarily large measurement energy.
  • Applications: The framework applies to clipped band-limited signals, inpainting, super-resolution, and spectrally sparse signals with impulse noise.Support information may come from clipping thresholds or known missing-entry locations.
  • Case I: Both supports known: When both support sets are known and nxne < f(nx, ne), the concatenated dictionary [AX BE] has full column rank.This guarantees existence of a pseudo-inverse for recovering the stacked active coefficients.
  • Special case and tightness: For Fourier-plus-identity dictionaries, the known-support condition reduces to nxne < M, and equality can produce indistinguishable signal and corruption decompositions.This establishes tightness in that special case.

B. Case II: Only X or only E is known

When one support set is known, projecting measurements away from the corresponding dictionary subspace reduces sparse corruption recovery to a normalized sparse-signal problem. Under coherence-based sparsity conditions, ℓ0 minimization, basis pursuit, and OMP recover the unknown signal or corruption, with extensions to general dictionaries.

  • Recovery when E is known and X is unknown: When E is known, condition 2n_xn_e < f(2n_x, n_e) guarantees recovery of x by (P0, E) and (BP, E).The guarantee applies to z = Ax + Be with E = supp(e) known.
  • Recovery when E is known and X is unknown: Projecting z onto the orthogonal complement of R(B_E) removes the sparse noise component and yields a modified sparse recovery problem for x.The projected dictionary is normalized using a diagonal scaling matrix before recovery.
  • Recovery when E is known and X is unknown: Condition (18) ensures nonzero projected columns and excludes sufficiently sparse vectors from ker(R_EA), enabling perfect recovery of x.It also guarantees linear independence of the active columns of B_E and existence of the pseudoinverse.
  • Recovery when E is known and X is unknown: Theorem 5 guarantees that (P0), BP, and OMP recover the unique solution after projection and normalization.The result extends earlier Fourier-plus-identity guarantees to pairs of general dictionaries and adds an OMP guarantee.
  • Recovery when X is known and E is unknown: When X is known, projecting onto the orthogonal complement of R(A_X) produces a standard sparse recovery problem for e.The transformed problem uses R_XB and diagonal normalization, with the roles of signal and corruption interchanged.
  • Recovery when X is known and E is unknown: When 2n_xn_e < f(n_x, 2n_e), (P0), BP, and OMP recover the unique corruption solution from the projected measurements.The condition also ensures that the columns of A_X are linearly independent, so the signal coefficients can subsequently be obtained.

C. Case III: Cardinality of E or X known

Case III considers recovery when neither support set is known but one sparsity cardinality is available, establishing a threshold for known noise sparsity and unknown signal sparsity.

  • Setup: Knowing the noise sparsity ne enables recovery of x when its support is unknown, while the case of known nx and unknown ne is analogous.The motivating example is a sparse pulse stream corrupted by electric hum with an unknown base frequency but known harmonic count.
  • Recovery guarantee: 4nxne < f(2nx, 2ne) is the sufficient condition for the unique solution of (P0, ne) to recover x.The theorem assumes z = Ax + Be and ne = ||e||0 is known.
  • Computational limitations: The (P0, ne) problem is generally combinatorial, and replacing its ℓ0 objective with ℓ1 does not make the formulation computationally tractable.The feasible constraint remains non-convex in general.
  • Algorithms: Greedy algorithms can incorporate prior knowledge of individual sparsity levels, but analytical guarantees for the modified algorithms are not available.The paper names OMP, CoSaMP, and subspace pursuit as examples.
  • Tightness: The threshold (24) is tight for A = F_M and B = I_M, with indistinguishable admissible pairs sharing the same measurement outcome at equality.The construction gives x and x′ with equal sparsity and identical observations.

D. Case IV: No knowledge about the support sets

Case IV addresses recovery when neither signal nor noise support is known, using joint sparse recovery in the concatenated dictionary and coherence-based guarantees for both exact and practical algorithms.

  • Setup: With no support-set knowledge, the model can represent audio restoration with unknown impulse locations and signal separation into distinct features.The signal and corruption are jointly represented through z = Ax + Be.
  • Recovery guarantee: Theorem 8 gives a sufficient coherence-based condition for w = [x^T e^T]^T to be the unique solution of (P0) over D = [A B].The condition uses the within-dictionary coherences µa and µb and the cross-dictionary coherence µd.
  • Algorithms: BP and OMP also recover the unique (P0) solution under a sufficient threshold that is only slightly more restrictive than the corresponding condition for (P0).Once w is recovered, x and e can be extracted directly.
  • Support knowledge: Without support-set knowledge, the recovery threshold is reduced by a factor of two compared with thresholds where X or E is known.This comparison covers thresholds (15), (18), (22), and (24), including the case where one sparsity cardinality is known.
  • Numerical illustration: For µa = µb = 0 and µm = 1/64, the thresholds are nxne < 64 with both supports known, < 32 with one support known, and < 16 when only ne is known.The no-support-knowledge case is more restrictive still.
  • Numerical illustration: For positive coherences µa = 0.1258, µb = 0.1319, and µm = 0.1321, all threshold curves are straight lines because the numerators depend on both nx and ne.The paper illustrates this behavior in Fig. 2.

B. The square-root bottleneck

The paper identifies a square-root bottleneck in coherence-based guarantees: in the noiseless case, guaranteed sparsity scales only with the square root of the measurement dimension, while probabilistic analyses can overcome this limitation.

  • Limitation: Coherence-based guarantees are fundamentally limited by the square-root bottleneck, unlike RIC-based guarantees.This limitation applies to the deterministic coherence framework discussed here.
  • Limitation: For fixed signal sparsity nx, coherence-based recovery requires a measurement count M on the order of nx^2.The noiseless threshold guarantees recovery only up to a square-root-scale number of nonzero entries.
  • Scope: Probabilistic analysis can break the square-root bottleneck, but that line of work is outside this paper’s scope.The paper points to related work for such analyses.
  • Trade-off between nx and ne: When ne = α√M and only E is known, the allowed signal sparsity scales as (1 − α)√M/2, up to lower-order terms.This demonstrates a trade-off between signal and error sparsity levels.
  • Empirical behavior: In the illustrated recovery simulations, analytical thresholds are generally pessimistic but correctly reflect observed recovery behavior, including the factor-of-two penalty.The experiments also include an inpainting example.

A. Impact of support-set knowledge on recovery thresholds

Support-set knowledge changes recovery thresholds, while dictionary coherence and algorithm choice also shape performance. Simulations show these effects across Hadamard–identity, approximate-ETF, DCT, and Haar-wavelet settings.

  • Support-set knowledge: Known signal and error supports use Case I recovery, partial support knowledge uses modified BP and OMP, and no support knowledge uses concatenated-dictionary BP and OMP.Case III is omitted because only uniqueness results, not analytical guarantees, are available when only the error-support cardinality is known.
  • Simulation design: The 50% success-rate contours are plotted for Hadamard–identity and approximate-ETF dictionary pairs under different support-knowledge assumptions.The approximate-ETF experiment uses dimension 64 × 80 dictionaries with µa ≈ 0.1258, µb ≈ 0.1319, and µm ≈ 0.1321.
  • Hadamard–identity pair: For the Hadamard–identity pair, full support knowledge reaches a 50% success contour near nx + ne ≈ M, outperforming the sufficient condition nxne < M.With either only X or only E known, performance is essentially independent of which support is known, and OMP outperforms BP.
  • Hadamard–identity pair: At nx = ne, OMP reaches 50% success near 31 with both supports known and near 23 with one support known, reflecting a factor-of-two penalty.The reported relation is 31·31 ≈ 23·23·2; BP does not visibly reflect this penalty in Fig. 3.
  • Simulation interpretation: Recovery succeeds at substantially higher sparsity levels numerically than the analytical thresholds, because the guarantees are deterministic and require perfect recovery in every case.The simulations instead plot 50% success-rate contours, explaining the difference between empirical and guaranteed thresholds.
  • Inpainting example: The signal dictionary should be designed for incoherence with the structured-noise dictionary, not sparsity alone, which can require different transform-basis criteria.For the example, µm = 1/2 for Haar–identity and µm ≈ 0.004 for DCT–identity; coherence-based thresholds explain the performance difference.
  • Inpainting example: In the image example, decreasing support knowledge increases MSE, and DCT outperforms Haar wavelets despite Haar’s often smaller classical transform-coding approximation error.The comparison uses DCT or three-octave Haar representations with identity-basis structured noise.
  • Limitations and open problems: Coherence-based guarantees for greedy algorithms such as CoSaMP and subspace pursuit across all studied cases remain an open problem.The paper identifies this as an extension of its general setup.

APPENDIX A PROOF OF THEOREM 3

The proof establishes uniqueness under support constraints by applying the uncertainty relation to differences between competing signal–noise decompositions. It then extends the argument to BP by controlling the competing signal’s ℓ1 norm.

  • APPENDIX A PROOF OF THEOREM 3: An alternative pair produces difference vectors supported within X and E, with sparsities at most nx and ne, respectively.Applying the uncertainty relation yields inequalities contradicting condition (15), proving uniqueness under known supports.
  • APPENDIX A PROOF OF THEOREM 3: With only E known, competing signal vectors can differ on at most 2nx entries, while the error difference remains supported within E and has sparsity at most ne.The uncertainty relation then contradicts condition (18), proving uniqueness of the P0 solution.
  • APPENDIX A PROOF OF THEOREM 3: For BP, an alternative signal with no larger ℓ1 norm requires the difference vector to be at least 50%-concentrated on X.Combining this concentration property with the uncertainty relation contradicts condition (18), establishing uniqueness of the BP solution.

APPENDIX C PROOF OF THEOREM 5

The proof of Theorem 5 shows that condition (18) makes the projected recovery problem well-defined and guarantees recovery after removing the known error-support subspace.

  • APPENDIX C PROOF OF THEOREM 5: Condition (18) first ensures that the columns of BE are linearly independent, then establishes nonzero projected columns and recovery of x by P0, BP, and OMP.The projected observation is ẑ = REA∆ẋ, with recovery result ẋ = ∆^-1x.
  • APPENDIX C PROOF OF THEOREM 5: Condition (18) implies ne < 1 + 1/µb, which guarantees linear independence of the ne columns of BE.The argument uses the coherence-based bound on the minimum number of linearly dependent dictionary columns.
  • APPENDIX C PROOF OF THEOREM 5: The proof verifies that every projected dictionary column satisfies ∥REaℓ∥2 > 0 by bounding its norm using projector properties and coherence estimates.Rayleigh–Ritz and Geršgorin’s disc theorem provide intermediate bounds leading to the required lower bound.
  • APPENDIX C PROOF OF THEOREM 5: A sparse vector with at most 2nx nonzeros in A has a nonzero component orthogonal to R(BE), ensuring the projected dictionary retains recoverable signal information.This property follows under condition (18) after establishing positivity of the relevant coherence-dependent bound.

C. Unique recovery through (P0), BP, and OMP

The proof bounds the coherence of a modified dictionary and inserts that bound into a standard sparsity threshold. Under condition (18), (P0), BP, and OMP recover the signal exactly.

  • C. Unique recovery through (P0), BP, and OMP: The proof reduces recovery to bounding the coherence of the modified dictionary REA∆.This bound is combined with a coherence-based recovery guarantee for the transformed observation.
  • C. Unique recovery through (P0), BP, and OMP: The sparsity threshold in (4) makes ˆx the unique solution of (P0), while condition (43) also permits recovery through BP and OMP.The proof preserves the sparsity level because ∥ˆx∥0 = ∥x∥0 = nx.
  • C. Unique recovery through (P0), BP, and OMP: The resulting threshold guarantees recovery of ˆx from ˆz = REA∆ˆx through (P0), BP, and OMP.The threshold is obtained by inserting the coherence bound into the recovery condition.
  • C. Unique recovery through (P0), BP, and OMP: Condition (18) therefore guarantees recovery of ˆx and, consequently, x = ∆ˆx through all three recovery procedures.The argument explicitly identifies the recovered transformed vector with the original signal via x = ∆ˆx.

APPENDIX D PROOF OF THEOREM 7

The proof establishes uniqueness by assuming an alternative sparse representation and applying the uncertainty relation to the resulting difference vectors. The resulting contradiction rules out any alternative satisfying the sparsity bounds.

  • APPENDIX D PROOF OF THEOREM 7: Assuming an alternative x′ with ∥x′∥0 ≤ nx yields a corresponding e′ with ∥e′∥0 ≤ ne.Both alternatives represent the same observation within the specified sparse-support structure.
  • APPENDIX D PROOF OF THEOREM 7: The difference vectors satisfy ∥x − x′∥0 ≤ 2nx and ∥e′ − e∥0 ≤ 2ne.Their supports are defined as P = supp(x − x′) and Q = supp(e′ − e).
  • APPENDIX D PROOF OF THEOREM 7: Applying the uncertainty relation to these difference vectors contradicts condition (24), proving uniqueness.The contradiction uses their exact concentration on P and Q together with |P| ≤ 2nx and |Q| ≤ 2ne.
Loading 1102.1621v4…