第32回信号処理シンポジウム 2017年11月8日〜10日（盛岡） - 262 -

Generalization of Discrete-Valued Vector Reconstruction Based on Approximate Message Passing

† ‡

†

‡

Ryo HAYAKAWA

Kazunori HAYASHI

† Graduate School of Informatics, Kyoto University

‡ Graduate School of Engineering, Osaka City University

DAMP Discreteness- aware Approximate Message Passing

DAMP

DAMP DAMP

1

[1], [2] MIMO (Multiple-Input Multiple- Output) [3] FTN (Faster-than-Nyquist)

[4]

[5]. [6], [7]

SOAV (Sum-of-Absolute-Value) [8] SOAV

SOAV SOAV

DAMP (Discreteness-aware Ap- proximate Message Passing)

[9], [10] DAMP

Approximate Message Pass-

ing, AMP [11], [12] SOAV

[9] [10]

[11], [13] DAMP

DAMP

(Mean-Square-

Error, MSE) DAMP

DAMP DAMP

(·)^T

1 1 0

0 v = [v1 · · ·vN]^T ∈ R^N

ℓ1 ∥v∥¹=!N

n=1|vn| ℓ2 ∥v∥²=

"!N

n=1v²_n v ⟨v⟩=

1 N

!N

n=1vn h:R^N →R

[14]

prox_h(u) = arg min

s∈R^N

#

h(s) +1

2∥s−u∥²2

$ (1) sgn(·)

第32回信号処理シンポジウム 2017年11月8日〜10日（盛岡）

φ(z) =

√1

2πexp%

−^z2²

&

Φ(z) ='z

−∞φ(z^′)dz^′ 2 DAMP

SOAV [8]

AMP [11]

DAMP 4.2 2.1 SOAV

SOAV b = [b1 · · ·bN]^T ∈

{r1, . . . , rL}^N ⊂R^N (r1<· · ·< rL)

y=Ab (2)

y = [y1· · · yM]^T ∈ R^M A ∈ R^M×N

A (m, n) am,n m = 1, . . . , M

n = 1, . . . , N b

Pr(bn = rℓ) = pℓ (n = 1, . . . , N ℓ = 1, . . . , L) i.i.d. independent and identically distributed

b−rℓ1

pℓN SOAV

ˆb= arg min

x∈R^N

(L ℓ=1

qℓ∥x−rℓ1∥¹ subject to y=Ax (3)

b SOAV [8]

qℓ ≥0 qℓ =pℓ

[5] q1 = · · · = qL = 1

3.2 . [9] [10]

(3)

2.2 DAMP

DAMP (3)

µ(x)

∝ )N n=1

exp

*

−β (L ℓ=1

qℓ|xn−rℓ| + _M

)

m=1

δ

⎛

⎝ym= (N j=1

am,jxj

⎞

⎠ (4)

[15]

β>0 δ%

ym=!N

j=1am,jxj

&

ym=!N

j=1am,jxj Dirac β → ∞

(4) (3)

xn (3)

N

M, N → ∞ M/N =∆ β → ∞

(4) sum-product

[12] AMP

A∈R^M×N i.i.d. 0 1/M DAMP

x^t+1=η 0

x^t+A^Tz^t;τ σt

√∆ 1

, (5)

z^t=y−Ax^t + 1

∆z^t−1 2

η^′ 0

x^t−1+A^Tz^t−1;τσt−1

√∆ 13

(6)

x^t t b

η(·)

η(u;c) = prox_cJ(u) (7) J(x) =!L

ℓ=1qℓ∥x−rℓ1∥¹

(3) [2]

prox_cJ(u) n [prox_cJ(u)]n

=

⎧⎪

⎪⎪

⎪⎪

⎪⎪

⎪⎪

⎪⎪

⎪⎪

⎪⎪

⎨

⎪⎪

⎪⎪

⎪⎪

⎪⎪

⎪⎪

⎪⎪

⎪⎪

⎪⎩

un−cQ1 (un < r1+cQ1)

r1 (r1+cQ1≤un< r1+cQ2)

... ...

un−cQk (r_k−1+cQk≤un< rk+cQk) rk (rk+cQk≤un < rk+cQk+1)

... ...

un−cQL+1 (rL+cQL+1≤un)

(8)

un u n Q1 =

−!L

ℓ=1qℓ, QL+1=!L ℓ=1qℓ, Qk=

k−1(

ℓ=1

qℓ− (L ℓ^′=k

qℓ^′ (k= 2, . . . , L) (9)

[prox_cJ(u)]n un η(u;c)

u (6) η^′(u;c)

n η(u;c) un

[prox_cJ(u)]n ∈ {r1, . . . , rL} [η^′(u, c)]n = 0 [η^′(u, c)]n = 1 τ (≥0) σ²_t =∥x^t−b∥²2/N t

MSE b

σ²_t σˆ²_t =∥z^t∥²2/N [16].

DAMP (5), (6)

AMP η(u, c)

[η(u, c)]n= sgn(un) max{|un|−c,0}

(7)–(9) η(u, c)

3 DAMP

[11], [13] DAMP

3.1

AMP

x^t MSE σ²_t =∥x^t−b∥²2/N

DAMP (5), (6)

σ_t+1² =Ψ(σ²_t) (10)

Ψ(σ²) = E 8#

η 0

X+ σ

√∆Z;τ σ

√∆ 1

−X

$29 (11)

X

Pr(X =rℓ) = pℓ (ℓ = 1, . . . , L)

Z X

[13]

A i.i.d. 0 1/M

η(·) [13]

i.i.d. 0 1/M

[11]

3.2

Ψ(σ²) DAMP

Ψ(0) = 0 Ψ(σ²) σ² = 0 1

(10)

{σ²_t}^t=0,1,... 0 dΨ

d(σ²) :: ::_σ

↓0

<1 Ψ(σ²)<σ² σ_t+1² =Ψ(σ²_t)<σ_t²

DAMP b

dΨ d(σ²)

:: ::_σ

↓0

dΨ d(σ²)

:: ::_σ

↓0

:=D(U) (12)

= 1

∆ (L ℓ=1

pℓ;

Uℓφ(Uℓ)−Uℓ+1φ(Uℓ+1) +<

1 +U_ℓ²= Φ(Uℓ) +<

1 +U_ℓ+1² =

(1−Φ(Uℓ+1))>

(13) U= [U1 · · · UL+1]^T Uℓ=τQℓ(ℓ= 1, . . . , L+ 1) (3) q1, . . . , qL≥0

τ ≥0 (13)

Dmin= min

U D(U) subject toU1≤· · ·≤UL+1 (14)

(14) U U^opt =

?U₁^opt · · · U_L+1^opt @^T

(14) U1 =

−UL+1 U1 UL+1

U₁^opt=−∞ U_L+1^opt =∞ Dmin

(14) [17]

(14) dΨ

d(σ²) :: ::

σ↓0

Dmin

(8)

?η^S(u)@

n=

⎧⎪

⎪⎪

⎪⎪

⎪⎪

⎪⎪

⎪⎪

⎪⎪

⎪⎪

⎪⎨

⎪⎪

⎪⎪

⎪⎪

⎪⎪

⎪⎪

⎪⎪

⎪⎪

⎪⎪

⎩ r1

0

un < r1+ σ

√∆U₂^opt 1

... ...

un− σ

√∆U_k^opt 0

r_k−1+ σ

√∆U_k^opt≤un < rk+ σ

√∆U_k^opt 1

rk

0

rk+ σ

√∆U_k^opt≤un< rk+ σ

√∆U_k+1^opt 1

... ...

rL

0

rL+ σ

√∆U_L^opt≤un

1

(15)

?η^S(u)@

n η^S(u) n η^S(·) DAMP

DAMP

Dmin < 1 Ψ^S(σ²) = EAB η^S%

X+^√σ_∆Z&

−XC²D

DAMP b Ψ(σ²)

d²Ψ d(σ²)² =

√∆ 2σ⁵

(L ℓ=1

pℓ

(L k=1

(−rℓ+rk)³{−φ(Tℓ,k,k) +φ(Tℓ,k,k+1)} (16)

Ψ^S(σ²)

4 DAMP

DAMP DAMP

4.1 DAMP

(5) (6) DAMP

(15) η(·)

(10) η(·)

?η^B(u)@

n = EE

X:::X+^√σ_∆Z =un

F

AMP [16]

η^B(·) Ψ(σ²) = EAB η%

X+^√σ_∆Z&

−XC2D

η(·) Ψ(σ²)

η^B(·)

η^B(·) X

Pr 0

X =rℓ

::

::X+ σ

√∆Z =un

1

= 1 αpℓφ

*√

∆

σ (un−rℓ) +

(17) α α=

!L

ℓ=1pℓφ%√

∆

σ (un−rℓ)&

(17)

?η^B(u)@

n=

!L

ℓ=1pℓrℓφ%√

∆

σ (un−rℓ)&

!L

ℓ^′=1pℓ^′φ%√

∆

σ (un−rℓ^′)& (18)

DAMP

σ²_t+1 = Ψ^B(σ²_t) Ψ^B(σ²) = EAB

η^B% X+√^σ

∆Z&

−XC2D

η^B(·)

Ψ(σ²) DAMP

MSE σ_t+1² =Ψ^B(σ²_t) MSE {σ²}^t=0,1,... Ψ^S(σ²) Dmin<1

0 Ψ^B(σ²)

DAMP

b

sum-product GAMP [18]

∥A∥²F=N DAMP

∥A∥^F="!M m=1

!N n=1a²_m,n A

DAMP MIMO

[19]

MSE σ_t² DAMP

DAMP MSE

DMAP 3.2

η^S(·) SOAV

[2], [3] AMP DAMP

i.i.d.

i.i.d.

SOAV

i.i.d. i.i.d

[3]

η^S(·) DAMP 4.2

y=Ab+v v

0 σ_v²I

AMP [16]

σ²_t+1=Ψ<

σ²_t+∆σ_v²=

(19) η^S(·) η^B(·) σ G

σ²+∆σ_v² DAMP

DAMP MSE

{σ²_t}^t=0,1,... (19) 5

DAMP

A∈R^M×N i.i.d.

0 1/M

x⁻¹=x⁰=0,z⁻¹=0

DAMP MSE

σ² = ∥x^t−b∥²/N

0 10 20 30 40 50 number of iterations

10⁻⁴ 10⁻³ 10⁻² 10⁻¹ 10⁰ 10¹

MSE

theoretical (state evolution) empirical (N= 100) empirical (N= 500) empirical (N= 1000) empirical (N= 5000)

Bayes optimal soft thresholding

1: MSE

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

∆ 0

0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

recoveryrate

p1= 0.3 (soft thr.) p1= 0.6 (soft thr.) p1= 0.9 (soft thr.) p1= 0.3 (Bayes opt.) p1= 0.6 (Bayes opt.) p1= 0.9 (Bayes opt.) p1= 0.9

p1= 0.3

p1= 0.6

2: b ∈ {0,1}^N,Pr(bn = 0) = p1,Pr(bn= 1) = 1−p1, N= 1000

1 r1 =−1, r2 = 0, r3 = 1, p1 = 0.4, p2 = 0.2, p3 = 0.4,∆ = 0.8,σ²_v = 0.01

N = 100,500,1000,5000 DAMP Bayes

optimal MSE DAMP

soft thresholding N

theoretical empirical

2, 3 DAMP

t= 500 σ_t²<10⁻³

2 b∈{0,1}^N(N = 1000)

∆

DAMP DAMP

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

∆ 0

0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

recoveryrate

L= 2 (soft thr.) L= 4 (soft thr.) L= 6 (soft thr.) L= 2 (Bayes opt.) L= 4 (Bayes opt.) L= 6 (Bayes opt.)

L= 2

L= 4

L= 6

3: b ∈ {±1}^N(L = 2),b ∈

{±1,±3}^N(L = 4),b ∈ {±1,±3,±5}^N(L = 6), N = 1000

0 0.2 0.4 0.6 0.8 1

∆ 10⁻⁴

10⁻³ 10⁻² 10⁻¹ 10⁰

MSE

theoretical (state evolution) empirical

Bayes optimal

soft thresholding

4: MSE

DAMP DAMP

1 t= 500

N

3

b∈{±1}^N,b ∈{±1,±3}^N,b∈{±1,±3,±5}^N 2

DAMP DAMP

MSE 4 b∈

{−1,0,1}^N(N = 1000) Pr(bn = 0) = 0.2,Pr(bn =−1) = Pr(bn = 1) = 0.4

σ_v²= 0.01, t = 500 “theoretical (state evolution)”

(19) (19)

∆ DAMP

MSE DAMP

6

DAMP DAMP

MSE DAMP

DAMP

15K06064, 15H02252, 17J07055

[1] Y. Kabashima, “A CDMA multiuser detection algo- rithm on the basis of belief propagation,”J. Phys.

A, vol. 36, pp. 11111–11121, Oct. 2003.

[2] H. Sasahara, K. Hayashi, and M. Nagahara, “Mul- tiuser detection based on MAP estimation with sum-of-absolute-values relaxation,” IEEE Trans.

Signal Process., vol. 65, no. 21, pp. 5621–5634, Nov.

2017.

[3] R. Hayakawa and K. Hayashi, “Convex optimiza- tion based signal detection for massive overloaded MIMO systems,”IEEE Trans. Wireless Commun., DOI: 10.1109/TWC.2017.2739140. (accepted for publication)

[4] H. Sasahara, K. Hayashi, and M. Nagahara, “Sym- bol detection for faster-than-Nyquist signaling by sum-of-absolute-values optimization,”IEEE Signal Process. Lett., vol. 23, no. 12, pp. 1853–1857, Dec.

2016.

[5] A. A¨ıssa-El-Bey, D. Pastor, S. M. A. Sba¨ı, and Y.

Fadlallah, “Sparsity-based recovery of finite alpha- bet solutions to underdetermined linear systems,”

IEEE Trans. Inf. Theory, vol. 61, no. 4, pp. 2008–

2018, Apr. 2015.

[6] D. L. Donoho, “Compressed sensing,”IEEE Trans.

Inf. Theory, vol. 52, no. 4, pp. 1289–1306, Apr.

[7] K. Hayashi, M. Nagahara, and T. Tanaka, “A user’s guide to compressed sensing for communica- tions systems,”IEICE Trans. Commun., vol. E96- B, no. 3, pp. 685–712, Mar. 2013.

[8] M. Nagahara, “Discrete signal reconstruction by sum of absolute values,”IEEE Signal Process. Lett., vol. 22, no. 10, pp.1575–1579, Oct. 2015.

[9] R. Hayakawa and K. Hayashi, “Discreteness-aware AMP for reconstruction of symmetrically dis- tributed discrete variables,” inProc. IEEE SPAWC 2017, July 2017.

[10] R. Hayakawa and K. Hayashi, “Binary vector recon- struction via discreteness-aware approximate mes- sage passing,” in Proc. APSIPA ASC 2017, Dec.

2017. (accepted for publication)

[11] D. L. Donoho, A. Maleki, and A. Montanari,

“Message-passing algorithms for compressed sens- ing,” Proc. Nat. Acad. Sci., vol. 106, no. 45, pp. 18914–18919, Nov. 2009.

[12] D. L. Donoho, A. Maleki, and A. Montanari, “Mes- sage passing algorithms for compressed sensing: I.

motivation and construction,” in Proc. IEEE Inf.

Theory Workshop, pp. 1–5, Jan. 2010.

[13] M. Bayati and A. Montanari, “The dynamics of message passing on dense graphs, with applications to compressed sensing,” IEEE Trans. Inf. Theory, vol. 57, no. 2, pp. 764–785, Feb. 2011.

[14] P. Combettes and J. Pesquet, “Proximal splitting methods in signal processing,” inFixed-Point Algo- rithms for Inverse Problems in Science and Engi- neering, ser. Springer Optimization and Its Appli- cations. Springer New York, vol. 49, pp. 185–212, 2011.

[15] J. Pearl, Probabilistic reasoning in intelligent sys- tems: networks of plausible inference, Morgan Kaufmann Publishers Inc., 1988.

[16] D. L. Donoho, A. Maleki, and A. Montanari, “The noise-sensitivity phase transition in compressed sensing,”IEEE Trans. Inf. Theory, vol. 57, no. 10, pp. 6920–6941, Oct. 2011.

[17] S. Boyd and L. Vandenberghe, Convex Optimiza- tion, Cambridge University Press, 2004.

[18] S. Rangan, “Generalized approximate message passing for estimation with random linear mixing,”

inProc. ISIT 2011, July–Aug. 2011.

[19] C. Jeon, R. Ghods, A. Maleki, and C. Studer, “Op- timality of large MIMO detection via approximate message passing,” inProc. ISIT 2015, June 2015.