Suppose I have a full `k*k`

covariance matrix `Sigma`

. I can use singular value decomposition (SVD) or the eigendecomposition to express this as `U * Lambda * U'`

where U has size `k * k`

.

In many applications (eg multivariate normal distributions, Gaussian processes, etc), large `k`

means that this is unwieldy because I need to invert this matrix to get the precision matrix, which has cost O(`k^3`

).

Now, suppose I want to construct a low-rank approximation to this, matrix which corresponds to a truncated SVD:

`Sigma_alt = V * Lambda * V'`

, where `V`

has dimension `[k, p]`

where `p`

< `k`

.

This can be obtained by truncating the SVD, but this requires calculating the whole SVD and then truncating, which has complexity O(`k^3`

).

Is there some fast way of calculating this low-rank approximation which doesn’t have O(`k^3`

)? (I imagine it would be O(`kp^2`

).

Thanks!

–

Edit: I suppose that one way to do this would be to specify the low-rank matrices as parameters in Stan then fit them to the data at hand. Nonetheless, I’m still curious as to whether such an algorithm exists.