# Fast Structured Orthogonal Dictionary Learning using Householder Reflections

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

## Key facts

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

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

- [Learning graphs from data: A signal representation perspective](https://mlsanity.com/paper/1806.00848/) (2018)
- [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)
- [Simple Alternating Minimization Provably Solves Complete Dictionary Learning](https://mlsanity.com/paper/2210.12816/) (2022)
- [Learning Fast Sparsifying Transforms](https://mlsanity.com/paper/1611.08230/) (2016)
- [Fast Orthonormal Sparsifying Transforms Based on Householder Reflectors](https://mlsanity.com/paper/1611.08229/) (2016)

## Abstract (arXiv)

In this paper, we propose and investigate algorithms for the structured orthogonal dictionary learning problem. First, we investigate the case when the dictionary is a Householder matrix. We give sample complexity results and show theoretically guaranteed approximate recovery (in the l∞ sense) with optimal computational complexity. We then attempt to generalize these techniques when the dictionary is a product of a few Householder matrices. We numerically validate these techniques in the sample-limited setting to show performance similar to or better than existing techniques while having much improved computational complexity.