Dongdong Ge, Xiaoye Jiang, and Yinyu Ye. A Note on Complexity of Lp Minimization. Mathematical Programming, accepted to appear.


We show that the Lp (0 ≤ p < 1) minimization problem arising from sparse solution construction and compressed sensing is both hard and easy. More precisely, for any fixed 0 < p < 1, we prove that finding the global minimal value of the problem is strongly NP-Hard; but approximating a local minimizer of the problem is polynomial-time doable. We also develop an interior-point algorithm with a provable complexity bound and demonstrate preliminary computational results of effectiveness of the algorithm.


author={Dongdong Ge and Xiaoye Jiang and Yinyu Ye},
title={A Note on Complexity of Lp Minimizatio},
journal={mathematical programming},