文献

J-GLOBAL ID：202002293523519710   整理番号：20A0219953

トレース再構成を超えて:欠失チャネルからの個体群回復【JST・京大機械翻訳】

Beyond Trace Reconstruction: Population Recovery from the Deletion Channel

著者 (5件)： Ban Frank (UC Berkeley) ,  Chen Xi (Columbia University) ,  Freilich Adam (Columbia University) ,  Servedio Rocco A. (Columbia University) ,  Sinha Sandip (Columbia University)
資料名： IEEE Conference Proceedings  (IEEE Conference Proceedings)
巻： 2019  号： FOCS  ページ： 745-768  発行年： 2019年 
JST資料番号： W2441A  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： 母集団回復は,未知のnビット列の集合上で未知の分布を学習する問題であり,いくつかの雑音チャネルに従って独立に劣化した分布から独立したドレインへのアクセスを与えられる。最近の研究は,{ビットフリップ}雑音チャネルと消去雑音チャネルの両方に対するこのような問題を集中的に研究している。本論文では,各ビットbがいくつかの固定確率で独立に削除され,生存ビットが連結され,伝送される,削除チャネルの下での母集団回復の研究を開始した。これは,ビットフリップ雑音または消去雑音よりはるかに困難な雑音モデルである。実際に,集団がサイズ1(単一ストリングに支持された自明な確率分布に対応する)の最も単純な場合でも,非常に最近注目されている挑戦的な問題であるトレース再構成問題に対応する。本研究では,母集団サイズがいくつかの値l>1のとき,削除チャネルの下での母集団回復のためのアルゴリズムと下限を与えた。著者らの主なサンプル複雑性上限として,任意の母集団サイズl=o(log n/log log n)に対して,{o,1}^nからのlストリングの母集団を,2つの^n ^1/2+o(1)サンプルを用いて削除チャネル雑音下で学習できることを示した。下限側では,少なくともn個のΩ(l)サンプルが,母集団サイズがl≦nの1/2-εの場合に,削除チャネル下での集団回復を行うために必要であることを示した。著者らの上限は,KrasikovとRoddity[KR97]による多項式ベースの解析のロバスト多変量一般化により得られ,ビットストリングのkデッキがストリングを一意的に同定する。これは,トレース再構成(l=1ケース)に対する最近のアルゴリズムからの非常に異なるアプローチである。著者らの下限はRoos[Roos:00]とDaskalakisとPapadimitriou[DP15]のモーメント整合結果に基づいている。Copyright 2020 The Institute of Electrical and Electronics Engineers, Inc. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： モーメント ,  甲板 ,  ロバスト性 ,  *個体群 ,  アルゴリズム ,  チャネル ,  雑音 ,  CASE ,  多項式 ,  母集団 ,  再構成 ,  確率分布
準シソーラス用語： 多変量 ,  複雑性 ,  雑音モデル , 【Automatic Indexing@JST】

分類 (1件)： 図形・画像処理一般  (JE04010I)

タイトルに関連する用語 (6件)： トレース ,  再構成 ,  欠失 ,  チャネル ,  個体群 ,  回復