Efficient Matrix Factorization Via Householder Reflections

Abstract

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

17 pages, a part of this has been updated and submitted as a manuscript, titled, "Fast Structured Orthogonal Dictionary Learning using Householder Reflections" to IEEE ICASSP, 2025