MiS Preprint Repository

The best approximation of a matrix by a low-rank matrix can be obtained by the singular value decomposition. For large-sized matrices this approach is too costly. Instead one may use a block decomposition. Approximating the small submatrices by low-rank matrices and agglomerating them into a new, coarser block decomposition, one obtains a recursive method. The required computation work is $O(rnm)$ if $r$ is the desired rank and $n\times m$ is the size of the matrix. The paper discusses the error $A-B$, where $A$ is the result of the recursive truncation, while $B$ is the best approximation.