I have nothing to add to Brians and Michaels explanation about $\ell^1$ vs. $\ell^0$. But since the question seems to be about Compressed Sensing I'd like to add my point of view: Compressed Sensing is neither about solving
$$\min\|x\|_0\quad\text{s.t}\quad Ax=b$$
nor about
$$\min\|x\|_1\quad\text{s.t.}\quad Ax=b.$$
Compressed Sensing is more a paradigm, which can be stated very roughly as
It is possible to identify sparse signals from a few measurements.
Compressed Sensing is really about taking as few measurements as possible to identify a signal in a certain class of signals.
One catchy phrase is:
Why should your 5 megapixel camera really measure 15 million values (three for each pixel) which cost you 15 megabytes of data when it is only storing about 2 megabytes (after compression)?
Could it be possible to measure the 2 megabytes right away?
There are quite different frameworks possible:
- linear measurements
- non-linear ones (e.g. "phaseless" ones)
- vector data, matrix/tensor data
- sparsity as just the number of non-zeros
- sparsity as "low-rank" or even "low complexity").
And there are also more methods to compute sparse solutions like matching pursuits (variants like orthogonal matching pursuit (OMP), regularized orthogonal matching pursuit (ROMP), CoSaMP) or the more recent methods based on message passing algorithms.
If one identifies Compressed Sensing with mere $\ell^1$- or $\ell^0$-minimization, one misses a great deal of flexibility when dealing with practical data acquisition problems.
If one, however, is only interested in obtaining sparse solutions to linear systems, one does something which I would call sparse reconstruction.