Efficient Matrix Factorization Via Householder Reflections
This work addresses orthogonal dictionary learning, a domain-specific problem in signal processing, with incremental improvements in recovery guarantees.
The paper tackles the problem of matrix factorization for orthogonal dictionary learning by proposing a method to recover a Householder matrix and a binary matrix from their product, guaranteeing exact recovery with a constant number of columns and approximate recovery in polynomial time with logarithmic columns.
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 $Ω(1)$ columns in $\mathbf{Y}$ . Next, we show approximate recovery (in the $l\infty$ sense) can be done in polynomial time($O(np)$) with $Ω(\log n)$ columns in $\mathbf{Y}$ . We hope the techniques in this work help in developing alternate algorithms for orthogonal dictionary learning.