Sampling and multilevel coarsening algorithms for fast matrix approximations

Shashanka Ubaru, Yousef Saad

Research output: Contribution to journalArticlepeer-review

4 Scopus citations


This paper addresses matrix approximation problems for matrices that are large, sparse, and/or representations of large graphs. To tackle these problems, we consider algorithms that are based primarily on coarsening techniques, possibly combined with random sampling. A multilevel coarsening technique is proposed, which utilizes a hypergraph associated with the data matrix and a graph coarsening strategy based on column matching. We consider a number of standard applications of this technique as well as a few new ones. Among standard applications, we first consider the problem of computing partial singular value decomposition, for which a combination of sampling and coarsening yields significantly improved singular value decomposition results relative to sampling alone. We also consider the column subset selection problem, a popular low-rank approximation method used in data-related applications, and show how multilevel coarsening can be adapted for this problem. Similarly, we consider the problem of graph sparsification and show how coarsening techniques can be employed to solve it. We also establish theoretical results that characterize the approximation error obtained and the quality of the dimension reduction achieved by a coarsening step, when a proper column matching strategy is employed. Numerical experiments illustrate the performances of the methods in a few applications.

Original languageEnglish (US)
Article numbere2234
JournalNumerical Linear Algebra with Applications
Issue number3
StatePublished - May 2019

Bibliographical note

Funding Information:
This work was supported by the National Science Foundation under Grant NSF/CCF-1318597. Shashanka Ubaru was supported by the IBM Goldstine Postdoctoral Fellowship.

Funding Information:
National Science Foundation, Grant/Award Number: NSF/CCF-1318597

Publisher Copyright:
© 2019 John Wiley & Sons, Ltd.


  • SVD
  • coarsening
  • multilevel methods
  • randomization
  • singular values
  • subspace iteration


Dive into the research topics of 'Sampling and multilevel coarsening algorithms for fast matrix approximations'. Together they form a unique fingerprint.

Cite this