Unique Sparse Decomposition of Low Rank Matrices

DOI10.1109/TIT.2022.3223230MaRDI QIDQ6153680zbMATH OpenOpenAlexFDO

Publication date 19 March 2024

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2106.07736

matrix factorization nonconvex optimization unsupervised learning sparse representation low-rank decomposition second-order geometry

Mathematics Subject Classification ID

Information and communication theory, circuits (94-XX)

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 i n m a t h b b R^{p i m e s n}

that admits a sparse representation. Specifically, we consider

Y = A X i n m a t h b b R^{p i m e s n}

where the matrix

A i n m a t h b b R^{p i m e s r}

has full column rank, with

r < m i n n, p

, and the matrix

X i n m a t h b b R^{r i m e s 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.

This page was built for publication: Unique Sparse Decomposition of Low Rank Matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6153680)