# How is it the matrix-vector multiplication with SVD is $O(m+n)$?

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

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$.
• 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.
• 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. Jan 17 '16 at 20:36
• @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$. Jan 17 '16 at 21:16