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.
Code (0)
등록된 구현이 없습니다.
Tasks
Dictionary LearningSimilar Papers 제목 키워드 기반
CWY Parametrization: a Solution for Parallelized Optimization of Orthogonal and Stiefel Matrices
We introduce an efficient approach for optimization over orthogonal groups on highly parallel computation units such as GPUs or TPUs. As in earlier work, we parametrize an orthogonal matrix as a product of Householder re…
Machine TranslationTranslationVideo PredictionBridging The Gap between Low-rank and Orthogonal Adaptation via Householder Reflection Adaptation
While following different technical routes, both low-rank and orthogonal adaptation techniques can efficiently adapt large-scale pre-training models in specific tasks or domains based on a small piece of trainable parame…
Fast Structured Orthogonal Dictionary Learning using Householder Reflections
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 result…
Dictionary LearningOne Reflection Suffice
Orthogonal weight matrices are used in many areas of deep learning. Much previous work attempt to alleviate the additional computational resources it requires to constrain weight matrices to be orthogonal. One popular ap…
GPUEfficient Orthogonal Parametrisation of Recurrent Neural Networks Using Householder Reflections
The problem of learning long-term dependencies in sequences using Recurrent Neural Networks (RNNs) is still a major challenge. Recent methods have been suggested to solve this problem by constraining the transition matri…