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

arXiv: https://arxiv.org/abs/1608.05749 · HTML: https://mlsanity.com/paper/1608.05749/

## Key facts

- Cited by 26 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Aug 2016.

## Built on by (most cited first, 26 of 26)

- [Training Tensor Attention Efficiently: From Cubic to Almost Linear Time](https://mlsanity.com/paper/2405.16411/) (2024)
- [Transformers can optimally learn regression mixture models](https://mlsanity.com/paper/2311.08362/) (2023)
- [Breaking the gridlock in Mixture-of-Experts: Consistent and Efficient Algorithms](https://mlsanity.com/paper/1802.07417/) (2018)
- [Theoretical Constraints on the Expressive Power of mathsfRoPE-based Tensor Attention Transformers](https://mlsanity.com/paper/2412.18040/) (2024)
- [On Learning Mixture of Linear Regressions in the Non-Realizable Setting](https://mlsanity.com/paper/2205.13166/) (2022)
- [Model Selection for Generic Contextual Bandits](https://mlsanity.com/paper/2107.03455/) (2021)
- [What Makes A Good Fisherman? Linear Regression under Self-Selection Bias](https://mlsanity.com/paper/2205.03246/) (2022)
- [Multi-Model 3D Registration: Finding Multiple Moving Objects in Cluttered Point Clouds](https://mlsanity.com/paper/2402.10865/) (2024)
- [Support Recovery of Sparse Signals from a Mixture of Linear Measurements](https://mlsanity.com/paper/2106.05951/) (2021)
- [Efficient List-Decodable Regression using Batches](https://mlsanity.com/paper/2211.12743/) (2022)
- [Imbalanced Mixed Linear Regression](https://mlsanity.com/paper/2301.12559/) (2023)
- [Linear Regression using Heterogeneous Data Batches](https://mlsanity.com/paper/2309.01973/) (2023)
- [Support Recovery in Mixture Models with Sparse Parameters](https://mlsanity.com/paper/2202.11940/) (2022)
- [Time and Memory Trade-off of KV-Cache Compression in Tensor Transformer Decoding](https://mlsanity.com/paper/2503.11108/) (2025)
- [Learning and Generalization with Mixture Data](https://mlsanity.com/paper/2504.20651/) (2025)
- [Model Selection for Generic Reinforcement Learning](https://mlsanity.com/paper/2107.05849/) (2021)
- [Model Selection in Reinforcement Learning with General Function Approximations](https://mlsanity.com/paper/2207.02992/) (2022)
- [EM for Mixture of Linear Regression with Clustered Data](https://mlsanity.com/paper/2308.11518/) (2023)
- [Unveiling the Cycloid Trajectory of EM Iterations in Mixed Linear Regression](https://mlsanity.com/paper/2405.18237/) (2024)
- [Agnostic Learning of Mixed Linear Regressions with EM and AM Algorithms](https://mlsanity.com/paper/2406.01149/) (2024)
- [Finite Sample Analysis of Tensor Decomposition for Learning Mixtures of Linear Systems](https://mlsanity.com/paper/2412.10615/) (2024)
- [Sample-Efficient Linear Regression with Self-Selection Bias](https://mlsanity.com/paper/2402.14229/) (2024)
- [Fast convergence of a Federated Expectation-Maximization Algorithm](https://mlsanity.com/paper/2408.05819/) (2024)
- [LocalKMeans: Convergence of Lloyd's Algorithm with Distributed Local Iterations](https://mlsanity.com/paper/2505.18420/) (2025)
- [Learning Mixtures of Linear Dynamical Systems via Hybrid Tensor-EM Method](https://mlsanity.com/paper/2510.06091/) (2025)
- [Expectation Maximization (EM) Converges for General Agnostic Mixtures](https://mlsanity.com/paper/2604.05842/) (2026)

## Abstract (arXiv)

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.