Igor Carron provides a nice history of Compressed Sensing on his blog. He reviews the computation complexity of various Compressed Sensing algorithms, noting that the field started with the discovery of polynomial time solutions to underdetermined linear problems. While $l_0$ norm regularization results in NP-complete problems, $l_1$ regularization is easier.