# Sparse Matrix Factorization

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Nov 2013.

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

- [Non-Convex Compressed Sensing with Training Data](https://mlsanity.com/paper/2101.08310/) (2021)
- [Learning Trees of ℓ0-Minimization Problems](https://mlsanity.com/paper/2302.02548/) (2023)
- [Don't Forget Your Embeddings: Robust Knowledge Erasure via Precise Editing of Embeddings](https://mlsanity.com/paper/2606.03695/) (2026)

## Abstract (arXiv)

We investigate the problem of factorizing a matrix into several sparse matrices and propose an algorithm for this under randomness and sparsity assumptions. This problem can be viewed as a simplification of the deep learning problem where finding a factorization corresponds to finding edges in different layers and values of hidden units. We prove that under certain assumptions for a sparse linear deep network with n nodes in each layer, our algorithm is able to recover the structure of the network and values of top layer hidden units for depths up to tilde O(n1/6). We further discuss the relation among sparse matrix factorization, deep learning, sparse recovery and dictionary learning.