Signal and Image Reconstruction with Tight Frames via Unconstrained $\ell_1-α\ell_2$-Analysis Minimizations

Peng Li, Huanmin Ge, Pengbo Geng

TL;DR

This paper introduces a new unconstrained reconstruction model that uses the $\ell_1 - \alpha\ell_2$ penalty to recover signals and images that are sparse under a "tight frame" transformation (like wavelets). By combining a nonconvex sparsity metric with a fast iterative algorithm (pFISTA), the authors achieve more accurate and faster MRI reconstructions than traditional $\ell_1$ or $\ell_p$ methods.

What Problem Does This Paper Address?

In the world of Compressed Sensing (CS), the goal is to reconstruct a high-dimensional signal from just a few measurements. Traditionally, we assume the signal is "sparse" (mostly zeros). However, many real-world signals—like medical MRI scans—aren't sparse in their raw form. They only become sparse after a mathematical transformation, such as a Wavelet transform.

There are two main ways to handle this:

  1. Synthesis Model: You try to find the sparse coefficients of the transform.
  2. Analysis Model: You try to find the signal itself such that its transform is sparse.

The Analysis Model is often more robust, but it's harder to solve mathematically. Furthermore, while the standard $\ell_1$ norm is the "go-to" tool for promoting sparsity, it’s often a loose approximation of the true goal (the $\ell_0$ norm, which simply counts non-zeros). Nonconvex penalties like $\ell_1 - \alpha\ell_2$ provide a much tighter approximation but come with significant theoretical and algorithmic challenges. This paper tackles the unconstrained analysis model using this nonconvex penalty, providing both the mathematical proof that it works and a fast algorithm to run it.

Methods

The authors propose the Analysis $\ell_1 - \alpha\ell_2$-ASSO model. The core objective function looks like this: $$\min_{x} \lambda(\|D^\top x\|_1 - \alpha\|D^\top x\|_2) + \frac{1}{2}\|Ax - b\|_2^2$$ Where $D$ is a tight frame (the transform), $A$ is the sensing matrix, and $b$ is the measured data.

Key Innovations:

  • Theoretical Guarantees: They develop new "technology lemmas" for tight frames. They prove stable recovery conditions based on the Restricted Isometry Property adapted to frames (D-RIP) and the Restricted Orthogonality Constant (D-ROC). Crucially, their proven conditions for recovery are "weaker" (easier to satisfy) than previous state-of-the-art results.
  • The Algorithm ($\ell_1 - \alpha\ell_2$-pFISTA): They adapt the Projected Fast Iterative Soft-Thresholding Algorithm (pFISTA) to handle the nonconvex $\ell_1 - \alpha\ell_2$ term. This allows for efficient computation even with the added complexity of the tight frame.

Datasets

The researchers evaluated their model using:

  • Synthetic 1D Signals: Used to generate "phase transition" diagrams to see exactly when the algorithm succeeds or fails based on the number of measurements and the level of sparsity.
  • Brain MRI (256x256): A standard benchmark for medical imaging reconstruction.
  • Foot MRI (512x512): A higher-resolution test case to demonstrate scalability and detail preservation.
  • Transformations: They used Daubechies wavelets with 4 decomposition levels as the tight frame ($D$).

Key Insights and Ideas

  • The "Bridge" Metric: The $\ell_1 - \alpha\ell_2$ metric acts as a bridge. When $\alpha=0$, it's standard $\ell_1$ (Lasso). As $\alpha$ increases toward 1, it behaves more like the $\ell_0$ norm, better identifying the "true" sparse structure of the image.
  • Analysis > Synthesis: By working in the analysis framework, the model directly optimizes the signal in its natural space, which the authors show leads to fewer artifacts in MRI images compared to coefficient-based synthesis models.
  • Theoretical Relaxation: The paper shows that you don't need as "perfect" a sensing matrix as previously thought to guarantee a good reconstruction. Their new bounds (Remark 1 in the paper) prove that this nonconvex approach is theoretically more forgiving than earlier $\ell_1 - \alpha\ell_2$ proofs.

Key Results

  • Higher Success Rates: In synthetic tests, the proposed method showed a significantly larger "success region" in phase transition plots compared to standard $\ell_1$ and $\ell_p$ ($p=0.5$) methods.
  • Superior MRI Quality: Visually, the reconstructed Brain and Foot MRIs showed fewer "speckle" artifacts and sharper edges.
  • Computational Efficiency: While nonconvex problems are usually slow, the pFISTA implementation was remarkably fast. For the Brain-MRI (30% sampling), the proposed method took ~85 seconds, compared to ~164 seconds for $\ell_{0.1}$ and ~322 seconds for $\ell_{0.9}$. It was nearly as fast as basic $\ell_1$ but with much higher accuracy.

Limitations and Future Work

  • Parameter Tuning: The performance depends on choosing the right $\alpha$ (usually between 0 and 1) and $\lambda$. The paper doesn't provide a universal rule for selecting these; they are currently tuned empirically for different types of data.
  • General Dictionaries: The current theory relies on tight frames (where $DD^\top = I$). Extending this to highly redundant, non-tight dictionaries (like those learned via machine learning) remains an open challenge.
  • Real-time Constraints: While faster than many alternatives, 85 seconds is still a long time for a doctor waiting at a scanner. Future work could involve GPU acceleration or hybridizing this with deep learning to reach sub-second reconstruction times.

Summary updated

Abstract

In the paper, we introduce an unconstrained analysis model based on the $\ell_{1}-α\ell_{2}$ $(0< α\leq1)$ minimization for the signal and image reconstruction. We develop some new technology lemmas for tight frame, and the recovery guarantees based on the restricted isometry property adapted to frames. The effective algorithm is established for the proposed nonconvex analysis model. We illustrate the performance of the proposed model and algorithm for the signal and compressed sensing MRI reconstruction via extensive numerical experiments. And their performance is better than that of the existing methods.
BibTeX
@misc{li2021signal,
  author = {Peng Li and Huanmin Ge and Pengbo Geng},
  title = {{Signal and Image Reconstruction with Tight Frames via Unconstrained $\textbackslash\{\}ell\_1-α\textbackslash\{\}ell\_2$-Analysis Minimizations}},
  year = {2021},
  eprint = {2112.14510},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2112.14510},
}
Figure