We study a specific family of matrix functions (1) spectral functions that rely on only eigenvalues of a matrix and (2) elementwise function that apply scalar function to each element in a matrix. They have been played an important role in many data sciences including quantum chromodynamics, network analysis, computational biology and machine learning including Gaussian graphical model, kernel learning and deep learning. Computation of such functions can yield scalability issues when they come with a huge size of matrices. We propose fast and efficient algorithms for both approximating and optimizing spectral functions and elementwise matrix functions. We utilize randomized trace estimator and polynomial approximation for spectral functions and linear sketching methods for elementwise functions. All algorithms can run in linear-time with respect to the input size, which is tens of magnitude faster in practice than the previously known methods. We provide rigorous approximation error analysis and experimentally verify the effectiveness of all the techniques that we develop, testing them on applications such as classification, interpolation, recommendation and deep network compression.
본 연구에서는 다음과 같은 입력 행렬을 이용하여 스칼라값을 계산하는 함수에 중점을 두었다: (1) 행렬의 고유 값에만 의존하는 스펙트럼 함수와 (2) 행렬의 각 요소에 스칼라 함수를 적용하는 요소 별 함수. 이러한 행렬 함수들은 양자 색역학, 네트워크 분석, 전산 생물학과 같은 데이터 과학 분야와 가우시안 그래피컬 모델, 커널 학습, 딥러닝과 같은 다양한 기계학습 분야에서 사용이 되어왔다. 하지만, 이러한 함수들을 계산하는 것은 입력 행렬이 대규모인 경우에 계산의 병목 현상을 야기하는 등 큰 문제가 된다. 이를 해결하기 위해 우리는 스펙트럼 함수에 대해서는 근사 및 최적화 문제를 요소 별 행렬 함수에 대해서는 근사하는 문제를 빠르고 효율적으로 해결할 수 있는 알고리즘을 제시하였다. 구체적으로 스펙트럼 함수에는 무작위 대각합 추정 방법과 다항식 근사를 사용하였고 요소 별 함수에는 선형 스케칭 방법과 핵심 요소 선택법을 사용하였다. 이 논문에서 제안한 모든 알고리즘은 입력 크기에 선형으로 비례하는 시간 내에 동작하여 이는 실제로 기존의 방법들보다 수십 배 더 빠르게 동작하는 결과를 확인하였다. 또한, 우리는 제안한 알고리즘들의 근사 오류를 엄밀하게 분석하였고 모든 기술의 효율성을 실험적으로 검증하여 분류, 보간, 추천 시스템 및 딥러닝 네트워크 압축과 같은 어플리케이션에서 정당성을 보였다.
