The Lawson-Hanson algorithm with deviation maximization: finite convergence and sparse recovery. (English) Zbl 07790614
Summary: The Lawson-Hanson with Deviation Maximization (LHDM) method is a block algorithm for the solution of NonNegative Least Squares (NNLS) problems. In this work we devise an improved version of LHDM and we show that it terminates in a finite number of steps, unlike the previous version, originally developed for a special class of matrices. Moreover, we are concerned with finding sparse solutions of underdetermined linear systems by means of NNLS. An extensive campaign of experiments is performed in order to evaluate the performance gain with respect to the standard Lawson-Hanson algorithm. We also show the ability of LHDM to retrieve sparse solutions, comparing it against several \(\ell_1\)-minimization solvers in terms of solution quality and time-to-solution on a large set of dense instances.
MSC:
| 65F25 | Orthogonalization in numerical linear algebra |
| 65K99 | Numerical methods for mathematical programming, optimization and variational techniques |
References:
| [1] | LeeDD, SeungHS. Learning the parts of objects by non‐negative matrix factorization. Nature. 1999;401(6755):788-91. Available from. https://doi.org/10.1038/44565 · Zbl 1369.68285 · doi:10.1038/44565 |
| [2] | GillisN. Nonnegative matrix factorization. Philadelphia: SIAM; 2020. |
| [3] | BrucksteinAM, EladM, ZibulevskyM. On the uniqueness of nonnegative sparse solutions to underdetermined systems of equations. IEEE Trans Inf Theory. 2008;54(11):4813-20. · Zbl 1319.15007 |
| [4] | FoucartS, KoslickiD. Sparse recovery by means of nonnegative least squares. Signal Process Lett IEEE. 2014;4(21):498-502. |
| [5] | WangM, TangA. Conditions for a unique non‐negative solution to an underdetermined system. Proceedings of the 47th Annual Allerton Conference on Communication, Control, and Computing. Allerton’09, IEEE Press; 2009:301-307. |
| [6] | WangM, XuW, TangA. A unique “nonnegative” solution to an underdetermined system: from vectors to matrices. IEEE Trans Signal Process. 2011;59(3):1007-16. · Zbl 1391.15004 |
| [7] | ChenSS, DonohoDL, SaundersMA. Atomic decomposition by basis pursuit. SIAM Rev.2001;43(1):129-59. Available from. https://doi.org/10.1137/S003614450037906X · Zbl 0979.94010 · doi:10.1137/S003614450037906X |
| [8] | DonohoDL, HuoX. Uncertainty principles and ideal atomic decomposition. IEEE Trans Inf Theory. 2001;47(7):2845-62. · Zbl 1019.94503 |
| [9] | EladM, BrucksteinAM. A generalized uncertainty principle and sparse representation in pairs of bases. IEEE Trans Inf Theory.2002;48:2558-67. · Zbl 1062.15001 |
| [10] | TibshiraniR. Regression shrinkage and selection via the lasso. J R Stat Soc Ser B (Methodol). 1996;58(1):267-88. Available from. http://www.jstor.org/stable/2346178 · Zbl 0850.62538 |
| [11] | LawsonCL, HansonRJ. Solving least squares problems. Vol 15. Philadelphia: SIAM; 1995. · Zbl 0860.65029 |
| [12] | BischofC, HansenP. A block algorithm for computing rank‐revealing QR factorizations. Numer Algorithms. 1992;10(2):371-91. · Zbl 0761.65029 |
| [13] | BischofC, Quintana‐OrtíG. Computing rank‐revealing QR factorizations of dense matrices. ACM Trans Math Softw.1998;6(24):226-53. · Zbl 0932.65033 |
| [14] | BischofC, Quintana‐OrtíG. Algorithm 782: codes for rank‐revealing QR factorizations of dense matrices. ACM Trans Math Softw. 1998;7(24):254-7. · Zbl 0932.65034 |
| [15] | Quintana‐OrtíG, SunX, BischofCH. A BLAS‐3 version of the QR factorization with column pivoting. SIAM J Sci Comput. 1998;19(5):1486-94. · Zbl 0912.65034 |
| [16] | BischofJR. A block QR factorization algorithm using restricted pivoting. Supercomputing ’89: Proceedings of the 1989 ACM/IEEE Conference on Supercomputing; 1989:248-256. |
| [17] | BroR, JongS. A fast non‐negativity‐constrained least squares algorithm. J Chemom. 1997;9(11):393-401. |
| [18] | Van BenthemMH, KeenanMR. Fast algorithm for the solution of large‐scale non‐negativity‐constrained least squares problems. J Chemom. 2004;18(10):441-50. Available from. https://analyticalsciencejournals.onlinelibrary.wiley.com/doi/abs/10.10 |
| [19] | PortugalLF, JúdiceJJ, VicenteLN. A comparison of block pivoting and interior‐point algorithms for linear least squares problems with nonnegative variables. Math Comput. 1994;63(208):625-43. · Zbl 0812.90124 |
| [20] | DessoleM, MarcuzziF. Deviation maximization for rank‐revealing QR factorizations. Numer Algorithms. 2022;91:1047-1079. Available from. https://doi.org/10.1007/s11075‐022‐01291‐1 · Zbl 1503.65073 · doi:10.1007/s11075‐022‐01291‐1 |
| [21] | DessoleM, MarcuzziF, VianelloM. Accelerating the Lawson‐Hanson NNLS solver for large‐scale Tchakaloff regression designs. Dolomites Res Notes Approx. 2020;13:20-9. · Zbl 1540.65586 |
| [22] | LorenzDA, PfetschME, TillmannAM. Solving basis pursuit: heuristic optimality check and solver comparison. ACM Trans Math Softw. 2015;41(2):1-29. Available from. https://doi.org/10.1145/2689662 · Zbl 1371.65055 · doi:10.1145/2689662 |
| [23] | NocedalJ, WrightSJ. Numerical optimization. 2nd ed.New York, NY, USA: Springer; 2006. · Zbl 1104.65059 |
| [24] | StoerJ. On the numerical solution of constrained least‐squares problems. SIAM J Numer Anal. 1971;8(2):382-411. · Zbl 0219.90039 |
| [25] | DonohoDL, EladM. Optimally sparse representation in general (nonorthogonal) dictionaries via [( {\ell}_1 \]\) minimization. Proc Natl Acad Sci. 2003;100(5):2197-202. · Zbl 1064.94011 |
| [26] | DonohoD. Compressed sensing. IEEE Trans Inf Theory. 2006;5(52):1289-306. · Zbl 1288.94016 |
| [27] | EladM. Sparse and redundant representations: from theory to applications in signal and image processing. 1st ed.New York, NY: Springer Publishing Company, Incorporated; 2010. · Zbl 1211.94001 |
| [28] | ChenS, DonohoD. Basis pursuit. Proceedings of 1994 28th Asilomar Conference on Signals, Systems and Computers. vol. 1; 1994:41-44. |
| [29] | CandèsEJ. The restricted isometry property and its implications for compressed sensing. C R Math. 2008;346(9):589-92. Available from. https://www.sciencedirect.com/science/article/pii/S1631073X08000964 · Zbl 1153.94002 |
| [30] | TillmannAM, PfetschME. The computational complexity of the restricted isometry property, the nullspace property, and related concepts in compressed sensing. IEEE Trans Inf Theory. 2014;60(2):1248-59. · Zbl 1364.94170 |
| [31] | TroppJA. Greed is good: algorithmic results for sparse approximation. IEEE Trans Inf Theory. 2004;50(10):2231-42. · Zbl 1288.94019 |
| [32] | BjörckA. Numerical methods for least squares problems. Philadelphia: Society for Industrial and Applied Mathematics; 1996. Available from. https://epubs.siam.org/doi/abs/10.1137/1.9781611971484 · Zbl 0847.65023 |
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.
