Randomized matrix-free trace and log-determinant estimators. (English) Zbl 1378.65094
The authors propose and analyse randomized algorithms for estimating the trace and determinant of Hermitian positive semi-definite matrices. Their estimators are are based on randomized subspace iteration and are accurate for many matrices of interest, which have a well-defined dominant eigenspace, with a large eigenvalue gap whose location is known. Comprehensive numerical experiments are also reported.
Reviewer: Constantin Popa (Constanţa)
MSC:
| 65F40 | Numerical computation of determinants |
| 68W20 | Randomized algorithms |
| 65F15 | Numerical computation of eigenvalues and eigenvectors of matrices |
| 65F25 | Orthogonalization in numerical linear algebra |
| 65F35 | Numerical computation of matrix norms, conditioning, scaling |
| 15B52 | Random matrices (algebraic aspects) |
| 62F15 | Bayesian inference |
Keywords:
randomized algorithms; Hermitian positive definite matrix; trace; determinant; subspace iteration; large eigenvalue gap; numerical experimentsSoftware:
mctoolboxReferences:
| [1] | Akçelik, V., Biros, G., Draganescu, A., Ghattas, O., Hill, J., Van Bloemen Waanders, B.: Dynamic data-driven inversion for terascale simulations: real-time identification of airborne contaminants. In: Supercomputing, 2005. Proceedings of the ACM/IEEE SC 2005 Conference, pp. 43-43 (2005) |
| [2] | Alexanderian, A., Gloor, P.J., Ghattas, O.: On Bayesian \[A\] A-and \[D\] D-optimal experimental designs in infinite dimensions. Bayesian Anal. 11(3), 671-695 (2016) · Zbl 1359.62315 · doi:10.1214/15-BA969 |
| [3] | Alexanderian, A., Petra, N., Stadler, G., Ghattas, O.: A-optimal design of experiments for infinite-dimensional Bayesian linear inverse problems with regularized \[\ell_0\] ℓ0-sparsification. SIAM J. Sci. Comput. 36(5), A2122-A2148 (2014) · Zbl 1314.62163 · doi:10.1137/130933381 |
| [4] | Anitescu, M., Chen, J., Wang, L.: A matrix-free approach for solving the parametric Gaussian process maximum likelihood problem. SIAM J. Sci. Comput. 34(1), A240-A262 (2012) · Zbl 1241.65020 · doi:10.1137/110831143 |
| [5] | Atkinson, A.C., Donev, A.N.: Optimum Experimental Designs. Oxford University Press, Oxford (1992) · Zbl 0829.62070 |
| [6] | Avron, H., Toledo, S.: Randomized algorithms for estimating the trace of an implicit symmetric positive semi-definite matrix. J. ACM 58(2), Art. 8, 17 (2011) · Zbl 1327.68331 |
| [7] | Bai, Z., Fahey, M., Golub, G.: Some large-scale matrix computation problems. J. Comput. Appl. Math. 74(1), 71-89 (1996) · Zbl 0870.65035 · doi:10.1016/0377-0427(96)00018-0 |
| [8] | Bai, Z., Golub, G.H.: Bounds for the trace of the inverse and the determinant of symmetric positive definite matrices. Ann. Numer. Math. 4(1-4), 29-38 (1997). The heritage of P.L. Chebyshev: a Festschrift in honor of the 70th birthday of T.J. Rivlin · Zbl 0883.15013 |
| [9] | Barry, R.P., Pace, R.K.: Monte Carlo estimates of the log determinant of large sparse matrices. Linear Algebra Appl. 289(1-3), 41-54 (1999). Linear algebra and statistics (Istanbul, 1997) · Zbl 1063.65502 |
| [10] | Boutsidis, C., Drineas, P., Kambadur, P., Zouzias, A.: A randomized algorithm for approximating the log determinant of a symmetric positive definite matrix. arXiv:1503.00374 (2015) · Zbl 1422.65071 |
| [11] | Chaloner, K., Verdinelli, I.: Bayesian experimental design: a review. Stat. Sci. 10(3), 273-304 (1995) · Zbl 0955.62617 · doi:10.1214/ss/1177009939 |
| [12] | Chen, J., Anitescu, M., Saad, Y.: Computing \[f({A})b\] f(A)b via least squares polynomial approximations. SIAM J. Sci. Comput. 33(1), 195-222 (2011) · Zbl 1234.65027 · doi:10.1137/090778250 |
| [13] | Flath, P.H., Wilcox, L.C., Akçelik, V., Hill, J., van Bloemen Waanders, B., Ghattas, O.: Fast algorithms for Bayesian uncertainty quantification in large-scale linear inverse problems based on low-rank partial Hessian approximations. SIAM J. Sci. Comput. 33(1), 407-432 (2011) · Zbl 1229.65174 · doi:10.1137/090780717 |
| [14] | Gittens, A., Mahoney, M.W.: Revisiting the Nystrom method for improved large-scale machine learning. arXiv:1303.1849 (2013) · Zbl 1367.68223 |
| [15] | Golub, G.H., Von Matt, U.: Generalized cross-validation for large-scale problems. J. Comput. Graph. Stat. 6(1), 1-34 (1997) · Zbl 0878.65032 |
| [16] | Gu, M.: Subspace iteration randomization and singular value problems. SIAM J. Sci. Comput. 37(3), A1139-A1173 (2015) · Zbl 1328.65088 · doi:10.1137/130938700 |
| [17] | Haber, E., Horesh, L., Tenorio, L.: Numerical methods for experimental design of large-scale linear ill-posed inverse problems. Inverse Probl. 24(5), 055012-055017 (2008) · Zbl 1153.65062 · doi:10.1088/0266-5611/24/5/055012 |
| [18] | Haber, E., Magnant, Z., Lucero, C., Tenorio, L.: Numerical methods for \[A\] A-optimal designs with a sparsity constraint for ill-posed inverse problems. Comput. Optim. Appl. 52, 293-314 (2012) · Zbl 1259.90135 · doi:10.1007/s10589-011-9404-4 |
| [19] | Halko, N., Martinsson, P.G., Tropp, J.A.: Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions. SIAM Rev. 53(2), 217-288 (2011) · Zbl 1269.65043 · doi:10.1137/090771806 |
| [20] | Han, I., Malioutov, D., Shin, J.: Large-scale log-determinant computation through stochastic Chebyshev expansions. arXiv:1503.06394 (2015) |
| [21] | Higham, N.J.: Accuracy and Stability of Numerical Algorithms, 2nd edn. Society for Industrial and Applied Mathematics (SIAM), Philadelphia (2002) · Zbl 1011.65010 · doi:10.1137/1.9780898718027 |
| [22] | Horn, R.A., Johnson, C.R.: Topics in Matrix Analysis. Cambridge University Press, Cambridge (1991) · Zbl 0729.15001 · doi:10.1017/CBO9780511840371 |
| [23] | Horn, R.A., Johnson, C.R.: Matrix Analysis, 2nd edn. Cambridge University Press, Cambridge (2013) · Zbl 1267.15001 |
| [24] | Hutchinson, M.F.: A stochastic estimator of the trace of the influence matrix for Laplacian smoothing splines. Commun. Stat. Simul. Comput. 18(3), 1059-1076 (1989) · Zbl 0695.62113 · doi:10.1080/03610918908812806 |
| [25] | Ledoux, M.: On Talagrand’s deviation inequalities for product measures. ESAIM Probab. Statist. 1, 63-87 (1995/1997) · Zbl 0869.60013 |
| [26] | Liberty, E., Woolfe, F., Martinsson, P.G., Rokhlin, V., Tygert, M.: Randomized algorithms for the low-rank approximation of matrices. Proc. Natl. Acad. Sci. USA 104(51), 20167-20172 (2007) · Zbl 1215.65080 · doi:10.1073/pnas.0709640104 |
| [27] | Lin, L.: Randomized estimation of spectral densities of large matrices made accurate. Numer. Math. 1-31 (2016). doi:10.1007/s00211-016-0837-7 · Zbl 1364.15007 |
| [28] | Mahoney, M.W.: Randomized Algorithms for Matrices and Data. Now Publishers Inc, Hanover (2011) · Zbl 1232.68173 |
| [29] | Martinsson, P.G., Rokhlin, V., Tygert, M.: A randomized algorithm for the decomposition of matrices. Appl. Comput. Harmon. Anal. 30(1), 47-68 (2011) · Zbl 1210.65095 · doi:10.1016/j.acha.2010.02.003 |
| [30] | Mitzenmacher, M., Upfal, E.: Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, Cambridge (2005) · Zbl 1092.60001 · doi:10.1017/CBO9780511813603 |
| [31] | Ouellette, D.V.: Schur complements and statistics. Linear Algebra Appl. 36, 187-295 (1981) · Zbl 0455.15012 · doi:10.1016/0024-3795(81)90232-9 |
| [32] | Pace, R.K., LeSage, J.P.: Chebyshev approximation of log-determinants of spatial weight matrices. Comput. Stat. Data Anal. 45(2), 179-196 (2004) · Zbl 1430.62213 · doi:10.1016/S0167-9473(02)00321-3 |
| [33] | Parlett, B.N.: The Symmetric Eigenvalue Problem. Prentice Hall Inc, Englewood Cliffs (1980) · Zbl 0431.65017 |
| [34] | Petra, N., Stadler, G.: Model variational inverse problems governed by partial differential equations. Tech. Rep. 11-05, The Institute for Computational Engineering and Sciences, The University of Texas at Austin (2011) |
| [35] | Roosta-Khorasani, F., Ascher, U.: Improved bounds on sample size for implicit matrix trace estimators. Found. Comput. Math. 15(5), 1187-1212 (2015) · Zbl 1323.65043 · doi:10.1007/s10208-014-9220-1 |
| [36] | Rudelson, M., Vershynin, R.: Smallest singular value of a random rectangular matrix. Commun. Pure Appl. Math. 62(12), 1707-1739 (2009) · Zbl 1183.15031 · doi:10.1002/cpa.20294 |
| [37] | Saad, Y.: Numerical methods for large eigenvalue problems. In: Classics in Applied Mathematics, vol. 66. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA (2011). Revised edition of the 1992 original · Zbl 0991.65039 |
| [38] | Saibaba, A.K., Kitanidis, P.K.: Fast computation of uncertainty quantification measures in the geostatistical approach to solve inverse problems. Adv. Water Resour. 82, 124-138 (2015) · doi:10.1016/j.advwatres.2015.04.012 |
| [39] | Sorensen, D.C., Embree, M.: A DEIM induced CUR factorization. SIAM J. Sci. Comput. 38(3), A1454-A1482 (2016) · Zbl 1382.65121 · doi:10.1137/140978430 |
| [40] | Stirling, D.S.G.: Mathematical Analysis and Proof, 2nd edn. Horwood Publishing Limited, Chichester (2009) · Zbl 1211.00005 · doi:10.1533/9780857099341 |
| [41] | Tang, J.M., Saad, Y.: A probing method for computing the diagonal of a matrix inverse. Numer. Linear Algebra Appl. 19(3), 485-501 (2012) · Zbl 1274.65132 · doi:10.1002/nla.779 |
| [42] | Tropp, J.A.: Improved analysis of the subsampled randomized Hadamard transform. Adv. Adapt. Data Anal. 3(1-2), 115-126 (2011) · Zbl 1232.15029 · doi:10.1142/S1793536911000787 |
| [43] | Tropp, J.A.: An introduction to matrix concentration inequalities. Found. Trends Mach. Learn. 8(1-2), 1-230 (2015) · Zbl 1391.15071 · doi:10.1561/2200000048 |
| [44] | Uciński, D.: Optimal Measurement Methods for Distributed Parameter System Identification. CRC Press, Boca Raton (2005) · Zbl 1155.93003 |
| [45] | Vershynin, R.: Introduction to the non-asymptotic analysis of random matrices. In: Eldar, Y.C., Kutyniok, G. (eds.) Compressed Sensing, pp. 210-268. Cambridge University Press, Cambridge (2012) |
| [46] | Wahba, G.: Practical approximate solutions to linear operator equations when the data are noisy. SIAM J. Numer. Anal. 14(4), 651-667 (1977) · Zbl 0402.65032 · doi:10.1137/0714044 |
| [47] | Wahba, G.: Spline Models for Observational Data, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 59. Society for Industrial and Applied Mathematics (SIAM), Philadelphia (1990) · Zbl 0813.62001 |
| [48] | Zhang, Y., Leithead, W.E., Leith, D.J., Walshe, L.: Log-det approximation based on uniformly distributed seeds and its application to Gaussian process regression. J. Comput. Appl. Math. 220(1-2), 198-214 (2008) · Zbl 1146.65015 · doi:10.1016/j.cam.2007.08.012 |
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.
