Matrices that appear in modern data analysis and machine learning problems often have complex hierarchical structures that go beyond what can be uncovered by traditional linear algebra tools, such as eigendecompositions. Inspired by ideas from multiresolution analysis, we introduce a new notion of matrix factorization that can capture structure 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 and as a prior for matrix completion. The work presented in this talk was done jointly with Nedelina Teneva and Vikas Garg.