Learning a mixture of two subspaces over finite fields
share
We study the problem of learning a mixture of two subspaces over 𝔽_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 ⊆ 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 𝔽_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) ≤α dim(A_1) 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.
READ FULL TEXT