EM Converges for a Mixture of Many Linear Regressions


We study the convergence of the Expectation-Maximization (EM) algorithm for mixtures of linear regressions with an arbitrary number k≥3 of components. We show that as long as signal-to-noise ratio (SNR) is Ω(k), well-initialized EM converges to the true regression parameters. Our finite-sample analysis implies the exact recovery as σ→0, in contrast to most previous local convergence results for EM.

[Arxiv] [Conference]