Multiresolution Matrix Compression

Nedelina Teneva, Pramod Kaushik Mudrakarta, Risi Kondor
Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, PMLR 51:1441-1449, 2016.

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 this Paper

BibTeX
@InProceedings{pmlr-v51-teneva16, title = {Multiresolution Matrix Compression}, author = {Teneva, Nedelina and Mudrakarta, Pramod Kaushik and Kondor, Risi}, booktitle = {Proceedings of the 19th International Conference on Artificial Intelligence and Statistics}, pages = {1441--1449}, year = {2016}, editor = {Gretton, Arthur and Robert, Christian C.}, volume = {51}, series = {Proceedings of Machine Learning Research}, address = {Cadiz, Spain}, month = {09--11 May}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v51/teneva16.pdf}, url = {https://proceedings.mlr.press/v51/teneva16.html}, 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.} }
Endnote
%0 Conference Paper %T Multiresolution Matrix Compression %A Nedelina Teneva %A Pramod Kaushik Mudrakarta %A Risi Kondor %B Proceedings of the 19th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2016 %E Arthur Gretton %E Christian C. Robert %F pmlr-v51-teneva16 %I PMLR %P 1441--1449 %U https://proceedings.mlr.press/v51/teneva16.html %V 51 %X 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.
RIS
TY - CPAPER TI - Multiresolution Matrix Compression AU - Nedelina Teneva AU - Pramod Kaushik Mudrakarta AU - Risi Kondor BT - Proceedings of the 19th International Conference on Artificial Intelligence and Statistics DA - 2016/05/02 ED - Arthur Gretton ED - Christian C. Robert ID - pmlr-v51-teneva16 PB - PMLR DP - Proceedings of Machine Learning Research VL - 51 SP - 1441 EP - 1449 L1 - http://proceedings.mlr.press/v51/teneva16.pdf UR - https://proceedings.mlr.press/v51/teneva16.html AB - 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. ER -
APA
Teneva, N., Mudrakarta, P.K. & Kondor, R.. (2016). Multiresolution Matrix Compression. Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 51:1441-1449 Available from https://proceedings.mlr.press/v51/teneva16.html.

Related Material