DocumentCode :
53568
Title :
Author :
Jigen Peng ; Shigang Yue ; Haiyang Li
Author_Institution :
Sch. of Math. & Stat., Xi´an Jiaotong Univ., Xi´an, China
Volume :
61
Issue :
7
fYear :
2015
fDate :
Jul-15
Firstpage :
4028
Lastpage :
4033
Abstract :
In this paper, we have proved that in every underdetermined linear system Ax = b, there corresponds a constant p*(A, b) > 0 such that every solution to the l p-norm minimization problem also solves the l0-norm minimization problem whenever 0 <; p <; p*(A, b). This phenomenon is named NP/CMP equivalence.
Keywords :
linear systems; minimisation; NP-CMP equivalence; information processing; lp-norm minimization problem; sparsity models l0 minimization; underdetermined linear system; Computational modeling; Information processing; Linear programming; Linear systems; Minimization; Optimization; Sparse matrices; $l_{p}$ minimization; Information processing; Sparse recovery; Sparse representation; Underdetermined linear system; lp minimization; sparse recovery; sparse representation; underdetermined linear system;
fLanguage :
English
Journal_Title :
Information Theory, IEEE Transactions on
Publisher :
ieee
ISSN :
0018-9448
Type :
jour
DOI :
10.1109/TIT.2015.2429611
Filename :
7101837
Link To Document :
