Abstract
Large matrices appearing in machine learning problems often have complex hierarchical structures that go beyond what can be found by traditional linear algebra tools, such as eigendecomposition. Inspired by ideas from multiresolution analysis, this paper introduces a new notion of matrix factorization that can capture struc ture in matrices at multiple different scales. The resulting Multiresolution Matrix Factorizations (MMFs) not only provide a wavelet basis for sparse approximation, but can also be used for matrix compression (similar to Nystr¨om approximations) and as a prior for matrix completion.