請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/66293
標題: | 對抗性擾動下的組合量化群試:基本極限和演算法 Combinatorial Quantitative Group Testing withAdversarially Perturbed Measurements: FundamentalLimits and Algorithms |
作者: | Yun-Han Li 李云漢 |
指導教授: | 王奕翔(I-Hsiang Wang) |
關鍵字: | 群試,壓縮感知,膨脹圖,阿達馬矩陣, Group testing,Compressed sensing,Expander graph,Hadamard matrix, |
出版年 : | 2021 |
學位: | 碩士 |
摘要: | 本文研究了帶有雜訊的「量化群試」(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). |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/66293 |
DOI: | 10.6342/NTU202100377 |
全文授權: | 有償授權 |
顯示於系所單位: | 電信工程學研究所 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
U0001-0202202114135300.pdf 目前未授權公開取用 | 1.28 MB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。