Here are some NIPS videos relevant to compressive sensing and other subjects mentioned on Nuit Blanche. Of particular interest is a question asked to Francis Bach at the end of his presentation where it looks like known bounds are O(p^6) whereas is own empirical experience seems to show an O(p^2) bound, mmmuh, a little bit like what happened in the 1970s' when the seismic folks thought the l_1 norm was a good proxy for l_0.....
How to Grow a Mind: Statistics, Structure and Abstraction by Josh Tenenbaum
Structured sparsity-inducing norms through submodular functions by Francis R. Bach
Optimization Algorithms in Machine Learning by Stephen J. Wright
Oral sesssions are here.