Unique sparse decomposition of low rank matrices

The problem of finding a 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 <inline-formula> <tex-math notation="LaTeX">$\boldsymbol Y\in \mathbb R ^{p\times n}$ </tex-math></inline-formula> that admits a sparse representation. Specifically, we consider <inline-formula> <tex-math notation="LaTeX">$\boldsymbol Y= \boldsymbol A \boldsymbol X$ </tex-math></inline-formula> where the matrix <inline-formula> <tex-math notation="LaTeX">$\boldsymbol A\in \mathbb R^{p\times r}$ </tex-math></inline-formula> has full column rank, with <inline-formula> <tex-math notation="LaTeX">$r < \min \{n,p\}$ </tex-math></inline-formula>, and the matrix <inline-formula> <tex-math notation="LaTeX">$\boldsymbol X\in \mathbb R^{r\times n}$ </tex-math></inline-formula> is element-wise sparse. We prove that this low rank, sparse decomposition of <inline-formula> <tex-math notation="LaTeX">$\boldsymbol Y$ </tex-math></inline-formula> 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 its nonconvex optimization landscape shows that any <italic>strict</italic> local solution is close to the ground truth, and can be recovered by a simple data-driven initialization followed with any second order descent algorithm. Our theoretical findings are corroborated by numerical experiments.<xref ref-type="fn" rid="fn1">1</xref>