文献

J-GLOBAL ID：201702236351265665   整理番号：17A0456545

雑音グループ試験のための効率的アルゴリズム【Powered by NICT】

Efficient Algorithms for Noisy Group Testing

著者 (4件)： Cai Sheng (Department of Information Engineering, The Chinese University of Hong Kong, Hong Kong) ,  Jahangoshahi Mohammad (Institute of Network Coding, The Chinese University of Hong Kong, Hong Kong) ,  Bakshi Mayank (Institute of Network Coding, The Chinese University of Hong Kong, Hong Kong) ,  Jaggi Sidharth (Institute of Network Coding, The Chinese University of Hong Kong, Hong Kong)
資料名： IEEE Transactions on Information Theory  (IEEE Transactions on Information Theory)
巻： 63  号： 4  ページ： 2113-2136  発行年： 2017年 
JST資料番号： C0231A  ISSN： 0018-9448  CODEN： IETTAW  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： グループ試験は,「小さな」数「プール」試験(すなわち,プールで試験されている項目の少なくとも一つである欠損で陽性結果を有し,他の負の結果を持つことを試験)によるN項目の(大きな)セットからD不良品の(小)サブセット(高い確率で)を同定する問題に言及した。本論文で提示を容易にするために,著者らはいくつかのδ>0のD=O(N~1 δ)領域に焦点を当てた。試験は無雑音またはノイズが高い可能性があると,試験手順は,適応(試験を定義するプールは以前の試験の結果に依存する可能性がある),または非適応である(各試験は他の試験の転帰の独立実行される)。豊富な文献がΘ(Dlog(N))試験を情報理論的に必要とグループ検定問題のための十分であることを示し,この性能を達成するアルゴリズムを提供した。しかし,Nの準線形計算複雑性を持つ再構成アルゴリズムを検討し始めたのはつい最近のことである。雑音結果と適応試験のシナリオでは,試験数と復号化計算量(両性能計量におけるO(Dlog(N)))の両方で同時にため最適である(小さな一定因子まで)ことを第1の方式を提示した。適応アルゴリズムの段階の総数は「小さな」である(O(log(D)))。同様に,雑音の多い結果と非適応試験のシナリオでは,試験数と復号複雑度(O(Dlog(D)log(N))試験を必要とするとO(D(logN+log~2D)の復号化計算量を持つことをアルゴリズムによる)の両方で同時に準最適であるという最初の方式を提案した。最後に,二段階のみを必要とする,の試験数と復号化計算量がO(D(logN+log~2D))としてスケール適応アルゴリズムを提案した。全ての三設定では,筆者らのアルゴリズムの誤差の確率はO(1/(ポリ(D))のようにスケールする。測定,復号化の複雑さ,誤りの確率の数の約前に述べたステートメントの各々に対して,著者らは明示的に計算この定理ステートメントにおける普遍的因子「小さな」を提供する。Copyright 2017 The Institute of Electrical and Electronics Engineers, Inc. All Rights reserved. Translated from English into Japanese by JST【Powered by NICT】

シソーラス用語： 線形性 ,  *雑音 ,  復号化 ,  計算量 ,  情報理論 ,  *アルゴリズム
準シソーラス用語： 複雑度 ,  適応アルゴリズム ,  再構成アルゴリズム ,  転帰 ,  *効率的アルゴリズム , 【Automatic Indexing@JST】

分類 (1件)： 符号理論  (ND02030R)

タイトルに関連する用語 (3件)： 雑音 ,  グループ試験 ,  効率的アルゴリズム