圧縮センシングの理論とその展開

名古屋工業大学
35分

和田山 正

圧縮センシング(CompressedSensing, Compressive Sensing)✤

信号処理・機械学習・情報理論の分野で注目✤

Donoho, Candes, Taoらが理論を建設(2003年前後)✤

スパース信号の再現理論✤

キーワード：スパース信号、Ｌ１最小化、ランダム行列

圧縮センシング(CompressedSensing, Compressive Sensing)✤

信号処理・機械学習・情報理論の分野で注目✤

Donoho, Candes, Taoらが理論を建設(2003年前後)✤

スパース信号の再現理論✤

キーワード：スパース信号、Ｌ１最小化、ランダム行列

信号処理的世界CS

情報理論的世界

本講演の概要

本講演の概要✤

本講演では、ＣＳの数理的な側面に重点を置き、Candes-Taoらの理論の概略を紹介する。そののち、ＣＳ分野の研究状況の一端について、お話ししたい。
✤問題設定

✤

Candes-Tao のCS理論の概要 (RIP, 完全再現条件)✤各種の復元アルゴリズム✤

多端子情報理論とのつながり

本講演の概要✤

本講演では、ＣＳの数理的な側面に重点を置き、Candes-Taoらの理論の概略を紹介する。そののち、ＣＳ分野の研究状況の一端について、お話ししたい。
✤問題設定

✤

Candes-Tao のCS理論の概要 (RIP, 完全再現条件)✤各種の復元アルゴリズム✤

多端子情報理論とのつながり
圧縮センシングに関する包括的和文解説としては、
田中利幸：圧縮センシングの数理(電子情報通信学会 Fundamentals review)
http://w2.gakkai-web.net/gakkai/ieice/vol4no1pdf/vol4no1_39.pdf

圧縮センシングの問題設定
センシング行列（センサ・復元器とも知っている）

S-スパースベクトル(非零要素個数がS個以内)

圧縮系列

圧縮センシングの問題設定
センシング行列（センサ・復元器とも知っている）

S-スパースベクトル(非零要素個数がS個以内)

圧縮系列

センサ

圧縮系列復元器連立方程式が解けるか？
圧縮系列

センサ復元器=連立方程式が解けるか？
圧縮系列

センサ

復元器
連立方程式を解く？

==に関する制約条件がなければ、不良設定問題→解が一意ではない圧縮センシングの問題意識: S-スパース=からが完全に定まる場合がある[1] 効率の良い復元アルゴリズムを開発したい[2] 完全再現のための十分条件を明らかにしたい完全再現のための十分条件
センサ

=

圧縮系列
復元器

スパースさを表すパラメータが与えられているとき、 をどれくらい大きくとればが成立するか、明らかにしたいCandes-Taoによる完全再現のための十分条件

Candes-Taoによる完全再現のための十分条件
センシング行列の行数がを満たすならば

L1復元法を利用することにより、が十分に高い確率で達成される(完全再現）

Candes-Taoによる完全再現のための十分条件
センシング行列の行数がを満たすならば

L1復元法を利用することにより、が十分に高い確率で達成される
L1復元法の解をとするときとする(完全再現）

L1復元法について

L1復元法について[1] スパース解が求まる (c.f. Lasso, L1正則化)L1復元法について[1] スパース解が求まる (c.f. Lasso, L1正則化)[2] 等価な線形計画法に書き換えることが可能 (多項式時間アルゴリズム)

L1復元法について[1] スパース解が求まる (c.f. Lasso, L1正則化)[2] 等価な線形計画法に書き換えることが可能 (多項式時間アルゴリズム)[3] 局所解＝大域解(凸計画問題)

完全再現条件の証明のなりたち

完全再現条件の証明のなりたち
Candes-Tao
制約等長性 (RIP: Restricted Isometry Property): RIP定数(センシング行列に対して定まる)

完全再現条件の証明のなりたち
Candes-Tao
制約等長性 (RIP: Restricted Isometry Property): RIP定数(センシング行列に対して定まる)＋Candes

完全再現条件の証明のなりたち
Candes-Tao
制約等長性 (RIP: Restricted Isometry Property): RIP定数(センシング行列に対して定まる)＋
Candes＋
ランダム行列アンサンブルにおけるRIP定数の大偏差的評価（最大・最小固有値の大偏差的評価）

制約等長性 (RIP)に対してが成り立つならば、「このセンシング行列はRIPを持つ」という (δは正の小さい実数)最小のδ→RIP定数
任意のサイズS以下の部分行列が正規直交系に近い（ズレの分がδ）

制約等長性 (RIP)に対してが成り立つならば、「このセンシング行列はRIPを持つ」という (δは正の小さい実数)最小のδ→RIP定数
任意のサイズS以下の部分行列が正規直交系に近い（ズレの分がδ）

Candesによる定理
仮定
行列Fはを満たす

Candesによる定理
仮定
行列Fはの解をを満たすとするときが成立するとする

RIP定数の評価とする

評価は計算量的に困難ランダム行列アンサンブル
要素がすべてガウス確率変数である行列(ランダム行列を考える)
Davidson and Szarek (2001)

最大特異値・最小特異値に関する大偏差的評価の一種

証明のスケッチ(1)証明のスケッチ(1)
ユニオン上界証明のスケッチ(1)
ユニオン上界Davidson and Szarek の結果を使う

証明のスケッチ(2)証明のスケッチ(2)
いくつかの変形・不等式評価

証明のスケッチ(2)
いくつかの変形・不等式評価が成立

証明のスケッチ(2)
いくつかの変形・不等式評価が成立

完全再現のための十分条件

証明のスケッチ(2)
いくつかの変形・不等式評価が成立

完全再現のための十分条件

解説記事：和田山正, ̀̀圧縮センシングにおける完全再現十分条件について'', 日本
神経回路学会誌, pp.63-69, Vol.17, no.2, 6月, 2010

ここまでのまとめ✤

良好なδSを有する行列を確定的に構成することは困難。

✤

ランダム行列が良好なδSを有することを確率的手法に基づき示す✤

圧縮系列長pとSとの間のトレードオフ関係を明らかにする✤

疎ベクトル再現ができる、というだけではなく、再現可能な条件について詳細に議論を詰めているのがCS理論の特徴

圧縮センシングに関する研究状況圧縮センシングに関する研究状況

復元アルゴリズムの改良と再現条件

圧縮センシングに関する研究状況

復元アルゴリズムの改良と再現条件

確定的なセンシング
行列の構成法圧縮センシングに関する研究状況

復元アルゴリズムの改良と再現条件

確定的なセンシング
行列の構成法

情報理論的設定における再現条件

圧縮センシングに関する研究状況

復元アルゴリズムの改良と再現条件

マルチセンサーに対するＣＳ理論

確定的なセンシング
行列の構成法

情報理論的設定における再現条件

圧縮センシングに関する研究状況

復元アルゴリズムの改良と再現条件

確定的なセンシング
行列の構成法

マルチセンサーに対するＣＳ理論

低ランク行列近似
行列補間問題

情報理論的設定における再現条件

圧縮センシングに関する研究状況

復元アルゴリズムの改良と再現条件

確定的なセンシング
行列の構成法

情報理論的設定における再現条件

マルチセンサーに対するＣＳ理論

低ランク行列近似
行列補間問題ＣＳの実問題への応用

圧縮センシングに関する研究状況

復元アルゴリズムの改良と再現条件

確定的なセンシング
行列の構成法

情報理論的設定における再現条件

マルチセンサーに対するＣＳ理論

低ランク行列近似
行列補間問題ＣＳの実問題への応用

http://dsp.rice.edu/cs Compressive Sensing Resources圧縮センシングに関する研究状況

復元アルゴリズムの改良と再現条件

確定的なセンシング
行列の構成法

情報理論的設定における再現条件

マルチセンサーに対するＣＳ理論

低ランク行列近似
行列補間問題ＣＳの実問題への応用

http://dsp.rice.edu/cs Compressive Sensing Resources様々な復元アルゴリズム
圧縮系列
復元器
L1復元法以外にも多くの選択肢✤

L0復元アルゴリズム✤

Lp復元アルゴリズム(0<p<1)✤Matching Pursuit✤

メッセージパッシング型✤

射影勾配法型

Lp復元法Lp復元法

完全再現十分条件
NP困難問題(組合せ最適化問題的になる)

Lp復元法

完全再現十分条件
NP困難問題(組合せ最適化問題的になる)
凸計画問題では無くなる→局所解の問題が生じる
実際にはかなりうまく動くことが示されている
Rick Chartrand, Exact reconstructions of sparse signals via nonconvexminimization. (IEEE Signal Proc. Lett., 14(10) pp. 707-710, 2007)

Matching Pursuit
残余ベクトルと最大相関を持つFの列ベクトルを探す(マッチング)
最小２乗法
残余ベクトルの更新
Joel Tropp and Anna Gilbert, Signal recovery from random measurements via
orthogonal matching pursuit. (IEEE Trans. on Information Theory, 53(12) pp.
4655-4666, December 2007)

射影勾配型アルゴリズム GraDes射影勾配型アルゴリズム GraDes

Rahul Garg! and Rohit Khandekar
Gradient Descent with Sparsification: An iterativealgorithm for sparse recovery with restrictedisometry property

射影勾配型アルゴリズム GraDesの等高線

Rahul Garg! and Rohit Khandekar
Gradient Descent with Sparsification: An iterativealgorithm for sparse recovery with restrictedisometry property

射影ステップ勾配法ステップ圧縮センシングに関する研究状況

復元アルゴリズムの改良と再現条件

確定的なセンシング
行列の構成法

情報理論的設定における再現条件

マルチセンサーに対するＣＳ理論

低ランク行列近似
行列補間問題ＣＳの実問題への応用

http://dsp.rice.edu/cs Compressive Sensing Resources相関のある情報源
情報源３
情報源１

情報源４
確率的相関
情報源２

相関のある情報源におけるセンシ
ング
センサ３
センサ１

センサ２

センサ４

相関のある情報源におけるセンシ
ング

センター

再現可能条件、トレードオフはどうなる？

Slepian-Wolf 的設定
センサ１

再現アルゴリズム

相関ある
スパース情報源
センサ２

Dror Baron, Marco F. Duarte, Michael B. Wakin, Shriram Sarvotham, andRichard G. Baraniuk, Distributed compressive sensing. (Preprint, 2005) [Seealso related technical report and conference publications: Allerton 2005,Asilomar 2005, NIPS 2005, IPSN 2006]

多端子情報理論とＣＳ理論のつながり

多端子情報理論とＣＳ理論のつながり
多端子情報理論における符号化有限体上のベクトルに有限体上の行列を乗じる

多端子情報理論とＣＳ理論のつながり
多端子情報理論における符号化

ＣＳにおけるセンシング

有限体上のベクトルに有限体上の行列を乗じる

実数体上のベクトルに実数体上の行列を乗じる

Koerner-Marton的設定
２つのデータの差分のみ知りたい
センサ１

再現アルゴリズムセンサ２

センシング過程が線形演算に成っているところがポイントまとめ✤✤✤

本講演では、ＣＳの数理的な側面に重点を置き、Candes-Taoらの理論の概略について説明した。
✤ＣＳ理論＝復元アルゴリズム＋再現条件✤

CS理論は信号処理的でもあり、情報理論的でもある

いくつかの復元アルゴリズムの原理について解説した
ＣＳと多端子情報理論のつながり・類似性に着目することで新しいテーマが生まれる可能性がある