Unique sparse decomposition of low rank matrices

Abstract

The problem of finding the unique low dimensional decomposition of a given matrix has been a fundamental and recurrent problem in many areas. In this paper, we study the problem of seeking a unique decomposition of a low rank matrix $Y\in {\mathbb{R}}^{p\times n}$ that admits a sparse representation. Specifically, we consider $Y=AX\in {\mathbb{R}}^{p\times n}$ where the matrix $A\in {\mathbb{R}}^{p\times r}$ has full column rank, with $r<\min \{n,p\}$, and the matrix $X\in {\mathbb{R}}^{r\times n}$ is element-wise sparse. We prove that this sparse decomposition of $Y$ can be uniquely identified, up to some intrinsic signed permutation. Our approach relies on solving a nonconvex optimization problem constrained over the unit sphere. Our geometric analysis for the nonconvex optimization landscape shows that any {\em strict} local solution is close to the ground truth solution, and can be recovered by a simple data-driven initialization followed with any second order descent algorithm. At last, we corroborate these theoretical results with numerical experiments.

arXiv commentAccepted by 2021 Neurips, in IEEE Transactions on Information Theory, 2022

References in corpus (6)

• Generalized power method for sparse principal component analysis
• Complete Dictionary Recovery over the Sphere I: Overview and the Geometric Picture
• Scalable Robust Matrix Recovery: Frank-Wolfe Meets Proximal Methods
• Finding a sparse vector in a subspace: Linear sparsity using alternating directions
• From Symmetry to Geometry: Tractable Nonconvex Problems
• Efficient Sparse Coding using Hierarchical Riemannian Pursuit