×

Solving basis pursuit: heuristic optimality check and solver comparison. (English) Zbl 1371.65055


MSC:

65K05 Numerical mathematical programming methods
65Y20 Complexity and performance of numerical algorithms
90C59 Approximation methods and heuristics in mathematical programming
65F20 Numerical solutions to overdetermined systems, pseudoinverses
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] M. Salman Asif. 2008. Primal dual pursuit—A homotopy based algorithm for the dantzig selector. Master’s thesis, Georgia Institute of Technology.
[2] Stephen Becker, Jérôme Bobin, and Emmanuel J. Candès. 2011. NESTA: A fast and accurate first-order method for sparse recovery. SIAM J. Imag Sci. 4, 1, 1–39.
[3] Ernesto G. Birgin, José M. Martínez, and Marcos Raydán. 2000. Nonmonotone spectral projected gradient methods on convex sets. SIAM J. Optimiz. 10, 4, 1196–1211.
[4] Stephen Boyd and Lieven Vandenberghe. 2004. Convex Optimization. Cambridge University Press, New York, NY. · Zbl 1058.90049 · doi:10.1017/CBO9780511804441
[5] Jian-Feng Cai, Stanley Osher, and Zuowei Shen. 2009. Linearized Bregman iterations for compressed sensing. Math. Comp. 78, 267, 1515–1536. · Zbl 1198.65102 · doi:10.1090/S0025-5718-08-02189-3
[6] Paolo M. Camerini, Luigi Fratta, and Francesco Maffioli. 1975. On improving relaxation methods by modified gradient techniques. Math. Prog. Study 3, 26–34. · doi:10.1007/BFb0120697
[7] Emmanuel J. Candès, Justin Romberg, and Terence Tao. 2006. Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information. IEEE Trans. Inf. Theory 52, 2, 489–509. · Zbl 1231.94017
[8] Giacomo D’Antonio and Antonio Frangioni. 2009. Convergence analysis of deflected conditional approximate subgradient methods. SIAM J. Optimiz 20, 1, 357–386. · Zbl 1187.90222 · doi:10.1137/080718814
[9] Geoffrey M. Davies, Stéphane G. Mallat, and Zhifeng Zhang. 1994. Adaptive time-frequency decompositions. Opt. Eng. 33, 7, 2183–2191.
[10] David L. Donoho. 2006. Compressed Sensing. IEEE Trans. Inf. Theory 52, 4, 1289–1306. · Zbl 1288.94016 · doi:10.1109/TIT.2006.871582
[11] David L. Donoho and Xiaoming Huo. 2001. Uncertainty principles and ideal atomic decomposition. IEEE Trans. Inf. Theory 47, 7, 2845–2862. · Zbl 1019.94503 · doi:10.1109/18.959265
[12] David L. Donoho and Yaakov Tsaig. 2008. Fast solution of ℓ1-norm minimization problems when the solution may be sparse. IEEE Trans. Inf. Theory 54, 11, 4789–4812. · Zbl 1247.94009 · doi:10.1109/TIT.2008.929958
[13] Junbo Duan, Charles Soussen, David Brie, Jérôme Idier, and Yu-Ping Wang. 2011. A sufficient condition on monotonic increase of the number of nonzero entry in the optimizer of L1 norm penalized least-square problem. arXiv:1104.3792 [stat.ML].
[14] Bradley Efron, Trevor Hastie, Iain Johnstone, and Robert Tibshirani. 2004. Least angle regression. Ann. Stat. 32, 2, 407–499. · Zbl 1091.62054 · doi:10.1214/009053604000000067
[15] Mário A. T. Figueiredo, Robert D. Nowak, and Stephen J. Wright. 2007. Gradient projection for sparse reconstruction: Applications to compressed sensing and other inverse problems. IEEE J. Select Topics Sig. Proc. 4, 1, 586–597.
[16] Jean-Jacques Fuchs. 2004. On sparse representations in arbitrary redundant bases. IEEE Trans. Inf. Theory 50, 6, 1341–1344. · Zbl 1284.94018 · doi:10.1109/TIT.2004.828141
[17] Markus Grasmair, Markus Haltmeier, and Otmar Scherzer. 2011. Necessary and sufficient conditions for linear convergence of ℓ1-regularization. Commun. Pure Appl. Math. 64, 2, 161–182. · Zbl 1217.65095 · doi:10.1002/cpa.20350
[18] Michael Held, Philip Wolfe, and Harlan P. Crowder. 1974. Validation of subgradient optimization. Math. Prog. 6, 62–88. · Zbl 0284.90057 · doi:10.1007/BF01580223
[19] Victor Klee and George J. Minty. 1972. How good is the simplex algorithm? In Inequalities, (III Proceedings of the 3rd Symposium Dedicated to the Memory of Theodore S. Motzkin). Academic Press, New York, NY, 159–175. · Zbl 0297.90047
[20] Torbjörn Larsson, Michael Patriksson, and Ann-Brith Strömberg. 1996. Conditional subgradient optimization – Theory and applications. Europ. J. Oper. Res. 88, 2, 382–403. · Zbl 0913.90225
[21] Churlzu Lim and Hanif D. Sherali. 2005. Convergence and computational analyses for some variable target value and subgradient deflection methods. Computat. Opt. Appl. 34, 3, 409–428. · Zbl 1153.90574 · doi:10.1007/s10589-005-3914-x
[22] Andreas Löbel. 1997. Optimal vehicle scheduling in public transit. Ph.D. Dissertation, Technische Universität Berlin.
[23] Dirk A. Lorenz. 2013. Constructing test instances for basis pursuit denoising. IEEE Trans. Sign. Process. 61, 5, 2010–2014. · Zbl 1393.94345 · doi:10.1109/TSP.2012.2236322
[24] D. A. Lorenz, M. E. Pfetsch, and A. M. Tillmann. 2014. An infeasible-point subgradient method using adaptive approximate projections. Computat. Optimiz. Appl. 57, 2, 271–306. · Zbl 1304.90159 · doi:10.1007/s10589-013-9602-3
[25] Dirk A. Lorenz, Stefan Schiffler, and Dennis Trede. 2011. Beyond convergence rates: Exact inversion with Tikhonov regularization with sparsity constraints. Inve. Prob. 27, 085009. · Zbl 1233.47007
[26] J. Mairal and B. Yu. 2012. Complexity analysis of the Lasso regularization path. In Proceedings of the 29th International Conference on Machine Learning (ICML). J. Langford and J. Pineau (Eds.), Omnipress, Madison, WI, 353–360.
[27] Dmitry M. Malioutov, Müjdat Çetin, and Alan S. Willsky. 2005. Homotopy continuation for sparse signal representation. In Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP’05). Vol. 5, IEEE, New York, NY, 733–736.
[28] Arkadi S. Nemirovskiy and Boris T. Polyak. 1984. Iterative methods for solving linear ill-posed problems under precise information. I. Izvestiya Akademii Nauk SSSR. Tekhnicheskaya Kibernetika 2, 13–25, 203.
[29] Yurii Nesterov. 2005. Smooth minimization of non-smooth functions. Math. Prog. 103, 1, 127–152. · Zbl 1079.90102 · doi:10.1007/s10107-004-0552-5
[30] Michael R. Osbourne, Brett Presnell, and Berwin A. Turlach. 2000. A new approach to variable selection in least squares problems. IMA J. Numer. Anal. 20, 3, 389–402. · Zbl 0962.65036 · doi:10.1093/imanum/20.3.389
[31] Y. C. Pati, R. Rezaiifar, and P. S. Krishnaprasad. 1993. Orthogonal matching pursuit: Recursive function approximation with applications to wavelet decomposition. In Proceedings of the 27th Annual Asilomar Conference on Signals, Systems and Computers. Vol. 1, CA, 40–44. · doi:10.1109/ACSSC.1993.342465
[32] Andrzej Ruszczyński. 2006. Nonlinear Optimization. Princeton University Press, Princeton, NJ.
[33] Naum Z. Shor. 1985. Minimization Methods for Non-Differentiable Functions. Springer, New York, NY. · doi:10.1007/978-3-642-82118-9
[34] Joel A. Tropp. 2004. Greed is good: Algorithmic results for sparse approximation. IEEE Trans. Inf. Theory. 50, 10, 2231–2242. · Zbl 1288.94019 · doi:10.1109/TIT.2004.834793
[35] Joel A. Tropp. 2006. Just relax: Convex programming methods for identifying sparse signals in noise. IEEE Trans. Inf. Theory 52, 3 (March 2006), 1030–1051. · Zbl 1288.94025 · doi:10.1109/TIT.2005.864420
[36] Joel A. Tropp and Anna C. Gilbert. 2007. Signal recovery from random measurements via orthogonal matching pursuit. IEEE Trans. Inf. Theory 53, 12, 4655–5666. · Zbl 1288.94022 · doi:10.1109/TIT.2007.909108
[37] Ewout van den Berg and Michael P. Friedlander. 2008. Probing the Pareto frontier for basis pursuit solutions. SIAM J. Sci. Comput. 31, 2, 890–912. · Zbl 1193.49033 · doi:10.1137/080714488
[38] Yilun Wang and Wotao Yin. 2010. Sparse signal reconstruction via iterative support detection. SIAM J. Imag. Sci. 3, 3, 462–491. · Zbl 1206.68340 · doi:10.1137/090772447
[39] Zaiwen Wen, Wotao Yin, Donald Goldfarb, and Yin Zhang. 2010. A fast algorithm for sparse reconstruction based on shrinkage, subspace optimization and continuation. SIAM J. Sci. Comput. 32, 4, 1832–1857. · Zbl 1215.49039 · doi:10.1137/090747695
[40] Roland Wunderling. 1996. Paralleler und objektorientierter Simplex-Algorithmus. Ph.D. Dissertation, Technische Universität Berlin. In German. · Zbl 0871.65048
[41] Allen Y. Yang, Zihan Zhou, Arvind Ganesh, S. Shankar Sastry, and Yi Ma. 2010. A review of fast ℓ1-minimization algorithms for robust face recognition. arXiv:1007.3753 [cs.CV].
[42] Junfeng Yang and Yin Zhang. 2011. Alternating direction algorithms for ℓ1-problems in compressive sensing. SIAM J. Sci. Comput. 33, 1, 250–278. · Zbl 1256.65060 · doi:10.1137/090777761
[43] Wotao Yin. 2010. Analysis and generalizations of the linearized Bregman model. SIAM J. Imag. Sci. 3, 4, 856–877. · Zbl 1211.68491 · doi:10.1137/090760350
[44] Wotao Yin, Stanley J. Osher, Donald Goldfarb, and Jérôme Darbon. 2008. Bregman iterative algorithms for ℓ1-minimization with applications to compressed sensing. SIAM J. Imag Sci. 1, 1, 143–168. · Zbl 1203.90153
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.