TY - JOUR
T1 - Analysis and Algorithms for Some Compressed Sensing Models Based on L1/L2 Minimization
AU - Zeng, Liaoyuan
AU - Yu, Peiran
AU - Pong, Ting Kei
N1 - Funding Information:
\ast Received by the editors July 24, 2020; accepted for publication (in revised form) April 15, 2021; published electronically June 22, 2021. https://doi.org/10.1137/20M1355380 Funding: The work of the first author was partially supported by the AMSS-PolyU Joint Laboratory Postdoctoral Scheme. The work of the third author was partially supported by Hong Kong Research Grants Council grant PolyU153003/19p. \dagger Department of Applied Mathematics, Hong Kong Polytechnic University, Hong Kong, People's Republic of China (zengly@lsec.cc.ac.cn, peiran.yu@connect.polyu.hk, tk.pong@polyu.edu.hk).
Publisher Copyright:
© 2021 Society for Industrial and Applied Mathematics
PY - 2021/6
Y1 - 2021/6
N2 - Recently, in a series of papers [Y. Rahimi, C. Wang, H. Dong, and Y. Lou, SIAM J. Sci. Comput., 41 (2019), pp. A3649-A3672; C. Wang, M. Tao, J. Nagy, and Y. Lou, SIAM J. Imaging Sci., 14 (2021), pp. 749-777; C. Wang, M. Yan, and Y. Lou, IEEE Trans. Signal Process., 68 (2020), pp. 2660-2669; P. Yin, E. Esser, and J. Xin, Commun. Inf. Syst., 14 (2014), pp. 87-109], the ratio of \ell
1 and \ell
2 norms was proposed as a sparsity inducing function for noiseless compressed sensing. In this paper, we further study properties of such model in the noiseless setting, and propose an algorithm for minimizing \ell
1/\ell
2 subject to noise in the measurements. Specifically, we show that the extended objective function (the sum of the objective and the indicator function of the constraint set) of the model in [Y. Rahimi, C. Wang, H. Dong, and Y. Lou, SIAM J. Sci. Comput., 41 (2019), pp. A3649-A3672] satisfies the Kurdyka-\ Lojasiewicz (KL) property with exponent 1/2; this allows us to establish linear convergence of the algorithm proposed in [C. Wang, M. Yan, and Y. Lou, IEEE Trans. Signal Process., 68 (2020), pp. 2660-2669] (see equation 11) under mild assumptions. We next extend the \ell
1/\ell
2 model to handle compressed sensing problems with noise. We establish the solution existence for some of these models under the spherical section property [S. A. Vavasis, Derivation of Compressive Sensing Theorems from the Spherical Section Property, University of Waterloo, 2009; Y. Zhang, J. Oper. Res. Soc. China, 1 (2013), pp. 79-105] and extend the algorithm in [C. Wang, M. Yan, and Y. Lou, IEEE Trans. Signal Process., 68 (2020), pp. 2660-2669] (see equation 11) by incorporating moving-balls-approximation techniques [A. Auslender, R. Shefi, and M. Teboulle, SIAM J. Optim., 20 (2010), pp. 3232-3259] for solving these problems. We prove the subsequential convergence of our algorithm under mild conditions and establish global convergence of the whole sequence generated by our algorithm by imposing additional KL and differentiability assumptions on a specially constructed potential function. Finally, we perform numerical experiments on robust compressed sensing and basis pursuit denoising with residual error measured by \ell
2 norm or Lorentzian norm via solving the corresponding \ell
1/\ell
2 models by our algorithm. Our numerical simulations show that our algorithm is able to recover the original sparse vectors with reasonable accuracy.
AB - Recently, in a series of papers [Y. Rahimi, C. Wang, H. Dong, and Y. Lou, SIAM J. Sci. Comput., 41 (2019), pp. A3649-A3672; C. Wang, M. Tao, J. Nagy, and Y. Lou, SIAM J. Imaging Sci., 14 (2021), pp. 749-777; C. Wang, M. Yan, and Y. Lou, IEEE Trans. Signal Process., 68 (2020), pp. 2660-2669; P. Yin, E. Esser, and J. Xin, Commun. Inf. Syst., 14 (2014), pp. 87-109], the ratio of \ell
1 and \ell
2 norms was proposed as a sparsity inducing function for noiseless compressed sensing. In this paper, we further study properties of such model in the noiseless setting, and propose an algorithm for minimizing \ell
1/\ell
2 subject to noise in the measurements. Specifically, we show that the extended objective function (the sum of the objective and the indicator function of the constraint set) of the model in [Y. Rahimi, C. Wang, H. Dong, and Y. Lou, SIAM J. Sci. Comput., 41 (2019), pp. A3649-A3672] satisfies the Kurdyka-\ Lojasiewicz (KL) property with exponent 1/2; this allows us to establish linear convergence of the algorithm proposed in [C. Wang, M. Yan, and Y. Lou, IEEE Trans. Signal Process., 68 (2020), pp. 2660-2669] (see equation 11) under mild assumptions. We next extend the \ell
1/\ell
2 model to handle compressed sensing problems with noise. We establish the solution existence for some of these models under the spherical section property [S. A. Vavasis, Derivation of Compressive Sensing Theorems from the Spherical Section Property, University of Waterloo, 2009; Y. Zhang, J. Oper. Res. Soc. China, 1 (2013), pp. 79-105] and extend the algorithm in [C. Wang, M. Yan, and Y. Lou, IEEE Trans. Signal Process., 68 (2020), pp. 2660-2669] (see equation 11) by incorporating moving-balls-approximation techniques [A. Auslender, R. Shefi, and M. Teboulle, SIAM J. Optim., 20 (2010), pp. 3232-3259] for solving these problems. We prove the subsequential convergence of our algorithm under mild conditions and establish global convergence of the whole sequence generated by our algorithm by imposing additional KL and differentiability assumptions on a specially constructed potential function. Finally, we perform numerical experiments on robust compressed sensing and basis pursuit denoising with residual error measured by \ell
2 norm or Lorentzian norm via solving the corresponding \ell
1/\ell
2 models by our algorithm. Our numerical simulations show that our algorithm is able to recover the original sparse vectors with reasonable accuracy.
KW - Kurdyka-Lojasiewicz exponent
KW - L1/L2 minimization
KW - Linear convergence
KW - Moving balls approximation
UR - http://www.scopus.com/inward/record.url?scp=85109456347&partnerID=8YFLogxK
U2 - https://doi.org/10.1137/20M1355380
DO - https://doi.org/10.1137/20M1355380
M3 - Journal article
SN - 1052-6234
VL - 31
SP - 1576
EP - 1603
JO - SIAM Journal on Optimization
JF - SIAM Journal on Optimization
IS - 2
ER -