A note on the complexity of Lp minimization |
| |
| Authors: | Dongdong Ge Xiaoye Jiang Yinyu Ye |
| |
| Affiliation: | (1) NASA – Goddard Space Flight Center, Mail Stop 596, Greenbelt, MD 20771, USA;(2) Applied Mathematics and Scientific Computing Program, University of Maryland, College Park, MD 20742, USA;(3) Department of Electrical and Computer Engineering and the Institute for Systems Research, University of Maryland, College Park, MD 20742, USA;(4) Department of Computer Science and Institute for Advanced Computer Studies, University of Maryland, College Park, MD 20742, USA |
| |
| Abstract: | We discuss the L p (0 ≤ p < 1) minimization problem arising from sparse solution construction and compressed sensing. For any fixed 0 < p < 1, we prove that finding the global minimal value of the problem is strongly NP-Hard, but computing a local minimizer of the problem can be done in polynomial time. We also develop an interior-point potential reduction algorithm with a provable complexity bound and demonstrate preliminary computational results of effectiveness of the algorithm. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
