# Using SVD to approximate matrix-vector multiplication?

Given some matrix A, is it possible to use Singular Value Decomposition to approximate Ax for some vector x within some error bound? According to Efficient low rank matrix-vector multiplication, it should be possible in O(m+n) time (where A is m by n). I'm not really sure how to get information from that answer though.

Throwing away small singular values gives a low rank approximation, call it $L$, to $A$. Since the Euclidean operator norm of a matrix is the largest singular value, $\| L-A \|_2$ is the largest singular value that was thrown away; call it $\sigma_k$. Hence

$$\frac{\| Lx-Ax \|_2}{\| x \|_2} \leq \sigma_k.$$

If you leave behind $\ell$ singular values, then calculating $Lx$ with this SVD approach requires you to multiply by a $\ell \times n$ (usually dense) matrix, then a $\ell \times \ell$ diagonal matrix, then a $m \times \ell$ (usually dense) matrix. Overall this multiplication step takes essentially $\ell m + \ell + \ell n$ time. (Of course getting the SVD the first time takes much longer than that.) This is $O(m+n)$ if $\ell$ is fixed, but holding $\ell$ fixed is not necessarily what you want to do--it depends on the $A$s that you are considering in your application.

• How are you computing the SVD in $O(m+n)$ time? May 13 '15 at 21:43
• @user7530 I'm not; let me make a minor edit to clarify. (I thought it was clear, but maybe not.)
– Ian
May 13 '15 at 21:43
• Oh I see; this means the approach makes sense if you need to compute many ($> n$) matrix-vector products? May 13 '15 at 21:46
• @user7530 Correct. It also makes sense even if you need to compute relatively few matrix-vector products, but you know only $A$, not $x$, until the real-time application goes live. Then you could precompute the SVD and use this approach to compute the products in real time.
– Ian
May 13 '15 at 21:46