cs.LGSep 26, 2026

Efficient Support Recovery of Mixtures of Sparse Linear Classifiers with Fewer Measurements

Authors: Xiaxin Li, Arya Mazumdar

Organizations: Halıcıoğlu Data Science Institute, University of California, San Diego

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

The support recovery problem in mixture of linear classifiers aims to identify the features relevant to the underlying decision rules when data is generated by a mixture of several linear decision rules. In particular, the goal is to recover the support (nonzero coordinates) of ll unknown kk-sparse vectors from sign measurements. Each measurement is generated by selecting one of the ll vectors uniformly at random, and returning the sign of its inner product with a chosen measurement vector. In this paper, we propose adaptive and non-adaptive schemes that significantly improve upon prior results by simultaneously reducing the number of measurements and achieving sublinear decoding time. In particular, our adaptive constructions substantially reduce measurements compared to existing approaches, while also lowering decoding complexity from super-quadratic to sublinear in the ambient dimension. We further provide a non-adaptive scheme that improves previous measurement bounds while maintaining efficient decoding. Overall, our approach yields a more efficient trade-off between sample complexity and decoding time for support recovery in mixture models compared to previously known methods.

Explore similar work

CardsList
Sep 1, 2025

The Price of Sparsity: Sufficient Conditions for Sparse Recovery using Sparse and Sparsified Measurements

We consider the problem of support recovery for sparse binary signals from noisy linear measurements. For sparse Gaussian measurement matrices we identify sufficient conditions on the minimal sample size for maximum-likelihood recovery in the high-SNR regime ds/p→∞ds/p \to \infty, where pp denotes the signal dimension, ss the number of non-zero components of the signal, and dd the expected number of non-zero components per row of measurement. Combined with known lower bounds, this yields an information-theoretic threshold of order slog⁡(p/s)/log⁡(ds/p)s\log(p/s) / \log(ds/p), making explicit the price of measurement sparsity. In particular, we highlight a regime where the sample-complexity loss from measurement sparsity is logarithmic while the computational gain is nearly linear. Second, we study recovery after sparsifying an originally dense Gaussian design: the observations are generated from the dense design, while estimation uses an independently sparsified design and a rescaled response. In the proportional regime s=αps=αp, d=ψpd=ψp, we prove that, for every fixed target error level δδ and every slack ε>0\varepsilon>0, a sample size of order p/ψ2p/ψ^2 is sufficient for support recovery for arbitrarily small ψψ.

Youssef Chaabouni, David Gamarnik

Massachusetts Institute of Technology

Sparse RecoverySample Complexity
AskPDF
Feb 18, 2026

Separating Oblivious and Adaptive Models of Variable Selection

Sparse recovery is among the most well-studied problems in learning theory and high-dimensional statistics. In this work, we investigate the statistical and computational landscapes of sparse recovery with ℓ∞\ell_\infty error guarantees. This variant of the problem is motivated by variable selection tasks, where the goal is to estimate the support of a kk-sparse signal in Rd\mathbb{R}^d. Our main contribution is a provable separation between the oblivious (for each'') and *adaptive* (for all'') models of ℓ∞\ell_\infty sparse recovery. We show that under an oblivious model, the optimal ℓ∞\ell_\infty error is attainable in near-linear time with ≈klog⁡d\approx k\log d samples, whereas in an adaptive model, ≳k2\gtrsim k^2 samples are necessary for any algorithm to achieve this bound. This establishes a surprising contrast with the standard ℓ2\ell_2 setting, where ≈klog⁡d\approx k \log d samples suffice even for adaptive sparse recovery. We conclude with a preliminary examination of a partially-adaptive model, where we show nontrivial variable selection guarantees are possible with ≈klog⁡d\approx k\log d measurements.

Ziyun Chen, Jerry Li, Kevin Tian +1

University of Washington · University of Texas at Austin

Sparse RecoveryFeature SelectionStatistical Learning TheoryInverse Problems
AskPDF
Oct 28, 2025

Robustness to Sparse Adversarial Corruption in Arbitrary Linear Measurements: Beyond Exact Recovery

Recovery from linear measurements under sparse adversarial corruption is typically formulated as an exact-recovery problem: one seeks structural conditions on A\mathbf{A} (e.g., restricted isometry property) guaranteeing unique recovery of x⋆\mathbf{x}^\star from y=Ax⋆+e\mathbf{y} = \mathbf{A}\mathbf{x}^\star + \mathbf{e} with ∥e∥0≤q\|\mathbf{e}\|_0 \leq q. However, these guarantees provide no guidance once exact recovery fails. This limitation obscures simple robustness phenomena -- for instance, repeated rows in A\mathbf{A} can preserve nontrivial information about x⋆\mathbf{x}^\star under sparse corruption. In this paper, we study what information about x⋆\mathbf{x}^\star can be uniformly recovered from y=Ax⋆+e\mathbf{y} = \mathbf{A}\mathbf{x}^\star + \mathbf{e} for arbitrary A∈Rm×n\mathbf{A}\in\mathbb{R}^{m\times n} and any qq-sparse e\mathbf{e}. We show that the robust information is precisely x⋆+ker⁡(U)\mathbf{x}^\star + \ker(\mathbf{U}), where U\mathbf{U} is the orthogonal projection onto the intersection of rowspaces of all submatrices of A\mathbf{A} obtained by deleting 2q2q rows. This clarifies how the row structure of A\mathbf{A} governs whether a qq-sparse corruption allows exact, partial, or only trivial recovery. We further prove every x\mathbf{x} minimizing ∥y−Ax∥0\|\mathbf{y} - \mathbf{A} \mathbf{x}\|_0 belongs to x⋆+ker⁡(U)\mathbf{x}^\star + \ker(\mathbf{U}), yielding a constructive approach to recover this set. For i.i.d. Gaussian matrices, we establish a sharp phase transition between exact and trivial recovery. We sketch two applications: robust network tomography and signal reconstruction from oversampled DCT.

Vishal Halder, Alexandre Reiffers-Masson, Abdeldjalil Aïssa-El-Bey +1

IMT Atlantique, Lab-STICC, CNRS UMR 6285, Brest, France · Department of Computer Science and Automation, Indian Institute of Science, Bengaluru, India

Sparse RecoveryAdversarial RobustnessCorruption RobustnessInverse Problems
AskPDF