Learning a mixture of two subspaces over finite fields

Aidao Chen, Anindya De, Aravindan Vijayaraghavan

Research output: Contribution to journalConference articlepeer-review

2 Scopus citations

Abstract

We study the problem of learning a mixture of two subspaces over Fn2 . The goal is to recover the individual subspaces A0, A1, given samples from a (weighted) mixture of samples drawn uniformly from the subspaces A0 and A1. This problem is computationally challenging, as it captures the notorious problem of “learning parities with noise” in the degenerate setting when A1 ⊆ A0. 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 Fn2? The main result of this paper is an affirmative answer to the above question. Namely, we show the following results: 1. When the subspaces A0 and A1 are incomparable, i.e., A0 6⊆ A1 and A1 6⊆ A0, then there is a polynomial time algorithm to recover the subspaces A0 and A1. 2. In the case when A1 ⊆ A0 such that dim(A1) ≤ α · dim(A0) for α < 1, there is a nO(1/(1-α)) time algorithm to recover the subspaces A0 and A1. 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.

Original languageEnglish (US)
Pages (from-to)481-504
Number of pages24
JournalProceedings of Machine Learning Research
Volume132
StatePublished - 2021
Event32nd International Conference on Algorithmic Learning Theory, ALT 2021 - Virtual, Online
Duration: Mar 16 2021Mar 19 2021

Keywords

  • learning parities with noise
  • mixture models
  • subspaces

ASJC Scopus subject areas

  • Artificial Intelligence
  • Software
  • Control and Systems Engineering
  • Statistics and Probability

Fingerprint

Dive into the research topics of 'Learning a mixture of two subspaces over finite fields'. Together they form a unique fingerprint.

Cite this