3
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ How are you computing the SVD in $O(m+n)$ time? $\endgroup$
    – user7530
    May 13 '15 at 21:43
  • $\begingroup$ @user7530 I'm not; let me make a minor edit to clarify. (I thought it was clear, but maybe not.) $\endgroup$
    – Ian
    May 13 '15 at 21:43
  • $\begingroup$ Oh I see; this means the approach makes sense if you need to compute many ($> n$) matrix-vector products? $\endgroup$
    – user7530
    May 13 '15 at 21:46
  • 1
    $\begingroup$ @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. $\endgroup$
    – Ian
    May 13 '15 at 21:46

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.