# Confusion about compressed sensing problem

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?

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 Candés, 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.

We would love to be able to solve

$\min \| x \|_{0}$

s.t.

$Ax=b$

but this problem is an NP-Hard combinatorial optimization problem that is impractical to solve in practice when $A$, $x$, and $b$ are of sizes typical in compressive sensing. It is possible to efficiently solve

$\min \| x \|_{1}$

s.t.

$Ax=b$

both in theory (it can be done in polynomial time) and in computational practice for even fairly large problems that arise in compressive sensing. We use $\| x \|_{1}$ as a "surrogate" for the $\| x \|_{0}$. This has some intuitive justification (the one-norm minimization prefers solutions with fewer nonzero entries in $x$), as well as much more sophisticated theoretical justifications (theorems of the form "If $Ax=b$ has a k-sparse solution then minimizing $\| x \|_{1}$ will find that solution with high probability."

In practice, since data are often noisy, the exact constraint $Ax=b$ is often replaced with a constraint of the form $\| Ax - b \|_{2} \leq \delta$.

It's also quite common to work with a variational form of the constrained problem, where for example we might minimize $\min \| Ax - b\|_{2}^{2} + \lambda \| x \|_{1}$.

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.

• Thanks! Can you rephrase the following into math formulation: " 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." – Tim Apr 7 '13 at 12:51
• No, I can't, because Compressed Sensing is not a mathematical theory but rather an engineering concept. – Dirk Apr 7 '13 at 15:25
• I think this answer is a good contribution, and I voted it up. As for the catchy phrase, though, I've always had a problem with it. It suggests that CS is so powerful that you could just throw away 13 million pixels and recover the image anyway. But no, you should never throw away data randomly, even in a CS system---a good recovery algorithm can always make use of more data. The promise of CS is the potential to develop sensors that collect less data in the first place in exchange for some important practical savings: power savings, faster collection, etc. – Michael Grant Apr 7 '13 at 21:38
• @MichaelGrant I agree: Do not throw away data you already measured and use date which you can measure with minimal effort. – Dirk Apr 8 '13 at 6:24