3
$\begingroup$

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?

$\endgroup$
1
  • 2
    $\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
    Commented Jul 20, 2014 at 20:20

1 Answer 1

8
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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