×

Bounding matrix functionals via partial global block Lanczos decomposition. (English) Zbl 1325.65060

Summary: Approximations of expressions of the form \(\mathcal{I} f : = \mathrm{trace}(W^T f(A) W)\), where \(A \in \mathbb{R}^{m \times m}\) is a large symmetric matrix, \(W \in \mathbb{R}^{m \times k}\) with \(k \ll m\), and \(f\) is a function, can be computed without evaluating \(f(A)\) by applying a few steps of the global block Lanczos method to \(A\) with initial block-vector \(W\). This yields a partial global Lanczos decomposition of \(A\). We show that for suitable functions \(f\) upper and lower bounds for \(\mathcal{I} f\) can be determined by exploiting the connection between the global block Lanczos method and Gauss-type quadrature rules. Our approach generalizes techniques advocated by Golub and Meurant for the standard Lanczos method (with block size one) to the global block Lanczos method. We describe applications to the computation of upper and lower bounds of the trace of \(f(A)\) and consider, in particular, the computation of upper and lower bounds for the Estrada index, which arises in network analysis. We also discuss an application to machine learning.

MSC:

65F30 Other matrix algorithms (MSC2010)
65D30 Numerical integration
68T05 Learning and adaptive systems in artificial intelligence
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Avron, H.; Toledo, S., Randomized algorithms for estimating the trace of an implicit symmetric positive semi-definite matrix, J. ACM, 58, 8:1-8:34 (2011) · Zbl 1327.68331
[2] Baglama, J.; Fenu, C.; Reichel, L.; Rodriguez, G., Analysis of directed networks via partial singular value decomposition and Gauss quadrature, Linear Algebra Appl., 456, 93-121 (2014) · Zbl 1295.05216
[3] Bai, Z.; Golub, G., Bounds for the trace of the inverse and the determinant of symmetric positive definite matrices, Ann. Numer. Math., 4, 29-38 (1997) · Zbl 0883.15013
[4] Bai, Z.; Fahey, M.; Golub, G., Some large-scale matrix computation problems, J. Comput. Appl. Math., 74, 71-89 (1996) · Zbl 0870.65035
[5] Beckermann, B.; Reichel, L., Error estimation and evaluation of matrix functions via the Faber transform, SIAM J. Numer. Anal., 47, 3849-3883 (2009) · Zbl 1204.65041
[6] Benzi, M.; Boito, P., Quadrature rule-based bounds for functions of adjacency matrices, Linear Algebra Appl., 433, 637-652 (2010) · Zbl 1191.65046
[7] Bonchi, F.; Esfandiar, P.; Gleich, D. F.; Greif, C.; Lakshmanan, L. V.S., Fast matrix computations for pairwise and columnwise commute times and Katz scores, Internet Math., 8, 73-112 (2012) · Zbl 1245.05026
[8] Brezinski, C.; Fika, P.; Mitrouli, M., Estimations of the trace of powers of self-adjoint operators by extrapolation of the moments, Electron. Trans. Numer. Anal., 39, 144-159 (2012) · Zbl 1287.65042
[9] Brezinski, C.; Fika, P.; Mitrouli, M., Moments of a linear operator on a Hilbert space, with applications to the trace of the inverse of matrices and the solution of equations, Numer. Linear Algebra Appl., 19, 937-953 (2012) · Zbl 1289.15014
[10] Calvetti, D.; Reichel, L.; Sgallari, F., Application of anti-Gauss quadrature rules in linear algebra, (Gautschi, W.; Golub, G. H.; Opfer, G., Applications and Computation of Orthogonal Polynomials (1999), Birkhäuser: Birkhäuser Basel), 41-56 · Zbl 0938.65075
[11] Chan, T. F., An optimal circulant preconditioner for Toeplitz systems, SIAM J. Sci. Stat. Comput., 9, 766-771 (1988) · Zbl 0646.65042
[12] de la Peña, J. A.; Gutman, I.; Rada, J., Estimating the Estrada index, Linear Algebra Appl., 427, 70-76 (2007) · Zbl 1184.05082
[13] Elbouyahyaoui, L.; Messaoudi, A.; Sadok, H., Algebraic properties of the block GMRES and block Arnoldi methods, Electron. Trans. Numer. Anal., 33, 207-220 (2009) · Zbl 1188.65031
[14] Estrada, E.; Higham, D. J., Network properties revealed through matrix functions, SIAM Rev., 52, 696-714 (2010) · Zbl 1214.05077
[15] Estrada, E.; Rodríguez-Velázquez, J. A., Subgraph centrality in complex networks, Phys. Rev. E, 71, 056103 (2005), (11 pages)
[16] Estrada, E.; Hatano, N.; Benzi, M., The physics of communicability in complex networks, Phys. Rep., 514, 89-119 (2012)
[17] Fenu, C.; Martin, D.; Reichel, L.; Rodriguez, G., Network analysis via partial spectral factorization and Gauss quadrature, SIAM J. Sci. Comput., 35, A2046-A2068 (2013) · Zbl 1362.65052
[18] Fenu, C.; Martin, D.; Reichel, L.; Rodriguez, G., Block Gauss and anti-Gauss quadrature with application to networks, SIAM J. Matrix Anal. Appl., 34, 1655-1684 (2013) · Zbl 1425.65063
[19] Fika, P.; Mitrouli, M.; Roupa, P., Estimates for the bilinear form \(x^T A^{- 1} y\) with applications to linear algebra problems, Electron. Trans. Numer. Anal., 43, 70-89 (2014) · Zbl 1302.65100
[20] Gallivan, K.; Heath, M.; Ng, E.; Peyton, B.; Plemmons, R.; Ortega, J.; Romine, C.; Sameh, A.; Voigt, R., Parallel Algorithms for Matrix Computations (1990), SIAM: SIAM Philadelphia · Zbl 0711.00021
[21] Gautschi, W., Orthogonal Polynomials: Computation and Approximation (2004), Oxford University Press: Oxford University Press Oxford · Zbl 1130.42300
[22] Golub, G. H.; Meurant, G., Matrices, moments and quadrature, (Griffiths, D. F.; Watson, G. A., Numerical Analysis 1993 (1994), Longman: Longman Essex, England), 105-156 · Zbl 0795.65019
[23] Golub, G. H.; Meurant, G., Matrices, Moments and Quadrature with Applications (2010), Princeton University Press: Princeton University Press Princeton · Zbl 0888.65050
[24] Hutchinson, M. F., A stochastic estimator of the trace of the influence matrix for Laplacian smoothing splines, Commun. Stat., Simul. Comput., 18, 1059-1076 (1989) · Zbl 0695.62113
[25] Jbilou, K.; Messaoudi, A.; Sadok, H., Global FOM and GMRES algorithms for matrix equations, Appl. Numer. Math., 31, 49-63 (1999) · Zbl 0935.65024
[26] Laurie, D. P., Anti-Gaussian quadrature formulas, Math. Comput., 65, 739-747 (1996) · Zbl 0843.41020
[27] Lehoucq, R. B.; Sorensen, D. C.; Yang, C., ARPACK Users’ Guide: Solution of Large-Scale Eigenvalue Problems with Implicitly Restarted Arnoldi Methods (1998), SIAM: SIAM Philadelphia · Zbl 0901.65021
[28] López Lagomasino, G.; Reichel, L.; Wunderlich, L., Matrices, moments, and rational quadrature, Linear Algebra Appl., 429, 2540-2554 (2008) · Zbl 1191.65010
[29] Meurant, G., Estimates of the trace of the inverse of a symmetric matrix using the modified Chebyshev algorithm, Numer. Algorithms, 51, 309-318 (2009) · Zbl 1166.65335
[30] Newman, M. E.J., Networks: An Introduction (2010), Oxford University Press · Zbl 1029.68010
[31] Ngo, T. T.; Bellalij, M.; Saad, Y., The trace ratio optimization problem, SIAM Rev., 54, 545-569 (2012) · Zbl 1251.65090
[32] Noschese, S.; Reichel, L., Generalized circulant Strang-type preconditioners, Numer. Linear Algebra Appl., 19, 3-17 (2012) · Zbl 1274.65086
[33] Noschese, S.; Reichel, L., A note on superoptimal generalized circulant preconditioners, Appl. Numer. Math., 75, 188-195 (2014) · Zbl 1302.65072
[34] Rasmussen, C. E., Gaussian processes in machine learning, (Bousquet, O.; von Luxburg, U.; Rätsch, G., Advanced Lectures on Machine Learning (2004), Springer: Springer Berlin), 63-71 · Zbl 1120.68436
[35] Redivo-Zaglia, M.; Rodriguez, G., Smt: a Matlab toolbox for structured matrices, Numer. Algorithms, 59, 639-659 (2012) · Zbl 1238.65036
[36] Tang, J.; Saad, Y., A probing method for computing the diagonal of the matrix inverse, Numer. Linear Algebra Appl., 19, 485-501 (2012) · Zbl 1274.65132
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.