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 we can use the singular value decomposition, writing M as follows,
where R, V are complex and unitary matrices, , and S is a diagonal matrix with non-zero elements, .
This way we can carry out the multiplication at by doing the product . 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 and define the effective low – rank approximation of M, , as the matrix , where is the diagonal matrix with all the singular values such that
This new matrix has rank
Using this idea, we can carry out the multiplication at with an extra error, due to the approximation.