
Dongdong Ge, Xiaoye Jiang, and Yinyu Ye. A Note on Complexity of Lp Minimization. Mathematical Programming, accepted to appear.
Abstract:
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 NPHard; but approximating a local minimizer of the problem is polynomialtime doable. We also develop an interiorpoint algorithm with a provable complexity bound and demonstrate preliminary computational results of effectiveness of the algorithm.
Bibtex:
@article{gjyanocolm11,
author={Dongdong Ge and Xiaoye Jiang and Yinyu Ye},
title={A Note on Complexity of Lp Minimizatio},
journal={mathematical programming},
}

