×

Sampling and multilevel coarsening algorithms for fast matrix approximations. (English) Zbl 1463.65096

The paper discusses approximation of large and sparse matrices and proposes a new approach based primarily on coarsening techniques. The authors consider several standard applications of the new strategy, in particular, computation of the partial singular value decomposition, column subset selection problem and graph sparsification. Furthermore, other interesting applications where one faces large and sparse matrices are mentioned. Approximation quality of the coarsening strategy based on column matching is theoretically analyzed. The achieved error bounds are similar to those developed earlier for randomized sampling. Performance of the coarsening techniques is demonstrated in various considered applications also numerically. The paper shows that the coarsening techniques can often provide similar results as other and more expensive alternatives.

MSC:

65F55 Numerical methods for low-rank matrix approximation; matrix compression
65F50 Computational methods for sparse matrices
68W25 Approximation algorithms
PDFBibTeX XMLCite
Full Text: DOI arXiv