  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 $\Omega(1)$ columns in
$\mathbf{Y}$ . Next, we show approximate recovery (in the $l\infty$ sense) can
be done in polynomial time($O(np)$) with $\Omega(\log n)$ columns in
$\mathbf{Y}$ . We hope the techniques in this work help in developing alternate
algorithms for orthogonal dictionary learning.
