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

Save this PDF as:
 WORD  PNG  TXT  JPG

Size: px
Start display at page:

Download "25 11M15133 0.40 0.44 n O(n 2 ) O(n) 0.33 0.52 O(n) 0.36 0.52 O(n) 2 0.48 0.52"

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,,

.1.1.1 S H(S) T canonical distribution P (S) = e βh(s) Z(β) (1) β = (k B T ) 1 k B Z(β) = Tr S e βh(s) partition function free energy F = β 1 ln Z(β)

.1.1.1 S H(S) T canonical distribution P (S) = e βh(s) Z(β) (1) β = (k B T ) 1 k B Z(β) = Tr S e βh(s) partition function free energy F = β 1 ln Z(β) 58 1 HAL9000 Google Amazon SF 1 [1, ] 1 E-mail: kaba@dis.titech.ac.jp .1.1.1 S H(S) T canonical distribution P (S) = e βh(s) Z(β) (1) β = (k B T ) 1 k B Z(β) = Tr S e βh(s) partition function free energy

More information

4 4 2 RAW 4 4 4 (PCA) 4 4 4 4 RAW RAW [5] 4 RAW 4 Park [12] Park 2 RAW RAW 2 RAW y = Mx + n. (1) y RAW x RGB M CFA n.. R G B σr 2, σ2 G, σ2 B D n ( )

4 4 2 RAW 4 4 4 (PCA) 4 4 4 4 RAW RAW [5] 4 RAW 4 Park [12] Park 2 RAW RAW 2 RAW y = Mx + n. (1) y RAW x RGB M CFA n.. R G B σr 2, σ2 G, σ2 B D n ( ) RAW 4 E-mail: hakiyama@ok.ctrl.titech.ac.jp Abstract RAW RAW RAW RAW RAW 4 RAW RAW RAW 1 (CFA) CFA Bayer CFA [1] RAW CFA 1 2 [2, 3, 4, 5]. RAW RAW RAW RAW 3 [2, 3, 4, 5] (AWGN) [13, 14] RAW 2 RAW RAW RAW

More information

0 1-4. 1-5. (1) + b = b +, (2) b = b, (3) + 0 =, (4) 1 =, (5) ( + b) + c = + (b + c), (6) ( b) c = (b c), (7) (b + c) = b + c, (8) ( + b)c = c + bc (9

0 1-4. 1-5. (1) + b = b +, (2) b = b, (3) + 0 =, (4) 1 =, (5) ( + b) + c = + (b + c), (6) ( b) c = (b c), (7) (b + c) = b + c, (8) ( + b)c = c + bc (9 1-1. 1, 2, 3, 4, 5, 6, 7,, 100,, 1000, n, m m m n n 0 n, m m n 1-2. 0 m n m n 0 2 = 1.41421356 π = 3.141516 1-3. 1 0 1-4. 1-5. (1) + b = b +, (2) b = b, (3) + 0 =, (4) 1 =, (5) ( + b) + c = + (b + c),

More information

Claude E. Shannon Award SITA 6 28 7 3 2009 IEEE International Symposium on Information Theory (ISIT2009) (7 2 ) 2010 Shannon Award (Te Sun Han) SITA A

Claude E. Shannon Award SITA 6 28 7 3 2009 IEEE International Symposium on Information Theory (ISIT2009) (7 2 ) 2010 Shannon Award (Te Sun Han) SITA A No.71 2009 7 17 Claude E. Shannon Award...................................................................................................................................................................

More information

<4D6963726F736F667420576F7264202D204850835483938376838B8379815B83578B6594BB2D834A836F815B82D082C88C60202E646F63>

<4D6963726F736F667420576F7264202D204850835483938376838B8379815B83578B6594BB2D834A836F815B82D082C88C60202E646F63> 誤 り 訂 正 技 術 の 基 礎 サンプルページ この 本 の 定 価 判 型 などは, 以 下 の URL からご 覧 いただけます http://wwwmorikitacojp/books/mid/081731 このサンプルページの 内 容 は, 第 1 版 発 行 時 のものです http://wwwmorikitacojp/support/ e mail editor@morikitacojp

More information

Run-Based Trieから構成される 決定木の枝刈り法

Run-Based Trieから構成される  決定木の枝刈り法 Run-Based Trie 2 2 25 6 Run-Based Trie Simple Search Run-Based Trie Network A Network B Packet Router Packet Filtering Policy Rule Network A, K Network B Network C, D Action Permit Deny Permit Network

More information

(a) 1 (b) 3. Gilbert Pernicka[2] Treibitz Schechner[3] Narasimhan [4] Kim [5] Nayar [6] [7][8][9] 2. X X X [10] [11] L L t L s L = L t + L s

(a) 1 (b) 3. Gilbert Pernicka[2] Treibitz Schechner[3] Narasimhan [4] Kim [5] Nayar [6] [7][8][9] 2. X X X [10] [11] L L t L s L = L t + L s 1 1 1, Extraction of Transmitted Light using Parallel High-frequency Illumination Kenichiro Tanaka 1 Yasuhiro Mukaigawa 1 Yasushi Yagi 1 Abstract: We propose a new sharpening method of transmitted scene

More information

(Basic of Proability Theory). (Probability Spacees ad Radom Variables , (Expectatios, Meas) (Weak Law

(Basic of Proability Theory). (Probability Spacees ad Radom Variables , (Expectatios, Meas) (Weak Law I (Radom Walks ad Percolatios) 3 4 7 ( -2 ) (Preface),.,,,...,,.,,,,.,.,,.,,. (,.) (Basic of Proability Theory). (Probability Spacees ad Radom Variables...............2, (Expectatios, Meas).............................

More information

2 1,384,000 2,000,000 1,296,211 1,793,925 38,000 54,500 27,804 43,187 41,000 60,000 31,776 49,017 8,781 18,663 25,000 35,300 3 4 5 6 1,296,211 1,793,925 27,804 43,187 1,275,648 1,753,306 29,387 43,025

More information

¿¸µLDPCÉä¹æ¤È¤½¤Î±þÍÑ

¿¸µLDPCÉä¹æ¤È¤½¤Î±þÍÑ LDPC 2010 9 21 1 / 51 LDPC LDPC LDPC 2 LDPC 2 / 51 Irregular LDPC Codes (λ(x), ρ(x)) Polar Codes Spatially Coupled Regular LDPC Codes 2 3 / 51 [ 08 Polyanskiy and Poor] log M (n, P B ) = nc(ɛ) nv (ɛ)q

More information

untitled

untitled 3,,, 2 3.1 3.1.1,, A4 1mm 10 1, 21.06cm, 21.06cm?, 10 1,,,, i),, ),, ),, x best ± δx 1) ii), x best ), δx, e,, e =1.602176462 ± 0.000000063) 10 19 [C] 2) i) ii), 1) x best δx

More information

(4) ω t(x) = 1 ω min Ω ( (I C (y))) min 0 < ω < C A C = 1 (5) ω (5) t transmission map tmap 1 4(a) 2. 3 2. 2 t 4(a) t tmap RGB 2 (a) RGB (A), (B), (C)

(4) ω t(x) = 1 ω min Ω ( (I C (y))) min 0 < ω < C A C = 1 (5) ω (5) t transmission map tmap 1 4(a) 2. 3 2. 2 t 4(a) t tmap RGB 2 (a) RGB (A), (B), (C) (MIRU2011) 2011 7 890 0065 1 21 40 105-6691 1 1 1 731 3194 3 4 1 338 8570 255 346 8524 1836 1 E-mail: {fukumoto,kawasaki}@ibe.kagoshima-u.ac.jp, ryo-f@hiroshima-cu.ac.jp, fukuda@cv.ics.saitama-u.ac.jp,

More information

The Empirical Study on New Product Concept of the Dish Washer Abstract

The Empirical Study on New Product Concept of the Dish Washer Abstract The Empirical Study on New Product Concept of the Dish Washer Abstract t t Cluster Analysis For Applications International Conference on Quality 96 in Yokohama Clustering Algorithms

More information

EndoPaper.pdf

EndoPaper.pdf Research on Nonlinear Oscillation in the Field of Electrical, Electronics, and Communication Engineering Tetsuro ENDO.,.,, (NLP), 1. 3. (1973 ),. (, ),..., 191, 1970,. 191 1967,,, 196 1967,,. 1967 1. 1988

More information

untitled

untitled K-Means 1 5 2 K-Means 7 2.1 K-Means.............................. 7 2.2 K-Means.......................... 8 2.3................... 9 3 K-Means 11 3.1.................................. 11 3.2..................................

More information

1 -- 9 -- 3 3--1 LMS NLMS 2009 2 LMS Least Mean Square LMS Normalized LMS NLMS 3--1--1 3 1 AD 3 1 h(n) y(n) d(n) FIR w(n) n = 0, 1,, N 1 N N = 2 3--1-

1 -- 9 -- 3 3--1 LMS NLMS 2009 2 LMS Least Mean Square LMS Normalized LMS NLMS 3--1--1 3 1 AD 3 1 h(n) y(n) d(n) FIR w(n) n = 0, 1,, N 1 N N = 2 3--1- 1 -- 9 3 2009 2 LMS NLMS RLS FIR IIR 3-1 3-2 3-3 3-4 c 2011 1/(13) 1 -- 9 -- 3 3--1 LMS NLMS 2009 2 LMS Least Mean Square LMS Normalized LMS NLMS 3--1--1 3 1 AD 3 1 h(n) y(n) d(n) FIR w(n) n = 0, 1,, N

More information

形状変形による古文書画像のシームレス合成

形状変形による古文書画像のシームレス合成 Use of Shape Deformation to Seamlessly Stitch Historical Document Images Wei Liu Wei Fan Li Chen Sun Jun あらまし 1 2 Abstract In China, efforts are being made to preserve historical documents in the form

More information

1 1 ( ) ( 1.1 1.1.1 60% mm 100 100 60 60% 1.1.2 A B A B A 1

1 1 ( ) ( 1.1 1.1.1 60% mm 100 100 60 60% 1.1.2 A B A B A 1 1 21 10 5 1 E-mail: qliu@res.otaru-uc.ac.jp 1 1 ( ) ( 1.1 1.1.1 60% mm 100 100 60 60% 1.1.2 A B A B A 1 B 1.1.3 boy W ID 1 2 3 DI DII DIII OL OL 1.1.4 2 1.1.5 1.1.6 1.1.7 1.1.8 1.2 1.2.1 1. 2. 3 1.2.2

More information

(Basics of Proability Theory). (Probability Spacees ad Radom Variables,, (Ω, F, P ),, X,. (Ω, F, P ) (probability space) Ω ( ω Ω ) F ( 2 Ω ) Ω σ (σ-fi

(Basics of Proability Theory). (Probability Spacees ad Radom Variables,, (Ω, F, P ),, X,. (Ω, F, P ) (probability space) Ω ( ω Ω ) F ( 2 Ω ) Ω σ (σ-fi I (Basics of Probability Theory ad Radom Walks) 25 4 5 ( 4 ) (Preface),.,,,.,,,...,,.,.,,.,,. (,.) (Basics of Proability Theory). (Probability Spacees ad Radom Variables...............2, (Expectatios,

More information

106 4 4.1 1 25.1 25.4 20.4 17.9 21.2 23.1 26.2 1 24 12 14 18 36 42 24 10 5 15 120 30 15 20 10 25 35 20 18 30 12 4.1 7 min. z = 602.5x 1 + 305.0x 2 + 2

106 4 4.1 1 25.1 25.4 20.4 17.9 21.2 23.1 26.2 1 24 12 14 18 36 42 24 10 5 15 120 30 15 20 10 25 35 20 18 30 12 4.1 7 min. z = 602.5x 1 + 305.0x 2 + 2 105 4 0 1? 1 LP 0 1 4.1 4.1.1 (intger programming problem) 1 0.5 x 1 = 447.7 448 / / 2 1.1.2 1. 2. 1000 3. 40 4. 20 106 4 4.1 1 25.1 25.4 20.4 17.9 21.2 23.1 26.2 1 24 12 14 18 36 42 24 10 5 15 120 30

More information

(Basics of Proability Theory). (Probability Spacees ad Radom Variables,, (Ω, F, P ),, X,. (Ω, F, P ) (probability space) Ω ( ω Ω ) F ( 2 Ω ) Ω σ (σ-fi

(Basics of Proability Theory). (Probability Spacees ad Radom Variables,, (Ω, F, P ),, X,. (Ω, F, P ) (probability space) Ω ( ω Ω ) F ( 2 Ω ) Ω σ (σ-fi II (Basics of Probability Theory ad Radom Walks) (Preface),.,,,.,,,...,,.,.,,.,,. (Basics of Proability Theory). (Probability Spacees ad Radom Variables...............2, (Expectatios, Meas).............................

More information

ii

ii I05-010 : 19 1 ii k + 1 2 DS 198 20 32 1 1 iii ii iv v vi 1 1 2 2 3 3 3.1.................................... 3 3.2............................. 4 3.3.............................. 6 3.4.......................................

More information

05-5.dvi

05-5.dvi 131 71 71 71 71 71 71 71 7 1 71 71 71 71 71 7 1 71 71 71 71 71 71 7 1 71 71 71 71 71 71 71 71 7 1 1 71 71 71 71 71 71 71 71 71 7 1 75(468) 1 71 71 7 517.95 1 7.1 7. 1 71 71 71 71 71 71 71 7, 1 7.1 7. 1

More information

Web 1 q q 2 1 2 Step1) Twitter Step2) (w i, w j ) S(w i, w j ) Step3) q 2 2 2.1 I Twitter MeCab[6] URL http:// @ 2.2 (w i, w j ) S(w i, w j ) I w i w

Web 1 q q 2 1 2 Step1) Twitter Step2) (w i, w j ) S(w i, w j ) Step3) q 2 2 2.1 I Twitter MeCab[6] URL http:// @ 2.2 (w i, w j ) S(w i, w j ) I w i w ARG WI2 No.6, 2015 a b b 565-0871 2-1 a) yoshitake@nanase.comm.eng.osaka-u.ac.jp b) {naoko, babaguchi}@comm.eng.osaka-u.ac.jp 1 Citizen Sensor [1] Twitter 140 Twitter Sakaki [2] [3] Massoudi [4] [5] Copyright

More information

JAPAN MARKETING JOURNAL 110 Vol.28 No.22008

JAPAN MARKETING JOURNAL 110 Vol.28 No.22008 JAPAN MARKETING JOURNAL 110 Vol.28 No.22008 JAPAN MARKETING JOURNAL 110 Vol.28 No.22008 JAPAN MARKETING JOURNAL 110 Vol.28 No.22008 JAPAN MARKETING JOURNAL 110 Vol.28 No.22008 JAPAN MARKETING JOURNAL 110

More information

JAPAN MARKETING JOURNAL 123 Vol.31 No.32012

JAPAN MARKETING JOURNAL 123 Vol.31 No.32012 Japan Marketing Academy JAPAN MARKETING JOURNAL 123 Vol.31 No.32012 JAPAN MARKETING JOURNAL 123 Vol.31 No.32012 JAPAN MARKETING JOURNAL 123 Vol.31 No.32012 JAPAN MARKETING JOURNAL 123 Vol.31 No.32012 JAPAN

More information

JAPAN MARKETING JOURNAL 115 Vol.29 No.32010

JAPAN MARKETING JOURNAL 115 Vol.29 No.32010 Japan Marketing Academy JAPAN MARKETING JOURNAL 115 Vol.29 No.32010 JAPAN MARKETING JOURNAL 115 Vol.29 No.32010 JAPAN MARKETING JOURNAL 115 Vol.29 No.32010 JAPAN MARKETING JOURNAL 115 Vol.29 No.32010 JAPAN

More information

(1970) 17) V. Kucera: A Contribution to Matrix Ouadratic Equations, IEEE Trans. on Automatic Control, AC- 17-3, 344/347 (1972) 18) V. Kucera: On Nonnegative Definite Solutions to Matrix Ouadratic Equations,

More information

α = 2 2 α 2 = ( 2) 2 = 2 x = α, y = 2 x, y X 0, X 1.X 2,... x 0 X 0, x 1 X 1, x 2 X 2.. Zorn A, B A B A B A B A B B A A B N 2

α = 2 2 α 2 = ( 2) 2 = 2 x = α, y = 2 x, y X 0, X 1.X 2,... x 0 X 0, x 1 X 1, x 2 X 2.. Zorn A, B A B A B A B A B B A A B N 2 1. 2. 3. 4. 5. 6. 7. 8. N Z 9. Z Q 10. Q R 2 1. 2. 3. 4. Zorn 5. 6. 7. 8. 9. x x x y x, y α = 2 2 α x = y = 2 1 α = 2 2 α 2 = ( 2) 2 = 2 x = α, y = 2 x, y X 0, X 1.X 2,... x 0 X 0, x 1 X 1, x 2 X 2.. Zorn

More information

.......p...{..P01-48(TF)

.......p...{..P01-48(TF) 1 2 3 5 6 7 8 9 10 Act Plan Check Act Do Plan Check Do 11 12 13 14 INPUT OUTPUT 16 17 18 19 20 21 22 23 24 25 26 27 30 33 32 33 34 35 36 37 36 37 38 33 40 41 42 43 44 45 46 47 48 49 50 51 1. 2. 3.

More information

核融合…予稿集

核融合…予稿集 9:30 9:45 9:45 10:00 10:05 10:10 10:10 10:40 2 3 10:40 11:10 11:10 11:40 11:40 12:00 6 7 8 9 10 11 13:10 13:20 13:20 14:00 14:00 14:20 14:20 14:40 14:50 15:20 15:20 15:50 15:50 15:55 14 15 16 17 18 19

More information

[1], B0TB2053, 20014 3 31. i

[1], B0TB2053, 20014 3 31. i B0TB2053 20014 3 31 [1], B0TB2053, 20014 3 31. i 1 1 2 3 2.1........................ 3 2.2........................... 3 2.3............................. 4 2.3.1..................... 4 2.3.2....................

More information

‚åŁÎ“·„´Šš‡ðŠp‡¢‡½‹âfi`fiI…A…‰…S…−…Y…•‡ÌMarkovŸA“½fiI›ð’Í

‚åŁÎ“·„´Šš‡ðŠp‡¢‡½‹âfi`fiI…A…‰…S…−…Y…•‡ÌMarkovŸA“½fiI›ð’Í Markov 2009 10 2 Markov 2009 10 2 1 / 25 1 (GA) 2 GA 3 4 Markov 2009 10 2 2 / 25 (GA) (GA) L ( 1) I := {0, 1} L f : I (0, ) M( 2) S := I M GA (GA) f (i) i I Markov 2009 10 2 3 / 25 (GA) ρ(i, j), i, j I

More information

Abstract Gale-Shapley 2 (1) 2 (2) (1)

Abstract Gale-Shapley 2 (1) 2 (2) (1) ( ) 2011 3 Abstract Gale-Shapley 2 (1) 2 (2) (1) 1 1 1.1........................................... 1 1.2......................................... 2 2 4 2.1................................... 4 2.1.1 Gale-Shapley..........................

More information

光学

光学 Fundamentals of Projector-Camera Systems and Their Calibration Methods Takayuki OKATANI To make the images projected by projector s appear as desired, it is e ective and sometimes an only choice to capture

More information

(2 X Poisso P (λ ϕ X (t = E[e itx ] = k= itk λk e k! e λ = (e it λ k e λ = e eitλ e λ = e λ(eit 1. k! k= 6.7 X N(, 1 ϕ X (t = e 1 2 t2 : Cauchy ϕ X (t

(2 X Poisso P (λ ϕ X (t = E[e itx ] = k= itk λk e k! e λ = (e it λ k e λ = e eitλ e λ = e λ(eit 1. k! k= 6.7 X N(, 1 ϕ X (t = e 1 2 t2 : Cauchy ϕ X (t 6 6.1 6.1 (1 Z ( X = e Z, Y = Im Z ( Z = X + iy, i = 1 (2 Z E[ e Z ] < E[ Im Z ] < Z E[Z] = E[e Z] + ie[im Z] 6.2 Z E[Z] E[ Z ] : E[ Z ] < e Z Z, Im Z Z E[Z] α = E[Z], Z = Z Z 1 {Z } E[Z] = α = α [ α ]

More information

example2_time.eps

example2_time.eps Google (20/08/2 ) ( ) Random Walk & Google Page Rank Agora on Aug. 20 / 67 Introduction ( ) Random Walk & Google Page Rank Agora on Aug. 20 2 / 67 Introduction Google ( ) Random Walk & Google Page Rank

More information

Note5.dvi

Note5.dvi 12 2011 7 4 2.2.2 Feynman ( ) S M N S M + N S Ai Ao t ij (i Ai, j Ao) N M G = 2e2 t ij 2 (8.28) h i μ 1 μ 2 J 12 J 12 / μ 2 μ 1 (8.28) S S (8.28) (8.28) 2 ( ) (collapse) j 12-1 2.3 2.3.1 Onsager S B S(B)

More information

xx/xx Vol. Jxx A No. xx 1 Fig. 1 PAL(Panoramic Annular Lens) PAL(Panoramic Annular Lens) PAL (2) PAL PAL 2 PAL 3 2 PAL 1 PAL 3 PAL PAL 2. 1 PAL

xx/xx Vol. Jxx A No. xx 1 Fig. 1 PAL(Panoramic Annular Lens) PAL(Panoramic Annular Lens) PAL (2) PAL PAL 2 PAL 3 2 PAL 1 PAL 3 PAL PAL 2. 1 PAL PAL On the Precision of 3D Measurement by Stereo PAL Images Hiroyuki HASE,HirofumiKAWAI,FrankEKPAR, Masaaki YONEDA,andJien KATO PAL 3 PAL Panoramic Annular Lens 1985 Greguss PAL 1 PAL PAL 2 3 2 PAL DP

More information

Taro13-第6章(まとめ).PDF

Taro13-第6章(まとめ).PDF % % % % % % % % 31 NO 1 52,422 10,431 19.9 10,431 19.9 1,380 2.6 1,039 2.0 33,859 64.6 5,713 10.9 2 8,292 1,591 19.2 1,591 19.2 1,827 22.0 1,782 21.5 1,431 17.3 1,661 20.0 3 1,948 1,541 79.1 1,541 79.1

More information

Accuracy Improvement by Compound Discriminant Functions for Resembling Character Recognition Takashi NAKAJIMA, Tetsushi WAKABAYASHI, Fumitaka KIMURA,

Accuracy Improvement by Compound Discriminant Functions for Resembling Character Recognition Takashi NAKAJIMA, Tetsushi WAKABAYASHI, Fumitaka KIMURA, Journal Article / 学 術 雑 誌 論 文 混 合 識 別 関 数 による 類 似 文 字 認 識 の 高 精 度 化 Accuracy improvement by compoun for resembling character recogn 中 嶋, 孝 ; 若 林, 哲 史 ; 木 村, 文 隆 ; 三 宅, 康 二 Nakajima, Takashi; Wakabayashi,

More information

aisatu.pdf

aisatu.pdf 1 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71

More information

IDRstab(s, L) GBiCGSTAB(s, L) 2. AC-GBiCGSTAB(s, L) Ax = b (1) A R n n x R n b R n 2.1 IDR s L r k+1 r k+1 = b Ax k+1 IDR(s) r k+1 = (I ω k A)(r k dr

IDRstab(s, L) GBiCGSTAB(s, L) 2. AC-GBiCGSTAB(s, L) Ax = b (1) A R n n x R n b R n 2.1 IDR s L r k+1 r k+1 = b Ax k+1 IDR(s) r k+1 = (I ω k A)(r k dr 1 2 IDR(s) GBiCGSTAB(s, L) IDR(s) IDRstab(s, L) GBiCGSTAB(s, L) Verification of effectiveness of Auto-Correction technique applied to preconditioned iterative methods Keiichi Murakami 1 Seiji Fujino 2

More information

2004 Copyright by Tatsuo Minohara Programming with Mac OS X in Lambda 21 - page 2

2004 Copyright by Tatsuo Minohara Programming with Mac OS X in Lambda 21 - page 2 Living with Mac OS X in Lambda 21 2004 Copyright by Tatsuo Minohara Programming with Mac OS X in Lambda 21 - page 1 2004 Copyright by Tatsuo Minohara Programming with Mac OS X in Lambda 21 - page 2 2004

More information

MacOSXLambdaJava.aw

MacOSXLambdaJava.aw Living with Mac OS X in Lambda 21 2005 Copyright by Tatsuo Minohara Programming with Mac OS X in Lambda 21 - page 1 2005 Copyright by Tatsuo Minohara Programming with Mac OS X in Lambda 21 - page 2 2005

More information

第85 回日本感染症学会総会学術集会後抄録(III)

第85 回日本感染症学会総会学術集会後抄録(III) β β α α α µ µ µ µ α α α α γ αβ α γ α α γ α γ µ µ β β β β β β β β β µ β α µ µ µ β β µ µ µ µ µ µ γ γ γ γ γ γ µ α β γ β β µ µ µ µ µ β β µ β β µ α β β µ µµ β µ µ µ µ µ µ λ µ µ β µ µ µ µ µ µ µ µ

More information

3 3 i

3 3 i 00D8102021I 2004 3 3 3 i 1 ------------------------------------------------------------------------------------------------1 2 ---------------------------------------------------------------------------------------2

More information

技術の系統化調査報告「プロセス制御システムの技術系統化調査」

技術の系統化調査報告「プロセス制御システムの技術系統化調査」 A Technical Survey of Process Control Systems 3 Yutaka Wakasa Abstract Yutaka Wakasa 95 1 2 96 Vol.11 2008.March 2.1 2.2 97 98 Vol.11 2008.March 99 3 3.1 3.2 3.3 100 Vol.11 2008.March 101 3.4 102 Vol.11

More information

Kumagai09-hi-2.indd

Kumagai09-hi-2.indd CSR2009 CONTENTS 1 2 3 4 5 6 7 8 9 10 350 11 12 13 14 15 16 17 18 Do Check Action Plan 19 20 INPUT r r r r k k OUTPUT 21 22 Plan Action Check Do 23 24 25 26 27 28 16:50 7:30 8:00 8:30 9:30 10:00 18:00

More information

地域総合研究第40巻第1号

地域総合研究第40巻第1号 * abstract This paper attempts to show a method to estimate joint distribution for income and age with copula function. Further, we estimate the joint distribution from National Survey of Family Income

More information

Grund.dvi

Grund.dvi 24 24 23 411M133 i 1 1 1.1........................................ 1 2 4 2.1...................................... 4 2.2.................................. 6 2.2.1........................... 6 2.2.2 viterbi...........................

More information

3 2 2 (1) (2) (3) (4) 4 4 AdaBoost 2. [11] Onishi&Yoda [8] Iwashita&Stoica [5] 4 [3] 3. 3 (1) (2) (3)

3 2 2 (1) (2) (3) (4) 4 4 AdaBoost 2. [11] Onishi&Yoda [8] Iwashita&Stoica [5] 4 [3] 3. 3 (1) (2) (3) (MIRU2012) 2012 8 820-8502 680-4 E-mail: {d kouno,shimada,endo}@pluto.ai.kyutech.ac.jp (1) (2) (3) (4) 4 AdaBoost 1. Kanade [6] CLAFIC [12] EigenFace [10] 1 1 2 1 [7] 3 2 2 (1) (2) (3) (4) 4 4 AdaBoost

More information

1., 1 COOKPAD 2, Web.,,,,,,.,, [1]., 5.,, [2].,,.,.,, 5, [3].,,,.,, [4], 33,.,,.,,.. 2.,, 3.., 4., 5., ,. 1.,,., 2.,. 1,,

1., 1 COOKPAD 2, Web.,,,,,,.,, [1]., 5.,, [2].,,.,.,, 5, [3].,,,.,, [4], 33,.,,.,,.. 2.,, 3.., 4., 5., ,. 1.,,., 2.,. 1,, THE INSTITUTE OF ELECTRONICS, INFORMATION AND COMMUNICATION ENGINEERS TECHNICAL REPORT OF IEICE.,, 464 8601 470 0393 101 464 8601 E-mail: matsunagah@murase.m.is.nagoya-u.ac.jp, {ide,murase,hirayama}@is.nagoya-u.ac.jp,

More information

橡同居選択における所得の影響(DP原稿).PDF

橡同居選択における所得の影響(DP原稿).PDF ** *** * 2000 13 ** *** (1) (2) (1986) - 1 - - 2 - (1986) Ohtake (1991) (1993) (1994) (1996) (1997) (1997) Hayashi (1997) (1999) 60 Ohtake (1991) 86 (1996) 89 (1997) 92 (1999) 95 (1993) 86 89 74 79 (1986)

More information

June 2016 i (statistics) F Excel Numbers, OpenOffice/LibreOffice Calc ii *1 VAR STDEV 1 SPSS SAS R *2 R R R R *1 Excel, Numbers, Microsoft Office, Apple iwork, *2 R GNU GNU R iii URL http://ruby.kyoto-wu.ac.jp/statistics/training/

More information

main.dvi

main.dvi 305 8550 1 2 CREST fujii@slis.tsukuba.ac.jp 1 7% 2 2 3 PRIME Multi-lingual Information Retrieval 2 2.1 Cross-Language Information Retrieval CLIR 1990 CD-ROM a. b. c. d. b CLIR b 70% CLIR CLIR 2.2 (b) 2

More information