Multiresolution Matrix Compression
Abstract
Multiresolution Matrix Factorization (MMF) is a recently introduced method for finding multiscale structure and defining wavelets on graphs and matrices. MMF can also be used for matrix compression (sketching). However, the original MMF algorithm of (Kondor et al., 2014) scales with n^3 or worse (where n is the number of rows/columns in the matrix to be factorized) making it infeasible for large scale problems. In this paper we describe pMMF, a fast parallel MMF algorithm, which can scale to n in the range of millions. Our experimental results show that when used for matrix compression, pMMF often achieves much lower error than competing algorithms (especially on network data), yet for sparse matrices its running time scales close to linearly with n.
Cite
Text
Teneva et al. "Multiresolution Matrix Compression." International Conference on Artificial Intelligence and Statistics, 2016.Markdown
[Teneva et al. "Multiresolution Matrix Compression." International Conference on Artificial Intelligence and Statistics, 2016.](https://mlanthology.org/aistats/2016/teneva2016aistats-multiresolution/)BibTeX
@inproceedings{teneva2016aistats-multiresolution,
title = {{Multiresolution Matrix Compression}},
author = {Teneva, Nedelina and Mudrakarta, Pramod Kaushik and Kondor, Risi},
booktitle = {International Conference on Artificial Intelligence and Statistics},
year = {2016},
pages = {1441-1449},
url = {https://mlanthology.org/aistats/2016/teneva2016aistats-multiresolution/}
}