25 11M n O(n 2 ) O(n) O(n) O(n)

Transcription

1 M15133

2 25 11M n O(n 2 ) O(n) O(n) O(n)

3

4 1 (Compressed Sensing) x x y x ϵ y x m n A (m < n) y = Ax y A x ϵ p e Candes Tao [1] L 1 RIP (Restricted Isometry Property) [2] L p (0 p 1) Donoho Tanner [3, 4] L 1 [2] [5] Krzakala [6] (Belief Propagation) [7] 2 RIP Luby (Verification-based Decoding Algorithm) [8] LDPC (Low-Density Parity-Check) Zhang [9] (Nodebased Verification-based Decoding Algorithm) Kudekar Pfister [10] (Massage-based Verification-based Decoding Algorithm) (Spatially Coupled) [11] 2

5 LDPC BP Chandar [12] n O(n)

6 2 2.1 α x = t (x 1,..., x n ) R n A R m n (m < n) y = Ax = t (y 1,..., y m ) R m α := m n A y ˆx m n A ranka = n ˆx = x ˆx A α < 1 m < n x ˆx x x j ( j [1, n]) ϵ ϵ := Pr[X j 0] ( j [1, n]) x j x R Pr[X j = x] = 0 ( j [1, n], x 0, x R) 4

7 p(x) := d Pr[X x] (x 0) dx X p(x) p(x) = (1 ϵ)δ(x) + ϵ p(x) δ(x) x j Pr[X j = x j ] = ˆx p e p e := 1 n j [1,n] { 1 ϵ (xj = 0) 0 (x j 0) Pr[ ˆX j X j ] {0, 1} d l 2 d r = d k d l (d k 2) m = d l M n = d r M (d l, d r, M)- α α = m n = d l d r = 1 d k

8 Kudekar [11] (d l, d r, L, M)- (d l, d r, L, M)- d l d r = d k d l 1 (L 1 + d l ) d k L H(d l, d r, L) H(5, 10, 7) H(5, 10, 7) = M M 0 M M (L 1 + d l )M d k LM (d l, d r, L, M)- M n = d k LM m = (L + d l 1)M α α = m n = L + d l 1 d k L = 1 d k + d l 1 d k L (2.1) (d l, d r, M)- 1 d k L 1 d k 2.3 (Belief Propagation) x\{x j } x \ x j y = (x 1,..., x n ) A y = (y 1,..., y m ) y = (y 1,..., y m ) ˆx = (ˆx 1,..., ˆx n ) p(x j y) = d dx j Pr[X j x j Y = y] x j p e p(x j y) ˆx j = arg max x j R = arg max x j R p(x j y) R p(x y) dx \ x j

9 p(y x)p(x) p(x y) = p(y) x p(y) n p(y x) = 1[Ax = y] x j p(x) = p(x j ) ˆx j = arg max x j R p(x y) 1[Ax = y] R ( 1[Ax = y] n p(x j ) j=1 n k=1 j=1 ) p(x k ) dx \ x j (2.2) (2.2) sum-product sum-product sum-product A 2 n m A i,j = 1 j i [ j x j i ] 1 x j = y i j c(i) i i j j i c (i) c (i) := {j [1, n] A i,j = 1} j v (j) v (j) := {i [1, m] A i,j = 1} (2.2) ˆx j = arg max x j R R ( m i=1 [ 1 k c (i) ]) n x k = y i p(x k ) dx \ x j (2.3) k=1

10 p(x 1 ). 1 x 1 1. [ 1 j c (1) x j = y 1 ] p(x j ) p(x n ). j x j n x n A i. m [ 1 j c (i) [ 1 j c (m) x j = y i ] x j = y m ] 2.1: A A (2.3) (2.3) l (l 1) j i µ (l) j i (x j) 1 j arg max p(x j y) k x j R j (j k) j p(x j ) µ (1) j i (x j) l 2 l 1 l (l 1) i j M (l) i j (x j) l l (l 1) j p (l) (x j y)

11 l j arg max p (l) (x j y) A t (arg max x j R ) p (l) (x j y) = y ˆx = t (arg max x j R ) p (l) (x j y) 1 x j R

12 : Input: y A Output: ˆx loop // l (l 1) foreach j [1, n] do if l = 1 then j µ (1) j i (x j) := (1 ϵ)δ(x j ) + ϵ p(x j ) else 2 j µ (l) j i (x j) := p(x j ) k v(j)\i M (l 1) k j (x j) foreach i [1, m] do i ( [ M (l) i j (x ] j) := 1 x h = y i R h c(i) foreach j [1, n] do j if j # arg max x j R p (l) (x j y) := i v (j) k c(i)\j M (l) i j (x j) ) µ (l) k i (x k) dx \ x j ) p (l) (x j y) = y then p (l) (x j y) = 1, A t (arg max x j R ˆx Aˆx = y ˆx output ˆx := t (arg max x j R ) p (l) (x j y)

13 [8,9,12 15] d X 1,..., X d ξ 0 X X d = ξ 0 d = 2 X 1 + X 2 q(x) p(x) (1 ϵ)δ(x) + ϵ p(x) ˆ q(x) = p(ξ)p(x ξ)dξ = (1 ϵ) 2 δ(x) + 2ϵ(1 ϵ) p(x) + ϵ 2 p 2 (x) ˆ ξ+η ξ 0 Pr[X = ξ] = lim p(x)dx = 0 η +0 ξ ˆ { ξ+η 0 (ξ 0) Pr[X 1 + X 2 = ξ] = lim q(x)dx = η +0 ξ ϵ 2 (ξ 0) d 3 2. d X 1,..., X d X X d = 0 X 1 = = X d = 0 [ ] J := {1,..., d} Pr X j = 0 j 0 J, X j0 = x j0 0 = 0 j J j J [ ] Pr X j = 0 j 0 J, X j0 = x j0 0 [ ] = Pr X j = X j0 j 0 J, X j0 = x j0 0 j J\j 0 [ ] = Pr X j = x j0 j 0 J, X j0 = x j0 0 j J\j 0 [ (a) ] = Pr X j = x j0 j J\j 0 (b) = 0 (a) 1 j J\j 0 X j X j0 (b)

14 d X 1,..., X d j 0 J 1, J 2 {1,..., d} ] Pr [X j0 = j J1 X j = j J2 X j j J1 X j = j J2 X j = 1 [ ] Pr X j = X j j J 1 J 2 \ j 0, X j 0 = 0 j J 1 j J 2 j J 1 [ ] Pr X j = X j j J 1 J 2 \ j 0, X j 0 j J 1 j J 2 [ ] = Pr X j = X j j J 1 J 2 \ j 0, X j 0 j J 1 \j 0 j J 2 \j 0 [ = Pr X j ] X j = X j1 j J 1 J 2 \ j 0, X j 0 j J 1 \{j 0,j } j J 2 \j 0 [ = Pr X j ] X j = x j 0 j J 1 \{j 0,j } j J 2 \j 0 = 0 4. J j 0 x j0 [ Pr X j0 = x 0 x ] X j = x 0, = 1 j J j J\j 0 X j = x 5. X 1,..., X d J := {1,..., d} j 0 x j0 [ Pr X j0 [λ, υ] j J \ j 0, X j [λ j, υ j ], ] X j = x = 1 j J λ := max (0, x ) υ j j J\j 0 υ := x λ j j J\j 0

15 X j0 = x j J\j 0 X j x j J\j 0 υ j x j J\j 0 X j x j J\j 0 λ j 6. x j0 x j0 Pr [ X j = λ j X j [λ j, υ j ], λ j = υ j ] = j i ˆx j j ˆx j s j λ j υ j 4 i σ i, d i, Λ i, Υ i 4 σ i y i ˆx j d i (2.7) (2.8) (2.9) i σ i d i ˆx j s j = 1 5 (2.5) ˆx j 6 (2.6) ˆx j s j = 1 2 (2.5) (2.6)

16 : - Input: y A Output: ˆx foreach j [1, n] do // j (ˆx j := 0, s j := 0, λ (0) j := 0, υ (0) j := max (y i)) i v (j) loop // l (l 1) foreach i [1, m] do // i ( (l) σ i := y i s j ˆx j, d (l) i := # c (i) Λ (l) i j c (i) := y i j c (i) j c (i) s j, υ (l 1) j, Υ (l) i := y i λ (l 1) ) j j c (i) (2.4) foreach j [1, n] s j = 0 do // j j (ˆxj := 0, s j := 0, λ (l) j := max(0, υ (l 1) j + max i v(j) (Λ (l) i )), υ (l) j := λ (l 1) j if λ (l) j := υ (l) j then + min (Υ (l) i ) ) (2.5) i v(j) (ˆx j := λ (l) j, s j := 1, λ (l+) j := ˆx j, υ (l+) j := ˆx j ) (2.6) else if i v (j), σ i = 0 then 0 (ˆx j := 0, s j := 1, λ (l+) j := ˆx j, υ (l+) j := ˆx j ) (2.7) else if i v (j), d i = 1 then 1 (ˆx j := σ i, s j := 1, λ (l+) j := ˆx j, υ (l+) j := ˆx j ) (2.8) else if h, i v (j), σ h = σ i then (ˆx j := σ i, s j := 1, λ (l+) j := ˆx j, υ (l+) j := ˆx j ) (2.9) if j [1,n] s j = n then ˆx output ˆx := t (ˆx j )

17 X j 0 < x min < x max x min, x max Pr [ X j [x min, x max ] X j 0 ] = 1 (3.1) x min x max 3.2 (3.1) Pr[X j x max X j x 1 ] = 1 (x max x 1 ) (3.2) Pr[X j x min X j x 2 ] = 1 (0 < x 2 x min ) (3.3) Pr[X j = 0 0 X j x 3 ] = 1 (0 < x 3 < x min ) (3.4) (3.2) (3.3) (3.4) 3 (3.5) (3.6) (3.7) 15

18 : - Input: y A x min x max Output: ˆx foreach j [1, n] do // j (ˆx j := 0, s j := 0, λ (0) j := 0, υ (0) j := x max ) loop // l (l 1) foreach i [1, m] do // i (2.4) foreach j [1, n] s j = 0 do // j j (2.5) if 0 < λ j < x min then 0 λ (l) j := x min (3.5) if υ j > x max then υ (l) j := x max (3.6) if λ (l) j = υ (l) j then (2.6) else if λ j = 0, υ j < 1 then (ˆx j := 0, s j := 1, λ (l+) j := ˆx j, υ (l+) j := ˆx j ) (3.7) if else if i v (j), σ i = 0 then 0 (2.7) else if i v (j), d i = 1 then 1 (2.8) else if h, i v (j), σ h = σ i then (2.9) s j = n then j [1,n] ˆx output ˆx := t (ˆx j )

19 [x min, x max ] p e r = x max x min { Xj U[x min, x max ] w.p. ϵ X j = 0 w.p. 1 ϵ (3.8) x j = x j x min f : x j x j { X j U[1, r] w.p. ϵ X j = 0 w.p. 1 ϵ (3.9) (3.9) x A y = Ax ˆx = (ˆx j) 3 4

20 : 3 Input: y A r Output: ˆx foreach j [1, n] do // j (ˆx j := 0, s j := 0, λ (0) j := 0, υ (0) j := r) loop // l (l 1) foreach i [1, m] do // i (2.4) foreach j [1, n] s j = 0 do // j j (2.5) if 0 < λ j < 1 then 0 1 λ (l) j := 1 if υ j > r then r υ (l) j := r if if λ (l) j = υ (l) j then (2.6) else if λ j = 0, υ j < 1 then 1 (3.7) else if i v (j), σ i = 0 then 0 (2.7) else if i v (j), d i = 1 then 1 (2.8) else if h, i v (j), σ h = σ i then (2.9) s j = n then j [1,n] ˆx output ˆx := t (ˆx j )

21 x min x max (3.8) X 3 (x min, x max ) X 3 (x min, x max ) A 3 p e 3(A, x min, x max ) 1 r (3.9) X 4 (r) X 4 (r) A 4 p e 4(A, r) x min A r > 1 x > 0 p e 3(A, x, rx) = p e 4(A, r) p e 3 r

22 G G = 4 i, h # ( c (i) c (h) ) 2 3 (2.9) # ( c (i) c (h) ) 1 G 6 α 0.5 d k d k = 2 ϵ ϵ := sup { ϵ lim M p e = 0 } ϵ M p e < 10 1 ϵ ϵ 4.1 r ϵ d l = 3, 4, r ϵ 2 r 3 r 2 ϵ n n = d l = 3 n n = d l = 3, 4, 5 (2.1) α = 0.51, 0.515, 0.52 d l α =

23 ϵ (3,6,100,10000) (4,8,100,10000) (5,10,100,10000) r 4.1: (d l, d r, L, M)- r-ϵ d l = 3, 4, (3,6,333334) (4,8,250000) (5,10,200000) ϵ r 4.2: (d l, d r, M)- r-ϵ d l = 3, 4, 5

24 d l = 5 ϵ d l 6 d l = d l = 3 ϵ d l = 5 d l = 3 ϵ d l = 5 ϵ (5,10,200,10000) (5,10,100,10000) (5,10,50,10000) (5,10,25,10000) (5,10,100,20000) (5,10,100,10000) (5,10,100,5000) (5,10,100,2500) G=6 G=8 G=10 pe ϵ ϵ ϵ 4.3: (5, 10, L, M)- ϵ-p e L = 25, 50, 100 M = G = 6 M = 2 500, 5 000, L = 100 G = 6 G = 6, 8, 10 L = 100 M = ϵ p e 0 p e < 0.3

25 L M G ϵ p e 4.3 L = 25, 50, 100, 200 (5, 10, L, )- (2.1) L 0.5 ϵ L 4.3 M = 2 500, 5 000, , (5, 10, 100, M)- n n = 5 000, , , n ϵ M ,8,10 (5, 10, 100, )- G G L = 100 M = G = (5, 10, 100, )- α = n O(n 2 ) O(n) 4.1 [6]

26 [6] x j x j R x j [0, + ) x j [0, x max ] α = 0.44 α = 0.52 α = 0.52 x j {0} [x min, + ) ϵ = 0.40 ϵ = 0.33 α = 0.52 ϵ = 0.36 ϵ = 0.36 x j {0} [x min, x max ] α = 0.52 r = 4 ϵ = 0.41 x j {0} [x min, x max ] α = 0.52 r = 2 ϵ = : α ϵ x max x min = r

27 [16] 25

28 26

29 [1] E. Candes and T. Tao, Decoding by linear programming, IEEE Trans. Inf. Theory, vol. 51, no. 12, pp , [2] Y. Kabashima, T. Wadayama, and T. Tanaka, A typical reconstruction limit for compressed sensing based on L p -norm minimization, Journal of Statistical Mechanics: Theory and Experiment, vol. 2009, no. 09, p. L09003, [3] D. L. Donoho, A. Maleki, and A. Montanari, Message-passing algorithms for compressed sensing, Proceedings of the National Academy of Sciences, vol. 106, no. 45, pp , abstract [4] D. L. Donoho and J. Tanner, Neighborliness of randomly projected simplices in high dimensions, Proceedings of the National Academy of Sciences, vol. 102, no. 27, pp , abstract [5] T. Tanaka, Mathematics of compressed sensing, IEICE ESS Fundamentals Review, vol. 4, no. 1, pp , [6] F. Krzakala, M. Mézard, F. Sausset, Y. F. Sun, and L. Zdeborová, Statisticalphysics-based reconstruction in compressed sensing, Phys. Rev. X, vol. 2, p , May [7] T. Wadayama, On random construction of a bipolar sensing matrix with compact representation, in Proc. IEEE Information Theory Workshop (ITW), 2009, pp [8] M. G. Luby and M. Mitzenmacher, Verification-based decoding for packetbased low-density parity-check codes, IEEE Trans. Inf. Theory, vol. 51, no. 1, pp , [9] F. Zhang and H. D. Pfister, List-message passing achieves capacity on the q- ary symmetric channel for large q, in Proc. IEEE Global Telecommunications Conference (GLOBECOM), 2007, pp

30 28 [10] S. Kudekar and H. D. Pfister, The effect of spatial coupling on compressive sensing, in Proc. Annual Allerton Conference on Communication, Control, and Computing (Allerton), 2010, pp [11] S. Kudekar, T. Richardson, and R. Urbanke, Threshold saturation via spatial coupling: Why convolutional LDPC ensembles perform so well over the BEC, IEEE Trans. Inf. Theory, vol. 57, no. 2, pp , [12] V. Chandar, D. Shah, and G. W. Wornell, A simple message-passing algorithm for compressed sensing, in Proc. IEEE International Symposium on Information Theory (ISIT), 2010, pp [13] F. Zhang and H. D. Pfister, Verification decoding of high-rate LDPC codes with applications in compressed sensing, IEEE Trans. Inf. Theory, vol. 58, no. 8, pp , [14] S. Sarvotham, D. Baron, and R. G. Baraniuk, Sudocodes - fast measurement and reconstruction of sparse signals, in Proc. IEEE International Symposium on Information Theory (ISIT), 2006, pp [15] X. Wu and Z. Yang, Verification-based interval-passing algorithm for compressed sensing, IEEE Signal Process. Lett., vol. 20, no. 10, pp , [16] Y. Eftekhari, A. Heidarzadeh, A. Banihashemi, and I. Lambadaris, Density evolution analysis of node-based verification-based algorithms in compressed sensing, IEEE Trans. Inf. Theory, vol. 58, no. 10, pp , 2012.

31 ,,,, 34 (SITA2011), pp , , MacKay-Neal,,