An M* Proxy for Sparse Recovery Performance

Mathieu Barré, Alexandre d’AspremontarXiv 2018 · DOI · arXiv

Abstract

This paper provides a new tractable lower bound for the sparse recovery threshold of sensing matrices. This lower bound is used as a proxy to quantify the quality of sensing matrices in two different applications. First, it serves as regularization for the classical dictionary learning problem in order to learn dictionaries with better generalisation properties on unseen data. Then, the proxy is used to design sampling schemes for MRI acquisition that exhibit high reconstruction performances.

Introduction: The Challenge of Recovery Thresholds

In compressed sensing, the goal is to reconstruct a sparse signal from a limited number of linear measurements. A fundamental metric in this field is the recovery threshold $k(A)$, which represents the maximum number of non-zero coefficients a signal can possess while still being guaranteed perfect reconstruction via $\ell_1$-minimization.

Probability of reconstruction as a function of signal sparsity for different sensing matrices.

As shown in Figure 1, different sensing matrices exhibit vastly different recovery behaviors. While Gaussian matrices often approach theoretical limits, "poor" sensing matrices fail much earlier as sparsity decreases. Unfortunately, computing $k(A)$ for an arbitrary matrix $A$ is NP-hard. Existing theoretical bounds, such as those derived from the Restricted Isometry Property (RIP), are often too conservative or computationally prohibitive to be used as active optimization objectives during dictionary learning or system design.

Methods: The $M^*$ Width Proxy

To overcome these computational hurdles, the authors propose using the $M^*$ width—a geometric measure of the "size" of a convex set—as a tractable proxy for the recovery threshold.

The Geometric Proxy

The core insight is that the recovery threshold of an augmented matrix (the original matrix plus a few Gaussian rows) is controlled by the $M^*$ width of the intersection between the $\ell_1$-ball and the nullspace of the sensing matrix. This geometric radius provides a high-probability bound on the reconstruction success that is much easier to estimate via simulation than the combinatorial $k(A)$.

Regularized Dictionary Learning

The authors incorporate this $M^*$ proxy into the dictionary learning objective as a structural regularizer. To maintain tractability, they employ an alternating minimization scheme:

  1. Atom Optimization: Standard updates for dictionary atoms.
  2. Nullspace Update: Stochastic gradient descent (SGD) on the Stiefel manifold to update the basis of the matrix's nullspace.
  3. Efficient Computation: By deriving a dual formulation, the problem is transformed into an $L_\infty$ norm linear regression, significantly speeding up the optimization for practical image sizes.

MRI Sampling Design

For MRI applications, the proxy is used within a greedy algorithm to select sampling "spirals" in Fourier space. The algorithm iteratively chooses trajectories that minimize the $M^*$ value of the resulting sampling set, thereby maximizing the expected reconstruction quality.

Key Results and Discussion

The $M^*$ proxy effectively tracks the phase transition between successful and failed recovery across various sampling regimes.

Phase transition diagram showing the recovery threshold boundary predicted by the $M^*$ proxy.

Performance in Inpainting and MRI

  • Superior Inpainting: In image inpainting tasks (e.g., the "lake" benchmark), the $M^*$-penalized dictionary achieved a PSNR of 35.4dB, significantly outperforming the standard weighted K-SVD (wKSVD) which reached only 30.8dB.
  • Computational Efficiency: Despite the complexity of the geometric penalty, the $M^*$-regularized algorithm was often twice as fast as wKSVD (e.g., 196s vs 444s) because it avoids the heavy truncated SVDs required by K-SVD variants.
  • MRI Optimization: Greedy $M^*$ selection for MRI spirals consistently yielded higher PSNR reconstructions than simpler heuristics based on sampling density or cardinality.

Generalization and Robustness

The $M^*$ penalty acts as a structural regularizer that prevents the dictionary from "overfitting" to specific noise patterns or masks. By forcing the dictionary to maintain good recovery properties for any sparse signal, it ensures better generalization to unseen data. Furthermore, the method proved more robust to poor initializations compared to coherence-based methods like INK-SVD.

Limitations and Future Directions

While the $L_\infty$ formulation is efficient, scaling to full-scale 3D MRI or ultra-high-resolution images remains a challenge due to memory constraints. Future work may involve "matrix-free" solvers to handle these larger datasets. Additionally, extending the framework to fully non-Cartesian, continuous MRI trajectories and implementing adaptive tuning for the regularization parameter $\mu$ are promising avenues for further improvement.

Summary updated

Abstract

This paper provides a new tractable lower bound for the sparse recovery threshold of sensing matrices. This lower bound is used as a proxy to quantify the quality of sensing matrices in two different applications. First, it serves as regularization for the classical dictionary learning problem in order to learn dictionaries with better generalisation properties on unseen data. Then, the proxy is used to design sampling schemes for MRI acquisition that exhibit high reconstruction performances.
BibTeX
@misc{barre2018m,
  author = {Mathieu Barré and Alexandre d’Aspremont},
  title = {{An M* Proxy for Sparse Recovery Performance}},
  year = {2018},
  eprint = {1810.02748},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1810.02748},
}
Figure