A fast splitting method tailored for Dantzig selector

详细信息    查看全文

• 作者：Hongjin He ; Xingju Cai ; Deren Han
• 关键词：Fast splitting method ; Dantzig selector ; Linear regression ; Alternating direction method of multipliers
• 刊名：Computational Optimization and Applications
• 出版年：2015
• 出版时间：November 2015
• 年：2015
• 卷：62
• 期：2
• 页码：347-372
• 全文大小：944 KB
• 参考文献：1.Becker, S., Cand茅s, E., Grant, M.: Templates for convex cone problems with applications to sparse signal recovery. Math. Program. Comput. 3, 165鈥?18 (2011)MATH MathSciNet CrossRef
  2.Bertsekas, D., Tsitsiklis, J.: Parallel and Distributed Computation, Numerical Methods. Prentice-Hall, Englewood Cliffs (1989)MATH
  3.Bickel, P.: Discussion: the dantzig selector: statistical estimation when \(p\) is much larger than \(n\) . Ann. Stat. 35(6), 2352鈥?357 (2007)MathSciNet CrossRef
  4.Boyd, S., Parikh, N., Chu, E., Peleato, B., Eckstein, J.: Distributed optimization and statistical learning via the alternating direction method of multipliers. Found. Trends Mach. Learn. 3, 1鈥?22 (2010)MATH CrossRef
  5.Breiman, L.: Better subset regression using the non-negative garrote. Technometrics 37, 373鈥?84 (1995)MATH MathSciNet CrossRef
  6.Cai, T., Lv, J.: Discussion: the dantzig selector: statistical estimation when \(p\) is much larger than \(n\) . Ann. Stat. 35, 2365鈥?368 (2007)MathSciNet CrossRef
  7.Cand茅s, E., Tao, T.: The Dantzig selector: statistical estimation when \(p\) is much larger than \(n\) . Ann. Stat. 35, 2313鈥?351 (2007)MATH CrossRef
  8.Cand茅s, E., Tao, T.: Rejoinder: the dantzig selector: statistical estimation when \(p\) is much larger than \(n\) . Ann. Stat. 35, 2392鈥?404 (2007)CrossRef
  9.Chan, R., Yang, J., Yuan, X.: Alternating direction method for image inpainting in wavelet domain. SIAM J. Imaging Sci. 4, 807鈥?26 (2011)MATH MathSciNet CrossRef
  10.Chen, C., He, B., Yuan, X.: Matrix completion via alternating direction method. IMA J. Numer. Anal. 32, 227鈥?45 (2012)MATH MathSciNet CrossRef
  11.Dobra, A.: Variable selection and dependency networks for genomewide data. Biostatistics 10, 621鈥?39 (2009)CrossRef
  12.Donoho, D., Tsaig, Y.: Fast solution of \(\ell _1\) minimization problems when the solution may be sparse. IEEE Trans. Inf. Theory 54, 4789鈥?812 (2008)MATH MathSciNet CrossRef
  13.Efron, B., Hastie, T., Johnstone, I., Tibshirani, R.: Least angle regression. Ann. Stat. 32, 407鈥?51 (2004)MATH MathSciNet CrossRef
  14.Efron, B., Hastie, T., Tibshirani, R.: Discussion: the dantzig selector: statistical estimation when \(p\) is much larger than \(n\) . Ann. Stat. 35, 2358鈥?364 (2007)MathSciNet CrossRef
  15.Esser, E., Zhang, X., Chan, T.: A general framework for a class of first order primal-dual aalgorithm for TV minimization. SIAM J. Imaging Sci. 3, 1015鈥?046 (2010)MATH MathSciNet CrossRef
  16.Facchinei, F., Pang, J.: Finite-Dimensional Variational Inequalities and Complementarity Problems. Springer, New York (2003)
  17.Friedlander, M., Saunders, M.: Discussion: the dantzig selector: statistical estimation when \(p\) is much larger than \(n\) . Ann. Stat. 35, 2385鈥?391 (2007)MathSciNet CrossRef
  18.Gabay, D., Mercier, B.: A dual algorithm for the solution of nonlinear variational problems via finite element approximations. Comput. Math. Appl. 2, 16鈥?0 (1976)CrossRef
  19.Golub, T., Slonim, D., Tamayo, P., Huard, C., Gaasenbeek, M., Mesirov, J., Coller, H., Loh, M., Downing, J., Caligiuri, M., Bloomfield, C., Lander, E.: Molecular classification of cancer: class discovery and class prediction by gene expression monitoring. Science 286, 531鈥?37 (1999)CrossRef
  20.Han, D., He, H., Yang, H., Yuan, X.: A customized Douglas-Rachford splitting algorithm for separable convex minimization with linear constraints. Numer. Math. 127, 167鈥?00 (2014)MATH MathSciNet CrossRef
  21.He, B., Xu, M., Yuan, X.: Solving large-scale least squares covariance matrix problems by alternating direction methods. SIAM J. Matrix Anal. Appl. 32, 136鈥?52 (2011)MATH MathSciNet CrossRef
  22.Hestenes, M.: Multiplier and gradient methods. J. Optim. Theory Appl. 4, 303鈥?20 (1969)MATH MathSciNet CrossRef
  23.James, G., Radchenko, P., Lv, J.: DASSO: connections between the Dantzig selector and lasso. J. R. Stat. Soc. B 71, 127鈥?42 (2009)MATH MathSciNet CrossRef
  24.Lu, Z.: Primal-dual first-order methods for a class of cone programming. Optim. Method Softw. 28, 1262鈥?281 (2013)MATH CrossRef
  25.Lu, Z., Pong, T., Zhang, Y.: An alternating direction method for finding Dantzig selectors. Comput. Stat. Data Anal. 56, 4037鈥?046 (2012)MATH MathSciNet CrossRef
  26.Meinshausen, N., Rocha, G., Yu, B.: Discussion: a tale of three cousins: Lasso, L2Boosting and Dantzig. Ann. Stat. 35(6), 2373鈥?384 (2007)MathSciNet CrossRef
  27.Powell, M.: A method for nonlinear constraints in minimization problems. In: R. Fletcher (ed.) Optimization, pp. 283鈥?98. Academic Press, New York (1969)
  28.Ritov, Y.: Discussion: the Dantzig selector: statistical estimation when \(p\) is much larger than \(n\) . Ann. Stat. 35, 2370鈥?372 (2007)MathSciNet CrossRef
  29.Romberg, J.: The Dantzig selector and generalized thresholding. In: IEEE 42nd Annual Conference on Information Sciences and Systems, pp. 22鈥?5. Princeton, New Jersey (2008)
  30.Tibshirani, R.: Regression shrinkage and selection via the LASSO. J. R. Stat. Soc. B 58, 267鈥?88 (1996)MATH MathSciNet
  31.Wang, X., Yuan, X.: The linearized alternating direction method of multipliers for Dantzig selector. SIAM J. Sci. Comput. 34, A2792鈥揂2811 (2012)MATH MathSciNet CrossRef
  32.Yang, J., Zhang, Y.: Alternating direction algorithms for \(\ell _1\) -problems in compressive sensing. SIAM J. Sci. Comput. 332, 250鈥?78 (2011)CrossRef
  33.Yeung, K., Bumgarner, R., Raftery, A.: Bayesian model averaging: development of an improved multi-class, gene selection and classification tool for microarray data. Bioinformatics 21, 2394鈥?402 (2005)CrossRef
  34.Yuan, X.: Alternating direction methods for covariance selection models. J. Sci. Comput. 51, 261鈥?73 (2012)MATH MathSciNet CrossRef
  35.Zou, H., Hastie, T.: Regularization and variable selection via the elastic net. J. R. Stat. Soc. B 67, 301鈥?20 (2005)MATH MathSciNet CrossRef
  
• 作者单位：Hongjin He (1)
  Xingju Cai (2)
  Deren Han (2)
  
  1. Department of Mathematics, School of Science, Hangzhou Dianzi University, Hangzhou, 310018, China
  2. School of Mathematical Sciences, Jiangsu Key Laboratory for NSLSCS, Nanjing Normal University, Nanjing, 210023, China
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Optimization
  Operations Research and Mathematical Programming
  Operation Research and Decision Theory
  Statistics
  Convex and Discrete Geometry
  
• 出版者：Springer Netherlands
• ISSN：1573-2894

文摘

In this paper, we introduce a splitting method for solving Dantzig selector problem, a new linear regression model that was extensively studied in the literature in the past few years. The new method is very simple in the sense that, per iteration, it only performs a projection onto a box, and does some matrix-vector products. We prove the global convergence of the method and report some promising numerical results, which demonstrate that the new method is competitive with some state-of-the-art methods recently developed in the literature. Keywords Fast splitting method Dantzig selector Linear regression Alternating direction method of multipliers