为什么说求解0范数是一个NP-hard问题

Question

最近在看稀疏表示方面的东西，这个，求解0范数是一个NP-hard问题，不太明白，望各位能给个准确的解释。

Answer 1

你好，最近我也在学习稀疏这一块。我看了michael elad的《sparse and redundant representation》这本书，第14页提到了。
Let us illustrate this complexity by the following simple example: Assume that
A is of size 500 × 2000 (n = 500, m = 2000), and suppose that we know that the
sparsest solution to (P0) has |S| = 20 non-zeros. We desire to find the proper set of
|S| columns. Thus, we exhaustively sweep through all  C m |S| ≈ 3.9E+ 47 (组合问题，从m中选|S|，页面上显示不出来，给你提示下) such options,
and per each test the small linear system b = AS xS for equality. Assume that each
individual test of such a system requires 1 E−9 seconds. A simple calculation reveals
that it will take more than 1.2E + 31 years(!!!) to conclude these series of tests.
The complexity of exhaustive search is exponential in m, and indeed, it has been
proven that (P0) is, in general, NP-Hard.

简单说，就是，求解最优解是个穷举搜索的过程，如果列数很大，比如2000，然后稀疏解是20，从2000中取20，有3.9E+ 47 种情况，e的47次方了，太大了。当然最后一句，他说已经证明了P0问题是np hard。

而且你想想在使用贪婪算法求解稀疏解时，由于贪婪算法本身的局限(只保证当前这一步最优，不保证全局最优)，不一定能得到P0问题的最优解(0范数最小)。
我也是刚看稀疏，就想到这些，偶然搜索时看到你的问题，跟你说说，估计时间这么久了，你也早已经解决和理解这问题了吧。如果有兴趣可以私信一下，我们可以交流一下，一块学习稀疏表示。