Beyond low rank + sparse: Multi-scale low rank matrix decomposition

The recent low rank + sparse matrix decomposition [1,2] enables us to decompose a matrix into sparse and globally low rank components. In this paper, we present a natural generalization and consider the decomposition of matrices into low rank components of multiple scales. The proposed multi-scale low rank decomposition is well motivated in practice, since natural data often exhibit multi-scale structure instead of globally or sparsely. Concretely, we propose a multi-scale low rank modeling to represent 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 a deterministic incoherence condition, the convex program recovers the multi-scale low rank components exactly. Empirically, we show that the multi-scale low rank decomposition provides a more intuitive decomposition than existing 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 with age information.