论文标题
在有限字段上学习两个子空间的混合
Learning a mixture of two subspaces over finite fields
论文作者
论文摘要
我们研究了在$ \ mathbb {f} _2^n $上学习两个子空间的混合物的问题。目的是恢复各个子空间，从两个子空间$ a_0 $和$ a_1 $均匀绘制的样品的（加权）混合物中给定样品。 这个问题在计算上具有挑战性，因为当$ a_1 \ subseteq a_0 $ $ a_1 \ subseteq a_0 $时，它捕获了臭名昭著的“学习噪声奇偶”的问题。这与可以在多项式时间（Vidal'03）中解决的真实问题的类似问题形成鲜明对比。这导致了以下自然问题：与噪声的学习平等是获得有效算法的唯一计算障碍，以在$ \ mathbb {f} _2 _2^n $上学习子空间的学习混合物？ 本文的主要结果是对上述问题的肯定答案。即，我们显示以下结果：1。当子空间$ a_0 $和$ a_1 $无与伦比时，即彼此内部不包含$ a_0 $和$ a_1 $，那么就有一个多项式时间算法，那么恢复了子领域$ a_0 $和$ a_1 $。 2. In the case when $A_1$ is a subspace of $A_0$ with a significant gap in the dimension i.e., $dim(A_1) \le αdim(A_0)$ for $α<1$, there is a $n^{O(1/(1-α))}$ time algorithm to recover the subspaces $A_0$ and $A_1$. 因此，我们的算法意味着两个子空间学习混合物问题的计算障碍性，除了通过学习噪声的学习平台捕获的退化设置。
We study the problem of learning a mixture of two subspaces over $\mathbb{F}_2^n$. The goal is to recover the individual subspaces, given samples from a (weighted) mixture of samples drawn uniformly from the two subspaces $A_0$ and $A_1$. This problem is computationally challenging, as it captures the notorious problem of "learning parities with noise" in the degenerate setting when $A_1 \subseteq A_0$. This is in contrast to the analogous problem over the reals that can be solved in polynomial time (Vidal'03). This leads to the following natural question: is Learning Parities with Noise the only computational barrier in obtaining efficient algorithms for learning mixtures of subspaces over $\mathbb{F}_2^n$? The main result of this paper is an affirmative answer to the above question. Namely, we show the following results: 1. When the subspaces $A_0$ and $A_1$ are incomparable, i.e., $A_0$ and $A_1$ are not contained inside each other, then there is a polynomial time algorithm to recover the subspaces $A_0$ and $A_1$. 2. In the case when $A_1$ is a subspace of $A_0$ with a significant gap in the dimension i.e., $dim(A_1) \le αdim(A_0)$ for $α<1$, there is a $n^{O(1/(1-α))}$ time algorithm to recover the subspaces $A_0$ and $A_1$. Thus, our algorithms imply computational tractability of the problem of learning mixtures of two subspaces, except in the degenerate setting captured by learning parities with noise.
