mlsanityData to 7 Oct 2026

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

arXiv 1608.05749 ↗First posted 19 Aug 2016cs.LG cs.IT math.ITcited by 26

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2018: 1; 2019: 0; 2020: 0; 2021: 3; 2022: 5; 2023: 4; 2024: 8; 2025: 4; 2026: 1.

26 papers.

Sort:

By area:

  1. 2024Training Tensor Attention Efficiently: From Cubic to Almost Linear Timecited by 29
  2. 2023Transformers can optimally learn regression mixture modelscited by 15
  3. 2018Breaking the gridlock in Mixture-of-Experts: Consistent and Efficient Algorithmscited by 13
  4. 2024Theoretical Constraints on the Expressive Power of mathsfRoPE-based Tensor Attention Transformerscited by 12
  5. 2022On Learning Mixture of Linear Regressions in the Non-Realizable Settingcited by 10
  6. 2021Model Selection for Generic Contextual Banditscited by 7
  7. 2022What Makes A Good Fisherman? Linear Regression under Self-Selection Biascited by 7
  8. 2024Multi-Model 3D Registration: Finding Multiple Moving Objects in Cluttered Point Cloudscited by 7
  9. 2021Support Recovery of Sparse Signals from a Mixture of Linear Measurementscited by 6
  10. 2022Efficient List-Decodable Regression using Batchescited by 5
  11. 2023Imbalanced Mixed Linear Regressioncited by 3
  12. 2023Linear Regression using Heterogeneous Data Batchescited by 3
14 more
  1. 2022Support Recovery in Mixture Models with Sparse Parameterscited by 2
  2. 2025Time and Memory Trade-off of KV-Cache Compression in Tensor Transformer Decodingcited by 2
  3. 2025Learning and Generalization with Mixture Datacited by 2
  4. 2021Model Selection for Generic Reinforcement Learningcited by 1
  5. 2022Model Selection in Reinforcement Learning with General Function Approximationscited by 1
  6. 2023EM for Mixture of Linear Regression with Clustered Datacited by 1
  7. 2024Unveiling the Cycloid Trajectory of EM Iterations in Mixed Linear Regressioncited by 1
  8. 2024Agnostic Learning of Mixed Linear Regressions with EM and AM Algorithmscited by 1
  9. 2024Finite Sample Analysis of Tensor Decomposition for Learning Mixtures of Linear Systemscited by 1
  10. 2024Sample-Efficient Linear Regression with Self-Selection Biascited by 0
  11. 2024Fast convergence of a Federated Expectation-Maximization Algorithmcited by 0
  12. 2025LocalKMeans: Convergence of Lloyd's Algorithm with Distributed Local Iterationscited by 0
  13. 2025Learning Mixtures of Linear Dynamical Systems via Hybrid Tensor-EM Methodcited by 0
  14. 2026Expectation Maximization (EM) Converges for General Agnostic Mixturescited by 0