Properties and iterative methods for the lasso and its variants

Abstract

The lasso of Tibshirani (1996) is a least-squares problem regularized by the ℓ ₁ norm. Due to the sparseness promoting property of the ℓ ₁ norm, the lasso has been received much attention in recent years. In this paper some basic properties of the lasso and two variants of it are exploited. Moreover, the proximal method and its variants such as the relaxed proximal algorithm and a dual method for solving the lasso by iterative algorithms are presented.

Keywords

Lasso / Elastic net / Smooth-lasso / ℓ ₁ regularization / Sparsity / Proximal method / Dual method / Projection / Thresholding

References

[1] Candes E J, Romberg J, Tao T. Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information. IEEE Trans. Inform. Theory, 2006, 52(2): 489-509

[2] Candes E J, Romberg J, Tao T. Stable signal recovery from incomplete and inaccurate measurements. Comm. Pure Applied Math., 2006, 59(2): 1207-1223

[3] Candes E J, Tao T. Near-optimal signal recovery from random projections: Universal encoding strategies?. IEEE Trans. Inform. Theory, 2006, 52(12): 5406-5425

[4] Candes E J, Wakin M B. An introduction to compressive sampling. IEEE Signal Processing Magazine, 2008 21-30

[5] SIAM News, 2006, 39 9

[6] Combettes P L, Wajs R. Signal recovery by proximal forward-backward splitting. Multiscale Model. Simul., 2005, 4(4): 1168-1200

[7] Donoho D. Compressed sensing. IEEE Trans. Inform. Theory, 2006, 52(4): 1289-1306

[8] Friedman, J., Hastie, T. and Tibshirani, R., A note on the group lasso and a sparse group lasso, arXiv:1001.0736V1.

[9] Geobel K, Kirk W A. Topics in Metric Fixed Point Theory. Cambridge Studies in Advanced Mathematics, Vol. 28, 1990

[10] Hebiri M, van de Geer S. The smooth-lasso and other ℓ ₁+ℓ ₂-penalized methods. Electron. J. Statist., 2011, 5: 1184-1226

[11] Marino G, Xu H K. Convergence of generalized proximal point algorithms. Comm. Pure Appl. Anal., 2004, 3(3): 791-808

[12] Micchelli C A, Shen L, Xu Y. Proximity algorithms for image models: Denoising. Inverse Problems, 2011, 27: 045009

[13] Moreau J J. Proprietes des applications “prox”. C. R. Acad. Sci. Paris Ser. A Math., 1963, 256: 1069-1071

[14] Moreau J J. Proximite et dualite dans un espace hilbertien. Bull. Soc. Math. France, 1965, 93: 272-299

[15] Raasch T. On the L-curve criterion in ℓ ₁ regularization of linear discrete ill-posed problems. International Conference on Inverse Problems and Related Topics, Nanjing, 2012

[16] Tibshirani R. Regression shrinkage and selection via the lasso. J. Royal Statist. Soc. Ser. B, 1996, 58: 267-288

[17] Tibshirani R, Saunders M, Rosset R Sparsity and smoothness via the fused lasso. J. Royal Statist. Soc., Ser. B, 2005, 67: 91-108

[18] Xu H K. Averaged mappings and the gradient-projection algorithm. J. Optim. Theory Appl., 2011, 150: 360-378

[19] Yuan M, Lin Y. Model selection and estimation in regression with grouped variables. J. Royal Statist. Soc., Ser. B, 2006, 68: 49-67

[20] Zou H, Hastie T. Regularization and variable selection via the elastic net. J. Royal Statist. Soc., Ser. B, 2005, 67: 301-320