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 Y is a product of a Householder matrix H and a binary matrix X. First, we show that the exact recovery of the factors H and X from Y is guaranteed with (1) columns in Y . Next, we show approximate recovery (in the l sense) can be done in polynomial time(O(np)) with ( n) columns in Y . We hope the techniques in this work help in developing alternate algorithms for orthogonal dictionary learning.

Tasks

Reproductions