4
$\begingroup$

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)?

$\endgroup$
5
  • 1
    $\begingroup$ Do you know the actual rank-2 expansion, or just know theoretically that it has rank-2? $\endgroup$
    – Nick Alger
    Mar 8 '14 at 20:05
  • 1
    $\begingroup$ For a matrix to be orthogonal, it must have full rank. $\endgroup$
    – augurar
    Mar 8 '14 at 20:39
  • $\begingroup$ @augurar you right, I've mixed different questions. $\endgroup$
    – DikobrAz
    Mar 9 '14 at 9:38
  • $\begingroup$ @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. $\endgroup$
    – DikobrAz
    Mar 9 '14 at 9:40
  • 2
    $\begingroup$ 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. $\endgroup$
    – Nick Alger
    Mar 9 '14 at 10:32
3
$\begingroup$

If you have an SVD representation of the matrix, you can use this to compute the product in linear time. I'm not sure how to efficiently compute this representation, though. You can also truncate the SVD of a higher-rank matrix to get a low-rank approximation.

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.

$\endgroup$
4
  • $\begingroup$ How can I compute product in linear time using SVD? I can multiply NxN matrix by Nx1 vector in O(N) only if it is diagonal/band matrix. $\endgroup$
    – DikobrAz
    Mar 9 '14 at 9:43
  • $\begingroup$ Or has any other structure with O(N) non-zero elements. $\endgroup$
    – DikobrAz
    Mar 9 '14 at 10:03
  • $\begingroup$ @DikobrAz I have updated my answer, hope this clarifies things. $\endgroup$
    – augurar
    Mar 9 '14 at 23:21
  • $\begingroup$ I see, thank you for clarification. $\endgroup$
    – DikobrAz
    Mar 10 '14 at 7:34

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.