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 = {Nedelina Teneva and Pramod Kaushik Mudrakarta and Risi Kondor}, pages = {1441--1449}, year = {2016}, editor = {Arthur Gretton and Christian C. Robert}, 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 = {http://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 %J Proceedings of Machine Learning Research %P 1441--1449 %U http://proceedings.mlr.press %V 51 %W PMLR %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 PY - 2016/05/02 DA - 2016/05/02 ED - Arthur Gretton ED - Christian C. Robert ID - pmlr-v51-teneva16 PB - PMLR SP - 1441 DP - PMLR EP - 1449 L1 - http://proceedings.mlr.press/v51/teneva16.pdf UR - http://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 PMLR 51:1441-1449

Related Material