  Mixed linear regression involves the recovery of two (or more) unknown
vectors from unlabeled linear measurements; that is, where each sample comes
from exactly one of the vectors, but we do not know which one. It is a classic
problem, and the natural and empirically most popular approach to its solution
has been the EM algorithm. As in other settings, this is prone to bad local
minima; however, each iteration is very fast (alternating between guessing
labels, and solving with those labels).
  In this paper we provide a new initialization procedure for EM, based on
finding the leading two eigenvectors of an appropriate matrix. We then show
that with this, a re-sampled version of the EM algorithm provably converges to
the correct vectors, under natural assumptions on the sampling distribution,
and with nearly optimal (unimprovable) sample complexity. This provides not
only the first characterization of EM's performance, but also much lower sample
complexity as compared to both standard (randomly initialized) EM, and other
methods for this problem.
