Compressed sensing: L0, L2 and no L1.
I heard Joel Tropp talk recently on his result with Deanna Needell. The problem involves measuring the signal with a small number of inner products and using these measurements to pick the linear combination of a small number of basis vectors that approximates the signal the best. Group testing and greedy methods (L0 approach) or linear programming (L1) have been in vogue recently. A different method (recent ex) iteratively refines a set of vectors (L0) and each time finds best linear combination by least squares optimization (L2). The Needell and Tropp result follows this approach, but uses the structural properties of the set of measurements to get nice bounds for the problem; this method may be among the most suitable for current technologies that perform these measurements.