稀疏恢复问题的解由下式给出：

的定义为否。中的非零条目。这也称为向量的稀疏性。$||x||_0$$x$

即，我们要求满足。$x$$y = Ax$

考虑最简单的情况，其中是 1-sparse，但您不知道该非零条目的位置。在这种情况下，对于 1-稀疏向量，我们有\binom{N} {1}个可能性，为了找到解决方案，我们必须检查所有\binom{N} {1} 个可能性的值以找到唯一的最小化器. 同样，如果你被告知x是k稀疏的，你需要搜索\binom{N} {k}个可能性。即，算法随着\binom{N}{k}随着k的增加而增长。由于k不是先验已知的，因此您必须检查k的所有N个可能值。$x$$\binom{N} {1}$$\binom{N} {1}$$x$$k$$\binom{N} {k}$$\binom{N}{k}$$k$$k$$N$$k$

因此，算法的复杂度为。这被称为 NP 难题，它是非多项式时间复杂度的首字母缩写。$\displaystyle\sum_{i=1}^N \binom{N}{i}$