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.

基于正交字典学习问题，我们提出了一种新的矩阵分解方法，其中数据矩阵 Y 是 Householder 矩阵 H 和二进制矩阵 X 的乘积。首先，我们证明了从 Y 中确切恢复出因子 H 和 X 是在 Y 中具有 Ω(1) 列的；接下来，我们证明了在 Y 中具有 Ω(log n) 列时，可以在多项式时间 (O (np)) 内以 l∞意义上近似恢复。希望本文中的技术有助于开发正交字典学习的替代算法。

有效的矩阵分解：通过 Householder 变换

Efficient Matrix Factorization Via Householder Reflections

The goal of Boolean Matrix Factorization (BMF) is to approximate a given
binary matrix as the product of two low-rank binary factor matrices, where the
product of the factor matrices is computed under the Boolean algebra. While the
problem is computationally hard, it is also attractive because the binary
nature of the factor matrices makes them highly interpretable. In the last
decade, BMF has received a considerable amount of attention in the data mining
and formal concept analysis communities and, more recently, the machine
learning and the theory communities also started studying BMF. In this survey,
we give a concise summary of the efforts of all of these communities and raise
some open questions which in our opinion require further investigation.

本文概述了 Boolean Matrix Factorization（BMF）在数据挖掘、正式概念分析、机器学习和理论等领域的研究进展，提出了需要进一步探讨的问题。