Anirudh Dash

Anirudh Dash, Aditya Siripuram

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_{\infty}$ 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.

Anirudh Dash, Aditya Siripuram

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.