Efficient Matrix Factorization Via Householder Reflections
<|reference_start|>Efficient Matrix Factorization Via Householder Reflections: 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.<|reference_end|>
@article{dash2024efficient,
    title={Efficient Matrix Factorization Via Householder Reflections},
    author={Anirudh Dash and Aditya Siripuram},
    journal={arXiv preprint arXiv:2405.07649},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.07649},
    primaryClass={eess.SP cs.LG}
}