×

Finding Dantzig selectors with a proximity operator based fixed-point algorithm. (English) Zbl 1468.62160

Summary: A simple iterative method for finding the Dantzig selector, designed for linear regression problems, is introduced. The method consists of two stages. The first stage approximates the Dantzig selector through a fixed-point formulation of solutions to the Dantzig selector problem; the second stage constructs a new estimator by regressing data onto the support of the approximated Dantzig selector. The proposed method is compared to an alternating direction method. The results of numerical simulations using both the proposed method and the alternating direction method on synthetic and real-world data sets are presented. The numerical simulations demonstrate that the two methods produce results of similar quality; however the proposed method tends to be significantly faster.

MSC:

62-08 Computational methods for problems pertaining to statistics
62J05 Linear regression; mixed models

Software:

TFOCS
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Bauschke, H. L.; Combettes, P. L., (Convex Analysis and Monotone Operator Theory in Hilbert Spaces, AMS Books in Mathematics, (2011), Springer New York) · Zbl 1218.47001
[2] Beck, A.; Teboulle, M., A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM J. Imaging Sci., 2, 183-202, (2009) · Zbl 1175.94009
[3] Becker, S.; Candes, E.; Grant, M., Templates for convex cone problems with applications to sparse signal recovery, Math. Program. Comput., 3, 165-218, (2010) · Zbl 1257.90042
[4] Bickel, P. J., Discussion: the Dantzig selector: statistical estimation when \(p\) is much larger than \(n\), Ann. Statist., 35, 2352-2357, (2007)
[5] Boyd, S.; Vandenberghe, L., Convex optimization, (2004), Cambridge University Press · Zbl 1058.90049
[6] Cai, T.; Lv, J., Discussion: the Dantzig selector: statistical estimation when \(p\) is much larger than \(n\), Ann. Statist., 35, 2365-2369, (2007)
[7] Candes, E.; Tao, T., Rejoinder: the Dantzig selector: statistical estimation when \(p\) is much larger than \(n\), Ann. Statist., 35, 2392-2404, (2007) · Zbl 1139.62019
[8] Candes, E.; Tao, T., The Dantzig selector: statistical estimation when \(p\) is much larger than \(n\), Ann. Statist., 35, 2313-2351, (2007) · Zbl 1139.62019
[9] Chambolle, A.; Pock, T., A first-order primal-dual algorithm for convex problems with applications to imaging, J. Math. Imaging Vision, 40, 120-145, (2011) · Zbl 1255.68217
[10] Dicker, L.; Lin, X., Parallelism, uniqueness, and large-sample asymptotics for the Dantzig selector, Canad. J. Statist., 4, 23-51, (2013) · Zbl 1348.62192
[11] Efron, B.; Hastie, T.; Johnstone, I.; Tibshirani, R., Least angle regression, Ann. Statist., 32, 407-451, (2004) · Zbl 1091.62054
[12] Efron, B.; Hastie, T.; Tibshirani, R., Discussion: the Dantzig selector: statistical estimation when \(p\) is much larger than \(n\), Ann. Statist., 35, 2358-2364, (2007)
[13] Esser, E.; Zhang, X.; Chan, T. F., A general framework for a class of first order primal-dual algorithms for convex optimization in imaging science, SIAM J. Imaging Sci., 3, 1015-1046, (2010) · Zbl 1206.90117
[14] Friedlander, M. P.; Saunders, M. A., Discussion: the Dantzig selector: statistical estimation when \(p\) is much larger than \(n\), Ann. Statist., 35, 2385-2391, (2007)
[15] Golub, T. R.; Slonim, D. K.; Tamayo, P.; Huard, C.; Gaasenbeek, M.; Mesirov, J. P.; Coller, H.; Loh, M. L.; Downing, J. R.; Caliguiri, M. A.; Bloomfield, C. D.; Lander, E. S., Molecular classification of cancer: class discovery and class prediction by gene expression monitoring, Science, 286, 531-537, (1999)
[16] James, G.; Radchenko, P.; Lv, J., DASSO: connections between the Dantzig selector and LASSO, J. R. Stat. Soc. Ser. B, 71, 127-142, (2009) · Zbl 1231.62129
[17] Li, Y.; Dicker, L.; Zhao, S., The Dantzig selector for censored linear regression models, Statist. Sinica, 24, 251-268, (2014) · Zbl 1285.62075
[18] Li, Q.; Micchelli, C. A.; Shen, L.; Xu, Y., A proximity algorithm accelerated by Gauss-Seidel iterations for \(\operatorname{L1/TV}\) denoising models, Inverse Problems, 28, 095003, (2012) · Zbl 1273.65085
[19] Lu, Z.; Pong, T. P.; Zhang, Y., An alternating direction for finding Dantzig selectors, Comput. Statist. Data Anal., 56, 4037-4046, (2012) · Zbl 1255.62096
[20] Lu, Z.; Zhang, Y., An augumented Lagrangian approach for sparse principle component analysis, Math. Program., 135, 149-193, (2012)
[21] Meinshausen, N.; Buhlmann, P., High-dimensional graphs and variable selection with the LASSO, Ann. Statist., 34, 1436-1462, (2006) · Zbl 1113.62082
[22] Meinshausen, N.; Rocha, G.; Yu, B., Discussion: the Dantzig selector: statistical estimation when \(p\) is much larger than \(n\), Ann. Statist., 35, 2373-2384, (2007)
[23] Nesterov, Y., Smooth minimization of non-smooth functions, Math. Program. A, 103, 127-152, (2005) · Zbl 1079.90102
[24] Osborne, M.; Presnell, B.; Turlach, B., On the LASSO and its dual, J. Comput. Graph. Statist., 9, 319-337, (2000)
[25] Ritov, Y., Discussion: the Dantzig selector: statistical estimation when \(p\) is much larger than \(n\), Ann. Statist., 35, 2370-2372, (2007)
[26] Rockafellar, R. T., Convex analysis, (1970), Princeton University Press Princeton, NJ · Zbl 0202.14303
[27] Tibshirani, R., Regression shrinkage and selection via the LASSO, J. R. Stat. Soc. Ser. B, 58, 267-288, (1996) · Zbl 0850.62538
[28] Tibshirani, R., Regression shrinkage and selection and via the LASSO: a retrospective, J. R. Stat. Soc. Ser. B, 73, 273-282, (2011)
[29] Tibshirani, R.; Saunders, M.; Rosset, S.; Zhu, J.; Knight, K., Sparsity and smoothness via the fused LASSO, J. R. Stat. Soc. Ser. B, 67, 91-108, (2005) · Zbl 1060.62049
[30] Wang, X.; Yuan, X., The linearized alternating direction method of multipliers for Dantzig selector, SIAM J. Sci. Comput., 34, 2792-2811, (2012)
[31] Zhao, P.; Yu, B., On model selection consistency of LASSO, J. Mach. Learn. Res., 7, 2541-2563, (2006) · Zbl 1222.62008
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.