3
$\begingroup$

Assuming the singular value decomposition is known, how is it the matrix-vector product of $\mathbf{A}$ ($m \times n$) and vector $\mathbf{x}$ ($n \times 1$) has $O(m+n)$ complexity? Somewhat related: Efficient low rank matrix-vector multiplication and this post on Using SVD to approximate matrix-vector multiplication?

The way I break it down, for $\mathbf{Ax} = \mathbf{U \Sigma V}^T\mathbf{x}$:

  • the product $\mathbf{L} = \mathbf{V}^T\mathbf{x}$ has $O(n^2)$ complexity
  • the product $\mathbf{H} = \mathbf{\Sigma}\mathbf{L}$ has $O(n)$ complexity
  • the product $\mathbf{U}\mathbf{H}$ has $O(mn)$ complexity.

Why is the matrix-product complexity of order $O(m+n)$ instead of $O(n^2 + n + mn)$?

$\endgroup$
2
$\begingroup$

If your question has the same conditions as the two posts you referred to, notice that they assume $A$ has rank $r$. Then $U$ is $m\times r$, $\Sigma$ is $r\times r$, $V^T$ is $r\times n$.

So

  • the product $\mathbf{L} = \mathbf{V}^T\mathbf{x}$ has $O(rn)$ complexity
  • the product $\mathbf{H} = \mathbf{\Sigma}\mathbf{L}$ has $O(r)$ complexity
  • the product $\mathbf{U}\mathbf{H}$ has $O(rm)$ complexity.

This gives $O(r(m+n))$ which is $O(m+n)$ if $r$ is fixed. This is in the sense that the problem has many different $A$'s or $x$'s, and the ranks of $A$'s remain constant.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks... my question is in the same spirit of $\mathbf{A}$ with rank $r$. This is the crux of my question: how can the problem go from $O(r(m+n))$ to $O(m+n)$? In a code writing sense, it doesn't look like you need any fewer nested for-loops to execute the computation. I just don't see how the complexity decreases. $\endgroup$ – user2183232343 Jan 17 '16 at 20:36
  • $\begingroup$ @dangler: Let's say we know a sequence of matrices $A$ that have rank $2$. In this case the computation becomes $O(2(m+n))$ which is just $O(m+n)$, since the big $O$ notation "annihilates" the constant coefficient. If it is just one matrix, of course it does not reduce the complexity at all. But for many many matrices, the number of operation $2n^2$ is in the order of $O(n^2)$. It means the complexity increases quadratically with respect to $n$. $\endgroup$ – KittyL Jan 17 '16 at 21:16

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.