Abstract
The iteratively reweighted ℓ 1 minimization algorithm (IRL1) has been widely used for variable selection, signal reconstruction and image processing. In this paper, we show that any sequence generated by the IRL1 is bounded and any accumulation point is a stationary point of the ℓ 2–ℓ p minimization problem with 0<p<1. Moreover, the stationary point is a global minimizer and the convergence rate is approximately linear under certain conditions. We derive posteriori error bounds which can be used to construct practical stopping rules for the algorithm.
Similar content being viewed by others
References
Bian, W., Chen, X.: Smoothing neural network for constrained non-Lipschitz optimization with applications. IEEE Trans. Neural Netw. 23, 399–411 (2012)
Byrd, R.H., Chin, G.M., Nocedal, J., Wu, Y.: Sample size selection in optimization methods for machine learning. Math. Program. 134, 127–155 (2012)
Candès, E., Wakin, M., Boyd, S.: Enhancing sparsity by reweighted l 1 minimization. J. Fourier Anal. Appl. 14, 877–905 (2008)
Chartrand, R.: Exact reconstruction of sparse signals via nonconvex minimization. IEEE Signal Process. Lett. 14, 707–710 (2007)
Chartrand, R., Staneva, V.: Restricted isometry properties and nonconvex compressive sensing. Inverse Probl. 24, 1–14 (2008)
Chartrand, R., Yin, W.: Iteratively reweighted algorithms for compressive sensing. In: ICASSP 2008, March 2008, pp. 3869–3872 (2008)
Chen, X.: Smoothing methods for nonsmooth, nonconvex minimization. Math. Program. 134, 71–99 (2012)
Chen, X., Zhou, W.: Convergence of reweighted l 1 minimization algorithms and unique solution of truncated l p minimization, Department of Applied Mathematics, The Hong Kong Polytechnic University (2010)
Chen, X., Xu, F., Ye, Y.: Lower bound theory of nonzero entries in solutions of l 2–l p minimization. SIAM J. Sci. Comput. 32, 2832–2852 (2010)
Chen, X., Ng, M., Zhang, C.: Nonconvex l p regularization and box constrained model for image restoration. IEEE Trans. Image Process. 21, 4709–4721 (2012)
Chen, X., Niu, L., Yuan, Y.: Optimality conditions and smoothing trust region Newton method for non-Lipschitz optimization, Department of Applied Mathematics, The Hong Kong Polytechnic University (2012)
Chen, X., Ge, D., Wang, Z., Ye, Y.: Complexity of unconstrained L 2-L p minimization. Math. Program. doi:10.1007/s10107-012-0613-0
Clarke, F.H.: Optimization and Nonsmooth Analysis. Wiley, New York (1983)
Donoho, D.L., Tsaig, Y.: Fast solution of l 1-norm minimization problems when the solution may be sparse. IEEE Trans. Inf. Theory 54, 4789–4812 (2008)
Figueiredo, M.A.T., Bioucas-Dias, J.M., Nowak, R.D.: Majorization-minimization algorithms for wavelet-based image restoration. IEEE Trans. Image Process. 16, 2980–2991 (2007)
Foucart, S., Lai, M.J.: Sparsest solutions of under-determined linear systems via l q minimization for 0<q≤1. Appl. Comput. Harmon. Anal. 26, 395–407 (2009)
Fukushima SOR, M.: Jacobi-type iterative methods for solving ℓ 1–ℓ 2 problems by way of Fenchel duality. Optim. Lett. 6, 679–686 (2012)
Ge, D., Jiang, X., Ye, Y.: A note on complexity of L p minimization. Math. Program. 129, 285–299 (2011)
Huang, J., Horowitz, J.L., Ma, S.: Asymptotic properties of bridge estimators in sparse high-dimensional regression models. Ann. Stat. 36, 587–613 (2008)
Lai, M., Wang, Y.: An unconstrained l q minimization with 0<q<1 for sparse solution of under-determined linear systems. SIAM J. Optim. 21, 82–101 (2011)
Marechal, P., Ye, J.: Optimizing condition numbers. SIAM J. Optim. 20, 935–947 (2009)
Nikolova, M.: Analysis of the recovery of edges in images and signals by minimizing nonconvex regularized least-squares. Multiscale Model. Simul. 4, 960–991 (2005)
Nikolova, M., Ng, M.K., Zhang, S., Ching, W.: Efficient reconstruction of piecewise constant images using nonsmooth nonconvex minimization. SIAM J. Imaging Sci. 1, 2–25 (2008)
Nocedal, J.: Second-order methods for stochastic, semi-smooth and nonlinear programming. In: Plenary Lecture, International Symposium on Mathematical Programming, Berlin (2012)
Wang, Y., Yin, W.: Sparse signal reconstruction via iterative support detection. SIAM J. Imaging Sci. 3, 462–491 (2010)
Xu, Z., Zhang, H., Wang, Y., Chang, X.: \(L_{\frac{1}{2}}\) regularization. Sci. China Inf. Sci. 53, 1159–1169 (2010)
Acknowledgements
We would like to thank the two referees for their very helpful comments and suggestions.
Author information
Authors and Affiliations
Corresponding author
Additional information
This paper is dedicated to Professor Masao Fukushima on the occasion of his 65th birthday.
The first author’s work was supported in part by the Hong Kong Research Grant Council, the second author’s work was supported by the NSF foundation (10901026) of China and the Key Project of the Scientific Research Fund (12A004) of the Hunan Provincial Education Department.
Rights and permissions
About this article
Cite this article
Chen, X., Zhou, W. Convergence of the reweighted ℓ 1 minimization algorithm for ℓ 2–ℓ p minimization. Comput Optim Appl 59, 47–61 (2014). https://doi.org/10.1007/s10589-013-9553-8
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10589-013-9553-8