Abstract
In this paper, we propose a Barzilai–Borwein-like iterative half thresholding algorithm for the \(L_{1/2}\) regularized problem. The algorithm is closely related to the iterative reweighted minimization algorithm and the iterative half thresholding algorithm. Under mild conditions, we verify that any accumulation point of the sequence of iterates generated by the algorithm is a first-order stationary point of the \(L_{1/2}\) regularized problem. We also prove that any accumulation point is a local minimizer of the \(L_{1/2}\) regularized problem when additional conditions are satisfied. Furthermore, we show that the worst-case iteration complexity for finding an \(\varepsilon \) scaled first-order stationary point is \(O(\varepsilon ^{-2})\). Preliminary numerical results show that the proposed algorithm is practically effective.
Similar content being viewed by others
References
Barzilai, J., Borwein, J.: Two point step size gradient methods. IMA J. Numer. Anal. 8, 141–148 (1988)
Beck, A., Teboulle, M.: A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM J. Imaging Sci. 2, 183–202 (2009)
Bian, W., Chen, X., Ye, Y.: Complexity analysis of interior point algorithms for non-Lipschitz and nonconvex minimization. Math. Program. 149, 301–327 (2015)
Candès, E., Wakin, M., Boyd, S.: Enhancing sparsity by reweighted \(L_1\) minimization. J. Fourier Anal. Appl. 14, 877–905 (2008)
Chen, X., Xu, F., Ye, Y.: Lower bound theory of nonzero entries in solutions of \(\ell _2\)-\(\ell _p\) minimization. SIAM J. Sci. Comput. 32, 2832–2852 (2010)
Chen, X., Zhou, W.: Convergence of the reweighted \(L_1\) minimization algorithm for \(L_2\)-\(L_p\) minimization. Comput. Optim. Appl. 59, 47–61 (2014)
Combettes, P.L., Wajs, V.R.: Signal recovery by proximal forward–backward splitting. SIAM J. Multiscale Model. Simul. 4, 1168–1200 (2005)
Dai, Y.H.: A new analysis on the Barzilai–Borwein gradient method. J. Oper. Res. Soc. China 1, 187–198 (2013)
Daubechies, I., De Friese, M., De Mol, C.: An iterative thresholding algorithm for linear inverse problems with a sparsity constraint. Commun. Pure Appl. Math. 57, 1413–1457 (2004)
Figueiredo, M., Nowak, R., Wright, S.: Gradient projection for sparse reconstruction: application to compressed sensing and other inverse problems. IEEE J. Sel. Top. Signal. 1, 586–598 (2007)
Grippo, L., Lampariello, F., Lucidi, S.: A nonmonotone line search technique for Newton’s method. SIAM J. Numer. Anal. 23, 707–716 (1986)
Hager, W.W., Phan, D.T., Zhang, H.: Gradient-based methods for sparse recovery. SIAM J. Imaging Sci. 4, 146–165 (2011)
Hale, E., Yin, W., Zhang, Y.: Fixed-point continuation for \(\ell _1\)-minimization: methodology and convergence. SIAM J. Optim. 19, 1107–1130 (2008)
Hale, E., Yin, W., Zhang, Y.: Fixed-point continuation applied to compressed sensing: implementation and numerical experiments. J. Comput. Math. 28, 170–194 (2010)
Lai, M., Wang, J.: An unconstrained \(L_q\) minimization with \(0<q\le 1\) for sparse solution of under-determined linear systems. SIAM J. Optim. 21, 82–101 (2011)
Lai, M., Xu, Y., Yin, W.: Improved iteratively reweighted least squares for unconstrained smoothed \(L_q\) minimization. SIAM J. Numer. Anal. 51, 927–957 (2013)
Li, D.H., Wu, L., Sun, Z., Zhang, X.J.: A constrained optimization reformulation and a feasible descent direction method for \(L_{1/2}\) regularization. Comput. Optim. Appl. 59, 263–284 (2014)
Lu, Z.: Iterative reweighted minimization methods for \(L_p\) regularized unconstrained nonlinear programming. Math. Program. 147, 277–307 (2014)
Raydan, M.: The Barzilai and Borwein gradient method for the large scale unconstrained minimization problem. SIAM J. Optim. 7, 26–33 (1997)
Wright, S.J., Nowak, R., Figueiredo, M.: Sparse reconstruction by separable approximation. IEEE Trans. Signal Process. 57, 2479–2493 (2009)
Wu, L., Sun, Z., Li, D.H.: Gradient based method for the \(L_2\)-\(L_{1/2}\) minimization and application to compressive sensing. Pac. J. Optim. 10, 401–414 (2014)
Xu, Z., Chang, X., Xu, F., Zhang, H.: \(L_{1/2}\) regularization: a thresholding representation theory and a fast solver. IEEE Trans. Neural Netw. Learn. Syst. 23, 1013–1027 (2012)
Xu, Z., Zhang, H., Wang, Y., Chang, X.: \(L_{1/2}\) regularizer. Sci. China Ser. F 52, 1–9 (2009)
Zeng, J., Lin, S., Wang, Y., Xu, Z.: \(L_{1/2}\) regularization: convergence of iterative half thresholding algorithm. IEEE Trans. Signal Process. 62, 2317–2329 (2014)
Acknowledgments
The authors would like to thank two anonymous referees for their valuable suggestions and comments.
Author information
Authors and Affiliations
Corresponding author
Additional information
The work was supported by the National Nature Science Foundation of P.R. China (No. 11501265, 11201197 and 11371154), the Nature Science Foundation of Jiangxi (No. 20132BAB211011), and the Foundation of Department of Education Jiangxi Province (No. GJJ13204).
Rights and permissions
About this article
Cite this article
Wu, L., Sun, Z. & Li, DH. A Barzilai–Borwein-Like Iterative Half Thresholding Algorithm for the \(L_{1/2}\) Regularized Problem. J Sci Comput 67, 581–601 (2016). https://doi.org/10.1007/s10915-015-0094-4
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10915-015-0094-4
Keywords
- \(L_{1/2}\) regularized problem
- Sparse optimization
- Prox-linear algorithms
- Barzilai–Borwein steplength
- Iterative half thresholding algorithm