I read some references including this.I am kind of confused what optimization problem compressed sensing builds and tries to solve. Is it$$\begin{array}{ll} \text{minimize} & \|x\|_1\\ \text{subject to} & Ax=b\end{array}$$or/and$$\begin{array}{ll} \text{minimize} & \|x\|_0\\ \text{subject to} & Ax=b\end{array}$$or/and something else?Thanks!
Confusion about compressed sensing problem
optimization
Brian is spot on. But I think it is helpful to add some compressed sensing context.First, note that the so-called 0 norm $\|x\|_0$---the cardinality function, or the number of nonzero values in $x$---is not a norm. It is probably best to write it as something like $\mathop{\textbf{card}}(x)$ in anything but the most casual contexts. Don't get me wrong, you're in good company when you use the $\|x\|_0$ shorthand, but I do think it tends to breed confusion.People have known for a long time that minimizing the $\ell_1$ norm $\|x\|_1$ tends to produce sparse solutions. There are some theoretical reasons for this that have to do with linear complementarity. But what was most interesting was not that the solutions were sparse, but that they were often the sparsest possible. That is, minimizing $\|x\|_1$ really does give you the minimum-cardinality solution in certain useful cases. (How did they figure this out, when the minimum cardinality problem is NP-hard? By constructing artificial problems with known sparse solutions.) This was not something that the linear complementarity theory could predict.The field of compressed sensing was born when researchers began to identify conditions on the matrix $A$ that would allow them to guarantee in advance that the $\ell_1$ solution was also the sparsest. See for example, the earliest papers by Cands, Romberg, and Tao, and other discussions of the Restricted isometry property, or RIP. Another useful web site if you really want to dive into some theory is Terence Tao's compressed sensing page.