Sparse Representations and High Dimensional Geometry: The upcoming success of randomized algorithms

In the short course on Sparse Representations and High Dimensional Geometry, there are obviously several items of interest to compressed sensing and the general framework around it. While Compressed Sensing could be done without random measurements, it seems that its connection to that subject has brought a lot exposure to subject areas that were using randomization as well. Joel Tropp's presentation on matching pursuit is interesting to follow in bringing some theoretical background to matlab codes already available.

Because the Fourier transform is at the heart of the first revolution in numerical analysis, I am very anxious to see how both developments in reconstruction from Fourier measurements as highlighted by Roman Vershynin and the algorithm for the Very Fast Fourier Transform of Jing Zou will pan out.

As a way to tickle one's interest in randomized algorithms, one can take a look at this intriguing paper from Roman on A randomized solver for linear systems with exponential convergence.