# Efficient low rank matrix-vector multiplication

If I have large matrix, but with very low rank, say 2. Is there an efficient way to multiply this matrix by vector (to achieve linear complexity)?

• Do you know the actual rank-2 expansion, or just know theoretically that it has rank-2? Mar 8 '14 at 20:05
• For a matrix to be orthogonal, it must have full rank. Mar 8 '14 at 20:39
• @augurar you right, I've mixed different questions. Mar 9 '14 at 9:38
• @NickAlger just theoretically, isn't there an automatic/systematic way to find rank-2 expansion. Maybe looking at this expansion will help to find efficient way of multiplication. Mar 9 '14 at 9:40
• There are ways, but then you have to factor in the cost of finding the top 2 singular vectors and singular values. The best modern ways for this are randomized SVD and the Arnoldi iteration, which require multiplying the matrix by several vectors - so you are back where you started. You could find a non-SVD low rank approximation with rank-revealing QR, but that's going to be at least as expensive as a matrix vector multiplication for a sparse matrix, and much more expensive for a full matrix. Mar 9 '14 at 10:32

More specifically, if an $m\times n$ matrix is of rank $r$, its (compact) SVD representation is the product of an $m\times r$ matrix, an $r \times r$ diagonal matrix, and an $r \times n$ matrix. If $r$ is constant, you can multiply this by a vector in $O(m+n)$ time.