Computation of the trace of a matrix function plays an important role in many scientific computing applications, including applications in machine learning, computational physics (e.g., lattice quantum chromodynamics), network analysis and computational biology (e.g., protein folding), just to name a few application areas. We propose a linear-time randomized algorithm for approximating the trace of matrix functions of large symmetric matrices. Our algorithm is based on coupling function approximation using Chebyshev interpolation with stochastic trace estimators (Hutchinson's method), and as such requires only implicit access to the matrix, in the form of a function that maps a vector to the product of the matrix and the vector. We provide rigorous approximation error in terms of the extremal eigenvalue of the input matrix and the Bernstein ellipse that corresponds to the function at hand. Based on our general scheme, we provide algorithms with provable guarantees for important matrix computations, including log-determinant, trace of matrix inverse, Estrada index, Schatten $p$-norm, and testing positive definiteness. In addition, we propose improved determinantal point processes inference algorithm based on the log-determinant estimation. We experimentally evaluate our algorithm and demonstrate its effectiveness on matrices with tens of millions dimensions.
행렬 함수의 대각합 계산은 머신 러닝, 계산물리학, 네트워크 분석 그리고 계산생화학 등의 많은 분야에서 사용이 되고 있다. 이 논문에서는 대규모 환경에서 행렬 함수의 대각합을 근사하는 선형 복잡도의 랜덤 알고리즘을 제안하였다. 제안된 알고리즘은 체비셰프 근사와 확률적인 대각합 근사 방법을 이용하여 행렬과 벡터의 곱의 연산만 요구되도록 디자인되었다. 또한 제안한 알고리즘의 이론적인 분석을 통한 오차율을 보였다. 이를 이용하여 로그행렬식, 역행렬의 대각합, 에스트라다 인덱스(Estrada Index) 그리고 양의정부호 판펼 알고리즘을 이론적인 분석과 함께 제시하였다. 또한, 행렬식 포인트프로세스의 추론 알고리즘을 로그행렬식 근사 알고리즘을 이용하여 효율적으로 디자인 하였다. 마지막으로 알고리즘의 효율성을 실험적인 결과로 보였다.
