  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\"{o}lder functions. Our theoretical findings suggest that
Fourier sampling outperforms random Gaussian sampling when the H\"older
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.
