お知らせ 研究会の開催と会場に参加される皆様へのお願い(2020年10月開催~)
電子情報通信学会 研究会発表申込システム
講演論文 詳細
技報閲覧サービス
[ログイン]
技報アーカイブ
 トップに戻る 前のページに戻る   [Japanese] / [English] 

講演抄録/キーワード
講演名 2021-07-08 16:40
[招待講演]Square-root bottleneckを超えるRIP行列と関連する組合せ論
佐竹翔平熊本大IT2021-22
抄録 (和) 圧縮センシングの理論は, 情報理論や信号処理の分野などへの幅広い応用をもち, 数学的にも興味深い. 制限等長性 (RIP)をもつ行列(RIP行列)の明示的構成はその最重要課題の1つである. 従来研究のほとんどにおいて, 保証可能なRIPにsquare-root bottleneckとよばれるbarrierがあり, このbarrierを超えることが求められていた. またbarrierを打破した構成例は依然少なく, またその構成例においてもbarrierをわずかに超えるにとどまっている. 一方で, そのようなRIP行列の構成は, 擬ランダム性, Ramsey理論などの組合せ論的な研究と関連することが, いくつかの先行研究や講演者の最近の研究でわかってきている.

本稿では, こうした背景を概説し, Bandeira, MixonおよびMoreira (2017)ならびに講演者によるsquare-root bottleneckを超える行列の (conditionalな) 構成, および上述の組合せ論との関連について説明する. 
(英) Compressed sensing theory has various applications to information theory and signal processing.
As one of challenging problems, deterministic constructions of matrices with the restricted isometry property (RIP) have been extensively studied.
In most of known construction of RIP matrices, their certified RIP face the barrier called the square-root bottleneck, and thus it has been desired to beat this barrier.
At present, there are only few known constructions of RIP matrices breaking the square-root bottleneck, and even in these matrices, their RIP exceeds the bottleneck very slightly.
On the other hand, some known works and our recent study found relationships between constructions of RIP matrices breaking the square-root bottleneck and several topics in combinatorics such as Ramsey theory and pseudo-randomness.

In this article, we briefly review these backgrounds and then introduce a (conditional) construction of RIP matrices breaking the square-root bottleneck due to Bandeira, Mixon and Moreira (2017) and the present author.
We also explain some relationships to the combinatorial topics mentioned above.
キーワード (和) 擬ランダム性 / 制限等長性 / Ramseyグラフ/トーナメント / / / / /  
(英) Pseudo-randomness / Ramsey graph/tournament / restricted isometry property / / / / /  
文献情報 信学技報, vol. 121, no. 96, IT2021-22, pp. 40-44, 2021年7月.
資料番号 IT2021-22 
発行日 2021-07-01 (IT) 
ISSN Print edition: ISSN 0913-5685  Online edition: ISSN 2432-6380
著作権に
ついて
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034)
PDFダウンロード IT2021-22

研究会情報
研究会 IT  
開催期間 2021-07-08 - 2021-07-09 
開催地(和) オンライン開催 
開催地(英) Online 
テーマ(和) フレッシュマンセッション,一般 
テーマ(英) Freshman session, General 
講演論文情報の詳細
申込み研究会 IT 
会議コード 2021-07-IT 
本文の言語 日本語 
タイトル(和) Square-root bottleneckを超えるRIP行列と関連する組合せ論 
サブタイトル(和)  
タイトル(英) RIP matrices breaking the square-root bottleneck and related combinatorics 
サブタイトル(英)  
キーワード(1)(和/英) 擬ランダム性 / Pseudo-randomness  
キーワード(2)(和/英) 制限等長性 / Ramsey graph/tournament  
キーワード(3)(和/英) Ramseyグラフ/トーナメント / restricted isometry property  
キーワード(4)(和/英) /  
キーワード(5)(和/英) /  
キーワード(6)(和/英) /  
キーワード(7)(和/英) /  
キーワード(8)(和/英) /  
第1著者 氏名(和/英/ヨミ) 佐竹 翔平 / Shohei Satake / サタケ ショウヘイ
第1著者 所属(和/英) 熊本大学 (略称: 熊本大)
Kumamoto University (略称: Kumamoto Univ.)
第2著者 氏名(和/英/ヨミ) / /
第2著者 所属(和/英) (略称: )
(略称: )
第3著者 氏名(和/英/ヨミ) / /
第3著者 所属(和/英) (略称: )
(略称: )
第4著者 氏名(和/英/ヨミ) / /
第4著者 所属(和/英) (略称: )
(略称: )
第5著者 氏名(和/英/ヨミ) / /
第5著者 所属(和/英) (略称: )
(略称: )
第6著者 氏名(和/英/ヨミ) / /
第6著者 所属(和/英) (略称: )
(略称: )
第7著者 氏名(和/英/ヨミ) / /
第7著者 所属(和/英) (略称: )
(略称: )
第8著者 氏名(和/英/ヨミ) / /
第8著者 所属(和/英) (略称: )
(略称: )
第9著者 氏名(和/英/ヨミ) / /
第9著者 所属(和/英) (略称: )
(略称: )
第10著者 氏名(和/英/ヨミ) / /
第10著者 所属(和/英) (略称: )
(略称: )
第11著者 氏名(和/英/ヨミ) / /
第11著者 所属(和/英) (略称: )
(略称: )
第12著者 氏名(和/英/ヨミ) / /
第12著者 所属(和/英) (略称: )
(略称: )
第13著者 氏名(和/英/ヨミ) / /
第13著者 所属(和/英) (略称: )
(略称: )
第14著者 氏名(和/英/ヨミ) / /
第14著者 所属(和/英) (略称: )
(略称: )
第15著者 氏名(和/英/ヨミ) / /
第15著者 所属(和/英) (略称: )
(略称: )
第16著者 氏名(和/英/ヨミ) / /
第16著者 所属(和/英) (略称: )
(略称: )
第17著者 氏名(和/英/ヨミ) / /
第17著者 所属(和/英) (略称: )
(略称: )
第18著者 氏名(和/英/ヨミ) / /
第18著者 所属(和/英) (略称: )
(略称: )
第19著者 氏名(和/英/ヨミ) / /
第19著者 所属(和/英) (略称: )
(略称: )
第20著者 氏名(和/英/ヨミ) / /
第20著者 所属(和/英) (略称: )
(略称: )
講演者
発表日時 2021-07-08 16:40:00 
発表時間 50 
申込先研究会 IT 
資料番号 IEICE-IT2021-22 
巻番号(vol) IEICE-121 
号番号(no) no.96 
ページ範囲 pp.40-44 
ページ数 IEICE-5 
発行日 IEICE-IT-2021-07-01 


[研究会発表申込システムのトップページに戻る]

[電子情報通信学会ホームページ]


IEICE / 電子情報通信学会