🔢 mathematics

On the sample complexity of Fourier compressed sensing: wavelets versus shearlets

Despite the superior sparsity and nonlinear approximation rates of shearlets for anisotropic features, this paper demonstrates that they offer no substantial theoretical or practical reduction in the number of Fourier measurements required for compressed sensing compared to traditional wavelets due to slower local coherence decay and redundancy challenges.

Original authors: Giovanni S. Alberti, Alessandro Felisi, Işıl Güleken

Published 2026-07-23

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Giovanni S. Alberti, Alessandro Felisi, Işıl Güleken

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to send a massive, high-definition movie to a friend, but your internet connection is incredibly slow. You can't send the whole thing, so you need a way to compress it into the smallest possible file without losing the important details. This is the daily struggle of compressed sensing, a branch of science that asks: How little data do we actually need to perfectly rebuild a picture or a sound?

For decades, the standard tool for this job has been wavelets. Think of wavelets as a set of tiny, square flashlights. They are great at finding simple spots of light or dark in an image, like a pixel or a small dot. However, real-world images—like a photo of a cat or a landscape—are full of long, curvy lines (edges) and smooth surfaces. Square flashlights struggle to trace these curves efficiently; they end up needing thousands of little squares just to draw a single smooth edge.

Enter shearlets. If wavelets are square flashlights, shearlets are like a magical set of stretchy, directional flashlights. They can elongate and rotate to perfectly hug the shape of a long edge or a curvy road. Because they fit the shape so well, they can describe a complex image using far fewer "flashlights" (or coefficients) than wavelets. This sounds like a dream come true: if you need fewer numbers to describe the image, surely you need fewer measurements to send it, right? That's the big question this paper sets out to answer.

The researchers in this paper, Giovanni S. Alberti, Alessandro Felisi, and I¸sıl G¨uleken, decided to put this dream to the test. They wanted to know if the superior "fit" of shearlets actually translates into a real-world advantage when taking Fourier measurements (the kind of data used in MRI machines and radio telescopes). The hypothesis was simple: since shearlets are much more "sparse" (meaning they use fewer numbers to describe an image), they should require significantly fewer measurements to reconstruct the image compared to traditional wavelets.

However, the story takes a twist. When the team dug into the math, they found some hidden obstacles. While shearlets are indeed better at describing the shape of an image, the rules for how to measure them are trickier. They discovered that the mathematical "coherence" (a measure of how well the measurement tool matches the image description) for shearlets decays much more slowly than for wavelets. In plain English, the "signal" from a shearlet gets lost in the noise of the measurement process much faster than a wavelet's signal does.

Furthermore, shearlets are highly redundant (there are many of them overlapping), which creates a mathematical bottleneck. The researchers found that under current theoretical frameworks, bounding the redundancy of shearlets leads to a sample complexity estimate that scales with the square of the sparsity, rather than just the sparsity itself. This means that even though shearlets are more efficient at describing the image, the current math required to guarantee their recovery cancels out that advantage.

To prove this, the team ran a series of computer simulations. They created a dataset of "cartoon-like" images—pictures made of smooth shapes with sharp edges, which are the perfect test case for shearlets. They confirmed that, just as theory predicted, shearlets could describe these images using far fewer numbers than wavelets. But then came the surprise: when they tried to reconstruct the images from partial data (simulating a slow internet connection), the number of data points required to get a perfect picture was almost the same for both systems.

The phase diagrams they generated (which map out success rates against data amounts) showed that while shearlets are mathematically "sparser," this didn't buy them a proportional reduction in the number of measurements needed. In fact, the advantage was negligible, shrinking down to just a tiny logarithmic factor.

So, what is the verdict? The paper concludes that despite the theoretical elegance and superior approximation rates of shearlets, they do not offer a practical shortcut in the number of measurements required for compressed sensing with Fourier data. The "magic" of the stretchy flashlights doesn't save you from the data bottleneck in this specific scenario. The researchers suggest that while shearlets are fantastic for representing images, the current mathematical tools for recovering them from limited data haven't quite caught up to their potential. It's a reminder that in science, being better at describing a problem doesn't always mean you can solve it with less effort.

Technical Summary: On the Sample Complexity of Fourier Compressed Sensing: Wavelets versus Shearlets

1. Problem Statement

The paper investigates the sample complexity requirements for signal recovery in compressed sensing (CS), specifically comparing the performance of shearlet frames against traditional wavelet systems when using subsampled Fourier measurements.

While directional representation systems like shearlets are known to provide superior nonlinear approximation rates for images with anisotropic features (e.g., edges in "cartoon-like" images) compared to wavelets, it remains an open question whether this improved sparsity translates into a proportional reduction in the number of Fourier measurements required for successful reconstruction. The central hypothesis tested is whether the sample complexity $m$ scales linearly with the effective sparsity of shearlets ( $s_{shear}$ ), i.e., $m \gtrsim s_{shear}$ , or if theoretical and practical obstacles prevent this advantage.

2. Methodology

The authors employ a dual approach combining rigorous theoretical analysis and comprehensive numerical experimentation.

2.1 Theoretical Framework

The analysis is grounded in the abstract recovery results for compressed sensing with general frames (specifically referencing results from [28], [3], and [42]). The sample complexity bound for stable recovery is governed by three key quantities:

Sparsity ( $s$ ): The number of significant coefficients in the representation.
Local Coherence ( $\mu_{loc}$ ): The maximum correlation between the measurement basis (Fourier) and the sparsifying frame elements.
Localization Factor ( $\eta_{s,D}$ ): A measure of the redundancy of the sparsifying frame, dependent on the lower frame bounds of finite subframes.

The authors analyze these quantities specifically for cone-adapted shearlets:

Local Coherence: They derive bounds for the local coherence between Fourier measurements and shearlets, showing it decays as $O((1+\|n\|_\infty)^{-3/4})$ . This is compared to the $O((1+\|n\|_\infty)^{-1})$ decay for wavelets.
Localization Factor: They investigate the difficulty of bounding the localization factor $\eta_{s,D}$ for shearlets. This requires estimating the optimal lower frame bounds ( $A_\Delta$ ) for arbitrary finite subframes of shearlets. The authors demonstrate that these bounds can be exponentially small, leading to an exponentially large localization factor, which negates theoretical gains.
Sparsity Comparison: They utilize known nonlinear approximation rates where shearlets achieve $O(N^{-2}(\log N)^3)$ error decay versus $O(N^{-1})$ for wavelets, implying $s_{wave} \approx s_{shear}^2$ .

2.2 Numerical Experiments

To validate theoretical findings, the authors conduct numerical experiments on a dataset of piecewise smooth, "cartoon-like" images (unions of disks with smooth boundaries).

Setup: They compare a Stationary Wavelet Transform (translation-invariant, redundant) and the ShearLab shearlet transform (highly redundant).
Measurements: Subsampled 2D Fourier measurements are acquired using a probability distribution derived from the local coherence bounds (decaying as $\|n\|_\infty^{-3/2}$ ).
Reconstruction: Recovery is performed via $\ell_1$ -minimization (analysis formulation) using the UNLocBoX solver.
Evaluation: Performance is assessed using phase diagrams, plotting the probability of successful reconstruction against the signal complexity (number of disks/boundary length) and the subsampling percentage.

3. Key Contributions and Results

3.1 Theoretical Findings

Coherence Decay: The local coherence between shearlets and Fourier measurements decays more slowly ( $O(n^{-3/4})$ ) than that of wavelets ( $O(n^{-1})$ ). This suggests a less favorable sampling distribution for shearlets.
Localization Factor Obstacle: The authors show that controlling the redundancy of shearlet frames via the localization factor $\eta_{s,D}$ is theoretically intractable with current methods. The required lower frame bounds for finite subframes can be exponentially small, causing $\eta_{s,D}$ to be exponentially large.
Sample Complexity Scaling: Even under an optimistic assumption where the localization factor is bounded (order 1), the derived sample complexity bound for shearlets scales as $m \gtrsim s_{shear}^2$ (due to the coherence term). Given the relationship $s_{wave} \approx s_{shear}^2$ , this implies that the theoretical sample complexity for shearlets is comparable to that of wavelets, offering no substantial reduction beyond logarithmic factors.

3.2 Numerical Findings

Sparsity Advantage Confirmed: The experiments confirm that shearlets represent the test images with significantly fewer non-zero coefficients than wavelets for a given approximation error, validating their superior nonlinear approximation properties.
No Proportional Gain in Measurements: Despite the sparsity advantage, the phase diagrams reveal that the number of Fourier measurements required to successfully recover the images is comparable for both wavelets and shearlets. The "sparsity advantage" does not translate into a proportional reduction in sample complexity.
Empirical Consistency: The numerical results align with the theoretical prediction that the slower decay of coherence and the redundancy issues in shearlets offset the gains from improved sparsity.

4. Significance and Claims

The paper claims to resolve the discrepancy between the theoretical superiority of shearlets in approximation theory and their lack of demonstrated advantage in compressed sensing sample complexity.

Theoretical Limitation: The authors conclude that the standard frame-based recovery theorems, when applied to shearlets, do not yield a sample complexity bound of the form $m \gtrsim s_{shear}$ . Instead, the bounds remain comparable to the wavelet benchmark ( $m \gtrsim s_{wave}$ ) due to the interplay between coherence decay and frame redundancy.
Practical Implication: The study suggests that for subsampled Fourier measurements (common in MRI and radio interferometry), switching from wavelets to shearlets may not reduce the acquisition time or data storage requirements, despite the better representation efficiency.
Future Directions: The authors modestly suggest that future work might explore multilevel sparsity approaches or infinite-dimensional settings to determine if different theoretical frameworks could overcome these obstacles, but they do not claim such improvements are currently available.

In summary, the paper argues that while shearlets are superior for representing anisotropic features, this advantage does not automatically guarantee a reduction in the sample complexity for Fourier-based compressed sensing, primarily due to the specific coherence properties and redundancy of the shearlet system.