PaperlayerView exact revision on arXiv

Source-linked AI summary

Robust Sparse Analysis Regularization

Samuel Vaiter, Gabriel Peyré, Charles Dossal, Jalal Fadili

arXiv:1109.6222v5cs.ITmath.IT

TL;DR

Regularized recovery addresses ill-posed inverse problems, while sparse ℓ0 minimization is computationally difficult. This paper establishes sufficient conditions for recovery and robustness with ℓ1-analysis regularization, including guarantees for small noise and for bounded noise with a sufficiently large regularization parameter.

Abstract

from arXiv · show

This paper investigates the theoretical guarantees of L1-analysis regularization when solving linear inverse problems. Most of previous works in the literature have mainly focused on the sparse synthesis prior where the sparsity is measured as the L1 norm of the coefficients that synthesize the signal from a given dictionary. In contrast, the more general analysis regularization minimizes the L1 norm of the correlations between the signal and the atoms in the dictionary, where these correlations define the analysis support. The corresponding variational problem encompasses several well-known regularizations such as the discrete total variation and the Fused Lasso. Our main contributions consist in deriving sufficient conditions that guarantee exact or partial analysis support recovery of the true signal in presence of noise. More precisely, we give a sufficient condition to ensure that a signal is the unique solution of the L1-analysis regularization in the noiseless case. The same condition also guarantees exact analysis support recovery and L2-robustness of the L1-analysis minimizer vis-a-vis an enough small noise in the measurements. This condition turns to be sharp for the robustness of the analysis support. To show partial support recovery and L2-robustness to an arbitrary bounded noise, we introduce a stronger sufficient condition. When specialized to the L1-synthesis regularization, our results recover some corresponding recovery and robustness guarantees previously known in the literature. From this perspective, our work is a generalization of these results. We finally illustrate these theoretical findings on several examples to study the robustness of the 1-D total variation and Fused Lasso regularizations.

I. INTRODUCTION

Linear inverse problems can be ill-posed, so regularization uses prior information to make recovery feasible. The section contrasts synthesis sparsity with analysis sparsity and introduces analysis priors including total variation and Fused Lasso.

A. Inverse Problems and Signal Priors

  • Ill-posed inverse problems motivate regularization, which uses prior information to make the search for solutions feasible.The forward mapping may be ill-conditioned or singular, and the regularization term enforces regularity according to the prior.Source: A. Inverse Problems and Signal Priors · p. 1

C. Synthesis and Analysis Sparsity Priors

  • Because ℓ0-based sparse minimization is NP-hard, the paper focuses on convex relaxation, replacing the ℓ0 pseudo-norm with ℓ1.Source: C. Synthesis and Analysis Sparsity… · p. 2
  • Synthesis sparsity measures the coefficients that construct a signal, whereas analysis sparsity measures its correlations with dictionary atoms; the priors differ for redundant dictionaries.Analysis regularization includes total variation, which favors piecewise-constant signals, and Fused Lasso, which promotes sparsity in both the signal and its derivative.Source: C. Synthesis and Analysis Sparsity… · pp. 2–3

D. Union of Subspaces Model

The D-support and its complement define a signal’s analysis cospace, yielding a union-of-subspaces model. The paper uses this framework to state recovery conditions for small noise, noiseless data, and arbitrary bounded noise.

D. Union of Subspaces Model

  • The D-support is supp(D∗x), its complement is the D-cosupport, and signals with a given cosupport lie in the corresponding cospace GJ.Cosupports partition signals into a union of subspaces; for 1-D total variation, the dimension-k subspaces are piecewise-constant signals with k−1 steps.Source: D. Union of Subspaces Model · p. 3

E. Organization of this Paper

  • The paper presents its main contributions in Section II, reviews related work in Section III, gives examples in Section IV, and defers proofs to Section V.Source: E. Organization of this Paper · p. 3

II. CONTRIBUTIONS

  • The paper establishes conditions for noiseless uniqueness, exact support recovery with sufficiently small noise, and partial support recovery with arbitrary bounded noise when λ is large enough.The small-noise condition also yields ℓ2-robustness and is described as sharp for support recovery.Source: §II · p. 3, A. Robustness to Small Noise · p. 4
  • The authors describe the work as the first, to their knowledge, to address all three recovery questions for analysis regularization, while extending previously known synthesis results.Source: §II · p. 3
  • Assumption (HJ) requires Φ to be invertible on GJ; without it, distinct signals in GJ can produce the same measurements, preventing unique reconstruction.When x0 and its cosupport J are known, x0 lies in GJ and matches the measurements; any h in Ker Φ ∩ GJ gives another candidate x0+h.Source: §II · p. 3

A. Robustness to Small Noise

  • The small-noise condition depends on the analysis sign and cosupport; when IC(sign(D∗x0)) < 1, the support and sign are recovered if nonzero analysis coefficients are large enough relative to noise.If IC(sign(D∗x0)) > 1, support and sign cannot be identified even with small noise.Source: A. Robustness to Small Noise · p. 4

B. Noiseless Identifiability

For noiseless measurements, the analysis identifiability criterion gives a sufficient condition for unique recovery. A stronger cosupport-based criterion extends the guarantee to partial support recovery and ℓ2 robustness under arbitrary bounded noise.

B. Noiseless Identifiability

  • If (HJ) holds and IC(sign(D∗x0)) < 1, then x0 is the unique solution of the noiseless analysis problem.Source: B. Noiseless Identifiability · p. 4
  • Under (HJ) and IC(sign(D∗x0)) > 1, Corollary 1 quantifies over every λ > 0 and any solution x⋆ of (Pλ(Φx0)), but the cited excerpt does not state its conclusion.At equality, Proposition 1 and Corollary 1 do not allow a conclusion; recovery can be possible or not depending on the noise structure.Source: B. Noiseless Identifiability · p. 4

C. Robustness to Bounded Noise

A. Previous Works on Synthesis Identifiability and Robustness

  • In the synthesis case, the paper’s criteria reduce to the established synthesis criteria: IC to ICS and RC to ERC.Prior synthesis results state that ERC(I) < 1 gives partial support recovery and ℓ2 consistency for sufficiently large λ.Source: A. Previous Works on Synthesis… · p. 5

B. Previous Works on Analysis Identifiability and Robustness

Earlier analysis results did not establish ℓ2-robustness for general D, and IC0 alone does not ensure noisy support stability. The section also describes algorithms for computing the criteria and studies their use in several regularizations.

B. Previous Works on Analysis Identifiability and Robustness

  • Earlier inverse-problem results established no ℓ2-robustness for general D, and did not guarantee sign or D-support recovery under noise.The cited work also discusses identifiability and convergence guarantees under additional conditions.Source: B. Previous Works on Analysis… · pp. 5–6

IV. EXAMPLES

  • The examples study total variation, shift-invariant Haar analysis, and the Fused Lasso alongside algorithms for computing IC and RC.The source code used for the numerical results is identified as available online.Source: §IV · p. 6

A. Computing Sparse Analysis Regularization

  • For denoising, the problem is strongly convex and can be solved through an equivalent Fenchel-Rockafellar dual; the general case uses a primal-dual algorithm.The described proximal computation combines soft-thresholding with diagonal Wiener filtering.Source: A. Computing Sparse Analysis… · p. 6

B. Computing the Criteria

  • When Ker DJ = {0}, computing IC reduces to convex minimization, while RC is difficult and a stronger, easier-to-compute criterion is obtained by setting u = 0.The stronger criterion can be below 1 when the cospace is close to the whole space, corresponding to high D-cosparsity.Source: B. Computing the Criteria · p. 7

C. Total Variation Denoising

For TV denoising, the IC criterion is below 1 without a staircase subsignal and equals 1 when one is present. This condition distinguishes the paper's small-noise robustness guarantee from a constructed case where stability depends on the noise structure.

C. Total Variation Denoising

  • Without a staircase subsignal, IC(sign(D*x0)) < 1; with one, IC(sign(D*x0)) = 1.For Φ = Id, the proposition characterizes the criterion through whether a staircase subsignal is present.Source: C. Total Variation Denoising · p. 7
  • Between consecutive jump locations, the associated dual vector linearly interpolates the values at those locations.The proposition links this behavior to the criterion used to assess TV robustness.Source: C. Total Variation Denoising · p. 7, Figure 1 · p. 7
  • TV denoising preserves x0's jumps under sufficiently small noise when x0 has no staircase subsignal; with a staircase, these results yield no robustness conclusion.The small-noise guarantee uses λ proportional to the noise level.Source: C. Total Variation Denoising · p. 7
  • In the constructed staircase example, the D-support matches x0 for ε < 0 over a λ interval, but differs for the other noise sign regardless of λ.The signals use noise w = ε(1_l3 − 1_l2); Figure 2 shows the signals and coordinate paths.Source: C. Total Variation Denoising · p. 8, Figure 2 · p. 8

D. Shift-Invariant Haar Deconvolution

The shift-invariant Haar analysis penalty provides a multiscale total-variation construction, studied alongside total variation and the Fused Lasso through identifiability-criterion experiments. The proof section begins by fixing notation and assuming (H0).

D. Shift-Invariant Haar Deconvolution

  • The Haar analysis penalty sums total-variation seminorms across filtered signal scales, reducing to total variation up to a factor when Jmax = 0.The dictionary uses scaled and dilated Haar filters; τ = 1 is unit-normed, while τ = 1/2 gives a Parseval tight-frame.Source: D. Shift-Invariant Haar Deconvolution · p. 8
  • The noiseless deconvolution experiment varies Gaussian-blur width σ and compares total variation with two Haar normalizations at fixed η = 0.2.The plotted IC curves use Jmax = 4; the unit-normed Haar curve appears to have smaller IC, but stronger conclusions require computing Theorem 1 constants.Source: D. Shift-Invariant Haar Deconvolution · p. 8, Figure 3 · p. 8

E. Fused Lasso Compressed Sensing

  • With Gaussian measurements, the empirical probability of IC < 1 rises as sampling ratio Q/N increases across 1000 Monte Carlo trials.The apparent increase as support size η decreases may depend on the Fused Lasso parameter ε and may differ for other choices.Source: E. Fused Lasso Compressed Sensing · p. 9, Figure 4 · p. 9
  • As ε decreases, the IC < 1 probability profile becomes nonmonotonic in η, peaking at intermediate support sizes before vanishing quickly.For large ε, the probability decreases monotonically as η increases; the peak probability also decreases as ε decreases.Source: E. Fused Lasso Compressed Sensing · p. 9, Figure 5 · p. 9

V. PROOFS

  • The proofs section introduces shorthand Ly,λ for the objective and assumes condition (H0) throughout its statements.The section says it develops proofs of Theorems 1–3.Source: §V · p. 9

A. Preparatory lemmata

These preparatory lemmata characterize minimizers through first-order conditions and derive uniqueness criteria and an implicit equation for candidate solutions. Strict dual-certificate bounds, together with the stated subspace condition, are central to the uniqueness results.

A. Preparatory lemmata

  • A minimizer satisfies a first-order condition with a certificate matching the analysis signs on its D-support and bounded by one on its D-cosupport.The certificate restricted to the D-cosupport is denoted σ.Source: A. Preparatory lemmata · pp. 9–10
  • A certificate with ||σJ||∞ < 1 constrains the normal cone at zero to lie in the orthogonal complement of Im(DJ).Lemma 2 states the containment N∂Ly,λ(x⋆)(0) ⊆ (Im DJ)⊥ = GJ.Source: A. Preparatory lemmata · pp. 10–11
  • A candidate is the unique minimizer when (HJ) holds and a subgradient certificate has norm strictly below one on the specified subset of its D-cosupport.Lemma 3 gives this sufficient condition for (Pλ(y)).Source: A. Preparatory lemmata · p. 11
  • Under (HJ), Lemma 4 gives an implicit equation satisfied by any minimizer, using its D-support and analysis-sign vector.The passage specifies that the D-support is I = Jc and s = sign(D*x⋆).Source: A. Preparatory lemmata · pp. 10–11
  • Under Lemma 5’s stated setup, xhat* solves (Pλ(y)) if and only if there exists σ satisfying one of the equivalent conditions; if ||σ||∞ < 1, xhat* is unique.Source: A. Preparatory lemmata · p. 11

B. Proof of Theorem 1

The proof constructs a candidate with the true analysis signs, then establishes conditions for sign consistency and minimality. Under the identifiability criterion and the stated conditions, it obtains a unique minimizer.

B. Proof of Theorem 1

  • The proof first constructs a candidate in the subspace GJ using the true analysis-sign vector s = sign(D*x0).It then develops conditions for sign consistency and for satisfying minimality conditions.Source: B. Proof of Theorem 1 · p. 12
  • The proof checks that its sign-consistency and minimality conditions are compatible using constants cJ and ˜cJ.The excerpt identifies these constants but does not give their definitions or bounds.Source: B. Proof of Theorem 1 · p. 12
  • Given IC(sign(D*x0)) < 1 and the required bound, the constructed certificate has ||σ||∞ < 1, yielding a unique solution by Lemma 5.The passage refers to the bound as a required condition without specifying its expression in this excerpt.Source: B. Proof of Theorem 1 · p. 12

C. Proof of Proposition 1

The proof of Proposition 1 invokes Lemmata 4 and 5 to connect a minimizer with matching analysis signs to the certificate characterization.

C. Proof of Proposition 1

  • Proposition 1 is presented as a consequence of Lemmata 4 and 5.The proof applies their characterizations to a solution whose analysis signs match those of x0.Source: C. Proof of Proposition 1 · p. 12
  • When a solution has the same analysis signs as x0, its D-cosupport is J.The proof then invokes the two lemmata to obtain a certificate.Source: C. Proof of Proposition 1 · p. 12
  • The proof uses a certificate with ||σ||∞ ≤ 1 in the characterization supplied by the lemmata.The excerpt indicates that this step leads to a contradiction.Source: C. Proof of Proposition 1 · p. 12

D. Proof of Theorem 2

Under (HJ) and IC(sign(D∗x0)) < 1, the proof establishes that x0 is the unique solution of (P0(y)). It first shows x0 is a solution, then rules out any other feasible solution.

D. Proof of Theorem 2

  • For sufficiently small λ, the stated corollary gives a unique solution of (Pλ(y)) in the noiseless case.Its stated solution is x̂⋆ = x0 − λA[J]D_Is_I.Source: D. Proof of Theorem 2 · p. 13
  • Under (HJ) and IC(sign(D∗x0)) < 1, x0 is a solution of (P0(y)).The proof specializes Theorem 1 to w = 0 before establishing uniqueness.Source: D. Proof of Theorem 2 · p. 13
  • The proof rules out any distinct feasible point of (P0(y)) and concludes that x0 is its unique solution.It uses uniqueness of (Pλ(y1)) for small λ and takes a limit as λ → 0 in the comparison.Source: D. Proof of Theorem 2 · p. 13

E. Proof of Theorem 3

The proof constructs a solution to a restricted problem, verifies its optimality and uniqueness for the full problem, and derives an ℓ2-robustness bound. The paper's conclusions distinguish exact recovery under small noise from partial support recovery under arbitrary bounded noise.

E. Proof of Theorem 3

  • The proof constructs a solution to a restricted problem, checks first-order optimality and uniqueness for the full problem, then derives an ℓ2-distance bound.The strategy is divided into four steps, including an implicit equation and a change of variable x = Uα.Source: E. Proof of Theorem 3 · pp. 13–14
  • The paper states that a sufficient condition gives exact D-support and sign recovery for sufficiently small noise, and that this support condition is sharp in some sense.The same conditions also guarantee ℓ2-error robustness.Source: CONCLUSION · p. 14
  • A stronger sufficient condition gives partial support recovery and ℓ2-robustness for arbitrary bounded noise when λ is sufficiently large.For 1-D total variation, staircasing is reported to destabilize the D-support, so jumps are not preserved.Source: CONCLUSION · p. 14

APPENDIX PROOF OF PROPOSITION 3

The proof uses IC(s) < 1 to construct a subgradient certificate whose image under D lies in Im Φ∗.

APPENDIX PROOF OF PROPOSITION 3

Loading 1109.6222v5…