$NP/CLP$ Equivalence: A Phenomenon Hidden Among Sparsity Models for Information Processing

Jigen Peng; Shigang Yue; Haiyang Li

paper

$N P / C L P$ Equivalence: A Phenomenon Hidden Among Sparsity Models for Information Processing

arXiv:1501.02018

Abstract

It is proved in this paper that to every underdetermined linear system $A x = b$ there corresponds a constant $p (A, b) > 0$ such that every solution to the $l_{p}$ -norm minimization problem also solves the $l_{0}$ -norm minimization problem whenever $0 < p < p (A, b)$ . This phenomenon is named $N P / C L P$ equivalence.

submitted to IEEE Transactions on Information Theory in June 2014

NP/CLP Equivalence: A Phenomenon Hidden Among Sparsity Models for Information Processing

Abstract

$N P / C L P$ Equivalence: A Phenomenon Hidden Among Sparsity Models for Information Processing