Solving a Mixture of Many Random Linear Equations by Tensor Decomposition and Alternating Minimization

Abstract

We consider the problem of solving mixed random linear equations with $k$ components. This is the noiseless setting of mixed linear regression. The goal is to estimate multiple linear models from mixed samples in the case where the labels (which sample corresponds to which model) are not observed. We give a tractable algorithm for the mixed linear equation problem, and show that under some technical conditions, our algorithm is guaranteed to solve the problem exactly with sample complexity linear in the dimension, and polynomial in $k$, the number of components. Previous approaches have required either exponential dependence on $k$, or super-linear dependence on the dimension. The proposed algorithm is a combination of tensor decomposition and alternating minimization. Our analysis involves proving that the initialization provided by the tensor method allows alternating minimization, which is equivalent to EM in our setting, to converge to the global optimum at a linear rate.

39 pages, 2 figures

Cited by in corpus (21)

• Principal component analysis for big data
• Homotopy Analysis for Tensor PCA
• Max-Affine Regression: Provable, Tractable, and Near-Optimal Statistical Estimation
• Robust high dimensional factor models with applications to statistical machine learning
• Learning Mixtures of Linear Regressions with Nearly Optimal Complexity
• Optimal Subspace Estimation Using Overidentifying Vectors via Generalized Method of Moments
• Global Convergence of EM Algorithm for Mixtures of Two Component Linear Regression
• Robust Meta-learning for Mixed Linear Regression with Small Batches
• Alternating Minimization Converges Super-Linearly for Mixed Linear Regression
• Iterative Least Trimmed Squares for Mixed Linear Regression
• Sample Complexity of Learning Mixtures of Sparse Linear Regressions
• On the Minimax Optimality of the EM Algorithm for Learning Two-Component Mixed Linear Regression
• Convergence of Parameter Estimates for Regularized Mixed Linear Regression Models
• Breaking the gridlock in Mixture-of-Experts: Consistent and Efficient Algorithms
• Meta-learning for mixed linear regression
• Learning Mixtures of Linear Regressions in Subexponential Time via Fourier Moments
• Learning Mixtures of Graphs from Epidemic Cascades
• Recovery of sparse linear classifiers from mixture of responses
• Learning Mixtures of Low-Rank Models
• Learning Mixtures of Sparse Linear Regressions Using Sparse Graph Codes
• Support Recovery of Sparse Signals from a Mixture of Linear Measurements