A note on the complexity of Lp minimization

• 成果类型: Article
• 署名作者: Ge, Dongdong; Jiang, Xiaoye; Ye, Yinyu
• 署名单位: Shanghai Jiao Tong University; Stanford University; Stanford University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-011-0470-2
• 发表日期: 2011
• 页码: 285-299
• 关键词: sparse; systems

摘要

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.