CS Paper Radar

Robust Recovery of Sparse Support in Constrained Group Testing

Jianing Li, Li Chai, Xinyao Rao, Hailin Zhang

eess.SP ·submitted 2026-09-17 14:18 UTC · v1

Abstract

In the early stage of a pandemic, rapidly identifying a small number of infected individuals through large-scale screening is critical for pandemic control. Group testing has been widely used to improve testing efficiency and numerous studies have investigated the problem under noisy measurements, typically modeled as bit-flipping of test outcomes. However, these methods do not consider the constraints imposed by dilution, pool size, and the limit of detection (LOD), which can lead to false negatives when the viral load in a pool falls below the LOD. In addition, liquid dispensing errors, common in laboratory settings, affects diluted viral loads in a nonlinear manner. In this work, we introduce a novel measurement model that characterizes the process of sample pooling and dilution, incorporating LOD-induced binary quantization as well as liquid dispensing errors. For the case with known sparsity level, we propose a low-complexity decoding algorithm and provide theoretical guarantees for exact support recovery under both noiseless and noisy settings. For the case with unknown sparsity level, we develop a blind support recovery algorithm, along with a heuristic variant to enhance robustness, which can achieve exact support recovery with only O(klogn) measurements. Extensive simulations show that the proposed algorithms outperform existing combinatorial group testing algorithms, validating the effectiveness, efficiency and robustness in large-scale screening.

Comment
This work has been submitted to the IEEE for possible publication. Copyright may be transferred without notice, after which this version may no longer be accessible

Closest papers

Nearest neighbours by meaning across the whole index.

Sparse Identification for Automatic Large-Scale Screening: A Constraint-Aware Framework with Ultra Fast Decoding Algorithm

cs.LG stat.MLeess.SP ·2026-09-18 ·Jianing Li, Li Chai, Yingcheng Lai
similarity 0.71
Abstract · This work has been submitted to the IEEE for possible publication. Copyright may be transferred without notice, after which this version may…

In the early stages of a pandemic, identification of a small number of infected individuals through large-scale screening is critical for pandemic control, yet remains challenging under limited reagents and testing capacity. Existing group testing methods suffer from either high computational complexity or low identification accuracy. Even worse, no available methods provide theoretically rigorous analysis for sparse identification with hard constraints caused by the sample usage constraint and the dilution effect existing ubiquitously in practical applications. In this article, we propose the Logic Screening method (LoSc), an ultra fast, accurate, and theoretically grounded framework for large-scale screening. LoSc introduces a novel decoding algorithm with a very simple selection strategy, achieving identification of all positives with only O(klogn) pooled tests. The decoding relies only on logical operations, enabling direct hardware implementation and yielding ultra fast computational implementation. Moreover, LoSc explicitly incorporates dilution and sample usage constraints into pooling designs, and establishes theoretical guarantees to guide optimal pooling configurations. Extensive simulations confirm the superior effectiveness, efficiency, and scalability. We believe LoSc offers a fast and reliable solution for automatic large-scale screening.

0.26

Graph-Aware Group Testing with Locally Clustered Infections

eess.SP ·2026-09-17 ·Jianing Li, Li Chai, Hailin Zhang
theory similarity 0.62
Abstract · This work has been submitted to the IEEE for possible publication. Copyright may be transferred without notice, after which this version may…

Group testing has been widely used to identify infected individuals with a limited number of tests, typically under the assumption of independent infections. Recent studies have exploited correlations among individuals, but often require additional information beyond the contact graph, such as community structures, interaction strengths, or detailed infection dynamics. Such information may be unavailable, incomplete or unreliable in practice. In this work, we assume that only the contact graph is known and develop a graph-aware group testing framework that exploits localized infection clustering in pooling design, fundamental limits of recovery, and decoding. Specifically, we propose an optimal transport-based pooling design that incorporates graph proximity and pooling constraints into a unified optimization framework. We prove that, under mild conditions, the proposed design eliminates uninfected individuals with higher probability than the Bernoulli pooling design, reducing the feasible search space for decoding. Then, we characterize the family of possible infected sets induced by localized infection clustering and derive necessary conditions on the number of tests required for exact recovery, revealing a lower testing requirement than that under the combinatorial prior. For decoding, we model the infection states of the population as a piecewise-constant graph signal and propose a graph total variation regularized decoder. We establish sufficient conditions for exact recovery under the Bernoulli pooling design in both noiseless and noisy settings, and show that O(Klog(n/K)) tests are sufficient under mild conditions in the noiseless case. Extensive simulations on synthetic and real-world networks demonstrate the effectiveness of the proposed framework and the benefit of exploiting graph-induced correlations in group testing.

0.30

Improved Constants in the Kautz-Singleton Construction for Probabilistic Group Testing

cs.IT math.ST ·2026-11-19 ·Trung-Khang Tran, Jonathan Scarlett
similarity 0.53
Abstract

We consider the probabilistic nonadaptive group testing problem, in which a uniformly random defective set of size $d$ is to be identified among $N$ items using a binary test matrix. For the explicit Kautz--Singleton construction, it is known that order-optimal scaling $T=Θ(d\log N)$ for high-probability recovery can be achieved in the regime $d=Ω(\log^2 N)$. However, the leading constant in this scaling remains uncharacterized even for standard low-complexity decoders. In this work, we revisit the probabilistic analysis of this construction and improve the leading constant for the COMP decoder, as well as establishing the same bound for the DD decoder. Our approach relies on a sharper analysis of the number of distinct roots associated with the defective items, yielding tighter bounds on the decoding error probability. In particular, we show that both COMP and DD achieve vanishing average error probability with $T\le (1/\ln 2+\varepsilon)d\log N$ tests for any $\varepsilon>0$, in the admissible regime $N=q^k$ for some prime power $q = Θ(d)$ and integer $k \ge 2$. For COMP, this leading constant matches that of the random near-constant column weight design, whereas for DD, a gap remains except in the sparse regime $d = N^{o(1)}$.

0.24

Instance Optimal Sparse Recovery from Nonlinear Observations: A Unified Framework

cs.IT eess.SPmath.ST ·2026-09-02 ·Junren Chen, Arian Maleki
similarity 0.53
Abstract

This paper develops a unified framework for instance optimal sparse recovery from nonlinear observations. The main ingredient is a signal-dependent restricted approximate invertibility condition (RAIC) of some gradient, which leads to the instance optimality of iterative hard thresholding. Under Gaussian designs, we apply the proposed framework to phaseless, one-bit, and ReLU measurements, which correspond to the problems of sparse phase retrieval, one-bit compressed sensing, and sparse ReLU regression, respectively. For sparse phase retrieval, we propose a variant of thresholded amplitude flow and show its instance optimality under $O(s^3)$ measurements (up to logarithmic factors), where $s$ is the sparsity level. To our best knowledge, this is the first instance optimal efficient algorithm for sparse phase retrieval and complements Gao, Wang and Xu (2016) that achieved this via a computationally intractable program. In one-bit compressed sensing, we establish the instance optimality of normalized binary iterative hard thresholding and strengthen the recent result of Matsumoto and Mazumdar (2024). In sparse ReLU regression, it is shown that a slight variant of the algorithm in Soltanolkotabi (2017) is instance optimal. Moreover, $(\ell_2,\ell_2)$ non-uniform instance optimal guarantees are obtained for these problems. The analysis is built upon a number of high-dimensional concentration bounds, including bounds on restricted eigenvalues and a novel instance-dependent hyperplane tessellation result.

0.51

Diffusion Models are Provably Efficient Priors for Sparse Recovery

cs.IT stat.MLcs.LGmath.OC ·2026-11-18 ·Ivan Lee, Xingyu Xu, Yuejie Chi
similarity 0.45
Abstract

Diffusion models have transformed generative modeling through their ability to capture and generate samples from complex data distributions. This success has spurred substantial interest in using pretrained diffusion models as expressive priors for highly ill-posed inverse problems in imaging and sensing. Despite strong empirical performance, theoretical understanding of this approach remains limited: existing guarantees are often asymptotic or entail prohibitive computational costs in the worst case. In this paper, we address this gap by studying sparse recovery from a small number of linear measurements, a classical problem in compressed sensing. We show that, given an accurate diffusion model capturing a sparsity-promoting Bernoulli-Gaussian prior, a likelihood-guided annealed Langevin sampler provably recovers the sparse signal in polynomial time with near-optimal sample complexity for a broad family of random and deterministic sensing matrices. When the signal is indeed drawn from the postulated prior, we further establish total variation guarantees for posterior sampling after a final denoising step. These results lay a theoretical foundation for statistically and computationally efficient inverse solvers with diffusion priors.

0.23

Excess Separability: Nuisance-Controlled Residual-Stream Probing for Benchmark Contamination Detection

cs.CL cs.LG ·2026-08-12 ·Florian Braun
benchmarkcode/data similarity 0.45
Abstract · 23 pages, 11 figures, 8 tables. v2: measures the placebo baseline's own sampling variance, finds it exceeds the permutation null's in every …

Benchmark contamination is diagnosed with n-gram overlap, likelihood-based membership inference, or canary strings, and each needs something usually unavailable: the training corpus, a well-chosen test statistic, or foresight at release. A recent alternative reads it off a linear probe on internal activations. We show the natural way to do this does not work, specify one that survives measurement, then find that the correction making it work carries more variance than the null it is tested against. The protocol reports a zero-sum contrast on the depth profile of probe accuracy, recentred on a level-matched placebo baseline, tested against a label-permutation null, with the reference set twice the size of the suspect set. Each choice replaces a simpler alternative we rejected on measurement. Reporting the level of excess separability rather than its shape makes the false positive rate track the size of the analyst's own control set, 0.03 to 0.99 under a true null. Contrasting against a flat depth profile rejects a true null 0.72 of the time when surface decodability rises with depth, and loses all power when it falls. On real transformers the protocol fails a test the simulations did not pose. The recentring subtracts an estimate, and the permutation null holds it fixed. Re-estimated across split seeds on four audits of contaminated checkpoints, its standard deviation is 1.30 to 1.56 times the null's own in every arm: what is subtracted to remove a bias is more variable than what it corrects. The one nominally significant result, p = 0.0075, becomes 0.0745 once that variance is propagated, and no verdict is issued. The simulations missed this because their surface key is the covariate driving item variation; on real text it is a proxy, and degrading key quality in simulation reproduces it. We add a companion measurement and a widened null. No arm shows contamination.

0.60

Two-Sided Conformal Evidence Sets for Retrieval-Augmented Generation

cs.LG cs.CL ·2026-11-07 ·Ben Jenkins, Mihaela Cardei
publishedbenchmark similarity 0.45
Abstract · Accepted at the 2026 IEEE International Conference on Tools with Artificial Intelligence (ICTAI 2026). 8 pages

Retrieval-augmented generation (RAG) can surface passages that support a claim, contradict it, or fail to address it, yet existing calibrated grounding methods are typically one-sided and model only supporting evidence. We introduce Conformal Evidence Sets (CES), a two-sided framework that returns separate support and refutation sets with finite-sample inclusion coverage of at least $1-α$ on each side under exchangeability; a Bonferroni union yields joint coverage of at least $1-2α$. On labeled candidate pools from the contrastive VitaminC benchmark, CES closely tracks nominal coverage across $α\!\in\!\{0.05,0.10,0.15,0.20,0.30\}$, with maximum deviations of $3.0$ percentage points for support and $5.4$ for refutation, and reaches essentially the same empirical coverage--size frontier as a test-tuned fixed-threshold heuristic without any test exposure. Stress tests mark the boundary of that guarantee: under FEVER distribution shift both sides under-cover, by up to $12.7$ percentage points, and support-side group-stratified recalibration substantially reduces the support gap. Scorer swaps, hard-negative retrieval, cross-dataset transfer, and a live end-to-end pilot expose a clear separation: when exchangeability holds and relevant evidence is retrieved, evidence inclusion remains calibrated even with an imperfect scorer, whereas the support/refute verdict tracks scorer quality directly. Calibrated evidence coverage and reliable verdicts are therefore distinct properties and should be reported separately.

0.39

Predicting Viral Evolution from a Single Early Measurement Using the Target Cell Limited Model

eess.SY ·2026-09-15 ·Rahal Nanayakkara, Paulo Tabuada
theoryunusual similarity 0.44
Abstract · 7 pages, 3 figures, IEEE CDC 2026

Recent advances in diagnostic techniques have enabled the accurate quantification of early-stage viral loads. A key problem of interest is translating these measurements into predictive clinical insights, such as forecasting a patient's onset of infectiousness and peak infection severity. In this work, we address this problem using the Target Cell Limited (TCL) model. Because the host's internal biological states are practically unobservable, predicting the viral trajectory from a single noisy viral load measurement is highly nontrivial. To overcome this, we introduce a novel coordinate transformation that converts the nonlinear viral dynamics into a monotone system. By leveraging monotone systems theory and taking into account invariant subspaces of the transformed system, we derive explicit analytical formulae that establish a strict upper bound on the peak viral load and a guaranteed lower bound on the time to infectiousness using a single early viral observation.

0.30