# Unique sparse decomposition of low rank matrices

arXiv: https://arxiv.org/abs/2106.07736 · HTML: https://mlsanity.com/paper/2106.07736/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 57 references that are in the map.
- First posted on arXiv 14 Jun 2021.

## Builds on (most cited first, 18 of 18)

- [How to Escape Saddle Points Efficiently](https://mlsanity.com/paper/1703.00887/) (2017)
- [From Symmetry to Geometry: Tractable Nonconvex Problems](https://mlsanity.com/paper/2007.06753/) (2020)
- [Learning Sparsely Used Overcomplete Dictionaries via Alternating Minimization](https://mlsanity.com/paper/1310.7991/) (2013)
- [On the Optimization Landscape of Tensor Decompositions](https://mlsanity.com/paper/1706.05598/) (2017)
- [Complete Dictionary Recovery over the Sphere](https://mlsanity.com/paper/1504.06785/) (2015)
- [Adaptive Estimation in Structured Factor Models with Applications to Overlapping Clustering](https://mlsanity.com/paper/1704.06977/) (2017)
- [Finding a sparse vector in a subspace: Linear sparsity using alternating directions](https://mlsanity.com/paper/1412.4659/) (2014)
- [Structured Local Optima in Sparse Blind Deconvolution](https://mlsanity.com/paper/1806.00338/) (2018)
- [Polynomial Matrix Completion for Missing Data Imputation and Transductive Learning](https://mlsanity.com/paper/1912.06989/) (2019)
- [Geometry and Symmetry in Short-and-Sparse Deconvolution](https://mlsanity.com/paper/1901.00256/) (2019)
- [Scalable Robust Matrix Recovery: Frank-Wolfe Meets Proximal Methods](https://mlsanity.com/paper/1403.7588/) (2014)
- [Analysis of the Optimization Landscapes for Overcomplete Representation Learning](https://mlsanity.com/paper/1912.02427/) (2019)
- [Manifold Gradient Descent Solves Multi-Channel Sparse Blind Deconvolution Provably and Efficiently](https://mlsanity.com/paper/1911.11167/) (2019)
- [A fast algorithm with minimax optimal guarantees for topic models with an unknown number of topics](https://mlsanity.com/paper/1805.06837/) (2018)
- [On the Global Geometry of Sphere-Constrained Sparse Blind Deconvolution](https://mlsanity.com/paper/1901.01913/) (2019)
- [Optimal estimation of sparse topic models](https://mlsanity.com/paper/2001.07861/) (2020)
- [Efficient Sparse Coding using Hierarchical Riemannian Pursuit](https://mlsanity.com/paper/2104.10314/) (2021)
- [Toward Guaranteed Illumination Models for Non-Convex Objects](https://mlsanity.com/paper/1307.1437/) (2013)

## Built on by (most cited first, 4 of 4)

- [Matrix Compression via Randomized Low Rank and Low Precision Factorization](https://mlsanity.com/paper/2310.11028/) (2023)
- [A Geometric Approach to k-means](https://mlsanity.com/paper/2201.04822/) (2022)
- [Optimal vintage factor analysis with deflation varimax](https://mlsanity.com/paper/2310.10545/) (2023)
- [Federated Independent Component Analysis via Spectral Alignment and Robust Aggregation](https://mlsanity.com/paper/2505.20532/) (2025)

## Abstract (arXiv)

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∈ ℝp× n that admits a sparse representation. Specifically, we consider Y = A X∈ ℝp× n where the matrix A∈ ℝp× r has full column rank, with r < minn,p, and the matrix X∈ ℝr× 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.