# Beyond Low Rank + Sparse: Multi-scale Low Rank Matrix Decomposition

arXiv: https://arxiv.org/abs/1507.08751 · HTML: https://mlsanity.com/paper/1507.08751/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 Jul 2015.

## Built on by (most cited first, 5 of 5)

- [Monarch: Expressive Structured Matrices for Efficient and Accurate Training](https://mlsanity.com/paper/2204.00595/) (2022)
- [Temporal Sparse Autoencoders: Leveraging the Sequential Nature of Language for Interpretability](https://mlsanity.com/paper/2511.05541/) (2025)
- [Physics-driven Deep Learning for PET/MRI](https://mlsanity.com/paper/2206.06788/) (2022)
- [A Flag Decomposition for Hierarchical Datasets](https://mlsanity.com/paper/2502.07782/) (2025)
- [Learning the Regularization in DCE-MR Image Reconstruction for Functional Imaging of Kidneys](https://mlsanity.com/paper/2109.07548/) (2021)

## Abstract (arXiv)

We present a natural generalization of the recent low rank + sparse matrix decomposition and consider the decomposition of matrices into components of multiple scales. Such decomposition is well motivated in practice as data matrices often exhibit local correlations in multiple scales. Concretely, we propose a multi-scale low rank modeling that represents a data matrix as a sum of block-wise low rank matrices with increasing scales of block sizes. We then consider the inverse problem of decomposing the data matrix into its multi-scale low rank components and approach the problem via a convex formulation. Theoretically, we show that under various incoherence conditions, the convex program recovers the multi-scale low rank components revisedeither exactly or approximately. Practically, we provide guidance on selecting the regularization parameters and incorporate cycle spinning to reduce blocking artifacts. Experimentally, we show that the multi-scale low rank decomposition provides a more intuitive decomposition than conventional low rank methods and demonstrate its effectiveness in four applications, including illumination normalization for face images, motion separation for surveillance videos, multi-scale modeling of the dynamic contrast enhanced magnetic resonance imaging and collaborative filtering exploiting age information.