250
PHƯƠNG PHÁP PHÂN TÍCH GIÁ TRỊ ĐƠN RÚT GỌN
VÀ ỨNG DỤNG TRONG NÉN ẢNH
Bùi Nguyễn Nhật Minh1, Nguyễn Thị Kim Ngân2
1. Lớp K212BV.TOAN01, Trường Đại học Thủ Dầu Một
2. Khoa Sư phạm, Trường Đại học Thủ Dầu Một
TÓM TẮT
Bài viết trình bày lại phương pháp phân tích giá trị đơn (singular value decomposition- viết tắt
SVD) và phương pháp phân tích giá trị đơn rút gọn (truncated SVD) và ứng dụng trong nén ảnh.
Từ khóa: nén ảnh, SVD, truncated SVD.
1. GIỚI THIỆU
Việc tìm hiểu và vận dụng kiến thức Toán học trong thực tiễn rất hữu ích với sinh viên ngành
Toán. Nó không những giúp sinh viên có động lực học môn Toán hơn mà quan trọng giúp sinh viên
biết vận dụng kiến thức, kĩ năng đã học trong chương trình để áp dụng công việc thực tế khi làm trong
các cơ quan, công ty hay ở các cơ sở giáo dục.
Môn Đại số tuyến tính được giảng dạy ở năm nhất chương trình cử nhân Toán, cũng như các
chương trình khối ngành kĩ thuật và kinh tế. Ứng dụng của môn học này rất nhiều trong các ngành,
nhất là lĩnh vực công nghệ thông tin, khi máy tính nhận dữ liệu dưới dạng ma trận, vectơ. Vì vậy,
chúng tôi chọn nghiên cứu phương pháp phân tích giá trị đơn (singular value decomposition- viết tắt
SVD) và phương pháp phân tích giá trị đơn rút gọn (truncated SVD) và ứng dụng trong nén ảnh để
làm báo cáo tốt nghiệp. Kiến thức tập trung phần Đại số tuyến tính và sử dụng phần mềm Matlab đã
học trong chương trình để xử lí nén ảnh.
Bài viết này trình bày ngắn gọn nội dung của báo cáo tốt nghiệp gồm lí thuyết về phương pháp
phân tích giá trị đơn và phương pháp phân tích giá trị đơn rút gọn và phần ứng dụng sẽ sử dụng
phương pháp này để nén ảnh trong Matlab.
2. PHƯƠNG PHÁP PHÂN TÍCH GIÁ TRỊ ĐƠN VÀ PHƯƠNG PHÁP PHÂN TÍCH GIÁ TRỊ
ĐƠN RÚT GỌN
Nội dung này chúng tôi tham khảo tài liệu (D. Lay và nnk, 2016; Nguyễn Tiến Dũng, 2018)
2.1. Các giá trị đơn của một ma trận
Cho 𝐴 là một ma trận cấp 𝑚×𝑛. Khi đó 𝐴𝑇𝐴 đối xứng và và do đó có thể chéo hóa trực giao
được (xem (Lay và nnk.,2016, Định lý 2, trang 398)).
Gọi {𝑣1,...,𝑣𝑛} là một cơ sở trực chuẩn của ℝ𝑛 bao gồm các vectơ riêng của 𝐴𝑇𝐴, và
𝜆1,...,𝜆𝑛là các giá trị riêng tương ứng của 𝐴𝑇𝐴. Khi đó, với 1 ≤𝑖≤𝑛,
∥𝐴𝑣𝑖∥2=(𝐴𝑣𝑖)𝑇𝐴𝑣𝑖=𝑣𝑖𝑇𝐴𝑇𝐴𝑣𝑖=𝑣𝑖𝑇𝜆𝑖𝑣𝑖=𝜆𝑖.
Do đó các giá trị riêng của 𝐴𝑇𝐴 là không âm. Ta có thể sắp xếp các giá trị riêng của 𝐴𝑇𝐴 như
sau 𝜆1≥ 𝜆2≥...≥ 𝜆𝑛≥0.
Các giá trị đơn của 𝐴 là căn bậc hai các giá trị riêng của 𝐴𝑇𝐴, kí hiệu bởi 𝜎1,...,𝜎𝑛, và sắp xếp
theo thứ tự giảm dần
251
𝜎𝑖=√𝜆𝑖,1≤𝑖≤𝑛.
2.2 Phương pháp phân tích giá trị đơn
Định lý (xem (Lay và nnk.,2016, Định lý 10, trang 419))
Cho 𝐴 là một ma trận cấp 𝑚×𝑛, có hạng 𝑟. Khi đó tồn tại ma trận Σ (xem (Lay và
nnk.,2016,(3), trang 419)) có dạng
(Nguồn hình tham khảo tài liệu (Lay và nnk.,2016,(3), trang 419))
Ở đây, các phần tử nằm trên đường chéo của ma trân chéo 𝐷 là r giá trị đơn của 𝐴, 𝜎1≥...≥
𝜎𝑟>0, và tồn tại các ma trận trực giao 𝑈 cấp 𝑚×𝑚, ma trận trực giao 𝑉 cấp 𝑛×𝑛, (nghĩa là
𝑈,𝑉 là các ma trận vuông khả nghich và 𝑈−1=𝑈𝑇,𝑉−1=𝑉𝑇 xem (Lay và nnk.,2016, trang 346)
sao cho 𝐴𝑚×𝑛=𝑈𝑚×𝑚Σ𝑚×𝑛(𝑉𝑛×𝑛)𝑇. (1)
Chứng minh. Giả sử {𝑣1,...,𝑣𝑟} là một cơ sở trực chuẩn của ℝ𝑟gồm các vectơ riêng của 𝐴𝑇𝐴,
tương ứng với các giá trị riêng 𝜆1≥ 𝜆2≥...≥ 𝜆𝑟>0 của 𝐴𝑇𝐴. Khi đó, {𝐴𝑣1,...,𝐴𝑣𝑟} là một cơ sở
trực giao của không gian các vectơ cột của ma trận 𝐴 (xem (Lay và nnk.,2016, Định lý 9, trang 418)).
Chuẩn tắc hóa 𝐴𝑣𝑖, ta được một cơ sở trực chuẩn {𝑢1,...,𝑢𝑟}, với
𝑢𝑖=1
∥𝐴𝑣𝑖 ∥𝐴𝑣𝑖=1
𝜎𝑖𝐴𝑣𝑖
𝑣à 𝐴𝑣𝑖=𝜎𝑖𝑢𝑖,(1≤𝑖≤𝑟)
Mở rộng {𝑢1,...,𝑢𝑟} thành một cơ sở trực chuẩn {𝑢1,...,𝑢𝑚} của ℝ𝑚 và đặt
𝑈=[𝑢1𝑢2... 𝑢𝑚] 𝑣à 𝑉=[𝑣1𝑣2... 𝑣𝑟]
Theo cách xây dựng trên, 𝑈,𝑉 là các ma trận trực giao và
𝐴𝑉=[𝐴𝑣1... 𝐴𝑣𝑟0 ... 0]=[𝜎1𝑣1... 𝜎2𝑣𝑟0 ... 0]
Gọi 𝐷 là ma trận chéo với các phần tử nằm trên đường chéo là 𝜎1,...,𝜎𝑟 và ma trận Σ như
trong phát biểu định lý. Khi đó
(Phép tính trích từ (Lay và nnk.,2016, Định lý 10, trang 419))
Vì 𝑉 là ma trận trực giao nên 𝑈Σ𝑉𝑇=𝐴𝑉𝑉𝑇=𝐴.
Ví dụ. Xây dựng một phép phân tích giá trị đơn cho ma trận
𝐴=[411 14
8 7 −2]
252
Lời giải.
Bước 1. Chéo hóa trực giao ma trận 𝑨𝑻𝑨
Ta có 𝐴𝑇𝐴=[4 8
11 7
14 −2][411 14
8 7 −2]=[80 100 40
100 170 140
40 140 200]
Xét đa thức đặc trưng của 𝐴𝑇𝐴
𝑝(𝜆)=𝑑𝑒𝑡(𝐴𝑇𝐴−𝜆𝐼)=|80−𝜆 100 40
100 170−𝜆 140
40 140 200−𝜆|
Và 𝑝(𝜆)=0⟺𝜆=0ℎ𝑜ặ𝑐 𝜆=90 ℎ𝑜ặ𝑐 𝜆=360.
Với 𝜆1=360 thì vectơ riêng tương ứng là nghiệm của phương trình
(𝐴𝑇𝐴−360𝐼)𝑣=0⟺[−280 100 40
100 −190 140
40 140 −160][𝑥1
𝑥2
𝑥3]=0⟹𝑣1=(1
3,2
3,2
3)
Tương tự, với 𝜆2=90 thì vectơ riêng đơn vị tương ứng là 𝑣2=(−2
3,−1
3,2
3), với 𝜆3=
0 thì vectơ riêng đơn vị tương ứng là 𝑣3=(2
3,−2
3,1
3).
Bước 2. Xây dựng 𝑽 𝒗à 𝜮
Đăt 𝑉=[𝑣1𝑣2𝑣3]=
[
1
3−2
32
3
2
3−1
3−2
3
2
32
31
3
]
Ngoài ra,
𝐴𝑣1=[411 14
8 7 −2][1/3
2/3
2/3]=[18
6],𝐴𝑣2=[411 14
8 7 −2][−2/3
−1/3
2/3]=[3
−9]
Nên 𝜎1=√𝜆1=∥𝐴𝑣1∥=6√10, 𝜎2=√𝜆2=∥𝐴𝑣2∥=3√10.
Các giá trị đơn khác không là những phần tử nằm trên đường chéo của 𝐷. Đặt
𝐷=[6√10 0
0 3√10] 𝑣à Σ=[𝐷 0]=[6√10 0 0
0 3√10 0]
Bước 3. Xây dựng 𝑼
Vì 𝐴 có hạng 2 nên 2 cột đầu tiên của 𝑈 là các vectơ chuẩn tắc nhận được từ 𝐴𝑣1,𝐴𝑣2.
Ta có, 𝑢1=1
𝜎1𝐴𝑣1=[3/√10
1/√10],𝑢2=1
𝜎2𝐴𝑣2=[1/√10
−3/√10]
Đặt 𝑈=[𝑢1𝑢2]=[3/√10 1/√10
1/√10 −3/√10]
Vậy
𝑈Σ𝑉𝑇=[3/√10 1/√10
1/√10 −3/√10][6√10 0 0
0 3√10 0]
[
1
3−2
32
3
2
3−1
3−2
3
2
32
31
3
]
𝑇
=[411 14
8 7 −2]=𝐴.
2.3 Phương pháp phân tích giá trị đơn rút gọn
(xem tài liệu [5])
Khi nhân các hàng và các cột không của ma trận 𝛴 thì các thừa số đều là không nên ta có thể
biểu diển ma trận 𝐴 như sau
253
𝐴=[𝑢1𝑢2... 𝑢𝑟][𝜎10... 0
0 𝜎2... 0
⋮0⋮0⋱
... ⋮
𝜎𝑟]
[
𝑣1𝑇
𝑣2𝑇
⋮
𝑣𝑟𝑇
]
(2)
Nếu ta nhân các cột và hàng của các ma trận ở phương trình (2), ta được
𝐴=𝜎1𝑢1𝑣1𝑇+𝜎2𝑢2𝑣2𝑇+...+𝜎𝑟𝑢𝑟𝑣𝑟𝑇
Ví dụ. Từ phép phân tích giá trị đơn của ma trận ở ví dụ mục 2.2 ta có
[411 14
8 7 −2]=[3/√10 1/√10
1/√10 −3/√10][6√10 0
0 3√10][1/3 −2/3
2/3 −1/3
2/3 2/3]𝑇.
[411 14
8 7 −2]=𝜎1𝑢1𝑣1𝑇+𝜎2𝑢2𝑣2𝑇
=6√10[3/√10
1/√10][1/3 2/3 2/3]
+3√10[1/√10
−3/√10][−2/3 −1/3 2/3].
Trong ma trận 𝛴, các giá trị trên đường chéo là không âm và giảm dần 𝜎1≥...≥𝜎𝑟≥0.
Thông thường, chỉ một lượng nhỏ 𝜎𝑖mang giá trị lớn, các giá trị còn lại thường nhỏ và gần không.
Khi đó ta có thể xấp xỉ 𝐴 bằng tổng của 𝑘<𝑟 ma trận có hạng 1:
𝐴≈𝐴𝑘=𝜎1𝑢1𝑣1𝑇+𝜎2𝑢2𝑣2𝑇+...+𝜎𝑘𝑢𝑘𝑣𝑘𝑇.
Đây được gọi là phép phân tích giá trị đơn rút gọn của ma trân 𝐴.
Sai số của cách xấp xỉ trên là Frobenius norm của hiệu hai ma trận
∥𝐴−𝐴𝑘∥𝐹
2=∑𝑖=𝑘+1
𝑟𝜎𝑖2
Ví dụ. Trong ví dụ trên, ta giữ lại 2 giá trị đơn khác không 𝜎1,𝜎2. Và do đó
𝐴=𝐴2=𝜎1𝑢1𝑣1𝑇+𝜎2𝑢2𝑣2𝑇
=6√10[3/√10
1/√10][1/3 2/3 2/3]+3√10[1/√10
−3/√10][−2/3 −1/3 2/3].
3. ỨNG DỤNG PHƯƠNG PHÁP PHÂN TÍCH GIÁ TRỊ ĐƠN RÚT GỌN TRONG NÉN ẢNH
Ngôn ngữ lập trình Matlab (xem [3]) được xử dụng nhiều trong khối ngành Kĩ thuật. Sinh viên
cử nhân Toán được học những kiến thức căn bản về Matlab hỗ trợ quá trình học tập, giảng dạy Toán.
Ở đây, chúng tôi tham khảo một code về phép phân tích giá trị đơn rút gọn (xem [4]) và sử dụng một
hình ảnh về trường Đại học Thủ Dầu Một để nén ảnh
254
Nguồn: https://ducnbb.blogspot.com/p/truong-ai-hoc-thu-dau-mot-tieng-anh-thu.html
và được kết quả sau:
- Với 5 giá trị đơn, hình ảnh chưa rõ nét
- Với 30 giá trị đơn, hình ảnh đã có nét
- Với 80 giá trị đơn, hình ảnh rõ nét hơn