BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC GIAO THÔNG VẬN TẢI

NGHIÊN CỨU KHOA HỌC SINH VIÊN

Đề tài:
KHAI TRIỂN SVD VÀ ỨNG DỤNG TRONG PHÂN TÍCH ẢNH

Nhóm nghiên cứu khoa học:
Vương Đình Tùng - Lớp XDCTGT tiên tiến K51
Trần Thị Hằng - Lớp XDCTGT tiên tiến K51
Phạm Anh Dũng - Lớp XDCTGT tiên tiến K51
Nguyễn Đình Khánh - Lớp XDCTGT tiên tiến K51
Giáo viên hướng dẫn: TS. Trần Văn Long

Hà Nội, 2012
1


MỤC LỤC

Lời mở đầu………………….………………………………………………………3

Chương I: Kiến thức chuẩn bị
1.1
1.2
1.3
1.4
1.5
1.6
1.7

Ma trận………………………..………………………………4
Ma trận trực giao……………………….…………………….5
Vec tơ riêng – Giá trị riêng……………………..…………….6
Chuẩn của vec tơ……………………………………….…….7
Chuẩn của ma trận…………………………………………....8
Hạng của ma trận……………………………………………..8
Vết của ma trận……………………………….………………9

Chương II: Khai triển SVD của ma trận
2.1 Khai triển SVD của ma trận…..…………………………………10
2.2 Ma trận nghịch đảo suy rộng….…………………………………15
2.3 Xấp xỉ ma trận……….………………..…………………………21

Chương III: Ứng dụng khai triển SVD trong xử lí ảnh
3.1 Phân tích SVD trong xử lí ảnh…………………….…………….28
3.2 Sử dụng Matlab trong xử lí ảnh…………………………………29

Kết luận………………….………………………………………………………...32
Tài liệu tham khảo………………………………………………………………...33

2


LỜI MỞ ĐẦU
SVD (singular value decomposition) là một dạng khai triển của ma trận có
rất nhiều ứng dụng trong những vấn đề liên quan đến nghịch đảo và số hóa các dữ
liệu. Hiện nay phân tích SVD của ma trận xuất hiện rất nhiều trong các ứng dụng
thực tế như về tín hiệu số, tính các giá trị xấp xỉ trong kĩ thuật, công nghệ thông
tin, và được ứng dụng trong các công cụ tìm kiếm trên các websites. Tuy nhiên,

nghiên cứu lý thuyết liên quan đến SVD đối với sinh viên là vấn đề mới, chưa gần
gũi và chưa dễ hiểu cho sinh viên cần nghiên cứu về mảng đề tài thú vị này. Do đó
nhóm nghiên cứu khoa học với đề tài “Khai triển SVD và ứng dụng trong phân
tích ảnh” thực hiện nghiên cứu này nhằm mục đích đưa đến cho người đọc những
kiến thức cơ bản nhất về khai triển SVD và tạo một cái nhìn tổng quan về cách
khai triển cũng như một số tính chất, hệ quả quan trọng liên quan đến dạng khai
triển này.
Nội dung của đề tài được viết thành 3 chương. Chương 1 trình bày một số
kiến thức cơ sở về ma trận. Một số kết quả quan trọng đối với khai triển SVD là
các Định lý 3, Định lý 5, Định lý 6, Định lý 9, Định lý 10 được trình bày trong
Chương 2. Trong Chương 3, cùng với cơ sở lí thuyết nhóm nghiên cứu cũng đi vào
một ứng dụng cụ thể là ứng dụng của SVD trong kĩ thuật phân tích ảnh.
Nhóm nghiên cứu cũng xin gửi lời cảm ơn chân thành đến thầy giáo, TS.
Trần Văn Long, Bộ môn Đại số - Xác suất thống kê, Trường Đại học Giao thông
Vận tải đã nhiệt tình giúp đỡ, giải đáp thắc mắc cũng như cung cấp tài liệu để
nhóm có thể hoàn thành đề tài nghiên cứu.
Hà Nội, ngày 22 tháng 4 năm
2012
Nhóm nghiên cứu khoa học sinh viên
3


CHƯƠNG 1: KIẾN THỨC CHUẨN BỊ
1.1

Ma trận
a) Định nghĩa 1: Ma trận một bảng gồm mxn số thực được sắp xếp thành m
dòng, n cột và gọi là ma trận cấp mxn.
Ký hiệu ma trận


A =

 a11 a12

 a21 a22
 M M

 am1 am 2

K
K
O
K

a1n 
÷
a2 n ÷
M÷
÷
amn 

,

hoặc

A=

 a11 a12
a
 21 a22

 M M

 am1 am 2

hoặc

K
K
O
K

a1n 
a2 n 
,
M

amn 

(a )

ij mxn

A=
Trong đó aij là phần tử của ma trận nằm trên dòng i, cột j,
i = 1, 2,..., m, j = 1, 2,..., n.

b)

Các phần tử aii gọi là phần tử nằm trên đường chéo chính.
Ma trận đơn vị

Định nghĩa 2: Ma trận đơn vị là ma trận có mọi phần tử nằm trên đường

chéo chính bằng 1, các phần tử khác bằng 0, và có dạng sau:

I

c)

=

1

0
M

0

0
1
M
0

K
K
O
K

0
÷
0÷

M÷
÷
1

Ma trận đường chéo
4


Định nghĩa 3: Ma trận đường chéo là ma trận vuông có các phần tử nằm
ngoài đường chéo chính bằng 0.
Ma trận đường chéo có dạng

D=
d)

 a11 0

 0 a22
 M M

0
 0

Ma trận dòng, cột
Ma trận dòng có dạng:
X=

( a1 ,

K

K
O
L

a2 , K

0 
÷
0 ÷
M÷
÷
ann 

an )

Ma trận cột có dạng:

Y=
e)

 a1 
 ÷
 a2 ÷
 M÷
 ÷
 an 

Ma trận chuyển vị
Định nghĩa 4: Ma trận AT của ma trận A có các dòng là các cột của ma


trận A (giữ nguyên thứ tự) gọi là ma trận chuyển vị của ma trận A.

T

A =
1.2

 a11 a21

 a12 a22
 M M

 a1n a2 n

K
K
O
K

am1 
÷
am 2 ÷
M÷
÷
amn 

Ma trận trực giao
Định nghĩa 5: Ma trận vuông A được gọi là ma trận trực giao nếu
A AT =AT.A = I
Tính chất:

a) Ma trận A =

 aij 

là ma trận trực giao khi và chỉ khi
n

∑a
k =1

ik

 1, i=j
.a jk = δ ij = 
0, i ≠ j

b) Như vậy ma trận trực giao A là khả nghịch và có A-1 = AT.

5


c) Mặt khác ta cũng thấy ma trận A trực giao khi và chỉ khi các vec tơ cột và
các hàng của A tạo thành các hệ trực chuẩn.
AT A = I = 1 → A = ±1

d)
1.3

Ta có:


Vec tơ riêng – Giá trị riêng
Định nghĩa 6: Cho A là ma trận vuông cấp n
 a11 a12
a
 21 a22
 M M

 an1 am 2

A=
Khi đó:
•

Đa thức bậc n của biến

λ

M
an1

λ

O
K

a1n 
a2 n 
M

ann 


:
a11 − λ
a21

λ

K
K

PA( ) = det (A- .I) =

λ

a12
K
a22 − λ K
M
am 2

O
K

a1n
a2 n
M
ann − λ

λ


= (-1)n. n + an-1. n-1 +….+ a1.
được gọi là đa thức đặc trưng của ma trận A.
•

1

+ a0

λ

Các nghiệm của đa thức đặc trưng PA( ) gọi là giá trị riêng của ma
trận A.

•

λ

Nếu

λ

λ

là một giá trị riêng của A thì det (A- .I) = 0. Khi đó hệ

phương trình thuần nhất:

λ

(A- .I)


 x1 
 M
 
 x2 

=

0
 M
 
 0 

(1)

có vô số nghiệm.

6


•

Không gian của hệ (1) gọi là không gian con riêng của ma trận
λ

•

A tương ứng với giá trị riêng .
Các vec tơ khác không là nghiệm của hệ (1) gọi là vec tơ riêng


•

của ma trận A ứng với giá trị riêng .
Các cơ sở tạo thành một cơ sở của không gian riêng (tức là các

λ

vec tơ tạo thành hệ nghiệm cơ bản của hệ (1)) gọi là các vec tơ
λ

riêng độc lập tuyến tính ứng với giá trị riêng .
1.4

Chuẩn của vec tơ
x

x

x

Định nghĩa 7: Cho vec tơ , chuẩn của , kí hiệu là

được xác định là

một số không âm thỏa mãn các tính chất sau:
x ≥0

a)

x =0


và

khi và chỉ khi x=0.

αx = α x

b)

với mọi

α ∈R

.

x+ y ≤ x + y

c)

(Bất đẳng thức tam giác).

Chuẩn Euclide:
Chuẩn Euclide của vec tơ x được xác định như sau:
x

E

(

1

2 2
n

= x 2 = x = x + x + ... + x
2
1

2
2

)

7


1.5

Chuẩn của ma trận
Định nghĩa 8: Cho ma trận A kích thước

m× n

A

, chuẩn của A kí hiệu

là một

số không âm thỏa mãn:
A ≥0


a)

A =0

và

khi và chỉ khi A=0.

αA = α A

b)

với mọi

α ∈R

.

A+ B ≤ A + B

c)

(Bất đẳng thức tam giác).

- Chuẩn F (Frobenius):

A = ( aij )
Cho


mxn

ta định nghĩa chuẩn F của ma trận A là
1

A

Ví dụ: Cho ma trận A =
A

F

=

F

 m n
2
=  ∑∑ aij2 ÷
 i =1 j =1 

 1 2 −2 

÷
 −1 1 3 

12 + 22 + ( −2) 2 + (−1) 2 + 12 + 32

=


20

- Chuẩn 2 của ma trận: Chuẩn 2 của ma trận A là căn bậc 2 của giá trị riêng

lớn nhất của ma trận ATA. Ký hiệu là

|| A ||2 = λmax ( AT A)

.
8


1.6 Hạng của ma trận
Định nghĩa 9: (Định thức con của ma trận)
A = aij
mxn
Xét ma trận
Từ A ta lấy các phần tử trên giao của s dòng và
s cột thì ma trận thu được gọi là ma trận vuông con cấp s của A với s là số

( )

s ≤ min ( m, n )

nguyên dương và
.
Định thức của ma trận con đó được gọi là định thức con cấp s của ma trận A.
Kí hiệu:

Di1ji12j....2 ....is js


gọi là định thức con cấp s của A.

Định nghĩa 10: (Hạng của ma trận)
Định thức con cấp cao nhất khác không của ma trận A gọi là định thức con
cơ sở của ma trận A.
Một ma trận A có thể có nhiều định thức con cơ sở đều có cùng cấp.
Hạng của ma trận A là cấp của định thức con cơ sở.
Ký hiệu hạng của ma trận A là rank (A) hay r(A).
Một số tính chất về hạng của ma trận:
-

-

rank ( Amxn .Bnxl ) = rank ( Amxn )

rank (Cmxn . Anxk ) = rank ( Anxk )

nếu

nếu

rank ( Bnxl ) = n

rank (Cmxn ) = n

1.7 Vết của ma trận

9



Vết của một ma trận vuông A bậc nxn được xác định bằng tổng các phần tử
trên đường chéo chính (đường nối từ góc trên bên trái xuống góc dưới bên phải)
của A,
n

Tr ( A) = a11 + a22 + ... + ann = ∑ aii
i =1

CHƯƠNG 2: KHAI TRIỂN SVD CỦA MA TRẬN
Trong chương này chúng tôi sẽ trình bày các kết quả quan trọng về khai triển SVD
của ma trận, một số tính chất và hệ quả liên quan.
2.1 Khai triển SVD của ma trận
ĐỊNH LÍ 1: Với mọi ma trận bất kỳ, khi đó mọi giá trị riêng của ma trận đều
không âm.
CHỨNG MINH:
Gọi là giá trị riêng của ma trận và v là vec tơ riêng tương ứng với

|| v ||= 1

. Dễ thấy:

2

Av = ( Av)T ( Av) = vT AT Av

Do λ là giá trị riêng của ma trận :
( – λ I). v = 0
.v = λ I v = λ v
Av = λ = λ =

= λ

λ ≥ 0.

Như ta đã chứng minh trên mọi giá trị riêng của đều không âm.
Ta có định nghĩa và cách xác định của giá trị kì dị (singular) của ma trận A:
10


= =,
Trong đó

λi

ĐỊNH LÍ 2

i = 1, 2,..., n

,

là các giá trị riêng của ma trận .
(Về sự phân tích SVD của ma trận)

Với mọi ma trận bất kỳ đều có thể phân tích dưới dạng:
A = U..
Với U và V là các ma trận trực giao. Ma trận ∑ được xây dựng:
=

với D =


CHỨNG MINH:
Từ Định lí 1 thì ma trận A có các giá trị kì dị = ,
do ≥ 0 r : ≥ ≥ … > 0,
≥ ≥ …. > 0 và = =

… =

=0

Ma trận V được xây dựng dựa trên các véc tơ riêng của ma trận Cụ thể:
V=[… ]
Xây dựng ma trận U:
Với các (i : 1 r ) là các giá trị kì dị của ma trận . Đặt = A v i
(i =
1, …, r ). Từ đó ta xây dựng được ma trận U = [ … ] (m > r), trong đó các vec-tơ
ur +1 ,..., um

là hệ trực chuẩn được bổ sung vào các vec-tơ
trực giao.

u1 ,..., ur

. Khi đó U là ma trận

Với các ma trận U, , V được xác định như trên thì ta sẽ chứng minh:
A = U..VT

⇔

AV = U


Ta có: A = với i = 1, …., r và = 0 với i = r +1, r + 2, …, n
11


A = 0 với i = r +1, r + 2, …, n
Ta có:

AV = A [ … ]
= [A …A ]
=[A …A ; 0,0,0…0]
=[ … ;0,0,0…0]
=[ ...]
=U.

Ví dụ 1: Tìm khai triển SVD của ma trận

A=

1 1 0 
0 0 1 



Giải:
Ta tìm các giá trị riêng của ma trận .

Ta có =

1 0 

1 0 

 1 1 0 
0 1  0 0 1 

.

=

1 1 0 
1 1 0 


0 0 1 

Giải phương trình det (A- .I) = 0 ta được các giá trị riêng của ma trận là
= 1, = 0.

= 2,

Với mỗi giá trị riêng , giải phương trình (A - I)x = 0 ta được các vec tơ riêng
tương ứng là:

=

1/ 2 


1/ 2 
 0 




,

=

0
0
 
1 

,

=

 −1/ 2 


 1/ 2 
 0 



12


 1/ 2 1/ 2

0

 0
 −1/ 2 1/ 2


Ta được ma trận VT =

Các giá trị kì dị của ma trận A là =

Từ đó ta được ma trận

=

0

1
0 

= 1,

=0

 2 0 0


 0 1 0

Tìm ma trận U:

= A


vi

⇒

u1 =

1/ 2 


1/ 2 

1 1 1 0  
0 


2 0 0 1  


u2 =

⇒
⇒

U=

0 
1 1 1 0  
0
1  0 0 1  
1 


=

1 
0 
 

=

0 
1 
 

1 0 
0 1 



Phân tích SVD của ma trận A là

A=

1 1 0 
0 0 1 



= U.. =

1 0   2 0 0 

0 1   0 1 0 


 

 1/ 2 1/ 2 0 


0
1
 0
 −1/ 2 1/ 2 0 



ĐỊNH LÍ 3 (Về dạng khai triển của phân tích SVD)
Mọi ma trận A có dạng khai triển:
13


A= +…..+ .
Với , ,

là các giá trị đã được nói đến ở Định lí 2.

CHỨNG MINH:
Ta có:
A=U.. =[ ...]

=[ ...]


 v1T 


 M
 vT 
 Tr 
 vr +1 
 M
 T 
 vn 

= [ ...] + [ ...]
Đặt Ur =

[ u1 , u2 ,..., ur ]

, Vr =

[ v1 , v2 ,..., vr ]

= [ ...] = Ur . D. Vr
= [ … ] = +…..+
ĐỊNH LÍ 4
Với ma trận A = U.. và , , …. > 0 là các giá trị kỳ dị của A. Khi đó:
(A) = r.

rank

CHỨNG MINH:

Theo tính chất của hạng ma trận thì:
Rank(Ur)= rank(Ur. UrT) = rank( = r
14


Rank(VrT) = rank(VrT.Vr) = rank() = r
Rank (A) = rank (U.. ) =rank(Ur. D.VrT) (xem ở Định lí 3)
= rank (.VrT) = rank () = r.
ĐỊNH LÍ 5:
Cho ma trận A có, , …. > 0 là các giá trị kì dị của A. Khi đó:
=
CHỨNG MINH:
Đầu tiên ta chứng minh tính chất sau: = với là ma trận trực giao và là vec-tơ bất
kì. Thật vậy,

Tiếp theo ta chứng minh: = với là ma trận trực giao và là ma trận bất kì. Thật
vậy:
=
= +…+
= +….+
=
Xét ma trận bất kì với SVD của nó là U.. :
= =

(U là ma trận trực giao)
= = =

(V là ma trận trực giao)

= +…+

=.
2.2 Ma trận nghịch đảo suy rộng
Trong phần này chúng tôi sử dụng khai triển SVD để tìm ma trận nghịch
đảo suy rộng theo nghĩa Moore-Penrose.
15


ĐỊNH LÍ 6 (Bài toán về ma trận nghịch đảo mở rộng)
Với ma trận bất kỳ thì được gọi là ma trận nghịch đảo suy rộng của A nếu ma trận
A thỏa mãn:
1.
2.
3.
4.

AA = A
A =
(=A
=A

Với mọi ma trận A có phân tích SVD là thì ma trận V.. là ma trận nghịch đảo
suy rộng của ma trận A . Với là ma trận nghịch đảo mở rộng của và
D

 0

+

=


0

0

, trong đó =

D −1

=

0 
1/ σ 1 L
 M O
M 

K 1/ σ n 
 0

CHỨNG MINH:
Tính chất 1:

AA = U.. . V.. . U..
= U.. I . . I ..
= U..
=A

Tính chất 2: A = V.. . U.. . V..
= V.. . .
= V.. =
Tính chất 3: ( = (

= (
=(.(
=U.(.
=
16


Mặt khác:

= =
=(

Tính chất 4: =
=
=(.(
=V.(.
=
Mặt khác:

= =
=

Ví dụ 2: Tìm ma trận nghịch đảo mở rộng của

1 1 0 
A=

0 0 1 

Theo ví dụ ở Định lí 2 ta có:


A = U.. =

 1/ 2 1/ 2 0 

1 0   2 0 0  
0
1
 0
0 1  

  0 1 0 

 −1/ 2 1/ 2 0 

Vì = V.. với =

Trong đó =









 D+

 0


0

0

1

0
2

0 1 
0 0 



17


⇒

= V.. =

1/ 2 0 −1/ 2  1/ 2 0 
1/ 2 0 


 1 0  
1 
= 1/ 2 0 
1/ 2 0 1/ 2   0


0 1
 0
 0 1 
1
0   0
0  



ĐỊNH LÍ 7
Cho hệ:
nhất.

Ax = b với A là ma trận bất kì. Với = thì nhỏ nhất và có độ dài nhỏ

CHỨNG MINH:
Xét ma trận A bất kì có rank (A) = r và phân tích SVD của nó là
= V..
Đặt y = x và c =b

Ta viết y và c dưới dạng: y =

 y1 
y 
 2

và c =

 c1 

c 
 2

Ta có = = (do là ma trận trực giao)
= =
= =
=
min khi:
c1 − Dy1 = 0 ⇔ y1 = D −1.c1
 D −1.c1 
⇒ x = Vy = V 

 y2 

Với mọi giá trị thì vẫn đạt giá trị nhỏ nhất

18


Đặt = V =

 D −1.c1 


 0 

ta sẽ chứng minh min:

Với x’ bất kì khác thì x’ =
Dễ thấy:


= = < ==

Mặt khác: = V = V

 D −1.c1 


 y '2 

(đpcm)

 D −1.c1 


 0 

= V.c = V.b

=V

 D −1 0   c1 

 
 0 0  c2 

= b
(Định lí được chứng minh)

Ví dụ 3: Giải phương trình:

 x1

 3 x1
4 x
 1

+

x2

= 2

+ 2 x2

= 3

+ 3 x2

= 6

(*)

Khi giải bằng phương pháp cơ bản thì phương trình đã cho vô nghiệm.
Chúng ta áp dụng Định lý 7 để tìm nghiệm tốt nhất có thể có của hệ đã cho.

Hệ (*)

⇔

Ax = b với


1 1

÷
A =  3 2÷
 4 3÷



và b=

2
 ÷
3÷
6÷
 

Tìm khai triển SVD của ma trận A:

ATA =

1 1
1 3 4  
÷

÷ 3 2 ÷
1 2 3   4 3 ÷




=

 25 19 

÷
 19 25 

19


T

Giải phương trình det (A A -

λ
1

= 44, và

λ
2

λI

) = 0, ta tìm được các giá trị riêng

Giải hệ:

(A A -


T

(A A -

⇒

V=








1
2
1
2

λ1 I

λ2 I

của ATA:

=6
44

Ta có các giá trị kỳ dị của ma trận A lần lượt là =


T

λ

)x = 0 ta được v1 =

)x = 0 ta được v2 =

1 
2 ÷
÷
1 ÷
−
÷
2

⇒

VT =

, và

=

6

1/ 2 

÷

1/ 2 ÷



 1/ 2 

÷
 −1/ 2 ÷



1/ 2

1/ 2


1/ 2 
÷
−1/ 2 ÷


Tìm ma trận U:

= A

vi

⇒

u1 =


1 1
1 
÷
3 2 ÷ 1/ 2 


÷
44 
÷ 1/ 2 ÷
4
3




u2 =

=












2 
÷
88 ÷
8 ÷
÷
88 ÷
7 ÷
÷
88 




1
1


 1/ 2  
1 
÷
3 2 ÷
÷=
 −1/ 2 ÷ 
6 
÷

 
3 3






0 ÷
÷
1 ÷
12 ÷
÷
1 ÷
÷
12 

20


⇒

U=






















⇒


0 ÷
÷
1 ÷
÷
12 ÷
1 ÷
÷
12 

2
88
5
88
7
88

2
88

5
88
7
88

,


0 ÷
÷
1 ÷
÷
12 ÷
1 ÷
÷
12 

 44
Σ=
 0


 44

 0


0 
÷
6÷



0   1/ 2
÷

6÷
  1/ 2

1/ 2 
÷
−1/ 2 ÷


A=
⇒

Ma trận nghịch đảo mở rộng A+

1/ 2

1/ 2


 1
 44

1/ 2  
÷ 0
−1/ 2 ÷



 2
0 ÷
÷ 88
1 ÷
÷ 0
6 

5
88
1
12

7 
88 ÷
÷
1 ÷
÷
12 

A+ =

=









 2
 88

 2

 88

1
88
1
88

1  2

12 ÷
÷  88
1 ÷
−
÷ 0
12  

37
264
−7
264

5
88
1

12

7 
88 ÷
÷
1 ÷
÷
12 

43 
264 ÷
÷
−1 ÷
÷
264 

=

21


= =

 2
 88

 2

 88


37
264
−7
264

=

43 
264 ÷
÷
−1 ÷
÷
264 

 2
 ÷
 3÷
6÷
 

 127 
 88 ÷

÷
 −5 ÷

÷
 88 

Chính là nghiệm xấp xỉ tốt nhất của phương trình đã cho.


2.3 Xấp xỉ ma trận
ĐỊNH LÍ 8: Cho ma trận A với dạng khai triển của phân tích SVD là:
A = +…..+
Xét ma trận

=+…..+ , ( k < r ). Khi đó:
rank () = k

CHỨNG MINH:
Ta viết

về dưới dạng:

=

(,….. , )

 u1 
 ÷
 u2 ÷
K ÷
 ÷
u ÷
 k

Ta có:
=

(u


T
1

Lại có:

u2T

K

urT

)

=

22


 u1 
 ÷
 u2 ÷
K ÷
 ÷ T
u ÷ u
 r 1

(

Nên


 u1 
 ÷
 u2 ÷
K ÷
 ÷
u ÷
 k

rank

 u1 
 ÷
 u2 ÷
K ÷
 ÷
u ÷
 k

u2T

urT

K

)

=

=


= rank = k

(1)

Xét rank (,….., )

(v

T
1

Ta có:

(v

T
1

(σ

v2T

T
1 1

v

v2T


K

K

vnT

σ 1v2T K

)

vnT

) (v

1

=
v2 K

(

vk

)

σ 1vnT ) v1 v 2 K

=

vk


)

=

 σ1 
 ÷
σ 2 ÷
 ... ÷
 ÷
σ k 

23


=

Do

rank

σ1 0 0 0 

÷
 0 σ2 0 0 ÷
 ... ... ... ... ÷

÷
 0 0 0 σk 


(v

1

= rank

σ1 0 0 0 

÷
 0 σ2 0 0 ÷
 ... ... ... ... ÷

÷
 0 0 0 σk 

v2 K

rank (,….. , ) = k
Từ (1), (2) ta có:

vk

)

=k

(2)
rank) = k

ĐỊNH LÍ 9: Giả sử A là ma trận cỡ


m×n

có

rank ( A) = r

, và có khai triển kỳ dị SVD

r

A = ∑ σ i ui viT
i =1

. Khi đó với mọi ma trận B có cỡ

m× n

và

rank ( B ) ≤ k

, ta có

k

|| A − B ||2F ≥|| A ||2F −∑ σ i2
i =1

k


B = Ak = ∑ σ i ui viT

Dấu bằng xảy ra khi

i =1

.

CHỨNG MINH:
Đầu tiên ta chứng minh bổ đề sau:

24


r

Giả sử A là ma trận cỡ

m×n

rank ( A) = r

có

1≤ k ≤ r

x

Khi đó với véc tơ bất kỳ,


A = ∑ σ i ui viT

, và có khai triển kỳ dị SVD

i =1

ta có:
k

k

i =1

i =1

|| Ax||2 ≤ σ k2 || x ||2 + ∑ σ i2 (viT x) 2 − σ k2 ∑ (viT x ) 2

.

(*)

CHỨNG MINH:
A

Theo khai triển kỳ dị SVD của ma trận

ta có

r


r

r

i =1

i =1

i =1

Ax = ∑ σ i ui viT x =∑ σ i ui (viT x) =∑ σ i (viT x )ui

Do

(ui )

.

là cơ sở trực chuẩn nên
r

k

i =1

i =1

|| Ax ||2 = ∑ σ i 2 (viT x) 2 ≤ ∑ σ i 2 (viT x) 2 + σ k 2


r

∑ (v

i = k +1

T
i

x) 2

.

Mặt khác,
k

σ k 2 ∑ (viT x )2 + σ k 2
i =1

r

∑

i = k +1

r

n

i =1


i =1

(viT x ) 2 = σ k 2 ∑ (viT x)2 ≤ σ k 2 ∑ (viT x)2 = σ k 2 || V T x ||2 = σ k 2 || x ||2

Do đó,
σk

2

r

∑ (v

i = k +1

T
i

x) ≤ σ k || x || −σ k
2

2

2

2

k


∑ (v
i =1

T
i

x) 2

Vậy
25