Efficient Support Recovery of Mixtures of Sparse Linear Classifiers with Fewer Measurements
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 l unknown k-sparse vectors from sign measurements. Each measurement is generated by selecting one of the l 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.
Related
- Ensemble-based support vector machine classifiers as an efficient tool for quality assessment of beef fillets from electronic nose data
- Reactive flash for ideal multiphase mixtures: Unified formulation and efficient computation
- Efficient three-phase Free-Water Flash calculations for water-hydrocarbon mixtures
- Fisher Information and Support Complexity of Gaussian Mixtures
- Simultaneous recovery of multiple parameters in nonlocal diffusion equations from internal measurements
BibTeX
@misc{li2026efficient,
title = {{Efficient Support Recovery of Mixtures of Sparse Linear Classifiers with Fewer Measurements}},
author = {Xiaxin Li and Arya Mazumdar},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.32176},
eprint = {2609.32176},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.32176},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Efficient Support Recovery of Mixtures of Sparse Linear Classifiers with Fewer Measurements
AU - Xiaxin Li
AU - Arya Mazumdar
PY - 2026
DA - 2026/10/02
PB - arXiv
DO - 10.48550/arxiv.2609.32176
UR - https://arxiv.org/abs/2609.32176
AB - 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 l unknown k-sparse vectors from sign measurements. Each measurement is generated by selecting one of the l 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.
ER -