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

This paper explores the measurement requirements for signal recovery in compressed sensing, comparing the performance of shearlet frames with traditional wavelet systems. Directional representation systems such as shearlets are known for their ability to sparsely represent images with anisotropic features, which allows for efficient nonlinear approximations. The central question we address is whether this difference in sparsity allows for a proportional reduction in the number of Fourier measurements needed for successful reconstruction.
On the theoretical front, we study the obstacles encountered when trying to apply standard frame-based recovery results to shearlet systems. First, we show that the (optimal) local coherence between Fourier measurements and cone-adapted shearlets decays more slowly than the corresponding local coherence for wavelets. Second, managing the sparsifying system's redundancy relies on evaluating a localization factor, which requires lower frame bound estimates that can become exponentially small. Thus, even under optimal theoretical conditions, the number of samples required for shearlets scales quadratically with sparsity, which offers no substantial theoretical reduction over the standard wavelet benchmark.
These theoretical limitations are assessed through a series of numerical experiments on a dataset of piecewise smooth images. While empirical observations confirm that shearlets can accurately represent these images using fewer coefficients than wavelets, phase diagrams indicate that this advantage in sparsity does not yield a proportional reduction in required Fourier samples. Ultimately, we conclude that despite the superior nonlinear approximation rates of shearlets, their practical sample complexity in compressed sensing scenarios with subsampled Fourier measurements remains comparable to that of traditional wavelets.