# Efficient Matrix Factorization Via Householder Reflections

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 24 references that are in the map.
- First posted on arXiv 13 May 2024.

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

- [Learning graphs from data: A signal representation perspective](https://mlsanity.com/paper/1806.00848/) (2018)
- [Complete Dictionary Recovery over the Sphere I: Overview and the Geometric Picture](https://mlsanity.com/paper/1511.03607/) (2015)
- [Simple, Efficient, and Neural Algorithms for Sparse Coding](https://mlsanity.com/paper/1503.00778/) (2015)
- [Learning Sparsely Used Overcomplete Dictionaries via Alternating Minimization](https://mlsanity.com/paper/1310.7991/) (2013)
- [New Algorithms for Learning Incoherent and Overcomplete Dictionaries](https://mlsanity.com/paper/1308.6273/) (2013)
- [Complete Dictionary Recovery over the Sphere](https://mlsanity.com/paper/1504.06785/) (2015)
- [Learning parametric dictionaries for graph signals](https://mlsanity.com/paper/1401.0887/) (2014)
- [Local Identification of Overcomplete Dictionaries](https://mlsanity.com/paper/1401.6354/) (2014)
- [Simple Alternating Minimization Provably Solves Complete Dictionary Learning](https://mlsanity.com/paper/2210.12816/) (2022)
- [Provable Alternating Gradient Descent for Non-negative Matrix Factorization with Strong Correlations](https://mlsanity.com/paper/1706.04097/) (2017)

## Abstract (arXiv)

Motivated by orthogonal dictionary learning problems, we propose a novel method for matrix factorization, where the data matrix Y is a product of a Householder matrix H and a binary matrix X. First, we show that the exact recovery of the factors H and X from Y is guaranteed with Omega(1) columns in Y . Next, we show approximate recovery (in the l∞ sense) can be done in polynomial time(O(np)) with Omega(log n) columns in Y . We hope the techniques in this work help in developing alternate algorithms for orthogonal dictionary learning.