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 Y ϵ Rp×n that admits a sparse representation. Specifically, we consider Y= A X where the matrix A ϵ Rp×r has full column rank, with r < n,p, and the matrix X ϵ Rr×n is element-wise sparse. We prove that this low rank, 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 its nonconvex optimization landscape shows that any strict 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.1.