Introduction
In standard linear regression, the goal is to find a single vector $\beta$ that maps inputs $x$ to outputs $y$. However, real-world data is often generated by a mixture of underlying relationships. Consider a medical study where patients belong to $L$ distinct sub-groups, each characterized by a unique genetic signature ($\beta^{(1)}, \dots, \beta^{(L)}$). When a measurement is taken, the sub-group identity is unknown, yielding a noisy observation $y = \langle x, \beta^{(\ell)} \rangle + \eta$.
This problem is significantly compounded when the underlying signals are sparse (most entries are zero), bridging the challenges of mixture models and compressed sensing. Historically, research in this domain has been constrained: algorithms either required restrictive "overlap" assumptions—dictating that signals could not share similar values at the same indices—or were strictly limited to mixtures of exactly two signals ($L=2$) in noisy environments.
This paper breaks through these barriers, introducing novel algorithms and theoretical bounds for learning multiple sparse signal vectors from a mixed stream of linear measurements. It achieves near-optimal sample complexity and provides the first robust reconstruction method for mixtures of more than two signals without relying on restrictive overlap assumptions.
Algorithmic Frameworks
The authors tackle the problem by dividing it into two distinct regimes: the noiseless case and the noisy case.
The Noiseless Case: Sparse Polynomials and Sorting
To recover $L$ signals without noise, the primary obstacle is "alignment"—determining which measurement corresponds to which signal across different queries. The authors leverage Vandermonde matrices (a class of Maximum Distance Separable matrices) to treat the inner product of a query and a signal as a polynomial.
The key insight here relies on the power of randomness in polynomials: the difference between two sparse signals is itself a sparse polynomial, which inherently has very few roots. The authors prove that by selecting a random evaluation point, the signals maintain a consistent sorted order. This allows the algorithm to effectively "unmix" the measurements simply by sorting them, acting as a reliable anchor across queries.
The Noisy Case: GMMs and Error Correction
When noise is introduced, simple sorting breaks down. To overcome this, the authors propose a robust three-step pipeline:
- Denoising via Gaussian Mixture Models (GMMs): By repeatedly querying the same vector, the authors transform the regression problem into a distribution learning problem. Multiple queries of the same vector are treated as a GMM. Using complex-analytic techniques, they can accurately estimate the underlying inner products.
- Alignment via Error-Correcting Codes: To link these inner products across different query vectors, the authors creatively apply algebraic coding theory. They perform redundant queries (e.g., querying $x_i$, $x_j$, and their sum $x_i + x_j$) to establish "parity checks." These checks reveal which values belong to the same underlying signal vector, bypassing the need for prior overlap assumptions.
- Recovery via Basis Pursuit: Once the measurements are successfully denoised and aligned, standard Basis Pursuit—a staple convex optimization tool from compressed sensing—is used to reconstruct the final sparse vectors.
Key Theoretical Results
As a purely theoretical work, the paper focuses on establishing rigorous sample complexity guarantees rather than empirical benchmarks.
- Near-Optimal Noiseless Complexity: The authors demonstrate that $O(kL \log(kL))$ queries are sufficient to recover all $L$ signals of sparsity $k$. They also prove a lower bound of $\Omega(kL)$ queries, establishing that their noiseless algorithm is nearly optimal in terms of measurement efficiency. Crucially, this works for any set of sparse vectors.
- Robust Noisy Complexity: For the noisy regime, the paper introduces the first robust algorithm for $L > 2$ signals. It requires $O(k \log^3 n \cdot \exp((\sigma/\epsilon)^{2/3}))$ queries. While the exponential dependence on the noise-to-error ratio appears steep, it represents a massive theoretical improvement over the $\exp(1/\epsilon)$ dependencies found in prior $L=2$ literature.
Limitations and Future Directions
While the proposed algorithms are highly sample-efficient, they come with practical trade-offs. The noisy reconstruction step relies on learning Gaussian mixtures, which can be computationally expensive to execute. Furthermore, the current noisy analysis assumes the number of signals $L$ is a constant; as $L$ scales, the complexity becomes significantly harder to manage.
Finally, the paper primarily investigates non-adaptive queries, where all input vectors $x$ are chosen upfront. The authors suggest that exploring adaptive queries—where the next $x$ is chosen based on previous $y$ observations—could further reduce the required number of measurements, presenting a promising avenue for future research.
Summary updated