Back to Search
Start Over
Unique Sparse Decomposition of Low Rank Matrices
- Source :
- IEEE Transactions on Information Theory. 69:2452-2484
- Publication Year :
- 2023
- Publisher :
- Institute of Electrical and Electronics Engineers (IEEE), 2023.
-
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 = A X\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.<br />Accepted by 2021 Neurips, in IEEE Transactions on Information Theory, 2022
- Subjects :
- Signal Processing (eess.SP)
FOS: Computer and information sciences
Computer Science - Machine Learning
Numerical Analysis (math.NA)
Library and Information Sciences
Machine Learning (cs.LG)
Computer Science Applications
Optimization and Control (math.OC)
FOS: Mathematics
FOS: Electrical engineering, electronic engineering, information engineering
Mathematics - Numerical Analysis
Electrical Engineering and Systems Science - Signal Processing
Mathematics - Optimization and Control
Information Systems
Subjects
Details
- ISSN :
- 15579654 and 00189448
- Volume :
- 69
- Database :
- OpenAIRE
- Journal :
- IEEE Transactions on Information Theory
- Accession number :
- edsair.doi.dedup.....bfc9fabf3cb8f34668e289bbef98245f