TY - GEN
T1 - Phase transition and noise sensitivity of ℓp-minimization for 0 ≤ p ≤ 1
AU - Weng, Haolei
AU - Zheng, Le
AU - Maleki, Arian
AU - Wang, Xiaodong
N1 - Publisher Copyright:
© 2016 IEEE.
PY - 2016/8/10
Y1 - 2016/8/10
N2 - Recovering a sparse vector x0 ⋯ ℝN from its noisy linear observations, y ⋯ ℝn with y = Ax0 + w, has been the central problem of compressed sensing. One of the classes of recovery algorithms that has attracted attention is the class of ℓp-regularized least squares (LPLS) that seeks the minimum of 1/2 ||y - Ax||22 + λ||x||pp for p ⋯ [0, 1]. In this paper we employ the Replica method1 from statistical physics to analyze the global minima of LPLS. Our paper reveals several surprising asymptotic properties of LPLS: (i) The phase transition curve of LPLS is the same for every 0 ≤ p < 1. These phase transition curves are much higher than the phase transition curve for p = 1. (ii) The phase transition curve of LPLS for every value of 0 ≤ p ≤ 1 depends only on the sparsity level and does not change with the distribution of the non-zero coefficients of x0. (iii) Despite the equality of the phase transition curves, different values of p show different performances once a small amount of measurement noise, w, is added.
AB - Recovering a sparse vector x0 ⋯ ℝN from its noisy linear observations, y ⋯ ℝn with y = Ax0 + w, has been the central problem of compressed sensing. One of the classes of recovery algorithms that has attracted attention is the class of ℓp-regularized least squares (LPLS) that seeks the minimum of 1/2 ||y - Ax||22 + λ||x||pp for p ⋯ [0, 1]. In this paper we employ the Replica method1 from statistical physics to analyze the global minima of LPLS. Our paper reveals several surprising asymptotic properties of LPLS: (i) The phase transition curve of LPLS is the same for every 0 ≤ p < 1. These phase transition curves are much higher than the phase transition curve for p = 1. (ii) The phase transition curve of LPLS for every value of 0 ≤ p ≤ 1 depends only on the sparsity level and does not change with the distribution of the non-zero coefficients of x0. (iii) Despite the equality of the phase transition curves, different values of p show different performances once a small amount of measurement noise, w, is added.
UR - http://www.scopus.com/inward/record.url?scp=84985995689&partnerID=8YFLogxK
U2 - 10.1109/ISIT.2016.7541384
DO - 10.1109/ISIT.2016.7541384
M3 - Conference contribution
AN - SCOPUS:84985995689
T3 - IEEE International Symposium on Information Theory - Proceedings
SP - 675
EP - 679
BT - Proceedings - ISIT 2016; 2016 IEEE International Symposium on Information Theory
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 2016 IEEE International Symposium on Information Theory, ISIT 2016
Y2 - 10 July 2016 through 15 July 2016
ER -