Nothing short of a revolution, part 3 : It does not need to be nonlinear

And then something happened in 1999: Emmanuel Candès and David Donoho noticed that with curvelets, one did not need an adaptive or a nonlinear scheme to converge on images with edges[1]. This is important because as stated before, the only way people were using wavelets and related functions (ridgelets,...) was through a nonlinear scheme, i.e. compute all the wavelet or fourier coefficients first and then do a threshold on them in order keep only the largest ones. While in the wavelet case, i.e. in 1-d, the issue is not really a big deal, it becomes a nightmare when you try to use this type of technique in multidimensional spaces. If you have to compute all the moments of an integral equation and then remove the ones that are too small (because wavelets sparsify certain integral kernel), you have barely made progress over the state of the art like fast multipole methods. So for the first time since the arrival of wavelets, there is hope that there is a linear process by which one can produce a sparse representation of a function or set of data. Ok so now we have a way to get a truely sparse approximation of a function using basis pursuit, we have tons of nice families of functions to do this and we now know that in order to find a sparse representation of a function we don't need a nonlinear scheme, why is this related to compressed sensing ?....

References

[1] Curvelets - a surprisingly effective nonadaptive representation for objects with edges. Curves and Surfaces, L. L. Schumaker et al. (eds), Vanderbilt University Press, Nashville, TN. Compressed Postscript (ps.gz) / (pdf)