The Cosparse Analysis Model and Algorithms

Sangnam Nam; Mike E. Davies; Michael Elad; Rémi Gribonval

Source-linked AI summary

The Cosparse Analysis Model and Algorithms

Sangnam Nam, Mike E. Davies, Michael Elad, Rémi Gribonval

arXiv:1106.4987v1Jun 24, 2011math.NAcs.IT

TL;DR

The paper addresses the shallow theoretical understanding of an analysis counterpart to the mature sparse synthesis model. It defines the cosparse analysis model, contrasts it with synthesis, and develops pursuit methods and theoretical recovery conditions. Experiments support its effectiveness, while substantial questions remain about measurement stability, noise, operator learning, and sharper guarantees.

Problem
The analysis model had received far less study than synthesis, leaving its generative formulation and theoretical understanding shallow despite empirical applications.
Method
The paper formalizes the cosparse analysis model, relates it to unions of subspaces, derives uniqueness and analysis ℓ1-minimization conditions, and proposes pursuit algorithms.
Results
Experiments demonstrate the effectiveness of the analysis model and proposed pursuit algorithms across synthetic tests and compressed sensing of the Shepp–Logan phantom.
Takeaways & Limitations
The cosparse analysis model is presented as a distinct, well-defined, and practically viable counterpart to the sparse synthesis model.
Takeaways & Limitations
Open work remains on measurement stability, noise effects, learning analysis operators, and concrete or optimal algorithmic success guarantees.

Abstract

from arXiv · show

After a decade of extensive study of the sparse representation synthesis model, we can safely say that this is a mature and stable field, with clear theoretical foundations, and appealing applications. Alongside this approach, there is an analysis counterpart model, which, despite its similarity to the synthesis alternative, is markedly different. Surprisingly, the analysis model did not get a similar attention, and its understanding today is shallow and partial. In this paper we take a closer look at the analysis approach, better define it as a generative model for signals, and contrast it with the synthesis one. This work proposes effective pursuit methods that aim to solve inverse problems regularized with the analysis-model prior, accompanied by a preliminary theoretical study of their performance. We demonstrate the effectiveness of the analysis model in several experiments.

1. Introduction

The paper develops the underexplored cosparse analysis model as a generative alternative to the mature sparse synthesis model. It contrasts their representations, proposes recovery algorithms and theoretical conditions, and evaluates the analysis approach experimentally.

Data models encode assumed mathematical properties that can stabilize inverse problems and support tasks including compression, detection, separation, and sampling.The paper frames careful model selection as central to effective signal treatment and successful applications.
The synthesis model represents signals as x = Dz, with a sparse coefficient vector z formed from few columns of a possibly redundant dictionary D.Its study has covered algorithms, performance guarantees, dictionary learning, and many signal- and image-processing applications.
The analysis counterpart assumes that Ωx is sparse, so signals are characterized by many zeros in their analysis representation rather than few nonzeros in z.Examples of analysis operators include shift-invariant wavelets, finite differences, and curvelets.
Unlike the extensively studied synthesis model, the analysis model had limited theoretical justification despite empirical use in denoising, deblurring, and compressed sensing.For square invertible dictionaries the models coincide, but their relationship for more general dictionaries remained unexplored.
The paper defines cosparsity more fully, compares analysis and synthesis through unions of subspaces, and develops uniqueness conditions and pursuit methods for analysis-model inverse problems.Its contributions include analysis ℓ1-minimization, a greedy analysis pursuit variant, and a preliminary theoretical study of recovery conditions.
Experiments demonstrate the effectiveness of the analysis model and proposed pursuit algorithms, including synthetic tests and compressed sensing of the Shepp–Logan phantom.The authors position the resulting cosparse analysis model as a well-defined and practically viable counterpart to synthesis modeling.

2. A Closer Look at the Cosparse Analysis Model

The analysis model represents signals through zeros in an analysis vector, or cosparsity, and generates a union of subspaces that can differ substantially from the synthesis model. Its structure can provide highly parsimonious models, but the abundance of low-dimensional subspaces may complicate recovery and sampling.

Introducing Cosparsity: The analysis model assumes Ωx has few nonzeros, whereas cosparsity emphasizes the number of zeros in this representation.The analysis operator Ω ∈ R^p×d may be redundant, with p ≥ d.
Introducing Cosparsity: Cosupport entries are the zero locations of Ωx, and their associated rows define the analysis subspace.Removing rows corresponding to nonzero analysis coefficients leaves that subspace unchanged.
Union-of-Subspaces Models: Both models form unions of subspaces, but their subspace structures are typically very different.Synthesis emphasizes nonzero representation supports, while analysis emphasizes zero locations in Ωx.
Union-of-Subspaces Models: The large number of low-dimensional analysis subspaces enriches descriptive power but makes recovery, coding, and sampling difficult.For general-position operators, achieving cosparsity d ≤ ℓ < p is impossible for nonzero signals; dependent analysis rows can allow this range.

3. Uniqueness Properties

The paper develops uniqueness conditions for cosparse analysis signals in underdetermined linear inverse problems, first with known cosupport and then when only cosparsity is known. The conditions depend on analysis-subspace dimensions, mutual independence of the measurement and analysis operators, and the required number of measurements.

Known cosupport: With known cosupport Λ, recovery is unique when the associated analysis subspace WΛ intersects Null(M) only at zero.Under mutual independence of M and Ω, this is guaranteed when dim(WΛ) ≤ m.
Known cosupport: The quantity κΩ(ℓ) determines the necessary and sufficient cosparsity level for identifying every cosparse signal with known cosupport.This result assumes mutual independence between Ω and M.
Unknown cosupport: When the cosupport is unknown, uniqueness requires that sums of pairs of ℓ-cosparse subspaces intersect Null(M) only at zero.Proposition 2 states equivalent formulations using uniqueness of ℓ-cosparse solutions and invertibility on the union of subspaces.
Unknown cosupport: For unknown cosupport, m ≥ ˜κΩ(ℓ) guarantees uniqueness under mutual independence, where ˜κΩ(ℓ) maximizes dim(WΛ1 + WΛ2) over cosupports of size at least ℓ.This condition is presented as sharp for the number of measurements.
General position: For analysis operators in general position, m ≥ d − ℓ suffices with known cosupport, whereas m ≥ 2(d − ℓ) suffices when the cosupport is unknown.The underdetermined setting m < d requires ℓ ≥ 2d − m for the unknown-cosupport guarantee.
Finite difference operator: For finite-difference operators, the Shepp–Logan phantom requires between 2552 and 3048 measurements for the stated uniqueness guarantee.The range follows from an empirical estimate and a worst-case bound on κΩDIF(128014).

4. Pursuit algorithms

The paper introduces algorithms for recovering cosparse signals from underdetermined measurements, focusing on analysis ℓ1-minimization and the greedy GAP method. GAP iteratively identifies cosupport elements by removing analysis-operator rows associated with large estimated coefficients.

Pursuit algorithms: The underdetermined system Mx = y is regularized using the analysis prior ∥Ωx∥0.The goal is to recover a cosparse signal when infinitely many measurement-consistent solutions exist.
Analysis ℓ1-minimization: Analysis ℓ1-minimization replaces the difficult nonconvex problem with a tractable convex optimization that promotes high cosparsity.The paper presents this method as an established approach for analysis-model recovery.
Greedy Analysis Pursuit: GAP greedily detects the cosupport of a cosparse signal rather than directly selecting a sparse representation support.In the analysis model, the informative locations are the zeros of Ωx.
Greedy Analysis Pursuit: GAP initializes the cosupport as all analysis rows and progressively removes rows until reaching the target cosparsity or a sufficient size of d −m.This reverses the usual strategy of adding detected cosupport elements.
Greedy Analysis Pursuit: At each iteration, GAP removes rows corresponding to the largest absolute entries of the estimated analysis vector Ωx̂.The reduced operator is then used to compute a new signal estimate.
Algorithm controls: The selection factor t allows GAP to remove multiple rows per iteration, reducing the number of iterations.The algorithm also considers stopping when the solution stabilizes or its analysis coefficients become small.

5. Theoretical analysis

The paper develops recovery conditions for analysis ℓ1-minimization and GAP, paralleling synthesis exact-recovery theory while exposing structural differences. An analysis ERC guarantees both methods under stated rank and null-space conditions, but its violation does not necessarily imply algorithmic failure.

Recovery conditions: The paper seeks analysis-model analogues of the synthesis null space property and exact recovery condition.These conditions are intended to characterize when analysis ℓ1-minimization recovers cosparse signals.
Analysis ℓ1-minimization: Under the stated full-rank condition on ΩΛN_T, the analysis ERC guarantees recovery of every signal with fixed cosupport Λ by analysis ℓ1-minimization.The result is given through Corollary 8 and its associated conditions.
GAP guarantee: The analysis ERC also guarantees the success of GAP when its selection factor satisfies the theorem’s stated bound.The proof proceeds by showing that GAP removes a row outside the true cosupport at each iteration.
Comparison with synthesis: Analysis and synthesis recovery conditions have similar forms but depend on different matrix structures.The synthesis condition is governed by column relations in MD, whereas the analysis condition involves relations among rows and columns of ΩN_T.
Condition sharpness: Unlike violation of the synthesis condition for OMP, violation of the analysis ERC does not necessarily imply that GAP fails.Even an incorrect intermediate selection may be followed by later steps that yield an accurate estimate.
Relation to prior guarantees: The cited D-RIP-based guarantee provides limited information for finite-difference analysis operators and can fail to explain recovery of simple highly cosparse signals.The discussion also notes that the result is not sharp because it ignores sign patterns.

6. Experiments

The experiments evaluate analysis recovery algorithms on synthetic cosparse signals and the Shepp Logan phantom. GAP is viable, outperforming analysis ℓ1 especially for overcomplete operators, and achieving perfect phantom recovery from limited Fourier observations.

Performance of analysis algorithms: Synthetic experiments vary measurements, co-sparsity, and operator size using phase-transition parameters δ=m/d and ρ=(d−ℓ)/m.Each parameter triplet is tested 50 times, with relative error below 10^-6 counted as perfect recovery.
Performance of analysis algorithms: GAP can recover cosparse signals and performs better than ℓ1-minimization, especially for overcomplete analysis operators.
Analysis-based Compressed Sensing: For a 256 × 256 Shepp Logan phantom, GAP perfectly recovered the image from 12 radial lines and 3032 Fourier measurements.These measurements were approximately 4.63% of the 65536 image pixels.
Analysis-based Compressed Sensing: The 512 × 512 phantom was also recovered with GAP using 7112 measurements, approximately 2.71% of the image size.The experiment used 5104 non-zero analysis coefficients; the cited sufficient uniqueness condition required at least 6126 measurements.
Analysis-based Compressed Sensing: The large phantom experiment modifies GAP by computing pseudo-inverses numerically and eliminating many rows per iteration.This super-greedy modification addresses the computational cost of the larger problems.
Analysis-based Compressed Sensing: The radial-line comparison varies the number of observations to assess algorithms relative to theoretical uniqueness thresholds.The compared methods include GAP, TV-minimization from l1magic, and back-projection or AIHT-based results.

7. Conclusions and Further Work

The paper presents the cosparse analysis model as a distinct alternative to sparse synthesis and argues that it is viable for practical applications. It also identifies substantial open questions for further theoretical and algorithmic study.

Conclusions: The cosparse analysis model is distinct from sparse synthesis despite their apparent similarities.The paper argues that treating analysis representations simply as sparse synthesis representations is not meaningful.
Conclusions: The model and associated algorithms are presented as an interesting subject with viable practical applications.
Further Work: Future work includes studying measurement stability, noise effects, and the design or learning of analysis operators.

Appendix A. Proof of Theorem 7 and Corollary 8

Appendix A derives recovery conditions for analysis ℓ1-minimization. It uses convexity, null-space parameterization, and a full-rank restriction to obtain necessary, sufficient, and related conditions.

Theorem 7: For a fixed signal and cosupport, analysis ℓ1-minimization recovers the signal uniquely exactly when the stated condition holds.
Theorem 7: The proof connects the recovery condition to strict local minima and uses convexity to establish a unique global optimum.
Corollary 8: Writing z=NT α removes the constraint z∈Null(M) and expresses the recovery condition through a basis of the measurement null space.
Corollary 8: Because ΩΛNT is thin and full-rank, defining β=ΩΛNT α yields a sufficient, but no longer necessary, recovery condition.
Corollary 8: The final implication follows by bounding the sign term and showing that condition (25) implies condition (24).

Appendix B. Proof of Lemma 9

Appendix B proves the lemma by applying Lagrange multipliers to the constrained analysis problem and reducing the error to the measurement null space. The resulting relations characterize the candidate solution through the analysis operator and null-space basis.

Proof of Lemma 9: Applying Lagrange multipliers to y=Mx yields stationarity relations involving the analysis operator and a multiplier v.
Proof of Lemma 9: Eliminating v gives Ω^TΩx̂0=0, which is rewritten using a pseudoinverse of a basis matrix for Null(M).
Proof of Lemma 9: The error u=x̂0−x0 lies in Null(M) and can therefore be represented as u=NTw.

Appendix C. Proof of Proposition 6

The appendix proves bounds for Proposition 6 by reducing the extremal graph problem to connected subgraphs and analyzing nearly square configurations. These constructions yield explicit lower bounds for κΩDIF and support the measurement range for the Shepp Logan image.

Connected extremal subgraphs: The extremal value is attained by a subgraph with |Λ| = ℓ and J(Λ) = 1.The proof first fixes the edge count and shows disconnected components can be shifted together without worsening the objective.
Connected extremal subgraphs: For connected Λ, minimizing |V (Λ)| determines κΩDIF(ℓ), motivating nearly square or rectangular grid configurations.Euler’s formula links this minimization to maximizing the number of faces.
Nearly square constructions: Adding edges to an r × r square can add one vertex per edge initially, producing the stated vertex counts through an r × (r + 1) rectangle.The square has |Λ| = 2(r2 −r) and |V (Λ)| = r2; subsequent additions give the cases summarized in the proof.
Bounds: κΩDIF(2(r2 −r) + 2j) ≥d −(r2 + j), for j = 1, . . . , r.Analogous inequalities are derived for the three other parity and rectangle cases.

Appendix D. Discussion on the analysis exact recovery condition

The appendix examines why the analysis ERC is generally non-sharp and develops more realistic interpretations through sign-pattern effects. It also identifies operator and measurement properties associated with favorable GAP and analysis-ℓ1 performance.

Exact recovery conditions: The analysis ERC condition (25) is not sharp in general, especially for redundant Ω.Sharpness would require a cosparse signal whose transformed approximation matches an exact sign pattern, which may not exist for over-complete operators.
Average-case behavior: The derived average-case condition is not a guarantee, but empirical observations indicate it reflects GAP and ℓ1-minimization success rates more faithfully.It models sign-pattern effects instead of using a worst-case bound.
Desirable operator and measurement properties: Favorable performance is associated with highly redundant, linearly dependent Ω, measurements M that are independent from Ω, incoherent rows, and large cosparsity.These properties are presented as desirable conditions rather than universal guarantees.
Desirable operator and measurement properties: For normalized rows of Ω, larger cosupports and more uniform singular values reduce the entries of R0.This motivates high linear dependencies and rows distributed nearly uniformly on the sphere.
Desirable operator and measurement properties: The 2D finite-difference operator may be considered incoherent despite coherence 1/4 because most row pairs are uncorrelated.The appendix distinguishes this practical notion from the relatively large maximum coherence value.