レプリカ法による制限等長定数の解析 A A A

2015年6月19日統計数理研究所オープンハウス
レプリカ法による制限等長定数の解析
坂田綾香
モデリング研究系助教
東京工業大学大学院総合理工学研究科樺島祥介氏との共同研究
N
Y＝
M
ゼロ成分
X
A
M
圧縮表現
最もスパースな原信号Xを
N
一意に復元するための条件は？
圧縮行列
原信号
スパースな原信号の復元方法
l0再構成
l1再構成
xˆ = arg min x 0 , subject to Y = Ax
xˆ = arg min x 1 , subject to Y = Ax
X
X
非ゼロ要素の数
絶対値の和
|xi|1
|xi|0
1
線形計画問題
NP困難
全数探索が必要
l0 再構成の凸緩和
xi
0
0
xi
復元成功の十分条件は制限等長定数により与えられる
制限等長定数の定義
1. δ2S < 1のとき、l0 再構成は一意なS-スパース解を与える。
S個の非ゼロ要素を持つベクトルをS-スパースベクトルと呼ぶ。
2. δ2S < 21/2 – 1のとき、l1 再構成はl0 再構成と同じ解を与える。
全ての S-スパースベクトル x∈ RN について、
min
max
次の関係を満たす定数 δ S , δ S が存在するとき、
(1 − δ Smin ) x
2
F
≤ Ax
2
F
≤ (1 + δ Smax ) x
[Candes and Tao, IEEE Trans. Inform. Theory (2005)]
2
3. (2.の改善)
F
max
(4 2 − 3)δ 2min
S + δ 2 S < 4( 2 − 1) のとき、
行列A はS-制限等長性(RIP)を満たす。
min max
δS = max{δ S , δ S }を制限等長定数(RIC)と呼ぶ。
l1 再構成はl0 再構成と同じ解を与える。
[Foucart and Lai, Appl. Comput. Harmon. Anal. (2009)]
δsが小さいとき、A は正規直交系に近い。
7
要するに
M/N = 0.5 での結果
a1 a2 a3 a4 a5
5
=
AT
＊
＊
a2 a4
XT
4
3
X
λmin ( ATT AT ) xT
2
F
≤ AT xT
Replica Symmetric
bound (Our result)
δS
δS
A
0
＊
0
＊
0
Bah-Tanner
(2010)
6
S = 2, T = {2,4}, N = 5, V = {1, 2, 3, 4, 5}
Numerical lower bound
(Dossal et al, 2010)
2
2
F
≤ λmax ( A TT A T ) xT
2
我々の見積もりは、
既存研究より
良い上界を与える。
詳しい導出は
arxiv: 1501.06281
Bah-Tanner
RS Bound
Numerical Lower Bound
1
F
0
δ S = max{1 − min λmin ( A TT A T ), max λmax ( A TT A T ) − 1}.
T :|T |= S ,T ⊆V
T :|T |= S ,T ⊆V
0
0.1
0.2
0.3
0.4
0.5
ρS/M
/α
0.6
0.7
0.8
0.9
1

Download Report