Fast matrix – vector multiplication

Hi all. This is the first part of my notes on ideas for fast multiplication of matrices with vectors. It’s also the first time that I use the LatexToWordpress tool (mentioned a few posts back). More to follow soon.

 Low – rank approximation ideas

2.1. Low – rank approximation

Let’s suppose that the matrix M has rank r. Then, if {r\leq N} we can use the singular value decomposition, writing M as follows,

\displaystyle M = RSV \ \ \ \ \ (1)

where R, V are complex and unitary matrices, {RR^{T}=I=VV^{T}}, and S is a diagonal matrix with non-zero elements, {\sigma_{1}\geq \sigma_{2}\geq \sigma_{3}\ldots\sigma_{N}\geq 0}.

This way we can carry out the multiplication at {O(N\cdot r)} by doing the product {RSVv}. Since many matrices have full rank, this technique is of little applicability but produces exact results (up to the floating point error).

2.2. Effective low – rank approximation

In order to be able to use the above ideas in more general cases we do the following. Let the SVD of the matrix M be the same as before. Then we choose a real number {\epsilon>0} and define the effective low – rank approximation of M, {M_{\epsilon}}, as the matrix {RS_{\epsilon}V}, where {S_{epsilon}} is the diagonal matrix with all the singular values {\sigma_{i}} such that

\displaystyle \sigma_{i}\geq \epsilon\cdot \sigma_{1} \ \ \ \ \ (2)

This new matrix {M_{\epsilon}} has rank

\displaystyle r_{\epsilon}=\#\left\{\sigma_{i}:\sigma_{i}\geq \epsilon\cdot \sigma_{1} \right\} \ \ \ \ \ (3)

Using this idea, we can carry out the multiplication at {O(N\cdot r_{\epsilon})} with an extra error, due to the approximation.