對抗性擾動下的組合量化群試：基本極限和演算法

Combinatorial Quantitative Group Testing withAdversarially Perturbed Measurements: FundamentalLimits and Algorithms

李云漢(Yun-Han Li)

指導教授 ： 王奕翔

國立臺灣大學/電機資訊學院/電信工程學研究所/碩士(2021年)

https://doi.org/10.6342/NTU202100377

摘要

本文研究了帶有雜訊的「量化群試」（QGT）。QGT的目標是通過計數，測量從大小為n的數據集之中檢測有缺陷的項目，每個測量都對選定的部分項目中的缺陷數量進行計數。與大多數文獻考慮的隨機雜訊的「機率性QGT」或無雜訊的「組合QGT」不同，本研究的目標是帶有對抗性雜訊的組合QGT。由於在對抗性雜訊下不可能完美解碼，因此我們關心部分解碼。在對抗性雜訊幅度小於dn= Θ(nδ)且解碼的錯誤數量要求小於kn= Θ(nκ)的情形下，我們的目標是找出需要的最小檢測次數(稱之為最佳檢測複雜度)，設計出能達到最佳檢測複雜度的檢測方法，同時提供一個快速的解碼演算法。我們證明對於非調整型演算法，當0<2δ≤κ <1時，最佳檢測複雜度為Θ 11−2δnlogn 。我們也提出一個接近最佳的非調整型演算法的構造方法，其測試複雜度與最佳測試複雜度只差常數倍。同時，此演算法的解碼複雜度為o(n1+ρ)對於所有ρ >0，幾乎和n呈線性關係。此外，針對有缺陷項目具有稀疏的情況，我們也提出了相應的延伸。

關鍵字

群試 ； 壓縮感知 ； 膨脹圖 ； 阿達馬矩陣

並列摘要

n this thesis, quantitative group testing (QGT) with noisy measurements isstudied. The goal of QGT is to detect defective items from a data set of sizenwith counting measurements, each of which counts the number of defects in aselected pool of items. While most literatures consider either probabilistic QGT withrandom noise or combinatorial QGT with noiseless measurements, our focus is on thecombinatorial QGT with noisy measurements that might be adversarially perturbedby additive bounded noises. Since perfect detection is impossible, a partial detectioncriterion is adopted. With the adversarial noise being bounded bydn= Θ(nδ)andthe detection criterion being to ensure no more thankn= Θ(nκ)errors can be made,our goal is to characterize the fundamental limit on the number of measurement,termed pooling complexity, as well as provide explicit construction of measurementplans with optimal pooling complexity and efficient decoding algorithms. We firstshow that the fundamental limit is11−2δnlognto within a constant factor not depending on(n, κ, δ)for the non-adaptive setting when0<2δ≤κ <1, sharpening theprevious result by Chen and Wang [7]. We also provide an explicit construction ofa non-adaptive deterministic measurement plan with11−2δnlog2npooling complexityup to a constant factor, matching the fundamental limit, with decoding complexitybeingo(n1+ρ)for allρ >0, nearly linear inn, the size of the data set. On topof CQGT, we also extend our results to SCQGT(CQGT with additional sparsityconstraint).

並列關鍵字

Group testing ； Compressed sensing ； Expander graph ； Hadamard matrix

參考文獻

[1]A. E. Alaoui, A. Ramdas, F. Krzakala, L. Zdeborová, and M. I. Jordan. De-coding from pooled data: Sharp information-theoretic bounds. SIAM Journalon Mathematics of Data Science, 1(1):161–168, 2019.

[2]M. Aldridge, O. Johnson, and J. Scarlett. Group testing: An information theoryperspective. Foundations and Trends® in Communications and InformationTheory, 15(3-4):196–392, 2019.

[3]N. H. Bshouty. On the coin weighing problem with the presence of noise. InApproximation, Randomization, and Combinatorial Optimization. Algorithmsand Techniques, pages 471–482. Springer Berlin Heidelberg, 2012.

[4]D. G. Cantor and W. H. Mills. Determination of a subset from certain combi-natorial properties. Canadian Journal of Mathematics, 18:42–48, 1966.

[5]C.-C. Cao, C. Li, and X. Sun. Quantitative group testing-based overlap-ping pool sequencing to identify rare variant carriers. BMC Bioinformatics,15(1):195, June 2014.