I have to compute the Mahalanobis distance for a $10^6$ dimensional multivariate random variable. What is the best (and fastest) way to do this?

I am currently taking cholesky decomposition of the covariance matrix and then back and forward solve the linear system to compute the distance. This approach works for lower dimensions (up to 300), however is not feasible for such dimensions as the covariance matrix has $10^{12}$ elements.

Can I avoid computing the full covariance and use an approximation?

  • 1
    $\begingroup$ In the general case, you're not going to be able to improve on that; that's just how many operations are required. However, if there is some sparsity to the covariance matrix (or it can be approximated with a sparse covariance matrix), you may be able to take advantage of that. $\endgroup$ – Cliff AB May 4 '16 at 18:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.