×

Split Bregman method for large scale fused Lasso. (English) Zbl 1328.65048

Summary: Ordering of regression or classification coefficients occurs in many real-world applications. Fused Lasso exploits this ordering by explicitly regularizing the differences between neighboring coefficients through an \(\ell _{1}\) norm regularizer. However, due to nonseparability and nonsmoothness of the regularization term, solving the fused Lasso problem is computationally demanding. Existing solvers can only deal with problems of small or medium size, or a special case of the fused Lasso problem in which the predictor matrix is the identity matrix. In this paper, we propose an iterative algorithm based on the split Bregman method to solve a class of large-scale fused Lasso problems, including a generalized fused Lasso and a fused Lasso support vector classifier. We derive our algorithm using an augmented Lagrangian method and prove its convergence properties. The performance of our method is tested on both artificial data and real-world applications including proteomic data from mass spectrometry and genomic data from array comparative genomic hybridization (array CGH). We demonstrate that our method is many times faster than the existing solvers, and show that it is especially efficient for large \(p\), small \(n\) problems, where \(p\) is the number of variables and \(n\) is the number of samples.

MSC:

65C60 Computational problems in statistics (MSC2010)
62J07 Ridge regression; shrinkage estimators (Lasso)
62H30 Classification and discrimination; cluster analysis (statistical aspects)
62J05 Linear regression; mixed models

Software:

CVX
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Ahmed, A.; Xing, E. P., Recovering time-varying networks of dependencies in social and biological studies, Proceedings of the National Academy of Sciences, 106, 29, 11878 (2009)
[2] Bredel, M.; Bredel, C.; Juric, D.; Harsh, G. R.; Vogel, H.; Recht, L. D.; Sikic, B. I., High-resolution genome-wide mapping of genetic alterations in human glial brain tumors, Cancer Research, 65, 10, 4088 (2005)
[3] Brègman, L. M., A relaxation method of finding a common point of convex sets and its application to the solution of problems in convex programming, Zhurnal Vychislitel’noi Matematiki i Matematicheskoi Fiziki, 7, 620-631 (1967) · Zbl 0186.23807
[4] Cai, J.-F.; Candès, E. J.; Shen, Z., A singular value thresholding algorithm for matrix completion, SIAM Journal on Optimization, 20, 4, 1956-1982 (2010) · Zbl 1201.90155
[5] Cai, J.-F.; Osher, S.; Shen, Z., Split Bregman methods and frame based image restoration, Multiscale Modeling and Simulation, 8, 2, 337-369 (2009) · Zbl 1189.94014
[6] Cai, J.-F.; Osher, S.; Shen, Z., Linearized Bregman iterations for compressed sensing, Mathematics of Computation, 78, 267, 1515-1536 (2009) · Zbl 1198.65102
[8] Ceccarelli, M.; d’Acierno, A.; Facchiano, A., A scale space approach for unsupervised feature selection in mass spectra classification for ovarian cancer detection, BMC Bioinformatics, 10, Suppl. 12, S9 (2009)
[9] Çetin, A. E., Reconstruction of signals from Fourier transform samples, Signal Processing, 16, 2, 129-148 (1989)
[10] Eckstein, J.; Bertsekas, D. P., On the Douglas Rachford splitting method and the proximal point algorithm for maximal monotone operators, Mathematical Programming, 55, 1, 293-318 (1992) · Zbl 0765.90073
[12] Friedman, J.; Hastie, T.; Höfling, H.; Tibshirani, R., Pathwise coordinate optimization, The Annals of Applied Statistics, 1, 2, 302-332 (2007) · Zbl 1378.90064
[13] Gabay, D.; Mercier, B., A dual algorithm for the solution of nonlinear variational problems via finite element approximation, Computers and Mathematics with Applications, 2, 1, 17-40 (1976) · Zbl 0352.65034
[14] Gao, H.; Zhao, H., Multilevel bioluminescence tomography based on radiative transfer equation part 1: l1 regularization, Optics Express, 18, 3, 1854-1871 (2010)
[16] Goldstein, T.; Osher, S., The split Bregman method for \(L 1\)-regularized problems, SIAM Journal on Imaging Sciences, 2, 2, 323-343 (2009) · Zbl 1177.65088
[18] Hestenes, M. R., Multiplier and gradient methods, Journal Optimization Theory & Applications, 4, 303-320 (1969) · Zbl 0174.20705
[19] Hiriart-Urruty, J. B.; Lemaréchal, C., Convex Analysis and Minimization Algorithms (1993), Springer-Verlag: Springer-Verlag Berlin · Zbl 0795.49001
[21] Kim, S.; Sohn, K. A.; Xing, E. P., A multivariate regression approach to association analysis of a quantitative trait network, Bioinformatics, 25, 12, i204 (2009)
[22] Osher, S.; Burger, M.; Goldfarb, D.; Xu, J.; Yin, W., An iterative regularization method for total variation-based image restoration, Multiscale Modeling and Simulation, 4, 2, 460-489 (2005), (electronic) · Zbl 1090.94003
[23] Osher, S.; Mao, Y.; Dong, B.; Yin, W., Fast linearized Bregman iteration for compressive sensing and sparse denoising, Communications in Mathematical Sciences, 8, 2, 93-111 (2010) · Zbl 1190.49040
[25] Rockafellar, R. T., A dual approach to solving nonlinear programming problems by unconstrained optimization, Mathematical Programming, 5, 354-373 (1973) · Zbl 0279.90035
[26] Rockafellar, R. Tyrrell, (Convex Analysis. Convex Analysis, Princeton Landmarks in Mathematics (1997), Princeton University Press: Princeton University Press Princeton, NJ), Reprint of the 1970 original, Princeton Paperbacks · Zbl 0311.49006
[27] Rosset, S.; Zhu, J., Piecewise linear regularized solution paths, Annals of Statistics, 35, 3, 1012 (2007) · Zbl 1194.62094
[28] Saad, Y., Iterative Methods for Sparse Linear Systems (2003), Society for Industrial Mathematics · Zbl 1002.65042
[29] Setzer, S., Split Bregman algorithm, Douglas-Rachford splitting and frame shrinkage, (Scale Space and Variational Methods in Computer Vision (2009)), 464-476
[30] Tibshirani, R.; Saunders, M.; Rosset, S.; Zhu, J.; Knight, K., Sparsity and smoothness via the fused lasso, Journal of the Royal Statistical Society: Series B (Statistical Methodology), 67, 1, 91-108 (2005) · Zbl 1060.62049
[31] Tibshirani, R.; Wang, P., Spatial smoothing and hot spot detection for CGH data using the fused lasso, Biostatistics, 9, 18-29 (2008) · Zbl 1274.62886
[32] Tseng, P., Convergence of a block coordinate descent method for nondifferentiable minimization, Journal of Optimization Theory and Applications, 109, 3, 475-494 (2001) · Zbl 1006.65062
[33] Vapnik, V. N., (Statistical Learning Theory. Statistical Learning Theory, Adaptive and Learning Systems for Signal Processing, Communications, and Control (1998), John Wiley & Sons Inc.: John Wiley & Sons Inc. New York), A Wiley-Interscience Publication · Zbl 0935.62007
[34] Wu, C.; Tai, X. C., Augmented Lagrangian method, dual methods, and split Bregman iteration for ROF, vectorial TV, and high order models, SIAM Journal on Imaging Sciences, 3, 300 (2010) · Zbl 1206.90245
[35] Yin, W.; Osher, S.; Goldfarb, D.; Darbon, J., Bregman iterative algorithms for \(l_1\)-minimization with applications to compressed sensing, SIAM Journal on Imaging Sciences, 1, 1, 143-168 (2008) · Zbl 1203.90153
[36] Zhang, X.; Burger, M.; Bresson, X.; Osher, S., Bregmanized nonlocal regularization for deconvolution and sparse reconstruction, SIAM Journal on Imaging Sciences, 3, 253-276 (2010) · Zbl 1191.94030
[37] Zhang, X.; Burger, M.; Osher, S., A unified primal-dual algorithm framework based on Bregman iteration, Journal of Scientific Computing (2010)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.