Keep in mind, L1 is not the only approach to compressive sensing. In our research, we've had better success with Approximate Message Passing (AMP). I am defining "success" as lower error, better phase transitions (ability to recover with fewer observations), and lower complexity (both memory and cpu).
The Approximate Message Passing algorithm establishes a Bayesian framework to estimate the unknown vectors in a large scale linear system where the inputs and outputs of the linear system are determined by probablistic models (e.g. "this vector was measured with noise", "this vector has some zeros"). The original AMP approach forged by Donoho has been refined by Rangan into Generalized Approximate Message Passing with Matlab code available. The inputs and outputs can be almost arbitrary probability density functions. In our research , we've found that GAMP is typically faster, more accurate, and more robust (read: better phase transition curves) than the L1 convex approaches and greedy approaches (e.g. Orthogonal Matching Pursuit).
My advisor and I just wrote a paper on using GAMP for Analysis CS, where one expects an abundance of zeros, not in the unknown vector x, but rather in a linear function of that unknown, Wx.