@shakir_za: “Writing reflections: This one gave me a way to re-discover the power of randomised algorithms in ML.”
Hutchinson’s estimator [1] is a simple way to obtain a stochastic estimate of the trace of a matrix. This is a simple trick that uses randomisation to transform the algebraic problem of computing the trace into the statistical problem of computing an expectation of a quadratic function. The randomisation technique used in this trick is just one from a wide range of randomised linear algebra methods [2] that are now central to modern machine learning, since they provide us with the needed tools for general-purpose, large-scale modelling and prediction. This post examines Hutchinson’s estimator and the wider research area of randomised algorithms. read more