  Evaluating the log determinant of a positive definite matrix is ubiquitous in
machine learning. Applications thereof range from Gaussian processes,
minimum-volume ellipsoids, metric learning, kernel learning, Bayesian neural
networks, Determinental Point Processes, Markov random fields to partition
functions of discrete graphical models. In order to avoid the canonical, yet
prohibitive, Cholesky $\mathcal{O}(n^{3})$ computational cost, we propose a
novel approach, with complexity $\mathcal{O}(n^{2})$, based on a constrained
variational Bayes algorithm. We compare our method to Taylor, Chebyshev and
Lanczos approaches and show state of the art performance on both synthetic and
real-world datasets.
