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?

  • 1
    $\begingroup$ Because it's equivalent to subset selection problem, which is an NP Hard combinatorial optimization problem. There's more information on Wikipedia $\endgroup$
    – 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.

  • 1
    $\begingroup$ Could you add some Latex formatting for improved readability? $\endgroup$
    – Matt L.
    Jun 19 '15 at 8:47
  • 1
    $\begingroup$ And this is how to do it $\endgroup$
    – jojek
    Jun 19 '15 at 8:49
  • $\begingroup$ Thanx a lot. A clear explanation. $\endgroup$
    – mrin9san
    Jun 20 '15 at 8:32
  • $\begingroup$ Not sure why the downvote. Nice answer: +1 $\endgroup$
    – Peter K.
    Oct 6 '15 at 0:06
  • $\begingroup$ 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? $\endgroup$
    – khanh
    Nov 12 '20 at 22:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.