1 SVD 1.1 SVD SVD SVD 3 I J A A = UD α V (A.1.1) D α α 1... α K K A (K min(i, J)) U, V I K, J K ( ) U U = V V = I :

Size: px

Start display at page:

Download "1 SVD 1.1 SVD SVD SVD 3 I J A A = UD α V (A.1.1) D α α 1... α K K A (K min(i, J)) U, V I K, J K ( ) U U = V V = I :"

ありかつやぶき
5 years ago
Views:

1 (SVD) Greenacare, M.J. (SVD) 1870 ( Marchall&Olkin, ) Psychometrika Eckart&Young(1936) Eckart-Young (Horst,1963; Green&Carroll,1976 pp ) (Eckart&Young,1936;Johnson,1963) (Good,1969;Kshirsagar,1972) (Benzécri et al., 1973) (2.1, 2.2 ) ( ) SVD SVD SVD SVD SVD SVD SVD Good(1969), Chambers(1977), Gabriel(1978), Rao(1989), Mandel(1982), Greenacre&Underhill(1982) : Greenacre, M.J.(1984) Theory and Applications of Correspondence Analysis. Academic Press. Appendix A: Singlar Value Decomposition (SVD) and Multidimensional Analysis. PDF (2011/01/21 ) (2014/09/23 ) R Clausen( ), ( ) ( ) (...) (2016/05/17 ) (2016/05/19 ) R (2018/05/09 ) 1

2 1 SVD 1.1 SVD SVD SVD 3 I J A A = UD α V (A.1.1) D α α 1... α K K A (K min(i, J)) U, V I K, J K ( ) U U = V V = I : = U... U U = = SVD K A = α k u k vk k=1 (A.1.2) u 1... u K v 1... v K U, V α k A u k v k A (k = 1... K) I A J A SVD 1 u k vk (k=1... K) K ( ) A α k u k vk 2

3 : = [ ] + SVD J J B K B = VD λ V = λ k v k vk k=1 K B (K J) V J K B SVD SVD A SVD B B A A = VD λ V A SVD A = UD α V V B Dα = D 1/2 λ (cf. Mardia et.al., 1979, pp ) SVD (Greenacre, 1978, Appendix A.) SVD SVD Greenacre(1978, Appendix A.) B λ x Bx = λx A Av = αu A u = αv α u, v ( α, u, v ) u, v (u u = v v) ( 1 ) u, v 1.2 SVD (α 1 α 2... α K > 0) ( ) reflection SVD 2 3

4 α k = α k+1 2 (cf. Section 8.1) 1.3 SVD U V Ũ [u 1... u K... u I ] Ṽ [v 1... v K... v I ] u K+1... u I u 1... u K Ũ Ũ = I Ṽ Ṽ = I SVD : A = Ũ Ṽ (A.1.3) [ Dα O O O ] A SVD (Green & Carroll, 1976, p.234 ) U, V SVD (cf. Kshirsagar, 1972, pp ) : ? ? = ? ? [ ] Ũ 4 u (A.1.2) SVD α K α K α 1... α K, (A.1.2) K K A A SVD Eckart&Young(1936) A [K ] A K K I J A [K ] K k=1 α ku k vk A [K ] 4

5 K X I i J (a ij x ij ) 2 = trace{(a X)(A X) } (A.1.4) j A [K ] A K K = A [2] = [ ] [ ] = A ( : Kshirsagar, 1972, pp ; Stewart, 1973) A SVD(A.1.3) (A.1.4) : trace{ũũ (A X)ṼṼ (A X) } = trace{( G)( G) } = K (α k g kk ) 2 + k K K k l k g 2 kl G I J G Ũ X T G X G α 1... α K 0 X = A [K ] U, D α, V U [U (K ) U (K K )] [ Dα(K ) O D α O D α(k K ) ] V [V (K ) V (K K )] I K U (K ) K K D α(k ) J K V (K ) 3 A [K ] SVD : A [K ] = U (K )D α(k )V (K ) (A.1.5) A A [K ] = U (K K )D α(k K )V (K K ) (A.1.6) Y trace(yy ) (A.1.1), (A.1.5), (A.1.6) 5

6 A K k α2 k A [K ] K k α 2 k A A [K ] K k=k +1 α2 k : K k τ K 100 α 2 k K k α2 k (A.1.7) α 2 1 = 642.4, α 2 2 = 4.6, α 2 3 = 2.9, 650( A ) τ 2 = SVD SVD SVD Ω (I I), Φ (J J) A (I J, K) : K A = ND α M = α k n k m k (A.1.8) N, M Ω, Φ : k N ΩN = M ΦM = I (A.1.9) N M A I J Ω, Φ ( ) (Section 2.3 ) D α ( ) SVD SVD Ω 1/2 AΦ 1/2 SVD (Ω Ω = WD µ W Ω 1/2 = WD 1/2 µ W ) Ω 1/2 AΦ 1/2 = UD α V, U U = V V = I N Ω 1/2 U M Φ 1/2 V (A.1.10) (A.1.11) (A.1.8) (A.1.9) 6

7 A SVD 1. B = Ω 1/2 AΦ 1/2 2. B SVD B = UD α V 3. N = Ω 1/2 U, M = Φ 1/2 V 4. A = ND α M A SVD Ω Ω = , Φ = I B = Ω 1/2 AΦ 1/2 = = A Ω Φ 3 SVD (A.1.8) K K A [K ] K k α k n k m k = N (K )D α(k )M α(k ) A K K ( ) X trace{ω(a X)Φ(A X) } (A.1.12) SVD (A.1.12) : Ω ω 1... ω I D ω I trace{d ω (A X)Φ(A X) } = ω i (a i x i ) Φ(a i x i ) (A.1.13) a i, x i A, X Pearson(1901), Young(1937) (Section 2.5 ) A I J ( ) I Φ (Section 2.5 Φ ) ω 1... ω I X K X A [K ] (A.1.13) A I i 7

8 m 1... m K N (K )D α(k ) = [α 1 n 1... α K n K ] ( ) Φ A [K ] M (K ) α K α K +1 ( SVD ). K α K α K +1 SVD F N (K )D α(k ) K (K 2 3) A Gabriel(1971, 1981) G M (K ) Tucker(1960) i ( F i fi ) j ( G j g ) a ij : a ij f i g j = (f i ) (g j ) (f i g j cosine) (A.1.14) a ij ( ) a ij > 0 f i, g j a ij < 0 8

9 2 Y 1 Y A 2 Ω, Φ A SVD ((A.1.10), (A.1.11) ): A = ND α M, N ΩN = M ΦM = I K : A [K ] = N (K )D α(k )M (K ) 3 ( ) a b F N (K )D a α(k ) G M (K )D b α(k ) K / / : 1. 1 / 2. 2 Ω, Φ 3. a, b A.1 A.1 A.1 1. (, b = 0) 2. a + b = 1 fi g j A a ij 9

10 3. b = 0 (a = 1 ) a = b 4. ( F ) (Y A ) SAS GENSTAT (Appendix B ) 5. (4) (5) (I 1) 1/2 MD 2 αm Y (1/I)11 Y (I 1) 1/2 = ND α M {Y (1/I)11 Y} {Y (1/I)11 Y} (I 1) G M (K )D α(k ) (Gabriel, 1971) 6. (2) (3) (i) (ii) 7. Ω, Φ (9) F A = D 1 r P 11 D c, Ω = D r, Φ = D 1 c, a = 1 P A D r ( (2)) (Section 2.5 ) G A = D 1 c P II D r, Ω = D c, Φ = D 1 r, b = 1 4 a, b ( 0 ) a = 0, b = 0 ( ) 2.1 A.1 (Gower, 1966) S ( 2.6.1(b) ) : S = ND µ N ND ω N = I D ω ( ) K F N (K )D 1/2 µ(k ) SVD 10

11 (Section 2.5 Appendix B ) D 1/2 ω SD 1/2 ω N = D 1/2 ω U a ij w ij A Gabriel & Zamir(1979) 1. w ij = 0 2. w ij 3. w ik = s i t j A SVD 11

12 A.1 SVD R1... R4, C1... C3 (1)(2)(3)(4)(5) 1 Y (1/I)11 Y Y (1/I)11 Y = (1/4) = = Y =

13 (1) ( ) Y 1 A = Y (1/I)11 Y 2 Ω = (1/I)I, Φ = I 3 a = 1, b = 0 J ( ) K G Pearson(1901) Hotelling(1933) (Bryant&Atchley(1975) 2 ); Morrison(1976); Gabriel(1971); Kendall(1975); Chambers(1977) A = Ω = (1/I)I, Φ = I SVD A = SVD D α 1/ I N I K = 3 F, G F = N (3) D α(3) = G = M (3) = F Ω = I, Φ = I G Ω = (1/I)I SVD Ω = I, Φ = I SVD ( SVD) F = ND α, G = M D α 13

14 第二主成分 C R1 R2 R3 C2 R C 第 1 主成分 10 14

15 R SVD SVD > Y <- matrix(c(1,2,3,6,4,5,8,9,7,10,11,12), ncol=3, byrow=true) > A <- scale(y, center = TRUE, scale = FALSE) > osvd <- svd(a) > osvd$u %*% diag(osvd$d) [,1] [,2] [,3] [1,] [2,] [3,] [4,] > osvd$v [,1] [,2] [,3] [1,] e [2,] e [3,] e

16 R stats prcomp sdev D α I/(I 1) F SD SAS SPSS rotation G x F > Y <- matrix(c(1,2,3,6,4,5,8,9,7,10,11,12), ncol=3, byrow=true) > result <- prcomp(y) > result$sdev [1] > result$rotation PC1 PC2 PC3 [1,] e [2,] e [3,] e > result$x PC1 PC2 PC3 [1,] [2,] [3,] [4,] biplot(result, scale=0) scale (5) SAS proc princomp cov 2 Ω = (1/(I 1))I D α D α I/(I 1) G F SPSS factor method=covariance, extraction=pc SAS proc princomp D α I/(I 1) G F 16

17 (2) ( ) D ω ( 1) (i) : 1 A = Y (1/I)11 D ω Y 2 Ω = (1/I)D ω, Φ 3 a = 1, b = 0 (ii) : 1 A = {Y (1/I)11 D ω Y}Φ 1/2 2 Ω = (1/I)D ω, Φ = I 3 a = 1, b = 0 (1) Φ, D ω ω 1... ω I A (i) (ii) F G (3) (3), (7), (8), (9) D ω, Φ 17

18 (3) ( ) (i) : 1 D s A = Y (1/I)11 Y 2 Ω = I, Φ = D 2 s 3 a = 1, b = 0 (ii) : 1 2 A = {Y (1/I)11 Y}D 1 s Ω = I, Φ = I 3 a = 1, b = 0 (2) (ii) G (i) G = D s G (4) ( (ii)) 18

19 (4) 1 2 A = Y (1/I)11 Y (I 1) 1/2 Ω = I, Φ = I 3 a = 0, b = 1 J ( ) K Gabriel(1971,1972,1981) SVD A = A = Y (1/I)11 Y SVD D α 1/ I 1 K = 3 G = M (3) D α(3) = F = N (3) = = G Y (1/I)11 Y 1 G Y (1/I)11 Y

20 第 2 軸 R1 R4 C3 0 C2 C1-0.5 R2 R 第 1 軸

21 R 1 F, G > Y <- matrix(c(1,2,3,6,4,5,8,9,7,10,11,12), ncol=3, byrow=true) > X <- scale(y, scale=false) > A <- X / sqrt(3) > osvd <- svd(a) > osvd$u [,1] [,2] [,3] [1,] [2,] [3,] [4,] > osvd$v %*% diag(osvd$d) [,1] [,2] [,3] [1,] e [2,] e [3,] e

22 R 2 prcomp (1) prcomp SVD(Ω = Φ = I SVD) M, D α, N x I ND α rotation M sdev I/(I 1))(1/ I) D α = 1 I 1 D α M, D α, N N 1 I 1 MD α F, G > Y <- matrix(c(1,2,3,6,4,5,8,9,7,10,11,12), ncol=3, byrow=true) > result <- prcomp(y) > t(t(result$x)/ (result$sdev*sqrt(3))) PC1 PC2 PC3 [1,] [2,] [3,] [4,] > t(t(result$rotation) * result$sdev) PC1 PC2 PC3 [1,] e [2,] e [3,] e

23 R 3 biplot > Y <- matrix(c(1,2,3,6,4,5,8,9,7,10,11,12), ncol=3, byrow=true) > result <- prcomp(y) > biplot(result) PC Var 3 Var 2 Var PC1 result$x (1,2) result$sdev I 1 I F result$rotation (1,2) result$sdev IG biplot(result) 23

24 R 4 biplot pc.biplot=true > Y <- matrix(c(1,2,3,6,4,5,8,9,7,10,11,12), ncol=3, byrow=true) > result <- prcomp(y) > biplot(result, pc.biplot=true) PC Var 3 Var 2 Var PC1 pc.biplot=true result$x (1,2) result$sdev I 1F result$rotation (1,2) result$sdev G pc.biplot=true 24

25 WRC Research Systems Brandmap Y Data Centering Row Y Factorization G*(V*H ) SVD Y SVD Brandmap 1 I 1 Y ( ) I I Y ( ) 25

26 (5) D s 1 A = {Y (1/I)11 Y}D 1/2 s (I 1) 1/2 2 Ω = I, Φ = I 3 a = 0, b = 1 J 1 K ( 2 ) Hill(1969) A I A = SVD A = K = 3 G = M (3) D α(3) = F = N (3) = = G 4/3 = 1.2 4/3 1 I 1 I 26

27 R R scale() SD SD SD > Y <- matrix(c(1,2,3,6,4,5,8,9,7,10,11,12), ncol=3, byrow=true) > agsd <- sqrt(apply(y, 2, var) * (3/4)) > A <- scale(y, center = TRUE, scale = agsd) / sqrt(3) > osvd <- svd(a) > osvd$u [,1] [,2] [,3] [1,] [2,] [3,] [4,] > osvd$v %*% diag(osvd$d) [,1] [,2] [,3] [1,] e [2,] e [3,] e WRC Research Systems Brandmap Y Data Centering Row Data Standardization Row Factorization G*(V*H ) Brandmap 1 ( (I 1)/I ) Y ( ) I 1, I 1 Y ( ) 27

28 (6) ŷ 1 A = Y ŷ11 2 Ω = I, Φ = I 3 a = 1/2, b = 1/2 - Bradu & Gabriel(1978); Gabriel(1981) 28

29 (7) 1 I J Y Y 1 Y 2 Y ( ) S 11, S 22 S 12 A = S 1 11 S 12S Ω = S 11, Φ = S 22 3 a = 1, b = 1 F G ( ) ( Y 1 F Y 2 G ) 2 ( S 1 11, S 1 22 ) 2 K Anderson(1958); Tatsuoka(1971); Morrison(1976); Mardia et al.(1979); Falkenhagen & Nash(1978); Chambers(1977); Gittins(1979) 29

30 (8) Y H J H J Ȳ D w (H H) S 1 A = Ȳ 11 D w Ȳ 2 Ω = D w, Φ = S 1 3 a = 1, b = 0 Y ( Ȳ ) (2) S 30

31 (9) ( ) 1 2 Y Y P P D r, D c A = D 1 r PD 1 c 11 Ω = D r, Φ = D c 3 a = 1, b = 1 (7) Y ( Example ) Benzécli et al.(1973); Hill(1974); Greenacre(1978); Nishisato(1980); Greenacre(1981); Gifi(1981); Gauch(1982); 1/ A = 0 1/ / /.42 = / / / D r, D c SVD [ A = F = G = [ [ ] [ ] = ] = Y 1 1, 6, 8, 10, (F 1 ) (G 1 ) ] 31

32 C2 R R1 C3 R4 R2 C

33 R > Y <- matrix(c(1,2,3,6,4,5,8,9,7,10,11,12), ncol=3, byrow=true) > P <- Y / sum(y) > DR <- diag(rowsums(p)) > DC <- diag(colsums(p)) > A <- solve(dr) %*% P %*% solve(dc) - 1 > A [,1] [,2] [,3] [1,] [2,] [3,] [4,] > # SVD > osvd <- svd(sqrt(dr) %*% A %*% sqrt(dc)) > N <- solve(sqrt(dr)) %*% osvd$u > M <- solve(sqrt(dc)) %*% osvd$v > # A > N %*% diag(osvd$d) %*% t(m) [,1] [,2] [,3] [1,] e [2,] e [3,] e [4,] e > # F > N %*% diag(osvd$d) [,1] [,2] [,3] [1,] e-17 [2,] e-17 [3,] e-17 [4,] e-17 > # G > M %*% diag(osvd$d) [,1] [,2] [,3] [1,] e-17 [2,] e-17 [3,] e-17 33

34 R ca ca ca() print() ca() rowcoord, colcoord F, G A SVD N, M > library(ca) > Y <- matrix(c(1,2,3,6,4,5,8,9,7,10,11,12), ncol=3, byrow=true) > oca <- ca(y) > print(oca) Principal inertias (eigenvalues): 1 2 Value Percentage 72.71% 27.29% Rows: [,1] [,2] [,3] [,4] Mass ChiDist Inertia Dim Dim Columns: [,1] [,2] [,3] Mass ChiDist Inertia Dim Dim > oca$rowcoord %*% diag(oca$sv) [,1] [,2] [1,] [2,] [3,] [4,] > oca$colcoord %*% diag(oca$sv) [,1] [,2] [1,] [2,] [3,]

35 ca() N, M plot F, G > plot(oca) Dimension 2 (27.3%) Dimension 1 (72.7%) WRC Research Systems Brandmap Factorization Symmetric Prn SAS proc corresp SPSS correspondence standardize=rcmean, measure=chisq, normalization=principal 35

A11 (1993,1994) 29 A12 (1994) 29 A13 Trefethen and Bau Numerical Linear Algebra (1997) 29 A14 (1999) 30 A15 (2003) 30 A16 (2004) 30 A17 (2007) 30 A18

A11 (1993,1994) 29 A12 (1994) 29 A13 Trefethen and Bau Numerical Linear Algebra (1997) 29 A14 (1999) 30 A15 (2003) 30 A16 (2004) 30 A17 (2007) 30 A18 2013 8 29y, 2016 10 29 1 2 2 Jordan 3 21 3 3 Jordan (1) 3 31 Jordan 4 32 Jordan 4 33 Jordan 6 34 Jordan 8 35 9 4 Jordan (2) 10 41 x 11 42 x 12 43 16 44 19 441 19 442 20 443 25 45 25 5 Jordan 26 A 26 A1