Search

MiS Preprint Repository

We have decided to discontinue the publication of preprints on our preprint server as of 1 March 2024. The publication culture within mathematics has changed so much due to the rise of repositories such as ArXiV (www.arxiv.org) that we are encouraging all institute members to make their preprints available there. An institute's repository in its previous form is, therefore, unnecessary. The preprints published to date will remain available here, but we will not add any new preprints here.

MiS Preprint
34/2014

New Estimates for the Recursive Low-Rank Truncation

Wolfgang Hackbusch

Abstract

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.

Received:
01.03.14
Published:
04.03.14
MSC Codes:
65Fxx, 65F30, 15A18, 15A45
Keywords:
low-rank approximation, singular value decomposition, error estimate, Hierarchical matrix

Related publications

inJournal
2016 Repository Open Access
Wolfgang Hackbusch

New estimates for the recursive low-rank truncation of block-structured matrices

In: Numerische Mathematik, 132 (2016) 2, pp. 303-328