Phân tích thành phần chính và ứng dụng PDF

Preview

Summary

BỘ GIÁO DỤC VÀ ĐÀO TẠOTRƯỜNG ĐẠI HỌC CÔNG NGHỆ VÀ THIẾT KẾ UEHKHOA TOÁN – THỐNG KÊ----------BÀI TIỂU LUẬN MÔN PHƯƠNG PHÁP TÍNHĐỀ TÀI: PHÂN TÍCH THÀNH PHẦN CHÍNH VÀ ỨNG DỤNGGiảng viên hướng dẫn:PGS Lê Xuân TrườngLớp:FM001 Khóa:KCác thành viên trong nhóm:Lương Đình Trường - 31191024170Phan Tấn Ph...

Description

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC CÔNG NGHỆ VÀ THIẾT KẾ UEH KHOA TOÁN – THỐNG KÊ ----------

BÀI TI ỂU LUẬN MÔN PHƯƠNG PHÁP TÍNH ĐỀ TÀI: PHÂN TÍCH THÀNH PHẦN CHÍNH VÀ ỨNG DỤNG Giảng viên hướng dẫn:PGS.TS Lê Xuân Trường Lớp:FM001

Khóa:K45

Các thành viên trong nhóm:18 Lương Đình Trường - 31191024170 Phan Tấn Phong

- 31191023775

Tô Thành Hiệp

- 31191026445

2

Mục lục I. Giới thiệu (mục tiêu và các ứng dụng của phương pháp phân tích thành phần chính): 1.Định nghĩa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6

2 M ục tiêu. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6

3 Ưu điểm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6

4. Các ứng dụng của PCA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 II. Nội dung thành phần chính: 1. Phân tích suy biến - Singular Value Decomposition (SVD) 1.1 Giới thiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

1.2 Mục tiêu của phân tích suy biến. . . . . . . . . . . . . . . . . . . . . . . . .

7

1.3 Kiến thức chung về đại số tuyến tính. . . . . . . . . . . . . . . . . . . . . .

8

1.4 Phát biểu SVD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

13

1.5 Các phép giảm chiều SVD. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 1.6 Phương pháp làm mỏng SVD. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 1.7. Phương pháp Compact SVD. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 1.8. Phương pháp Truncated SVD . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 1.9. Ứng dụng của phân tích suy biến SVD. . . . . . . . . . . . . . . . . . . . . 20 1.9.1 Giải phương trình tuyến tính . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 1.9.2 Giảm chiều dữ liệu hình ảnh. . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 2 . Phương pháp phân tích thành phần chính – Principal Component Annalysis (PCA)

3

2.1 Khái niệm . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.2 Đặc tính của PCA. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 2.3 Mục tiêu c ủa PCA. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 2.4 Thuật toán PCA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 2.4.1 Tiền xử lí . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 2.4.2 Xây d ựng không gian mới. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 2.4.3 Chuyển dữ liệu từ không gian ban đầu vào không gian mới. . . . . . 30 2.5 Cơ sở toán học c ủa PCA. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 2.6. Các bước để phân tích thành phần chính. . . . . . . . . . . . . . . . . . . . . . 33 2.6.1 Toán nền (Background Mathematics) . . . . . . . . . . . . . . . . . . . . . . 33 2.6.1.1 Thống kê(Statistics). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 2.6.1.2 Độ lệch chuẩn(Standard Deviation) . . . . . . . . . . . . . . . . . . . . . . 33 2.6.1.3 Phương sai (variance). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 2.6.1.4 Hiệp phương sai (covariance). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 2.6.1.5 Các ma trận hiệp phương sai(The covariance matrix) . . . . . . . . . . . . . 38 2.6.1.6 Đại số ma trận(Matrix Algebra). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 2.6.1.7 Vector riêng(Eigenvectors) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 2.6.1.8 Giá trị riêng(Eigenvalues). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 2.7

Phương pháp(Method) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

2.7.1

Bước 1: Nhận được một số dữ liệu (Get some data) . . . . . . . . . . . .. 43

2.7.2

Bước 2: Trừ các trung bình (Subtract the mean) . . . . . . . . . . . . . . . .43

2.7.3

Bước 3: Tính toán ma trận hiệp phương sai(Calculate the covariance

matrix) 44 2.7.4

Bước 4: Tính vector riêng và giá trị riêng của ma trận hiệp phương sai

(Calculate the eigenvectors and eigenvalues of the covariance matrix) . . . . . . . . . . . . . . . .44

4

2.7.5

Bước 5: Lựa chọn các thành phần và hình thành một vector đặc trưng

(Choosing components and forming a feature vector) ...................................45 2.7.6

Bước 6 : Phát sinh các tập dữ liệu mới ............................................47

2.7.7

Lấy dữ liệu cũ trở lại .....................................................................49

2.8

Các ứng dụng phân tích thành phần chính (Applications of principal

component analysis ) .................................................................................... 52 2.8.1

Tổng quan về bản dữ liệu (Overview (plots) of any data table ) ......53

2.8.2

Giảm biến đa chiều (Dimensionality reduction) ............................53

2.8.3

Mô hình tương đồng (Similarity models ) .....................................54

III. Phân tích thành phần chính (PCA) trong Python 3.1 Giới thiệu và ứng dụng c ủa PCA ..............................................................55 3.1.1 Giới thiệu .........................................................................................55 3.1.2 Ứng dụng .........................................................................................55 3.1.3 Ý nghĩa ............................................................................................56 3.2 Phân tích thành phần chính (PCA) để trực quan hóa dữ liệu ........................56 3.2.1 Tải tệp dữ liệu Iris .............................................................................56 3.2.2 Chuẩn hóa dữ liệu .............................................................................57 3.2.3 Phép chiếu PCA sang 2D ...................................................................57 3.2.4 Trực quan hóa phép chiếu 2D .............................................................58 3.3 Phân tích thành phần chính (PCA) để tăng tốc thuật toán Machine-Learning 60 3.3.1 Tải dữ liệu xuống ..............................................................................60 3.3.2 Tách dữ liệu thành các tập huấn luyện và kiểm tra................................61 3.3.3 Chuẩn hóa dữ liệu .............................................................................62

5

3.3.4 Các bước sử dụng PCA mà để tăng tốc thuật toán Machine Learning (hồi quyLogistic) .............................................................................................62 3.3.5 Số thành phần, phương sai, bảng thời gian...........................................63

IV. Ứng dụng 4.1 Chúng ta sẽ bắt đầu bằng một ví dụ mang tính chất minh họa trực quan……64 4.2 Ví dụ miêu tả cách tính toán PCA bằng Matlab ……………………………. 66 4.3 Các ví dụ khác………………………………………………………………. 68

6

I. Giới thiệu (mục tiêu và các ứng dụng c ủa phương pháp phân tích thành phần chính). 1. Định nghĩa: Phép phân tích thành phần chính (Principal Components Analysis - PCA) là một thuật toán thống kê sử dụng phép biến đổi trực giao để biến đổi một tập hợp dữ liệu từ một không gian nhiều chiều sang một không gian mới ít chiều hơn (2 hoặc 3 chiều) nhằm tối ưu hóa việc thể hiện sự biến thiên của dữ liệu. Phân tích thành phần chính (PCA) cũng là một phương pháp giảm thứ nguyên. Điều này không liên quan trực tiếp đến vấn đề dự đoán, nhưng một số phương pháp hồi quy phụ thuộc trực tiếp vào nó. Các phương pháp hồi quy (PCR và PLS) sẽ được xem xét sau. Giờ đây, một động lực để giảm thứ nguyên đang được thiết lập. PCA cũng có thể phân cụm các điểm dữ liệu tương tự dựa trên sự tương quan giữa chúng. 2. Mục tiêu của phương pháp này trên là chúng ta có thể: - Giới thiệu Phân tích thành ph ần chính. - Tiền thân của Kỹ thuật hồi quy sau giảm thứ nguyên. - Nắm bắt sự thay đổi nội tại của dữ liệu. - Giảm kích thước của một tập dữ liệu, để dễ giải thích hoặc là một cách để tránh trang bị quá nhiều và để chuẩn bị cho phân tích tiếp theo. 3. Ưu điểm với tập dữ liệu: •

Giảm số chiều của không gian ch ứa dữ liệu khi nó có số chiều lớn, không thể thể hiện trong không gian 2 hay 3 chiều.

•

Xây dựng những trục tọa độ mới, thay vì giữ lại các trục của không gian cũ, nhưng lại có khả năng biểu diễn dữ liệu tốt tương đương, và đảm bảo độ biến thiên của dữ liệu trên mỗi chiều mới.

•

Tạo điều kiện để các liên kết tiềm ẩn của dữ liệu có thể được khám phá trong không gian mới, mà nếu đặt trong không gian cũ thì khó phát hiện vì những liên kết này không thể hiện rõ.

7

•

Đảm bảo các trục tọa độ trong không gian mới luôn trực giao đôi một với nhau, mặc dù trong không gian ban đầu các trục có thể không trực giao. 4. Các ứng dụng chính của phương pháp phân tích thành phần chính (PCA):

+Tăng tốc độ thuật toán Machine Learning (ML) + Trực quan hoá dữ liệu II. Nội dung thành phần chính 1 Singular Value Decomposition (SVD) 1.1 Giới thiệu chung Phương pháp phân tích suy biến (singular value decomposition) được viết tắt là SVD là một trong những phương pháp thuộc nhóm matrix factorization được phát triển lần đầu bởi những nhà hình học vi phân. Ban đầu mục đích của phương pháp này là tìm ra một phép xoay không gian sao cho tích vô hướng của các vector không thay đổi. Từ mối liên hệ này khái niệm về ma trận trực giao đã hình thành để tạo ra các phép xoay đặ c biệt. Phương pháp SVD đã được phát triển dựa trên những tính chất của ma trận trực giao và ma trận đường chéo để tìm ra một ma trận xấp xỉ với ma trận gốc. Phương pháp này sau đó đã được ứng dụng rộng rãi trong các lĩnh vực như hình học vi phân, hồi qui tuyến tính, xử lý hình ảnh, clustering, các thuật toán nén và giảm chiều dữ liệu, và đặc biệt hiệu quả trong các bài toán recommendation 1.2. Mục tiêu c ủa phân tích suy biến. Phương pháp SVD sẽ tìm ra một lớp các ma trận xấp xỉ tốt nhất với một ma trận cho trước dựa trên khoảng cách norm Frobenios giữa 2 ma trận. Người ta đã chứng minh được rằng ma trận xấp xỉ tốt nhất được biểu diễn dưới dạng tích của 3 ma trận rất đặc biệt bao gồm 2 ma trận trực giao (orthogonal matrix) và 1 ma trận đường

8

chéo (diagonal matrix). Quá trình nhân ma trận thực chất là quá trình biến đổi các điểm dữ liệu c ủa ma trận gốc thông qua những phép xoay trục (rotation) và phép thay đổi độ lớn (scaling) và từ đó tạo ra những điểm dữ liệu mới trong không gian mới. Điều đặc biệt của ma trận đường chéo đó là các phần tử của nó chính là những giá trị riêng của ma trận gốc. Những điểm dữ liệu trong không gian mới có thể giữ được 100% thông tin ban đầu hoặc chỉ giữ một phần lớn thông tin của dữ liệu ban đầu thông qua các phép truncated SVD. B ằng cách sắp xếp các trị riêng theo thứ tự giảm dần trên đường chéo chính thuật toán SVD có thể thu được ma trận x ấp xỉ tốt nhất mà vẫn đảm bảo giảm được hạng của ma trận sau biến đổi và kích thước các ma trận nhân tử nằm trong giới hạn cho phép. Do đó nó tiết kiệm được thời gian và chi phí tính toán và đồng thời cũng tìm ra được một giá trị dự báo cho ma trận gốc với mức độ chính xác cao. Trên đây là những thông tin chung nhất về thuật toán SVD. Chắc rằng chúng ta sẽ rất mơ hồ khi mới lần đầu tiếp cận phương pháp này. Chính vì vậy kiến thức về đại số tuyến tính sẽ được hệ thống trước khi đi vào thuật toán. 1.3. Kiến thức chung về đại số tuyến tính. Hệ trực giao: Trong đại số tuyến tính, hệ trực giao là một lý thuyết quan trọng. Một

hệ vector cơ sở 𝑼 = [𝒖𝟏 , 𝒖𝟐 , … , 𝒖𝒏 ] ∈ ℝ𝑛 được gọi là một hệ trực giao (orthogonal)

nếu thỏa mãn hệ điều kiện:

||𝒖𝒊 ||𝟐𝟐 > 0, 𝒖𝑻𝒊 𝒖𝒋 = 0

∀1 ≤ 𝑖 ≠ 𝑗 ≤ 𝑛

Hệ trực chu ẩn: Hệ trực chuẩn (orthonormal) là một trường hợp đặc biệt của hệ trực giao khi điều kiện ||𝒖𝒊 ||𝟐𝟐 > 0 được thay thế thành ||𝒖𝒊 ||𝟐𝟐 = 1 .

Ma trận trực giao: Ma trận trực giao (orthogonal matrix) là ma trận vuông thỏa mãn

các dòng và c ột của nó là một hệ trực chuẩn. Điều đó có nghĩa là một ma trận 𝑼 ∈

ℝ𝑛×𝑛 sẽ bao gồm các c ột 𝒖𝑖 𝑖𝑛ℝ𝑛 có tính chất:

||𝒖𝒊 ||𝟐 > 0, 𝒖𝑻𝒊 𝒖𝒋 = 0 ∀1 0 khi A xác định dương. Mặt khác 𝜆𝒙𝑻𝒙 = 𝜆||𝒙||𝟐𝟐, ||𝒙||𝟐𝟐 > 0∀𝒙 ≠ 0. Suy ra λ>0λ>0, như vậy mọi trị riêng của A đều dương. Chứng minh tương tự cho trường hợp A bán xác định đương.

5. Tổng các phần tử trên đường chéo chính c ủa ma trận 𝑨 ∈ ℝ𝑛×𝑛 thì bằng tổng các trị riêng. Để chứng minh công thức này cần sử dụng đến phép phân tích

riêng sẽ được trình bày bên dưới. Khi ma trận A độc lập tuyến tính nó có thể biểu diễn dưới dạng phân tích riêng như sau: 𝑨 = 𝑷𝑫 𝑷−𝟏

Áp dụng hằng đẳng thức 𝒕𝒓𝒂𝒄𝒆(𝑨𝑩) = 𝒕𝒓𝒂𝒄𝒆(𝑩𝑨) ta có:

𝒕𝒓𝒂𝒄𝒆(𝑨) = 𝒕𝒓𝒂𝒄𝒆(𝑷𝑫𝑷−𝟏 ) = 𝒕𝒓𝒂𝒄𝒆((𝑷𝑫)𝑷−𝟏) = 𝒕𝒓𝒂𝒄𝒆(𝑷−𝟏 𝑷𝑫) = 𝒕𝒓𝒂𝒄𝒆(𝑫)

Từ đó suy ra tổng các phần tử trên đường chéo chính c ủa ma trận A bằng tổng các trị riêng. 6. Định thức của ma trận 𝑨 ∈ ℝ𝑛×𝑛 thì bằng tích các trị riêng của nó. Sử dụng phép phân tích riêng đối với ma trận A độ lập tuyến tính ta có: 𝑨 = 𝑷𝑫 𝑷−𝟏

𝑨 = 𝑷𝑫 𝑷−𝟏 ⇒ 𝒅𝒆𝒕(𝑨) = 𝒅𝒆𝒕(𝑷𝑫𝑷−𝟏 ) = 𝒅𝒆𝒕(𝑷). 𝒅𝒆𝒕(𝑫). 𝒅𝒆𝒕(𝑷−𝟏) = 𝒅𝒆𝒕(𝑫)

13

. Phép phân tích riêng: Phép phân tích riêng (Eigen Decomposition) cũng là một dạng matrix factorization. Nó có mối liên h ệ chặt chẽ với SVD. Trong đại số tuyến tính chúng ta luôn có thể phân tích một ma trận vuông độc lập tuyến tính

𝑨 ∈ ℝ𝑛×𝑛 thành tích của những ma trận vuông 𝑷 ∈ ℝ𝑛×𝑛khả nghịch và ma trận

đường chéo 𝑫 ∈ ℝ𝑛×𝑛 theo công thức:

𝑨 = 𝑷𝑫 𝑷−𝟏

Đẳng thức trên tương đương với:

AP=PD Bây giờ ta chỉ xét đến c ột thứ i c ủa cả 2 ma trận bên vế trái và phải: 𝑨𝒑𝒊 = 𝑷𝒅𝒊

Trong đó 𝒑𝒊 , 𝒅𝒊 lần lượt là cột thứ i của ma trận P và D. Mặt khác do D là ma trận

đường chéo nên 𝑑𝑖chỉ có duy nhất một phần tử khác 0 là𝑑𝑖𝑖 nên 𝑷𝒅𝒊 = 𝒑𝒊 𝑑𝑖𝑖. Như vậy:

𝑨𝒑𝒊 = 𝒑𝒅𝒊

Đây chính là phương trình xác định trị riêng của A. Ta có thể thấy diidii chính là trị riêng của ma trận A và 𝒑𝒊 là các vector riêng tương ứng của 𝑑𝑖𝑖.

Như vậy điểm đặc biệt của phân tích riêng đó là đường chéo chính của D là các trị riêng của ma trận A và các cột của P là các vector riêng tương ứng với trị riêng nằm

trên đường chéo chính. Ngoài ra phép phân tích riêng không là duy nh ất. Nếu ma trận trực giao P thỏa mãn phương trình phân tích riêng thì ma trận kP cũng thỏa mãn phương trình phân tích riêng đó.

1.4 Phát biểu SVD Phương pháp phân tích trị riêng (SVD – Singular Value Decomposition) là một đề tài rất được quan tâm của đại số tuyến tính. Đặc điểm quan trọng của

14

phương pháp này là nó có thể áp dụng cho bất kỳ ma trận thực m x n nào. Nội dung của nó là: phân tích một ma trận A cho trước thành 3 ma trận U, D, V, sao cho: A = UDV T •

U = (u1,u2,...,uN) là một ma trận trực giao N x N.,uj,j = 1,...,N, tạo cơ sở trực chuẩn cho không gian được kéo dài bởi vectơ cột của ma trận X.

•

V = (v1,v2,...,v p) là một ma trận trực giao p × p.vj,j = 1,...,p,tạo cơ sở trực chuẩn cho không gian được kéo dài bởi vectơ dòng của ma trận X.

•

D là một ma trận hình chữ nhật Nxp với các ph ần tử khác không dọc theo đường chéo thứ nhất p x p. diag(d1,d2,...,d p), d1 ≥ d2 ≥ ··· ≥ dp là các giá trị riêng của ma trận X với N > p. Các cột của V tức là vj,(j = 1,...,p) là các giá trị riêng của XTX. Chúng được gọi là hướng thành phần chính của ma trận X. Các giá trị đường chéo trong D tức là dj,j = (1,...,p) là căn bậc hai các giá trị riêng của XTX.

Hình 1: SVD cho ma trận A khi: mn(hình dưới). Σ là một ma trận đường chéo với các phần tử trên đó giả m dần và không âm. Màu đỏ càng đậm thể hiện giá trị càng cao. Các ô màu trắng trên ma trận này thể hiện giá trị 0

15

2.4 Phân tích suy biến trong python Trong python phép phân tích suy biến của một ma trận được thực hiện dễ dàng thông qua việc sử dụng hàm SVD của pa ckage scipy như sau: import scipy.linalg as ln import numpy as np m, n = 2, 3 n_diag = min(m, n) #Init normal standard random variable A with size (m, n) A = np.random.rand(m, n) U, S_diag, V = ln.svd(A) #Create diagonal matrix S based on diagonal S = np.zeros((n_diag, n_diag)) np.fill_diagonal(S, S_diag) if m > n: S = np.concatenate((S, np.zeros((1, n))), axis = 0) elif m < n: S = np.concatenate((S, np.zeros((m, 1))), axis = 1) print('Matrix A: \n %s \n'%A) print('orthogonal matrix U: \n %s \n'%U) print('Check Frobenius U^TU-I: \n %s \n'%ln.norm(np.dot(U.T,U)-np.eye(m, m), 'fro')) print('orthogonal matrix V: \n %s \n'%V) print('Check Frobenius V^TV-I: \n %s \n'%ln.norm(np.dot(V.T,V)-np.eye(n, n), 'fro')) print('Diagonal matrix S: \n %s \n'%S_diag) print('Matrix S: \n %s \n'%S) print('Check Frobenius U.S.V - A: \n %s \n'%ln.norm(np.dot(U, S.dot(V))-A,'f ro'))

Matrix A: [[0.14630186 0.28630696 0.95385295] [0.74528454 0.31837132 0.51025156]] orthogonal matrix U: [[ 0.73134897 -0.68200343] [ 0.68200343 0.73134897]] Check Frobenius U^TU-I: 4.7152287001014445e-16

16

orthogonal matrix V: [[ 0.47845355 0.33166831 0.81306724] [ 0.84663666 0.07144886 -0.52735323] [ 0.23299908 -0.94068655 0.24661758]] Check Frobenius V^TV-I: 1.1025824029789615e-15 Diagonal matrix S: [1.28598551 0.52594546] Matrix S: [[1.28598551 0. [0.

0.

0.52594546 0.

] ]]

Check Frobenius U.S.V - A: 1.0576294775109601e-15

1.5 Các phép giảm chiều SVD. Thông thường việc phân tích suy biến một ma trận có kích thước lớn sẽ rất lâu vì đòi hỏi phải giải phương trình đặc trưng để tìm ra các giá trị đặc trưng, từ đó suy ra ma trận đường chéo Σ. Từ phương trình phân tích riêng 𝑨𝑻𝑨 = 𝑽𝜮𝑻𝜮𝑽𝑻 suy

ra 𝑨𝑻𝑨𝑽 = 𝑽𝜮𝑻𝜮, sử dụng phương trình ứng với từng cột cả 2 vế trái và phải để

tính ra được các vector riêng ứng với mỗi trị riêng và suy ra được ma trận V. Cách tìm ma trận U cũng được suy ra tương tự từ phương trình phân tích riêng

𝑨𝑨𝑻 = 𝑼𝜮𝜮𝑻𝑼𝑻. Quá trình này phải trải qua nhiều bước và khi kích thước ma trận

lớn, chi phí thời gian và lưu trữ sẽ rất lớn. Vì v ậy các dạng giảm chiều SVD sẽ rút gọn quá trình tính toán.

17

1.6 Phương pháp làm mỏng SVD. Xuất phát từ ý tưởng số quan sát thường lớn g ấp rất nhiều lần so với số chiều hay m>>nm>>n trong hầu hết các trường hợp của ma trận A nên thay vì phải tính toán bộ ma trận 𝑼𝑚𝑚 ta sẽ chỉ tính n cột đầu tiên là 𝑼𝑛𝑛 . Số chiều c ủa ma trận

đường chéo 𝜮𝑚𝑚 cũng giảm xuống thành 𝜮𝑛𝑛 . Khi đó ma trận A được biểu diễn dưới dạng:

𝑻 𝑨 = 𝑼𝑚𝑛 𝜮𝑛𝑛 𝑽𝑛𝑛

Như vậy số lượng các trị riêng cần tìm chỉ còn nn và số lượng vector riêng chỉ còn 2n2n (nn cột của ma trận 𝑼𝑚𝑛 và n c ột c ủa ma trận 𝑽𝑛𝑛 ). 1.7 Phương pháp Compact SVD.

Ta có thể biểu diễn ma trận 𝑨 dưới dạng tổng của các tích vector c ột 𝒖𝒊 ∈

ℝ𝑚 của 𝑼𝑚𝑚 và vector dòng của 𝑽𝑻𝑛𝑛 như sau: 𝑛

𝑨 = ∑ 𝒖𝒊 𝜎𝒊 𝒗𝒊 𝑖=1

Các vector 𝒖𝒊 và 𝒗𝒊 là các hệ cơ sở độc lập tuyến tính. Thông thường trong ma trận đường chéo 𝜮𝑛𝑛 chỉ một lượng lớn các trị riêng có lớn hơn 0. Các trị riêng còn lại

đều xấp xỉ 0. Do đó chỉ tại rr vị trí dòng và cột tương ứng với các trị riêng đủ lớn ta

mới thực hiện tính toán SVD. Biểu diễn ma trận 𝑨𝑛𝑛 dưới dạng compact SVD như

sau:

𝑨 = 𝑼𝑟 𝜮𝑟 𝑽𝑟𝑻

Trong đó các ma trận 𝑼𝑟 , 𝜮𝑟 , 𝑽𝑻𝑟 lần lượt là các ma trận sau khi đã rút gọn các dòng và cột để chỉ giữ lại các vị trí tương ứng với σiσi đủ lớn. Nếu r 0 lớn nhất của A từ 𝑼, 𝑽𝑻. Phần còn lại của ma trận sẽ bị loại bỏ. Như vậy trong ph...