Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Iterative reweighted minimization methods for \(l_p\) regularized unconstrained nonlinear programming

  • Full Length Paper
  • Series A
  • Published:
Mathematical Programming Submit manuscript

Abstract

In this paper we study general \(l_p\) regularized unconstrained minimization problems. In particular, we derive lower bounds for nonzero entries of the first- and second-order stationary points and hence also of local minimizers of the \(l_p\) minimization problems. We extend some existing iterative reweighted \(l_1\) (\(\mathrm{IRL}_1\)) and \(l_2\) (\(\mathrm{IRL}_2\)) minimization methods to solve these problems and propose new variants for them in which each subproblem has a closed-form solution. Also, we provide a unified convergence analysis for these methods. In addition, we propose a novel Lipschitz continuous \({\epsilon }\)-approximation to \(\Vert x\Vert ^p_p\). Using this result, we develop new \(\mathrm{IRL}_1\) methods for the \(l_p\) minimization problems and show that any accumulation point of the sequence generated by these methods is a first-order stationary point, provided that the approximation parameter \({\epsilon }\) is below a computable threshold value. This is a remarkable result since all existing iterative reweighted minimization methods require that \({\epsilon }\) be dynamically updated and approach zero. Our computational results demonstrate that the new \(\mathrm{IRL}_1\) method and the new variants generally outperform the existing \(\mathrm{IRL}_1\) methods (Chen and Zhou in 2012; Foucart and Lai in Appl Comput Harmon Anal 26:395–407, 2009).

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Barzilai, J., Borwein, J.M.: Two point step size gradient methods. IMA J. Numer. Anal. 8, 141–148 (1988)

    Article  MathSciNet  MATH  Google Scholar 

  2. Beck, A., Teboulle, M.: A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM J. Imaging Sci. 2, 183–202 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  3. Bian, W., Chen, X.: Smoothing SQP algorithm for non-Lipschitz optimization with complexity analysis. Preprint, February (2012)

  4. Bian, W., Chen, X., Ye, Y.: Complexity analysis of interior point algorithms for non-Lipschitz and nonconvex minimization. Preprint, July (2012)

  5. Birgin, E.G., Martínez, J.M., Raydan, M.: Nonmonotone spectral projected gradient methods on convex sets. SIAM J. Optim. 4, 1196–1211 (2000)

    Article  Google Scholar 

  6. Blumensath, T., Davies, M.E.: Iterative hard thresholding for compressed sensing. Appl. Comput. Harmon. Anal. 27(3), 265–274 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  7. Candés, E.J., Romberg, J., Tao, T.: Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information. IEEE Trans. Inf. Theory 52, 489–509 (2006)

    Article  MATH  Google Scholar 

  8. Candès, E., Tao, T.: Decoding by linear programming. IEEE Trans. Inf. Theory 51(12), 4203–4215 (2005)

    Article  MATH  Google Scholar 

  9. Candès, E., Wakin, M., Boyd, S.: Enhancing sparsity by reweighted \(l_1\) minimization. J. Fourier Anal. Appl. 14, 877–905 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  10. Chartrand, R.: Exact reconstruction of sparse signals via nonconvex minimization. IEEE Signal Process. Lett. 14, 707–710 (2007)

    Article  Google Scholar 

  11. Chartrand, R., Staneva, V.: Restricted isometry properties and nonconvex compressive sensing. Inverse Probl. 24, 1–14 (2008)

    Article  MathSciNet  Google Scholar 

  12. Chartrand, R., Yin, W.: Iteratively reweighted algorithms for compressive sensing. In: 33rd International Conference on Acoustics, Speech, and Signal Processing (ICASSP) (2008)

  13. Chen, S., Donoho, D., Saunders, M.: Atomic decomposition by basis pursuit. SIAM J. Sci. Comput. 20, 33–61 (1998)

    Article  MathSciNet  Google Scholar 

  14. Chen, X., Ge, D., Wang, Z., Ye, Y.: Complexity of unconstrained \(L_2\)-\(L_p\) minimization. Submitted to Math. Program, May 2011

  15. Chen, X., Niu, L., Yuan, Y.: Optimality conditions and smoothing trust region Newton method for non-Lipschitz optimization. Preprint, March (2012)

  16. 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)

    Article  MathSciNet  MATH  Google Scholar 

  17. Chen, X., Zhou, W.: Convergence of reweighted \(l_1\) minimization algorithms and unique solution of truncated \(l_p\) minimization. Preprint, April 2010

  18. Clarke, F.H.: Optimization and Nonsmooth Analysis. Wiley, New York (1983)

    MATH  Google Scholar 

  19. Daubechies, I., DeVore, R., Fornasier, M., Gunturk, C.S.: Iteratively reweighted least squares minimization for sparse recovery. Commun. Pure. Appl. Math. 63, 1–38 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  20. Foucart, S., Lai, M.: Sparsest solutions of underdetermined linear systems via \(l_q\)-minimization for \(0 < q \le 1\). Appl. Comput. Harmon. Anal. 26, 395–407 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  21. Ge, D., Jiang, X., Ye, Y.: A note on the complexity of \(L_p\) minimization. Math. Program. 21, 1721–1739 (2011)

    MathSciNet  Google Scholar 

  22. Hale, E.T., Yin, W., Zhang, Y.: Fixed-point continuation applied to compressed sensing: Implementation and numerical experiments. J. Comput. Math 28(2), 170–194 (2010)

    MathSciNet  MATH  Google Scholar 

  23. Herrity, K.K., Gilbert, A.C., Tropp, J.A.: Sparse approximation via iterative thresholding. IEEE Int. Conf. Acoust. Speech Signal Processing (2006)

  24. Koh, K., Kim, S.J., Boyd, S.: An interior-point method for large-scale \(l_1\)-regularized logistic regression. J. Mach. Learn. Res. 8, 1519–1555 (2007)

    MathSciNet  MATH  Google Scholar 

  25. Lai, M., Wang, J.: An unconstrained \(l_q\) minimization with \(0<q \le 1\) for sparse solution of underdetermined linear systems. SIAM J. Optim. 21, 82–101 (2010)

    Article  MathSciNet  Google Scholar 

  26. Lu, Z., Zhang, Y.: Sparse approximation via penalty decomposition methods. SIAM J. Optim. (to appear) (2013)

  27. Mourad, N., Reilly, J.P.: Minimizing nonconvex functions for sparse vector reconstruction. IEEE Trans. Signal Process. 58, 3485–3496 (2010)

    Article  MathSciNet  Google Scholar 

  28. Rao, B.D., Kreutz-Delgado, K.: An affine scaling methodology for best basis selection. IEEE Trans. Signal Process. 47, 187–200 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  29. Sun, Q.: Recovery of sparsest signals via \(l_q\) minimization. Appl. Comput. Harmon. Anal. 32, 329–341 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  30. Tibshirani, R.: Regression shrinkage and selection via the lasso. J. R. Stat. Soc. B 58(1), 267–288 (1996)

    MathSciNet  MATH  Google Scholar 

  31. Van Den Berg, E., Friedlander, M.P.: Probing the Pareto frontier for basis pursuit solutions. SIAM J. Sci. Comput. 31(2), 890–912 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  32. Wright, S.J., Nowak, R., Figueiredo, M.: Sparse reconstruction by separable approximation. IEEE T. Image Process. 57, 2479–2493 (2009)

    MathSciNet  Google Scholar 

  33. Xu, Z., Zhang, H., Wang, Y., Chang, X.: \(L_{\frac{1}{2}}\) regularizer. Sci. China 52, 1–9 (2009)

    Google Scholar 

  34. Yun, S., Toh, K.-C.: A coordinate gradient descent method for \(l_1\)-regularized convex minimization. Comput. Optim. Appl. 48, 273–307 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  35. Zhao, Y., Li, D.: Reweighted \(l_1\)-minimization for sparse solutions to underdetermined linear systems. SIAM J. Optim. 22, 1065–1088 (2012)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics, Simon Fraser University, Burnaby, BC , V5A 1S6, Canada

    Zhaosong Lu

Authors
  1. Zhaosong Lu
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Zhaosong Lu.

Additional information

This work was supported in part by NSERC Discovery Grant. Part of this work was conducted during the author’s sabbatical leave in the Department of Industrial and Systems Engineering at Texas A&M University. The author would like to thank them for hosting his visit.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Lu, Z. Iterative reweighted minimization methods for \(l_p\) regularized unconstrained nonlinear programming. Math. Program. 147, 277–307 (2014). https://doi.org/10.1007/s10107-013-0722-4

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10107-013-0722-4

Keywords

Search

Navigation