•
， とする•
を計算•
となる があれば，それを復号結果とする•
出力：このステップで復号された の集合
Step 2
• ,
： の に対する直交成分•
を計算•
を計算•
となる があれば，それを復号結果とする•
出力：このステップで復号された の集合
Step
• ,
： の に対する直交成分
•
を計算•
を計算•
となる があれば，それを復号結果とする•
出力：このステップで復号された の集合
直交成分の作り方
•
シュミットの直交化法により行う•
―
ただし復号のペースを制限する方法
の作り方の変更
•
（ ）•
：step
において閾値を超えた の集合•
•
を に入れていくが を超えないよう
な制限の元で，できるだけ多く入れる
•
は指定しておく（
1
にすると となる） 38終了条件
•
復号された の数が になったとき•
閾値を超える が一つもなかったとき•
が１以上になったとき指定すべきパラメータ
① 電力割り当て
② 復号のペース制限
③ を構成するため
のパラメータ
update function
•
•
ただし， ， は標準正規分布の上側確 率
•
辞書のサイズと通信路( )
，閾値を設定すると 決まるg L (x) によるペースの観察
[Barron and Joseph 2010]より
の設定
•
を用意→
で設定•
① のとき
→
② のとき
→
ベイズ最適適応的逐次復号 [Barron and Cho 12]
• 初期ステップ
• 各列 1,2, … , と各セクション 1,2, … , に対して以下を計
算
, , ‖ ‖
, ,
, ,
∑ ∈ , ,
, ,
Barron and Cho, ``High‐rate sparse superposition codes with iteratively optimal estimates." Proc. of IEEE Intl. Symp. on Inform. Theory. Cambridge, MA, July 2012, pp. 120‐124.
ベイズ型アルゴリズム ( 続き )
•
第 ステップ•
以下を計算, ,
, ,
∑ ∈ , ,
, ,
•
規定の回数反復した後，最終的な から台を求めて 終了(MAP)
ベイズ型アルゴリズムの特徴
•
, が第 ステップの時点で 列が正しい列であるという事 後確率•
は , , で各成分対応する列の事後確率 で決まる•
ステップが進むにつれ が に近づく•
の期待値は第 ステップの時点で正しく推定でき るセクション数の割合の期待値と一致するLemma2, [Barron and Cho 2012]
⇒ AMP
のt
状態発展式
の役割に類似．E の振る舞いは g で分かる
実験
•
各アルゴリズムによる復号を行ってセクション誤り率 をみ る:
誤って復号されたセクション数:
列が復号されなかったセクション数復号実験パラメータ
• snr=7
•
レートR = 0.3C, 0.4C, 0.5C
．•
各アルゴリズムで各設定100
回ずつ実験•
ビット誤り率< q
となる回数を計測(q=0.1
～0.5)
•
使用環境• R on Linux
，Intel(R) Xeon(R) CPU E5-2690 0 @ 2.90GHz
•
逐次復号アルゴリズムについて•
閾値2log 0.1
達成可能レート
宮本らによる実験で，
Joseph & Barron
アルゴリズムでR = 0.4C,
ベイズ最適化で，R = 0.5C
程度参考 ([Barron & Cho 2012]の図)
考察 at ISIT2012 (Boston)
• LDPC
符号• MAP
復号でC
達成• BP
による効率的復号ではC
までギャップ•
空間結合で効率的復号でC
達成．•
圧縮センシング(Bayes
最適AMP)
• L0
再構成で情報理論的限界達成• L1
再構成は性能のギャップあり．•
空間結合でL0
と同等の性能[Donoho et al. 2013]
•
スパース重ねあわせ符号•
最尤復号でC
達成•
効率的復号では大きなレートドロップLDPC
符号と圧縮センシングの状況から類推して，空間結合でレートドロップを改善できないか？
次元ベクトル ，観測行列（
, A
によって 次元ベクトル が次のように与えられているとする。問題設定
⋮ ⋯⋱ ⋮
⋯
A
～N 0,
：
( ‐)
スパースなベクトル圧縮センシングとは（
1/2
）圧縮率 信号密度
[5]田中利幸, ``圧縮センシングの数理,'' IEICE Fundamentals Review, Vol.4, No.1, pp.39‐
47,2010年.
圧縮センシングでは非零要素の位置が未知である場合の復元をどの程 度まで が小さい範囲で行えるかを問題とする
圧縮センシングとは（
2/2
）（計算困難）
（効率的）
再構成： arg min | | . .
再構成： arg min | | . .
右に示す３種類のノルムを用いる
• また，各要素が N 0, σ に従うノイズ
W
∈ があると（計算困難）
（効率的）
再構成： arg min | | . . | |
再構成： arg min | | . . | |
ノルム：
ノルム：
ノルム：
⇔ arg min λ （ラグランジュ未定乗数法による）
ノイズなし
ノイズあり
（ユークリッドノルム）
で復元可能
（弱しきい値） で復元可能
再構成のアルゴリズムの１つで理論的によいとされている
条件（残差のノルムが一定値以下，反復回数が一定回数以 上等）を満たすまで次の反復式を用いて未知ベクトルを推定
圧縮センシングの再構成アルゴリズム
Approximate Message Passing
（AMP）
, λ
1 · η’ , λ
（ ：反復回数）
[5]田中利幸, ``圧縮センシングの数理,'' IEICE Fundamentals Review, Vol.4, No.1, pp.39‐47,2010年.
, λ
1 · η’ , λ
（ ：反復回数）
空間結合圧縮センシング
空間結合
空間結合 観測行列を帯対角の形にすることによって，計算量を低く 保ったまま復元限界を改良するというアイデア
Bayes 最適AMPと呼ばれるアルゴリズムを用いる 手法
手法
未知ベクトルの事前分布を とすると，復元可能な の下 限は によって決まり，その値を とする
特徴
[1] Donoho, Javanmard, and Montanari, "Information‐theoretically optimal compressed sensing via spatial coupling and approximate message passing," IEEE transactions on information theory 59.11 (2013): 7434‐7464.
空間結合圧縮センシングのアイデア
もし， ， ， が
推定できたとすると
…
連鎖的に他の要素も決定する． 空間結合の構造を，単純化した例を使って説明する．
観測行列 は行列 によって決まる．
空間結合圧縮センシングの再構成アルゴリズム
⊙ ∗ AMP
⊙ Bayes
Optimal AMP Bayes Optimal AMP
：観測行列Aの要素のインデックスを，
対応する ブロックのインデックス に写す関数
⊙ はアダマール積を表す
未知ベクトル について事前分布を既知としている
[1] Donoho, Javanmard, and Montanari, "Information‐theoretically optimal compressed sensing via spatial coupling and approximate message passing," IEEE transactions on information theory 59.11 (2013): 7434‐7464.
Bernoulli‐Gussian事前分布 の場合
スパース重ね合わせ符号における空間結合
[Barbier et al. 14]
はΓ Γのブロックに分けられる．インデックスを , とし，各ブロックを , とする．
即ち， /Γ列, /Γ行となる．ここで /Γ ， /Γ とする．
帯の幅を決定する ，行列 の要素の値を決定する関数 を導入．
0 1 0
とすると．∀ において，
は∑ , 1 と正規化し，
, の各要素は N 0, , に従う
, ≔ Γ
2 1
シェイプマトリックス ,
[2] Barbier, Dia, and Macris, "Proof of Threshold Saturation for Spatially Coupled Sparse Superposition Codes,"
arXiv preprint arXiv:1603.01817 (2016): 7434‐7464.
Replica 解析： AMP vs 適応的逐次復号 [Barbier & Krzakala 2014]
Barbier and Krzakala, ``Replica analysis and approximate message passing decoder
空間結合
AMP
復号器の大極限理論保証[Barbier, Dia, & Macris 16]
lim→
定理6.2 孤立系理論限界と空間結合系AMP閾値の関係
シェイプマトリックスが非常に大きいとき…
→
孤立系 理論限界
通信路符号化定理 ： C
セクション サイズが大
セクション サイズが大
⇒
通信路容量通信路容量達成達成Barbier, Mohamad, & Macris, "Proof of Threshold Saturation for Spatially Coupled
Sparse Superposition Codes," arXiv preprint arXiv:1603.01817 (2016): 7434‐7464.
実験１
(
波多江ら)
：孤立系
SS
符号の復号(
反復11
回で復元)
信号密度 0.1のときの孤立系AMPの限界 0.2385 であること がわかっている．具体的な値は下表に示す．
符号長 1750
ベクトル の次元 5000 セクションサイズ 10
圧縮率 0.35
信号密度 0.1
SN比 5
伝送速度 0.7343C
＜孤立系の実験設定＞
実験２
(
波多江ら)
：空間結合系
SS
符号の復号(
反復63
回で復元成功)
シェイプマトリックスを無限に大きくしたときの伝送速度 を とする
シェイプマトリックスのサイズは55*50，帯の幅は6とした １ブロックの符号長 21
１ブロックのベクトル 次元 100
符号長 1155
ベクトル の次元 5000 セクションサイズ 10
圧縮率 0.21
信号密度 0.1
SN比 80
伝送速度 0.4537C
伝送速度 0.7045C
1
1/2 1/2 1/3 1/3 1/3 1/4 1/4 1/4 1/4
1/5 1/5 1/5 1/5 1/5 1/5 1/6 1/6 1/6 1/6 1/6 1/6 1/6
1/6 1/6 1/6 1/6 1/6 1/6 1/6
1/3 1/3 1/3 1/2 1/2 1
・・・
O
O
＜空間結合系の実験設定＞
＜デザインマトリックスの構造＞
[Donoho, Javanmard, Montanari 13] の シミュレーションの追試 1 [ 大浦 16]
[大浦 16] 大浦聡一郎, 状態発展式による空間結合圧縮センシングの解析 ，
[Donoho, Javanmard, Montanari 13]
のシミュレーションの追試 2 [ 大浦 16]
実験３
(
波多江ら)
：空間結合系
SS
符号の復号（復元不可能） 実験２の設定において帯の幅を変えずにシェイプマトリックスを大きくした
デザインマトリックスのサイズは55*50から75*70へとした
1
1/2 1/2 1/3 1/3 1/3 1/4 1/4 1/4 1/4
1/5 1/5 1/5 1/5 1/5 1/5 1/6 1/6 1/6 1/6 1/6 1/6 1/6
1/6 1/6 1/6 1/6 1/6 1/6 1/6
1/3 1/3 1/3 1/2 1/2 1
・・・
O
O
＜空間結合系の実験設定＞
＜デザインマトリックスの構造＞
１ブロックの符号長 21 １ブロックのベクトル 次元 100
符号長 1575
ベクトル の次元 7000 セクションサイズ 10
圧縮率 0.21
信号密度 0.1
SN比 80
伝送速度 0.4537C
伝送速度 0.7045C
power allocation AMP 復号器の理論保証 [Rush & Venkataramanan 17]
AMP
反復式誤り確率の上界
ベイズ最適 AMP 復号器のシミュレーション [Rush, Greig, Venkataramanan 17]
power allocation with Bayes最適AMP，ただし，辞書はアダマール行列
v = 15 C = 2
ベイズ最適 AMP の
最新のシミュレーション ( 波多江ら )
• n =351, L = 100, M =30, N =3000, v =10, R = 0.8C
power allocation
あり： ビット誤り率 平均7%
程度ベルヌーイ辞書を用いた スパース重ね合わせ符号
[Takeishi, Kawakita, and Takeuchi 12]
[Takeishi & Takeuchi 16]
[1] Y. Takeishi, M. Kawakita, and J. Takeuchi, "Least squares superposition codes with
Bernoulli dictionary are still reliable at Rates up to Capacity," IEEE Trans. Inform._ Theory, vol.
60, no. 5, pp. 2737‐2750, May 2014.
[2] Y. Takeishi and J. Takeuchi, "An improved upper bound on block error probability of least squares superposition codes with unbiased Bernoulli dictionary," Proc. of 2016 IEEE Intl.
Symp. on Inform. Theory, pp. 1168 ‐1172, Barcelona, Spain, July 10‐15, 2016.
Barron and Joseph による予想
(2010)
•
ベルヌーイ辞書を用いた場合でも通信路容量を達 成できる
この場合も，符号語の平均電力制約は満たされる
符号語は各次元独立に， にしたがう分布に 近づく（中心極限定理）ベルヌーイ辞書： で生成
本研究ではこの予想を確かめた
‐1 ‐1 1 1 ‐1 1 1 1 ‐1
定理（ベルヌーイ辞書のときの最尤復号）
は各要素独立に確率
1/2
で ，確率1/2
で として生成する．とし，セクションサイズ率 はある条件を満た すものとする．このとき， に対して，
が成り立つ．ただし，
である．
補題７ ( 簡略版 ) [Takeishi, Kawakita, Takeuchi 14]
1000
以上の任意の自然数 に対して，が成り立つ．