Efficient multiplication between a low-rank matrix approximation and a vector

General Usage
1

Dear All,

I am quite new to Julia, and I am searching for a recommendation. Calling svd(A), I obtain a singular-value decomposition object that gives me access to the U, S, V, as discussed in the documentation.

I am interested in approximating the matrix-vector product A*z, where z is a vector, by approximating A with its k-rank approximation. A direct way to do this is to do

Ak = U[:,1:k] * Diagonal(S[1:k]) * V[:,1:k]'
w = Ak*z

but this does not seem a good idea, because Ak has the same size of the original matrix, and this does not buy me anything. A possible alternative is

w = U[:,1:k] * Diagonal(S[1:k]) * V[:,1:k]' * z

Of course, one can also write a specific for loop that accomplishes that. I am interested in knowing if there are off-the-shelves solutions for this (that use the SVD object created by svd), and if you see ways to write the most efficient

2

Look at GitHub - JuliaArrays/LazyArrays.jl: Lazy arrays and linear algebra in Julia.

Edit: or better GitHub - JuliaLinearAlgebra/LowRankApprox.jl: Fast low-rank matrix approximation in Julia

1 Like
3

Thanks @mohamed82008. I could not find in the documentation of the package LowRankApprox.jl how to quickly perform matrix-vector multiplies (which is separate from factorizing the matrix).

4

It’s already defined under the hood if you call * or mul! on the output. LowRankApprox.jl/src/psvd.jl at master · JuliaLinearAlgebra/LowRankApprox.jl · GitHub

2 Likes
5

Thank you, this was very helpful

6

This won’t do what you want because * is left-associative in Julia: it is equivalent to ((U[:,1:k] * Diagonal(S[1:k])) * V[:,1:k]') * z, which still forms the full matrix. You want:

w = U[:,1:k] * (Diagonal(S[1:k]) * (V[:,1:k]' * z))

or (to avoid allocating slices):

@views w = U[:,1:k] * (Diagonal(S[1:k]) * (V[:,1:k]' * z))

or to perform the diagonal multiplication in-place:

@views w = U[:,1:k] * lmul!(Diagonal(S[1:k]), V[:,1:k]' * z)
2 Likes
7

This is great advice, thank you so much!