# ${L}_{0}$ Pseudo Norm Minimization in Compressive Sensing

I have recently taken up studying compressive sensing related papers. Some things are not very clear to me or may be I am not able to visualize the scenario as is said. Like how $l_0$ norm minimization is NP hard? Can somebody explain with an example (step by step example may be?) of a matrix and vector for an equation $y=Ax$, how $l_0$ minimization of the same can be NP hard?

• Because it's equivalent to subset selection problem, which is an NP Hard combinatorial optimization problem. There's more information on Wikipedia – Emre Jul 20 '14 at 20:20

the solution for a sparse recovery problem is given by: $$\text{min} ||x||_0$$ $$\text{s.t} \hspace{2mm} y = Ax$$

The definition of $||x||_0$ is no. of non-zero entries in $x$. This is also called the sparsity of the vector.

i.e., we are asking for the sparsest solution $x$, that satisfies $y = Ax$.

Consider the simplest case where $x$ is 1-sparse but you don't know the location of that non-zero entry. In such a case, we have $\binom{N} {1}$ possibilities for a 1-sparse vector and to find the solution we have to examine the values of all the $\binom{N} {1}$ possibilities for finding the unique minimizer. Similarly, if you are told that $x$ is $k$-sparse, you need to search $\binom{N} {k}$ possibilities. i.e., the algorithm grows as $\binom{N}{k}$ with increase in $k$. Since $k$ is not known a priori, you have to check for all the $N$ possible values of $k$.

Hence, the complexity of the algorithm is $\displaystyle\sum_{i=1}^N \binom{N}{i}$. This is called as NP hard problem which is an acronym for Non-polynomial time complexity.

• Could you add some Latex formatting for improved readability? – Matt L. Jun 19 '15 at 8:47
• And this is how to do it – jojek Jun 19 '15 at 8:49
• Thanx a lot. A clear explanation. – mrin9san Jun 20 '15 at 8:32
• Not sure why the downvote. Nice answer: +1 – Peter K. Oct 6 '15 at 0:06
• That's definitely not valid proof. Base on his logic, given a list of numbers, and a check algorithm gives whether a list is sorted or not. We need N! times of checking, hence sorting is NP-hard? – khanh Nov 12 '20 at 22:27