Large-Scale Log-Determinant Computation via Weighted L_2 Polynomial Approximation with Prior Distribution of Eigenvalues

摘要

Since the classic determinant computation method Cholesky decomposition may devastate sparsity of matrices and cost cubic steps, it is impractical to apply this method to large-scale symmetric positive-definite matrices due to limitation of storage and efficiency. Therefore, a randomized algorithm is proposed to calculate log-determinants of symmetric positive-definite matrices via stochastic trace approximations, implemented by weighted L_2 orthogonal polynomial expansions with efficient recursion formulas and matrix-vector multiplications based on the matrix eigenvalue distribution. As Chebyshev expansions have been applied to this problem before, our main contribution is proposing the strategies of weighted function selection based on prior eigenvalue distribution, which generalizes approximating polynomials for this problem and may accelerate computation.