Learning a mixture of two subspaces over finite fields

We study the problem of learning a mixture of two subspaces over Fⁿ₂ . The goal is to recover the individual subspaces A₀, A₁, given samples from a (weighted) mixture of samples drawn uniformly from the subspaces A₀ and A₁. This problem is computationally challenging, as it captures the notorious problem of “learning parities with noise” in the degenerate setting when A₁ ⊆ A₀. 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 Fⁿ₂? 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₀ and A₁ are incomparable, i.e., A₀ 6⊆ A₁ and A₁ 6⊆ A₀, then there is a polynomial time algorithm to recover the subspaces A₀ and A₁. 2. In the case when A₁ ⊆ A₀ such that dim(A₁) ≤ α · dim(A₀) for α < 1, there is a n^O(1/^(1-α)) time algorithm to recover the subspaces A₀ and A₁. 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.