Group testing is an approach aimed at identifying up to $d$ defective items
among a total of $n$ elements. This is accomplished by examining subsets to
determine if at least one defective item is present. In our study, we focus on
the problem of identifying a subset of $\ell\leq d$ defective items. We develop
upper and lower bounds on the number of tests required to detect $\ell$
defective items in both the adaptive and non-adaptive settings while
considering scenarios where no prior knowledge of $d$ is available, and
situations where an estimate of $d$ or at least some non-trivial upper bound on
$d$ is available.
When no prior knowledge on $d$ is available, we prove a lower bound of $
\Omega(\frac{\ell \log^2n}{\log \ell +\log\log n})$ tests in the randomized
non-adaptive settings and an upper bound of $O(\ell \log^2 n)$ for the same
settings. Furthermore, we demonstrate that any non-adaptive deterministic
algorithm must ask $\Theta(n)$ tests, signifying a fundamental limitation in
this scenario. For adaptive algorithms, we establish tight bounds in different
scenarios. In the deterministic case, we prove a tight bound of
$\Theta(\ell\log{(n/\ell)})$. Moreover, in the randomized settings, we derive a
tight bound of $\Theta(\ell\log{(n/d)})$.
When $d$, or at least some non-trivial estimate of $d$, is known, we prove a
tight bound of $\Theta(d\log (n/d))$ for the deterministic non-adaptive
settings, and $\Theta(\ell\log(n/d))$ for the randomized non-adaptive settings.
In the adaptive case, we present an upper bound of $O(\ell \log (n/\ell))$ for
the deterministic settings, and a lower bound of $\Omega(\ell\log(n/d)+\log
n)$. Additionally, we establish a tight bound of $\Theta(\ell \log(n/d))$ for
the randomized adaptive settings.

本研究探讨了使用不同的群组检测算法来识别不同数量的不良元素的问题，提出了自适应和非自适应算法的上下界，并讨论了是否有先验知识或估计确切数量的情况下的检测数量的限制。

关于在群检测中检测某些缺陷品的研究

On Detecting Some Defective Items in Group Testing

Matrix trace estimation is ubiquitous in machine learning applications and
has traditionally relied on Hutchinson's method, which requires
$O(\log(1/\delta)/\epsilon^2)$ matrix-vector product queries to achieve a $(1
\pm \epsilon)$-multiplicative approximation to $\text{tr}(A)$ with failure
probability $\delta$ on positive-semidefinite input matrices $A$. Recently, the
Hutch++ algorithm was proposed, which reduces the number of matrix-vector
queries from $O(1/\epsilon^2)$ to the optimal $O(1/\epsilon)$, and the
algorithm succeeds with constant probability. However, in the high probability
setting, the non-adaptive Hutch++ algorithm suffers an extra
$O(\sqrt{\log(1/\delta)})$ multiplicative factor in its query complexity.
Non-adaptive methods are important, as they correspond to sketching algorithms,
which are mergeable, highly parallelizable, and provide low-memory streaming
algorithms as well as low-communication distributed protocols. In this work, we
close the gap between non-adaptive and adaptive algorithms, showing that even
non-adaptive algorithms can achieve $O(\sqrt{\log(1/\delta)}/\epsilon +
\log(1/\delta))$ matrix-vector products. In addition, we prove matching lower
bounds demonstrating that, up to a $\log \log(1/\delta)$ factor, no further
improvement in the dependence on $\delta$ or $\epsilon$ is possible by any
non-adaptive algorithm. Finally, our experiments demonstrate the superior
performance of our sketch over the adaptive Hutch++ algorithm, which is less
parallelizable, as well as over the non-adaptive Hutchinson's method.

本文研究了矩阵迹估计的算法，提出了 Hutch++ 以及一种新的非自适应算法，通过实验证明了该算法的优越性。