Sampling Rates for 𝓁1-Synthesis

Maximilian März, Claire Boyer, Jonas Kahn, Pierre WeissarXiv 2020 · arXiv

TL;DR

This paper analyzes the theoretical guarantees for recovering signals and their sparse representations from noisy, undersampled measurements using the 𝓁¹-synthesis framework. It provides precise conditions and sampling rates for successful recovery, distinguishing between signal recovery and coefficient recovery, and revealing their differing robustness to noise.

What Problem Does This Paper Address?

Compressive sensing (CS) aims to recover signals from fewer measurements than traditionally required, often by assuming the signal has a sparse representation in some basis or dictionary. The 𝓁¹-synthesis model assumes a signal $x_0$ can be represented as $x_0 = Dz_0$, where $D$ is a dictionary and $z_0$ is a sparse coefficient vector. Recovering $z_0$ (coefficient recovery) and $x_0$ (signal recovery) can be done via 𝓁¹-minimization. However, when the dictionary $D$ is redundant (more columns than rows), the sparse representation $z_0$ might not be unique. This raises questions: When can we recover the signal even if the exact sparse representation is elusive? How many measurements are needed for each type of recovery? How do noise and dictionary properties affect these recovery processes? This paper tackles these questions by providing precise theoretical bounds on the sampling rates required for both coefficient and signal recovery.

Methods

The paper leverages tools from convex geometry and functional analysis to derive theoretical guarantees. Key techniques include:

  • Conic Singular Values and Mean Width: The authors relate the success of recovery to geometric properties of the measurement matrix $A$ and the dictionary $D$. Specifically, they use the minimum conic singular value and the conic mean width of certain cones derived from $D$ and the 𝓁¹-norm.
  • Descent Cones: The analysis heavily relies on the geometry of descent cones of convex functions, particularly the 𝓁¹-norm and the gauge function associated with the synthesis model.
  • Upper Bounds on Conic Mean Width: A significant contribution is deriving new, more accessible upper bounds for the conic mean width, which directly translate to sampling rates. These bounds are based on:
  • Local Condition Number: Analyzing the conditioning of the dictionary $D$ at a specific sparse representation.
  • Geometric Analysis (Circumangle): Exploiting the structure of polyhedral cones and their "circumangle" to bound the conic mean width, offering a more general approach.
  • Distinguishing Coefficient and Signal Recovery: The paper formally differentiates between recovering the coefficient vector $z$ and the signal $x = Dz$, showing that signal recovery can be guaranteed even when coefficient recovery fails.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and uses synthetic data generated according to specific models (e.g., sub-Gaussian measurements).

Key Insights and Ideas

  • Signal vs. Coefficient Recovery: Signal recovery is generally more robust and requires fewer assumptions than coefficient recovery. While coefficient recovery requires the sparse representation to be unique (a "minimal 𝓁¹-representer"), signal recovery does not have this strict requirement.
  • Conic Mean Width as the Key Metric: The paper establishes that the conic mean width of a transformed cone related to the dictionary and the 𝓁¹-norm is the fundamental quantity determining the sampling rate for both coefficient and signal recovery.
  • New Upper Bounds for Sampling Rates: The introduction of bounds based on the "circumangle" provides a more geometrically intuitive and potentially tighter characterization of sampling rates, especially for redundant and coherent dictionaries where traditional methods struggle.
  • Robustness to Noise Differs: The analysis reveals that signal recovery is robust to noise without additional conditions, whereas coefficient recovery's robustness is directly influenced by the dictionary's conditioning (measured by the minimum conic singular value).

Key Results

  • Precise Sampling Rate Formulas: The paper derives theoretical sampling rates for both coefficient recovery (Theorem 3.6) and signal recovery (Theorem 3.8) in the sub-Gaussian measurement model. These rates are primarily governed by the conic mean width of a specific cone related to the dictionary and the 𝓁¹-norm.
  • Signal Recovery is More Robust: Theorem 3.8 shows that signal recovery is robust to noise, with an error bound that does not depend on the minimum conic singular value. In contrast, Theorem 3.6 shows coefficient recovery's error bound does depend on this value, implying less inherent robustness.
  • Geometric Bounds: Proposition 4.3 and Theorem 4.17 provide new upper bounds on the conic mean width using geometric properties like the "circumangle," offering a more tractable way to estimate sampling rates for complex dictionaries.
  • Numerical Validation: Extensive simulations (Figures 1, 6, 7, 8) support the theoretical findings, demonstrating sharp phase transitions and confirming the derived sampling rates.

Limitations and Future Work

  • Tightness of Bounds: While the paper provides upper bounds, the authors note that some bounds might not be tight in general (e.g., error bound for coefficient recovery in Theorem 3.6).
  • Computational Complexity: Computing quantities like the minimum conic singular value is NP-hard in general, motivating the search for more accessible bounds.
  • Signal-Dependent Analysis: The paper emphasizes a "non-uniform" or signal-dependent analysis, which is crucial for redundant dictionaries but contrasts with some prior work that relied on uniform properties of the dictionary.
  • Future Work: The authors suggest exploring more accurate descriptions of random conic spectra and further investigating the trade-offs between stable recovery and measurement requirements. They also point out that the derived bounds might be pessimistic in some cases, hinting at potential for tighter theoretical results.

Summary updated

BibTeX
@misc{marz2020sampling,
  author = {Maximilian März and Claire Boyer and Jonas Kahn and Pierre Weiss},
  title = {{Sampling Rates for 𝓁1-Synthesis}},
  year = {2020},
  eprint = {2004.07175},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2004.07175},
}
Figure