New Estimates for the Recursive Low-Rank Truncation

Wolfgang Hackbusch

Contact the author: Please use for correspondence this email.
Submission date: 01. Mar. 2014 (revised version: September 2014)
Pages: 19
published in: Numerische Mathematik, 132 (2016) 2, p. 303-328 
DOI number (of the published article): 10.1007/s00211-015-0716-7
Bibtex
with the following different title: New estimates for the recursive low-rank truncation of block-structured matrices
MSC-Numbers: 65Fxx, 65F30, 15A18, 15A45
Keywords and phrases: low-rank approximation, singular value decomposition, error estimate, Hierarchical matrix
Download full preprint: PDF (973 kB)

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×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.