Do log factors matter? On optimal wavelet approximation and the foundations of compressed sensing

Abstract

A signature result in compressed sensing is that Gaussian random sampling achieves stable and robust recovery of sparse vectors under optimal conditions on the number of measurements. However, in the context of image reconstruction, it has been extensively documented that sampling strategies based on Fourier measurements outperform this purportedly optimal approach. Motivated by this seeming paradox, we investigate the problem of optimal sampling for compressed sensing. Rigorously combining the theories of wavelet approximation and infinite-dimensional compressed sensing, our analysis leads to new error bounds in terms of the total number of measurements $m$ for the approximation of piecewise $\alpha$-Hölder functions. Our theoretical findings suggest that Fourier sampling outperforms random Gaussian sampling when the Hölder exponent $\alpha$ is large enough. Moreover, we establish a provably optimal sampling strategy. This work is an important first step towards the resolution of the claimed paradox, and provides a clear theoretical justification for the practical success of compressed sensing techniques in imaging problems.

References in corpus (11)

• Sparsity and Incoherence in Compressive Sampling
• Structured Compressed Sensing: From Theory to Applications
• Compressive ghost imaging
• Square-Root Lasso: Pivotal Recovery of Sparse Signals via Conic Programming
• Compressive Fluorescence Microscopy for Biological and Hyperspectral Imaging
• Polynomial approximation via compressed sensing of high-dimensional functions on lower sets
• Spread spectrum magnetic resonance imaging
• On asymptotic structure in compressed sensing
• Generalized sampling: stable reconstructions, inverse problems and compressed sensing over the continuum
• On the absence of the RIP in real-world applications of compressed sensing and the RIP in levels
• Spread spectrum compressed sensing MRI using chirp radio frequency pulses