Entropic Trace Estimates for Log Determinants
This work addresses a scalability problem for practitioners using machine learning methods that rely on matrix determinants, offering a faster and more efficient solution.
The paper tackles the bottleneck of scalable matrix determinant calculation in machine learning methods like determinantal point processes and Gaussian processes by estimating log determinants using maximum entropy with moment constraints from stochastic trace estimation. The result is a significant improvement over state-of-the-art methods, demonstrated on a variety of UFL sparse matrices, and it accelerates inference in large-scale learning methods such as general Markov random fields.
The scalable calculation of matrix determinants has been a bottleneck to the widespread application of many machine learning methods such as determinantal point processes, Gaussian processes, generalised Markov random fields, graph models and many others. In this work, we estimate log determinants under the framework of maximum entropy, given information in the form of moment constraints from stochastic trace estimation. The estimates demonstrate a significant improvement on state-of-the-art alternative methods, as shown on a wide variety of UFL sparse matrices. By taking the example of a general Markov random field, we also demonstrate how this approach can significantly accelerate inference in large-scale learning methods involving the log determinant.