# Mahalanobis distance for highly multivariate random variable

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?

• 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. – Cliff AB May 4 '16 at 18:11