A randomized algorithm for approximating the log determinant of a symmetric positive definite matrix. (English) Zbl 1422.65071
Summary: We introduce a novel algorithm for approximating the logarithm of the determinant of a symmetric positive definite (SPD) matrix. The algorithm is randomized and approximates the traces of a small number of matrix powers of a specially constructed matrix, using the method of H. Avron and S. Toledo [J. ACM 58, No. 2, Article No. 8, 17 p. (2011; Zbl 1327.68331)]. From a theoretical perspective, we present additive and relative error bounds for our algorithm. Our additive error bound works for any SPD matrix, whereas our relative error bound works for SPD matrices whose eigenvalues lie in the interval \((\theta_1, 1)\), with \(0 < \theta_1 < 1\); the latter setting was proposed in [I. Han, D. Malioutov and J. Shin, “Large-scale log-determinant computation through stochastic Chebyshev expansions”, in: Proceedings of the 32nd international conference on machine learning, ICML 2015, Lille, France, July 6–11, 2015. Red Hook, NY: Curran Associates, Inc. 908–917 (2015)]. From an empirical perspective, we demonstrate that a C++ implementation of our algorithm can approximate the logarithm of the determinant of large matrices very accurately in a matter of seconds.
MSC:
| 65F40 | Numerical computation of determinants |
| 15A15 | Determinants, permanents, traces, other special matrix functions |
| 68W20 | Randomized algorithms |
| 68W25 | Approximation algorithms |
Keywords:
logdeterminant approximation; SPD matrix; randomized algorithm; power method; trace estimationCitations:
Zbl 1327.68331References:
| [1] | Avron, H.; Toledo, S., Randomized algorithms for estimating the trace of an implicit symmetric positive semi-definite matrix, J. ACM, 58, 2, 8 (2011) · Zbl 1327.68331 |
| [2] | Barry, Ronald Paul; Kelley Pace, R., Monte Carlo estimates of the log determinant of large sparse matrices, Linear Algebra Appl., 289, 1, 41-54 (1999) · Zbl 1063.65502 |
| [3] | Curran, Paul F., On a variation of the Gershgorin circle theorem with applications to stability theory, (IET Irish Signals and Systems Conference. IET Irish Signals and Systems Conference, ISSC 2009 (2009)) |
| [4] | Davidson, Ernest R., The iterative calculation of a few of the lowest eigenvalues and corresponding eigenvectors of large real-symmetric matrices, J. Comput. Phys., 17, 1, 87-94 (1975) · Zbl 0293.65022 |
| [5] | Davis, Timothy A., Direct Methods for Sparse Linear Systems, vol. 2 (2006), SIAM · Zbl 1119.65021 |
| [6] | d’Aspremont, Alexandre; Banerjee, Onureena; El Ghaoui, Laurent, First-order methods for sparse covariance selection, SIAM J. Matrix Anal. Appl., 30, 1, 56-66 (2008) · Zbl 1156.90423 |
| [7] | Davis, Timothy A.; Hu, Yifan, The university of Florida sparse matrix collection, ACM Trans. Math. Software, 38, 1, 1 (2011) · Zbl 1365.65123 |
| [8] | Eberly, Wayne; Giesbrecht, Mark; Villard, Gilles, On computing the determinant and smith form of an integer matrix, (Foundations of Computer Science, 2000. Proceedings. 41st Annual Symposium on (2000), IEEE), 675-685 |
| [9] | Friedman, Jerome; Hastie, Trevor; Tibshirani, Robert, Sparse inverse covariance estimation with the graphical lasso, Biostatistics, 9, 3, 432-441 (2008) · Zbl 1143.62076 |
| [10] | Guennebaud, Gaël; Jacob, Benoît, Eigen v3 (2010) |
| [11] | Gupta, Anshul; Karypis, George; Kumar, Vipin, Highly scalable parallel algorithms for sparse matrix factorization, IEEE Trans. Parallel Distrib. Syst., 8, 5, 502-520 (1997) · Zbl 0896.65026 |
| [12] | Gupta, Anshul, Wsmp: Watson sparse matrix package (part-i: direct solution of symmetric sparse systems) (2000), IBM TJ Watson Research Center: IBM TJ Watson Research Center Yorktown Heights, NY, Tech. Rep. RC, 21886 |
| [13] | Goto, Kazushige; Van De Geijn, Robert, High-performance implementation of the level-3 blas, ACM Trans. Math. Software, 35, 1, 4 (2008) |
| [14] | Hunter, Timothy; El Alaoui, Ahmed; Bayen, Alexandre, Computing the log-determinant of symmetric, diagonally dominant matrices in near-linear time (2014), arXiv preprint |
| [15] | Han, Insu; Malioutov, Dmitry; Avron, Haim; Shin, Jinwoo, Approximating the spectral sums of large-scale matrices using Chebyshev approximations (2016), arXiv preprint · Zbl 1372.65126 |
| [16] | Han, Insu; Malioutov, Dmitry; Shin, Jinwoo, Large-scale log-determinant computation through stochastic Chebyshev expansions, (Blei, David; Bach, Francis, Proceedings of the 32nd International Conference on Machine Learning, ICML-15, JMLR Workshop and Conference Proceedings (2015)), 908-917 |
| [17] | Hsieh, Cho-Jui; Sustik, Mátyás A.; Dhillon, Inderjit S.; Ravikumar, Pradeep K.; Poldrack, Russell, Big & quic: sparse inverse covariance estimation for a million variables, (Advances in Neural Information Processing Systems (2013)), 3165-3173 |
| [18] | Kambadur, Prabhanjan; Lozano, Aurelie, A parallel, block greedy method for sparse inverse covariance estimation for ultra-high dimensions, (Proceedings of the Sixteenth International Conference on Artificial Intelligence and Statistics (2013)), 351-359 |
| [19] | LeSage, James P.; Kelley Pace, R., Spatial dependence in data mining, (Data Mining for Scientific and Engineering Applications (2001), Springer), 439-460 |
| [20] | Leithead, W. E.; Zhang, Yunong; Leith, D. J., Efficient gaussian process based on bfgs updating and logdet approximation, (The 16th IFAC World Congress (2005)) |
| [21] | Martin, R. J., Approximations to the determinant term in gaussian maximum likelihood estimation of some spatial models, Comm. Statist. Theory Methods, 22, 1, 189-205 (1992) · Zbl 0800.62570 |
| [22] | Pace, R. Kelley; Barry, Ronald, Quick computation of spatial autoregressive estimators, Geogr. Anal., 29, 3, 232-247 (1997) |
| [23] | Kelley Pace, R.; Barry, Ronald; Gilley, Otis W.; Sirmans, C. F., A method for spatial-temporal forecasting with an application to real estate prices, Int. J. Forecast., 16, 2, 229-246 (2000) |
| [24] | Pace, R. Kelley; LeSage, James P., Chebyshev approximation of log-determinants of spatial weight matrices, Comput. Statist. Data Anal., 45, 2, 179-196 (2004) · Zbl 1430.62213 |
| [25] | Poulson, Jack; Marker, Bryan; Van de Geijn, Robert A.; Hammond, Jeff R.; Romero, Nichols A., Elemental: a new framework for distributed memory dense matrix computations, ACM Trans. Math. Software, 39, 2, 13 (2013) · Zbl 1295.65137 |
| [26] | Reusken, Arnold, Approximation of the determinant of large sparse symmetric positive definite matrices, SIAM J. Matrix Anal. Appl., 23, 3, 799-818 (2002) · Zbl 1010.65021 |
| [27] | Saibaba, Arvind K.; Alexanderian, Alen; Ipsen, Ilse C. F., Randomized matrix-free trace and log-determinant estimators, Numer. Math. (2017) · Zbl 1378.65094 |
| [28] | Salmon, John K.; Moraes, Mark A.; Dror, Ron O.; Shaw, David E., Parallel random numbers: as easy as 1, 2, 3, (High Performance Computing, Networking, Storage and Analysis (SC), 2011 International Conference for (2011), IEEE), 1-12 |
| [29] | Spielman, Daniel A.; Teng, Shang-Hua, Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems, (Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing (2004), ACM), 81-90 · Zbl 1192.65048 |
| [30] | Trevisan, Luca, Graph partitioning and expanders, Handout, 7 (2011) · Zbl 1290.11016 |
| [31] | Zhang, Yunong; Leithead, William E., Approximate implementation of the logarithm of the matrix determinant in gaussian process regression, J. Stat. Comput. Simul., 77, 4, 329-348 (2007) · Zbl 1122.62074 |
| [32] | Zhang, Yunong; 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, 198-214 (2008) · Zbl 1146.65015 |
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.
