Research map / Learning theory and algorithms / Sample complexity
Recovery of Sparse Signals from a Mixture of Linear Samples
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Gaussian query vectors rather than arbitrary compressed-sensing queries | Recovery of two sparse linear models · Two sparse linear models | query complexity: O((log gap)⁻¹) for large gap; O((gap log gap)⁻¹) for small gap | Helped |
| Use mean and variance as sufficient statistics for the equal-weight, known-variance mixture | Scalar Gaussian-mixture mean estimation · Two-component scalar Gaussian mixture | samples for parameter recovery: O(σ_M⁴) samples; O(σ_G¹²) for the general case | Helped |
| Use one fitted Gaussian when the requested precision is at least on the scale of the component separation | Recovery of two sparse linear models · γ = Ω(||β¹−β²||₂) | query complexity: O(k log n ⌈log k/SNR⌉) | Helped |
| Add sum and difference queries to align component-mean estimates across queries | Recovery of two sparse linear models · Alignment step | alignment correctness | Helped |
| Use Gaussian-mixture EM when projected component means are well separated | Scalar Gaussian-mixture mean estimation · Component gap |μ₁−μ₂| = Ω(σ) | samples for mean estimation: O(⌈(σ²/γ²) log 1/η⌉) | Helped |
| Fit a single Gaussian instead of separating the mixture when both noise and component separation are small | Scalar Gaussian-mixture mean estimation · σ ≤ γ and |μ₁−μ₂| ≤ γ | samples for estimating both means within γ: O(⌈(σ²/γ²) log 1/η⌉) | Helped |
| Use a single Gaussian fit instead of naively averaging all mixture samples | Scalar Gaussian-mixture mean estimation · Small component gap and small component variance | sample complexity dependence on component gap | Helped |
Closest papers by meaning
- Recovery of sparse linear classifiers from mixture of responses (NeurIPS 2020 · similarity 0.91)
- Exact Recovery of Sparse Binary Vectors from Generalized Linear Measurements (ICML 2025 · similarity 0.86)
- The Price of Sparsity: Sufficient Conditions for Sparse Recovery using Sparse and Sparsified Measurements (NeurIPS 2025 · similarity 0.86)
- Robust Sparse Regression with Non-Isotropic Designs (NeurIPS 2024 · similarity 0.85)
- Straight-Through Meets Sparse Recovery: the Support Exploration Algorithm (ICML 2024 · similarity 0.85)
- A Unified Framework for Learning with Nonlinear Model Classes from Arbitrary Linear Samples (ICML 2024 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.