| 講演名 | 2012-11-08 事後確率最大化推定に基づく圧縮センシングのデータ復元アルゴリズム(第15回情報論的学習理論ワークショップ) 竹田 晃人, 樺島 祥介, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 圧縮センシングにおける疎データ復元問題を解く際の効率的な解法を導出する手続きに付いて考察する.良く知られた解法である線形計画法に基づいたl_1ノルム最小化復元では計算量がデータサイズの3乗となるが,本稿では事後確率最大化に基づくアルゴリズムを考えるとこの計算量が2乗(疎行列観測過程なら1乗)となること,さらにアルゴリズムを工夫することで最小限の観測数で復元が理論上は可能なことを議論する.さらに既知の確率伝搬法に基づいた同様のアルゴリズムとの関係についても議論する. |
| 抄録(英) | We propose an idea for how to derive sparse data recovery algorithm with smaller computational cost in compressed sensing. It is known that the cost of the standard l_1 recovery algorithm based on linear programming is O(N^3). We show that this cost can be reduced to O(N^2)(for sparse matrix O(N)) by introducing the maximization procedure of posterior. Furthermore, by this method we can reconstruct original data with as small number of observations as possible in principle. We also discuss the relationship between belief-propagation based recovery algorithm in preceding work and our idea. |
| キーワード(和) | 圧縮センシング / データ圧縮 / データ疎性 / 統計力学 / 事後確率最大化 |
| キーワード(英) | compressed sensing / data compression / sparsity / statistical mechanics / maximum a posteriori estimation |
| 資料番号 | IBISML2012-76 |
| 発行日 |
| 研究会情報 | |
| 研究会 | IBISML |
|---|---|
| 開催期間 | 2012/10/31(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Information-Based Induction Sciences and Machine Learning (IBISML) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 事後確率最大化推定に基づく圧縮センシングのデータ復元アルゴリズム(第15回情報論的学習理論ワークショップ) |
| サブタイトル（和） | |
| タイトル（英） | Revocery algorithm in compressed sensing based on maximim a posteriori estimation |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 圧縮センシング / compressed sensing |
| キーワード(2)（和/英） | データ圧縮 / data compression |
| キーワード(3)（和/英） | データ疎性 / sparsity |
| キーワード(4)（和/英） | 統計力学 / statistical mechanics |
| キーワード(5)（和/英） | 事後確率最大化 / maximum a posteriori estimation |
| 第 1 著者 氏名（和/英） | 竹田 晃人 / Koujin TAKEDA |
| 第 1 著者 所属（和/英） | 東京工業大学大学院総合理工学研究科知能システム科学専攻 Department of Computational Intelligence and Systems Science, Tokyo Institute of Technology |
| 第 2 著者 氏名（和/英） | 樺島 祥介 / Yoshiyuki KABASHIMA |
| 第 2 著者 所属（和/英） | 東京工業大学大学院総合理工学研究科知能システム科学専攻 Department of Computational Intelligence and Systems Science, Tokyo Institute of Technology |
| 発表年月日 | 2012-11-08 |
| 資料番号 | IBISML2012-76 |
| 巻番号（vol） | vol.112 |
| 号番号（no） | 279 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |