ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN
—————————

TRẦN THỊ HUYỀN

PHƯƠNG PHÁP GIẢI BÀI TOÁN BIỂU DIỄN THƯA

LUẬN VĂN THẠC SĨ KHOA HỌC

Hà Nội - 2017


ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN
—————————

TRẦN THỊ HUYỀN

PHƯƠNG PHÁP GIẢI BÀI TOÁN BIỂU DIỄN THƯA

Chuyên ngành: Cơ sở toán cho tin học
Mã số
: 60460110

LUẬN VĂN THẠC SĨ KHOA HỌC

NGƯỜI HƯỚNG DẪN KHOA HỌC: TS. VŨ TIẾN DŨNG

Hà Nội - 2017

LỜI CẢM ƠN
Được sự phân công của khoa Toán - Cơ - Tin học, Trường Đại học Khoa Học Tự
Nhiên, Đại Học Quốc Gia Hà Nội, được sự đồng ý của Thầy giáo hướng dẫn TS. Vũ Tiến
Dũng, tôi đã thực hiện đề tài "PHƯƠNG PHÁP GIẢI BÀI TOÁN BIỂU DIỄN THƯA".
Để hoàn thành luận văn này, tôi xin bày tỏ lòng biết ơn sâu sắc tới TS. Vũ Tiến
Dũng - người Thầy đã trực tiếp hướng dẫn và chỉ bảo giúp tôi hoàn thành luận văn thạc
sĩ.
Tôi cũng xin chân thành cảm ơn các Thầy, Cô giáo đã tận tình hướng dẫn, giảng
dạy trong suốt quá trình tôi học tập và rèn luyện tại trường.
Qua đây, tôi xin gửi lời cảm ơn tới gia đình, bạn bè, đồng nghiệp - những người
đã luôn bên cạnh cổ vũ, động viên, giúp đỡ tôi trong suốt quá trình học tập và thực hiện
luận văn này.
Mặc dù tôi đã vô cùng cố gắng thực hiện luận văn nhưng chắc rằng không thể
tránh khỏi những thiếu sót nhất định. Tôi rất mong được sự góp ý của quý Thầy, Cô giáo
và các bạn.
Tôi xin chân thành cảm ơn!.
Hà Nội, ngày..... tháng ..... năm 2017
Học viên

Trần Thị Huyền


BẢNG KÍ HIỆU, CHỮ VIẾT TẮT
STT VIẾT TẮT
1
An×m
2
c ∞
3

d
4
epsilon
5
I
6
M SE
7
MP
8
OM P
9
r
10
x pp
8
Ψ, φ
11
µ(A)
12
λt
13
γ
14
ε
15
x 22

Ý NGHĨA
Ma trận A kích thước m x n

Giá trị tuyệt đối tối đa của vector tương quan c
Hướng cập nhật
Sai số
Tập hỗ trợ chứa các chỉ số của các cột hỗ trợ trong A
Trung bình bình phương sai số
Matching Pursuit
Orthogonal Matching Pursuit
Vector dư
Lũy thừa P của chuẩn P
Ma trận đơn nguyên
Sự liên kết lẫn nhau của ma trận A
Là một số vô hướng bước thứ t
Kích cỡ bước đi
Giá trị ngưỡng
Bình phương chuẩn 2 của vector x

2


Danh sách hình vẽ
1

Ví dụ minh họa thuật toán OMP . . . . . . . . . . . . . . . . . . . . . . .

27

2

Tái tạo lại một bản vá của một hình ảnh từ các mẫu nén của nó bằng cách
sử dụng OMP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .


34

3

Hình ảnh thu được sau khi khôi phục miếng vá . . . . . . . . . . . . . . .

35

4

Khôi phục tín hiệu dựa trên phân tích QR với giá trị của phần tử khác 0
được sinh theo phân bố chuẩn . . . . . . . . . . . . . . . . . . . . . . . .

37

Khôi phục tín hiệu dựa trên phân tích Cholesky với giá trị của phần tử
khác 0 được sinh theo phân bố chuẩn . . . . . . . . . . . . . . . . . . . .

38

6

Các phần tử khác 0 sinh theo phân phối chuẩn. . . . . . . . . . . . . . . .

39

7

Các phần tử khác 0 sinh theo phân phối đều. . . . . . . . . . . . . . . . .


39

8

Các phần tử khác 0 sinh theo hàm dấu. . . . . . . . . . . . . . . . . . . .

40

9

Quá trình thực hiện của thuật toán LARS . . . . . . . . . . . . . . . . . .

42

10

Kết quả thực sau khi sửa lỗi trong một kênh truyền dữ liệu nhiễu thưa . .

56

11

Các Cột của ma trận A và vector đo lường y . . . . . . . . . . . . . . . . .

67

12

Các bước lựa chọn và cập nhật ở vòng lặp đầu tiên của OMP và LARS.

Sự thay đổi tương đối thu được bằng cách nhân ma trận A với vector cập
nhật nghiệm hiện tại . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

69

Các bước lựa chọn và cập nhật ở vòng lặp thứ hai (cuối cùng) của OMP
và LARS. Sự thay đổi tương đối thu được bằng cách nhân ma trận A với
vector cập nhật nghiệm hiện tại . . . . . . . . . . . . . . . . . . . . . . .

70

Hệ số nghiệm của vector được xây dựng lại trên các vòng lặp của OMP
và LARS, và chuẩn sai số của Euclide giữa vector x và vector xây dựng
lại sau khi các thuật toán chấm dứt . . . . . . . . . . . . . . . . . . . . . .

71

So sánh mối liên hệ độ đo và độ thưa giá trị trung bình MSE . . . . . . .

73

5

13

14

15

3



Danh sách bảng
1

Thuật toán Matching Pursuit (MP) . . . . . . . . . . . . . . . . . . . . . .

23

2

Thuật toán ORTHOGONAL MATCHING PURSUIT (OMP) . . . . . . .

25

3

Thuật toán OMP dựa trên phân tích QR . . . . . . . . . . . . . . . . . . .

29

4

Thuật toán OMP dựa trên phân tích Cholesky . . . . . . . . . . . . . . . .

31

5

Đánh giá độ phức tạp của OMP dựa trên phân tích QR và Cholesky. . . .


33

6

Thuật toán LARS cơ bản . . . . . . . . . . . . . . . . . . . . . . . . . . .

47

7

Thuật toán LARS cải biên . . . . . . . . . . . . . . . . . . . . . . . . . .

53

8

So sánh các bước của hai thuật toán OMP VÀ LARS . . . . . . . . . . . .

59

9

Bước cập nhật tập hỗ trợ trong các thuật toán OMP và LARS dạng cải
tiến và dạng chưa cải tiến. . . . . . . . . . . . . . . . . . . . . . . . . . . .

61

So sánh bước cập nhật vector nghiệm của OMP và LARS trước và sau
khi chỉnh lại cập nhật. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .


64

10

4


Mục lục
Chương 1 Tổng quan về bài toán biểu diễn thưa

9

1.1

Sơ lược về bài toán biểu diễn thưa . . . . . . . . . . . . . . . . . . . . . .

9

1.2

Bài toán biểu diễn thưa [2] . . . . . . . . . . . . . . . . . . . . . . . . . .

10

1.3

Kiến thức trang bị [11] . . . . . . . . . . . . . . . . . . . . . . . . . . . .

11


1.3.1

Một số định nghĩa . . . . . . . . . . . . . . . . . . . . . . . . . .

11

1.3.2

Phân phối đều, phân phối chuẩn Gauss . . . . . . . . . . . . . . .

12

1.3.3

Tích vô hướng, các định nghĩa và tính chất của không gian Hilbert 13

1.3.4

Độ dài và góc . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

14

1.3.5

Hệ trực giao, hệ trực chuẩn, cơ sở trực giao, cơ sở trực chuẩn . .

15

1.3.6


Phép biến đổi trực giao . . . . . . . . . . . . . . . . . . . . . . . .

15

Tính chất không chắc chắn và tính duy nhất nghiệm của bài toán . . . . .

16

1.4.1

Trường hợp hai ma trận trực giao . . . . . . . . . . . . . . . . . .

16

1.4.2

Mối liên hệ giữa tính chất không chắc chắn với tính duy nhất
nghiệm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

18

Phân tích tính duy nhất nghiệm trong trường hợp tổng quát . . . . . . . .

18

1.5.1

Tính duy nhất nghiệm thông qua Spark . . . . . . . . . . . . . . .


18

1.5.2

Tính duy nhất nghiệm thông qua mối liên kết lẫn nhau (Uniqueness via the Mutual - Coherence) . . . . . . . . . . . . . . . . . .

18

1.4

1.5

Chương 2 Một số thuật toán giải bài toán biểu diễn thưa và ứng dụng
2.1

Thuật toán Orthogonal Matching Pursuit (OMP) . . . . . . . . . . . . . .

21

2.1.1

Thuật toán MP với ma trận từ điển A tùy ý [1] . . . . . . . . . . .

21

2.1.2

Thuật toán Orthogonal Matching Pursuit (OMP)[2] . . . . . . . .

24


2.1.3

Các phương pháp giải phương trình đại số tuyến tính trong thuật
toán OMP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

28

Một số kết quả thực nghiệm . . . . . . . . . . . . . . . . . . . . .

33

Thuật toán Least Angle Regression (LARS) [1] . . . . . . . . . . . . . .

40

2.1.4
2.2

21

5


2.2.1

Thuật toán LARS cơ bản. . . . . . . . . . . . . . . . . . . . . . .

40


2.2.2

Thuật toán LARS cải biên để giải quyết bài toán LASSO . . . . .

48

2.2.3

Định lý hội tụ của thuật toán trong trường hợp tổng quát. . . . . .

54

2.2.4

Một số kết quả thực nghiệm[1] . . . . . . . . . . . . . . . . . . .

54

Chương 3 Phân tích và so sánh giữa hai thuật toán OMP và LARS

57

3.1

Các bước thuật toán . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

57

3.2


Xây dựng lại bước cập nhật tập hỗ trợ . . . . . . . . . . . . . . . . . . . .

60

3.3

Xây dựng lại bước cập nhật vector nghiệm . . . . . . . . . . . . . . . . .

61

3.4

Phân tích Hiệu suất . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

66

3.4.1

Thời gian hội tụ . . . . . . . . . . . . . . . . . . . . . . . . . . . .

66

3.4.2

Độ chính xác . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

66

Mối liên hệ giữa kích thước ma trận độ đo và độ thưa dựa trên trung bình
bình phương sai số . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .


72

3.5

6


Lời mở đầu
Bài toán biểu diễn thưa xuất hiện nhiều trong các bài toán thực tế thuộc nhiều
lĩnh vực khác nhau của đời sống, đặc biệt trong các lĩnh vực xử lý tín hiệu, xử lý hình
ảnh, học máy và thị giác máy tính, ví dụ như các bài toán: khử nhiễu ảnh, xử lý ảnh mờ,
inpainting, khôi phục ảnh, phân lớp ảnh và phân vùng ảnh.
Những kết quả nghiên cứu đầu tiên về bài toán biểu diễn thưa xuất hiện trong bài
báo của Stephane Mallat và Zhifeng Zang vào năm 1993, trong đó các tác giả giới thiệu
khái niệm từ điển thay thế cho các phép biến đổi dựa trên các cơ sở truyền thống (cơ sở
Fourierr, cơ sở Wavelet, vv. . . ). Trong công trình này, tác giả nhận định với một từ điển
cho trước, bài toán biểu diễn thưa hay việc tìm biểu diễn hay xấp xỉ thưa nhất của một tín
hiệu dựa trên từ điển sẽ linh hoạt và khó hơn trường hợp tìm biểu diễn thưa dựa trên một
cơ sở truyền thống, tương ứng. Nghiên cứu của B. K. Natarajan năm 1995 đã chỉ ra rằng
bài toán biểu diễn thưa thuộc lớp các bài toán NP-hard. Cũng trong bài báo của Stephane
Mallat và Zhifeng Zang năm 1993, các tác giả đã đề xuất ý tưởng giải bài toán biểu diễn
thưa (thuật toán matching persuit) mà ý tưởng cốt lõi của thuật toán đã trở thành cơ sở
nền tảng phát triển của nhiều thuật toán được đề xuất sau này. Ngày nay, kỹ thuật này
được xem là một trong các kỹ thuật chính để giải bài toán biểu diễn thưa và thường được
gọi là kỹ thuật tìm kiếm tham (greedy pursuit technique).
Vào năm 1998, Scott Shaobing Chen, David Donoho và Michael Saunders (Chen
và cộng sự) đã giới thiệu một kỹ thuật tìm kiếm khác sử dụng kỹ thuật nới lỏng bằng
cách thay thế bài toán biểu diễn thưa với tiêu chuẩn chọn nghiệm dựa trên chuẩn 0 bằng
bài toán nới lỏng là bài toán tối ưu lồi với tiêu chuẩn chọn nghiệm dựa trên chuẩn 1 .

Trong một số trường hợp, các tác giả đã chỉ ra rằng nghiệm của bài toán biểu diễn thưa
và nghiệm của bài toán nới lỏng là trùng nhau. Khi đó, rất nhiều các phương pháp tối ưu
lồi đã biết có thể được sử dụng để giải bài toán biểu diễn thưa.
Năm 2001, Donoho và Huo đã đề xuất và giải quyết một phần bài toán mà sau
này đã trở thành câu hỏi chìa khóa trong mọi nghiên cứu lý thuyết về bài toán biểu diễn
thưa, đó là với điều kiện nào đặt ra thì nghiệm của bài toán biểu diễn thưa có thể được
tìm thấy bằng các kỹ thuật tìm kiếm. Những phân tích của Donoho và Huo trong bài báo
cung cấp những cơ sở lý thuyết cần thiết cho các nghiên cứu, đề xuất các thuật toán giải
bài toán biểu diễn thưa của rất nhiều nhà khoa học trong và ngoài nước sau này dựa trên
các kỹ thuật tìm kiếm.

7


Nhận thấy tầm quan trọng của bài toán biểu diễn thưa đối với các ứng dụng thực tế
và việc giải quyết bài toán này đã và đang được sự quan tâm nghiên cứu bởi rất nhiều nhà
khoa học trong và ngoài nước. Trong luận văn này, tôi tập trung tìm hiểu một số thuật
toán giải bài toán biểu diễn thưa. Và tôi đã quyết định chọn đề tài " PHƯƠNG PHÁP
GIẢI BÀI TOÁN BIỂU DIỄN THƯA" với mục đích, đối tượng và nội dung nghiên cứu
như sau:
Mục đích: Tìm hiểu một số phương pháp giải bài toán biểu diễn thưa.
Đối tượng nghiên cứu: Bài toán biểu diễn thưa, thuật toán MP, OMP, phân tích
OMP dựa trên QR và Cholesky, thuật toán LARS cơ bản, thuật toán LARS cải biên.
Nội dung nghiên cứu của luận văn: Nghiên cứu tổng quan bài toán biểu diễn thưa,
tập trung tìm hiểu về thuật toán OMP và thuật toán LARS cải biên , so sánh đánh giá
hiệu quả của hai thuật toán khi áp dụng giải bài toán biểu diễn thưa.
Dựa vào mục đích đối tượng và nội dung nghiên cứu, bố cục luận văn gồm 3
chương chính cùng với phần mở đầu và phần kết luận.
Chương 1: Tổng quan về bài toán biểu diễn thưa và kiến thức chuẩn bị
Chương 2: Một số thuật toán giải bài toán biểu diễn thưa và ứng dụng

Chương 3: So sánh hai thuật toán OMP và thuật toán Lars cải biên

8


Chương 1
1.1

Tổng quan về bài toán biểu diễn thưa

Sơ lược về bài toán biểu diễn thưa

Trong những năm gần đây xuất hiện một chủ đề được nhiều nhà khoa học quan
tâm đó là bài toán "Nén cảm biến (CS)". Bài toán "Biểu diễn thưa" có nguồn gốc xuất
phát từ bài toán "Nén cảm biến". Người đầu tiên đề xuất những khái niệm cơ sở về nén
cảm biến đó là tác giả Donoho.
Lý thuyết nén cảm biến chỉ ra được nếu một tín hiệu ban đầu có tính chất thưa, tín
hiệu này có thể được phục hồi lại chỉ bằng một số giá trị đo được, ít hơn nhiều so với số
lượng các giá trị được để xuất bởi các lý thuyết lấy mẫu đã sử dụng trước đây như định lý
lấy mẫu Shannon (SST). Từ quan điểm toán học, Candes và các công sự đã chứng minh
tính đúng đắn của lý thuyết nén cảm biến, nghĩa là tín hiệu ban đầu có thể được tái tạo
lại chính xác chỉ sử dụng một số lượng nhỏ các hệ số trong biến đổi Fourier. Baraniuk
đưa ra các phân tích một số trường hợp cụ thể của lý thuyết nén cảm biến và trình bày
một số thuật toán khôi phục tín hiệu khác. Tất cả các lý thuyết này đã đặt nền móng cho
lý thuyết nén cảm biến và cung cấp cơ sở lý thuyết cho các nghiên cứu trong tương lai.
Một số lượng lớn các thuật toán dựa trên lý thuyết nén cảm biến đã được đề xuất để giải
quyết các bài toán khác nhau trong các lĩnh vực khác nhau. Lý thuyết nén cảm biến có
thể được xem bao gồm ba thành phần cơ bản: lý thuyết biểu diễn thưa, độ đo mã hóa và
các thuật toán khôi phục. Như vậy, chúng ta có thể khẳng định lý thuyết biểu diễn thưa
là một điều kiện tiên quyết không thể thiếu của lý thuyết nén cảm biến và được xem là

kỹ thuật nổi bật nhất được sử dụng để giải quyết một số vấn đề khó khăn xuất hiện trong
nhiều lĩnh vực khác nhau của đời sống.
Bài toán biểu diễn thưa có nhiều ứng dụng trong thực tế, thu hút sự chú ý của
nhiều nhà khoa học. Các thuật toán dựa trên lý thuyết biểu diễn thưa tốn ít thời gian và
thuận lợi trong việc lưu trữ mẫu, đã được đề xuất để giải quyết hiệu quả các bài toán xử
lý tín hiệu.
Trong phần tiếp theo chúng ta tìm hiểu về bài toán biểu diễn thưa và một số kỹ
thuật phổ biến thường được dùng để giải quyết bài toán biểu diễn thưa.

9


1.2

Bài toán biểu diễn thưa [2]

Để xét bài toán biểu diễn thưa, chúng ta bắt đầu với một bài toán giải hệ phương trình đại
số tuyến tính dưới xác định:
Ax = y, m > n
(1.2.1)
Trong đó:
- y : là một tín hiệu cần được xử lý
- x: là nghiệm thưa cần phải tìm của bài toán.
- A: là ma trận từ điển có các cột được chuẩn hóa theo chuẩn

2,

A ∈ Rm×n

Giả sử ma trận A có hạng đầy đủ, khi đó phương trình (1.2.1) có vô số nghiệm.

Trong các bài toán kỹ thuật, chúng ta cần chọn ra một nghiệm tốt nhất trong số các
nghiệm của phương trình (1.2.1). Để lựa chọn được nghiệm này, chúng ta cần một hàm
đo lường chất lượng J(x) để xếp hạng các nghiệm dựa trên một số tiêu chí và dựa theo
xếp hạng này chúng ta chọn được nghiệm mà chúng ta mong muốn. Thực chất, ta cần
giải quyết bài toán: Tìm:
x = argminJ(x) thỏa mãn điều kiện Ax = y

(1.2.2)

Ta có bài toán thay thế như sau:
P0 : x = arg min

x

x

0

thỏa mãn điều kiệnAx = y

(1.2.3)

Trong thực tế dữ liệu thu được của chúng ta có thể tồn tại nhiễu, và chúng ta không
mong đợi tìm được nghiệm hoàn hảo nhất cho bài toán Ax = y . Thay vào đó chúng ta có
sai số giữa Ax và y , dẫn đến bài toán thay thế (P0∈ ) như sau. Tìm:
x = arg min
x

x


0

thỏa mãn Ax − y

2

(1.2.4)

Trong đó liên quan chặt chẽ với tính chất nhiễu.
Để hiểu được sự phức tạp của bài toán trên, ta xem xét một phương pháp giải trực
tiếp bài toán biểu diễn thưa. Ta định nghĩa thuật ngữ tập hỗ trợ ký hiệu là sup(x) là tập
các phần tử khác 0 của x. Với L = 1, chúng ta xét tất cả các tập hỗ trợ {Si }Ii=1 gồm L
phần tử (với I = (m
L ) là tập hỗ trợ). Đối với mỗi tập hỗ trợ, chúng ta sử dụng chỉ số cột từ
ma trận A có chỉ số trong tập hỗ trợ để biểu diễn y . Điều này có thể được thực hiện bằng
cách giải bài toán bình phương tối thiểu Least-Squares (LS):
min
x

Ax − y

2

thỏa mãnSup(x) = Sj

10

(1.2.5)



Nếu kết quả thu được nhỏ hơn , chúng ta đã tìm ra nghiệm của bài toán và bài
toán có thể kết thúc. Nếu không có tập hỗ trợ nào đưa ra được sai số thấp hơn ngưỡng ,
L được tăng lên và quá trình thực hiện được lặp lại.
Ví dụ: Xét bài toán biểu diễn thưa trong trường hợp m=2000, giả sử kích thước
tập hỗ trợ đã biết L = 15 và đòi hỏi 10−9 giây để giải quyết bài toán bình phương tối
thiểu LS, khi đó chúng ta sẽ mất 7.5.1023 năm để giải quyết bài toán biểu diễn thưa. Điều
này là do độ phức tạp hàm mũ của bài toán và bài toán được biết là bài toán thuộc lớp
NP-HARD. Do vậy để giải bài toán biểu diễn thưa, chúng ta thường dùng các thuật toán
xấp xỉ.

1.3
1.3.1

Kiến thức trang bị [11]
Một số định nghĩa

Tập lồi
Tập A ⊂ X được gọi là tập lồi, nếu:
∀x1 , x2 ∈ A, ∀λ ∈ R : 0 ≤ λ ≤ 1 =⇒ λx1 + (1 − λ)x2 ∈ A

Hàm lồi
Giả sử D là tập lồi trong không gian X , hàm f : D −→ (−∞, +∞], khi đó f lồi trên D
khi và chỉ khi
f (λx + (1 − λ)y) ≤ λf (x) + (1 − λ)f (y)

(∀λ ∈ [0, 1], ∀x, y ∈ D)

Bất đẳng thức Jensen
Giả sử f : X −→ (−∞, +∞], khi đó f là hàm lồi khi và chỉ khi
m


∀λi ≥ 0(i = 1...m),

λi = 1, ∀x1 , ..., xm ∈ X ta luôn có
i

f (λ1 x1 + ... + λm xm ) ≤ λ1 f (x1 ) + ... + λm f (xm )

Tổ hợp lồi
n

λi xi gọi là tổ hợp lồi của x1 , ..., xn ∈ Rn nếu:

Tổ hợp tuyến tính
i=1

n

λi ≥ 0, ∀i,

λi = 1
i=1

11


Dưới đạo hàm (Subgradient)
Cho f : Rn −→ R ∪ {+∞}. Ta nói x∗ ∈ Rn là dưới đạo hàm của f tại x nếu
< x∗ , z − x > +f (x)


f (z), ∀z

Ký hiệu tập hợp tất cả các đạo hàm của f tại x là ∂f (x)
Định lý 1. Cho f là hàm lồi, khả dưới vi phân trên Rn , khi đó
y ∈ arg minn f (x)
x∈R

Khi và chỉ khi
0 ∈ ∂f (y)

1.3.2

Phân phối đều, phân phối chuẩn Gauss

a. Phân bố đều
Biến ngẫu nhiên X được gọi là có phân bố đều trên [a, b], ký hiệu X ∼ U ([a, b])
nếu hàm mật độ của X xác định bởi:

 1
(a ≤ x ≤ b)
f (x) = b − a
0
nếu ngược lại
Vậy X có khả năng nhận giá trị trong đoạn [a, b] là đều nhau.
Các tham số đặc trưng của biến ngẫu nhiên có phân bố đều
- Kỳ vọng: µ = E[X] = a+b
2
2
2
- Phương sai: σ = V arX = (b−a)

12
b. Phân phối chuẩn (hay còn gọi là phân phối chuẩn Gauss)
Biến ngẫu nhiên liên tục X có phân phối chuẩn với tham số µ và σ 2 , ký hiệu
X ∼ N (µ, σ 2 ) nếu hàm mật độ có dạng: f (x) =

√1 e−
σ 2π

(x−µ)2
2σ 2

, −∞ < x < +∞

Các tham số đặc trưng của biến ngẫu nhiên có phân bố chuẩn
- Kỳ vọng: EX = µ
- Phương sai: V arX = σ 2

12


1.3.3

Tích vô hướng, các định nghĩa và tính chất của không gian Hilbert

Định nghĩa 1. 1. Cho không gian vector X trên trường số K (K = R hoặc K = C ). Một
ánh xạ từ X × X vào K , (x, y) −→< x, y > được gọi là tích vô hướng trên X nếu nó thỏa
mãn một số điều kiện sau:
a. x, x ≥ 0, ∀x ∈ X
x, x = 0 ⇐⇒ x = ∅
b. y, x = x, y ( y, x = x, y nếu K = R) ∀x, y ∈ X


c. x + x y = x, y + x , y ∀x, x , y ∈ X
d. λx, y = λ x, y ∀x, y ∈ X , λ ∈ R
Từ tính chất 1 và tính chất 4 ta cũng có:
x , y + y = x, y + x, y , x, λy = λ x, y
2. Nếu ., . là một tích vô hướng trên X thì ánh xạ x −→ ( x, x ) là một chuẩn trên X ,
gọi là chuẩn sinh bởi tích vô hướng
3. Nếu ., . là tích vô hướng trên X thì cặp (X, ., . ) gọi là không gian tiền Hilber (hay
không gian Unita, không gian với tích vô hướng). Sự hội tụ, khái niệm tập mở,...,trong
(X, ., . ) luôn được gắn với chuẩn sinh bởi ., . . Nếu không gian định chuẩn tương ứng
đầy đủ thì ta nói (X, ., . ) là không gian Hilbert.
Chú ý: Từ tính chất tuyến tính của tích vô hướng theo từng biến (1, 2) ta có công
thức sau:
1. < 0, α >=< α, 0 >= 0 ∀ α ∈ V
n
2. Giả sử α = m
i=1 ai αi β =
i=1 bj βi thì
m

< α, β >=<

n

ai α i ,
i=1

m

n


bi βi >= ai bi =
i=1

< αi βj >
i=1 i=1

Nếu <.,.> là một tích vô hướng trên V thì ánh xạ α −→
trên V , gọi là chuẩn sinh bởi tích vô hướng.

√
< α, α >, là một chuẩn

Nếu <.,.> là tích vô hướng trên V thì cặp (V,<.,.>) gọi là một không gian tiền Hilbert
(hay không gian Unita, không gian tích vô hướng).
Các tính chất của không gian Hilbert:
∇ Bất đẳng thức Cauchy-Schwartz: |< α, β >|
∇

α+β

2

+

α−β

2=

2( α


2

+

13

β

2)

α

.

β

(Đẳng thức hình bình hành)


∇ Nếu limαn = a, limβn = b thì lim < αn , βn >=< αn , βn >=< a, b >

Sự trực giao:
Định nghĩa 2. Cho không gian với tích vô hướng, (V, < ., . >) và α, β ∈ V , y ∈ X ,
∅=M ⊂V
∇ Ta nói α Trực giao với β (ký hiệu α ⊥ β ) Nếu < α, β >= 0.
∇ Nếu α ⊥ β ∀ β ∈ M thì ta viết α ⊥ M . Ta ký hiệu M ⊥ = α ∈ XV : α ⊥ M

Phân tích trực giao
Định nghĩa 3. Nếu M là một không gian con đóng của không gian Hilbert (v, <

., . >) thì mỗi α ∈ V có duy nhất phân tích ở dạng
α = β + z, β ∈ M, z ∈ M ⊥

(1.3.1)

Phần tử β trong (1.3.1) gọi là hình chiếu trực giao của α lên và có tính chất
α−β
α − β =inf
β ∈M

1.3.4

Độ dài và góc

Định nghĩa 4. Cho E là không gian vector Euclide. Với mỗi vector α ∈ E , độ dài của
vector α, ký hiệu là α là số thực không âm, xác định như sau:
α =

√

< α, α >

Ví dụ: E = Rn , x = (x1 , ..., xn ) ∈ Rn thì x =

x21 + ... + xn2

Định nghĩa 5. Cho E là không gian Euclide. Ta gọi góc giữa hai vector khác không
α, β ∈ E là số thực ϕ ∈ [0, π] được xác định bởi:
cos(α) =


<α,β>
α . β

Hai vector α, β ∈ E gọi là trực giao, ký hiệu là α ⊥ β nếu < α, β >= 0
Công thức pitago
∀α, β ∈ E, α ⊥ β ⇔ α + β

14

2=

α

2

+

β

2


1.3.5

Hệ trực giao, hệ trực chuẩn, cơ sở trực giao, cơ sở trực chuẩn

Hệ vector α1 , ..., αm ∈ E gọi là hệ trực giao nếu chúng đôi một trực giao, nghĩa là
ai ⊥ aj ∀i = j

Hệ vector α1 , ..., αm ∈ E gọi là hệ trực chuẩn nếu chúng là hệ trực giao và độ dài

của mỗi vector αi đều bằng 1
Như vậy, hệ vector α1 , ..., αm ∈ E là hệ trực chuẩn khi và chỉ khi:
αi , αj =

0

nếu i = j

1

i=j

Một cơ sở của E là hệ trực chuẩn được gọi là cơ sở trực chuẩn của E .
Nếu α1 , ..., αm ∈ E là một hệ trực giao, không chứa vector 0 của E thì hệ: u1 = αα11 ,
m
u2 = αα22 ,..., um = ααm
, là một hệ trực chuẩn của E .
Phép biến đổi trên ta gọi là phép trực chuẩn hóa một hệ vector trực giao. nếu
α1 , ..., αm là cơ sở trực giao của E thì trực chuẩn hóa cơ sở đó, ta sẽ được một
cơ sở trực chuẩn của E
Chú ý: Một hệ vector trực giao không chứa vector không thì độc lập tuyến tính

1.3.6

Phép biến đổi trực giao

Ma trận trực giao: Ma trận vuông A gọi là ma trận trực giao nếu A−1 = AT (AT là ma
trận chuyển vị của ma trận A).
Định nghĩa 6. Cho E là không gian vector Euclide. Môt phép biến đổi tuyến tính f của
E gọi là phép biến đổi trực giao của E nếu f bảo toàn tích vô hướng, tức là:

∀α, β ∈ E < α, β >=< f (α), f (β) >

Tính chất cơ bản nhất của phép biển đổi trực giao được cho trong định lý sau:
Định lý 2. Cho f là biến đổi tuyến tính của không gian vector Euclide E . Khi đó các
khẳng định sau là tương đương:
- f là phép biến đổi trực giao
- Ma trận f trong một cơ sở trực chuẩn là ma trận trực giao

15


1.4

Tính chất không chắc chắn và tính duy nhất nghiệm của bài toán

Đối với hệ phương trình tuyến tính không xác định, Ax = y (Ma trận A ∈ Rn×m với
n < m có hạng đầy đủ), chúng ta cần có một số câu hỏi sau:
1. Hệ có nghiệm duy nhất khi nào?
2. Hệ có nghiệm x thỏa mãn Ax = y , với điều kiện nào của x thì x là nghiệm của bài toán
P0 ?
Phần tiếp theo sẽ trả lời các câu hỏi trên và một số câu hỏi mở rộng. Để đơn giản,
thay vì trả lời trực tiếp các câu hỏi trên với trường hợp tổng quát, trước tiên chúng ta
xét trường hợp ma trận A đặc biệt, sau đó mở rộng câu trả lời trong trường hợp A tổng
quát[3].

1.4.1

Trường hợp hai ma trận trực giao

Trước tiên chúng ta xét bài toán (P0 ) trong trường hợp cụ thể: Ma trận A được

kết hợp từ hai ma trận trực giao, Ψ và Φ. Ví dụ A là sự kết hợp của ma trận đơn vị I và
ma trận Fourier F , A = [I, F ]. Trong trường hợp như vậy, hệ phương trinh y = Ax là hệ
dưới xác định và khi đó mỗi tín hiệu y cho trước có nhiều cách biểu diễn y như là một tổ
hợp tuyến tính của các spikes (các cột của ma trận đơn vị) và các sinusoids (tức là các
cột của ma trận fourier). Một nghiệm thưa của phương trình trên là một biểu diễn của tín
hiệu dưới dạng tổ hợp tuyến tính của một số sinusoids và một số spikes.

a.

Một nguyên tắc không chắc chắn

Trong phần này, chúng tôi khẳng định một tín hiệu không thể được biểu diễn
thưa cả về thời gian và tần số. Giả sử chúng ta có một vector khác vector không y và tập
cơ sở trực giao Ψ và Φ. Sau đó y có thể được biểu diễn dưới dạng tổ hợp tuyến tính của
các cột ma trận Ψ cũng như các cột của ma trận Φ
y = Ψα = Φβ

(1.4.1)

Rõ ràng α và β được xác định duy nhất. Trong trường hợp đặc biệt, Ψ chỉ đơn giản
là ma trận đơn vị, và Φ là ma trận biến đổi của Fourier. Khi đó, ma trận Ψ là đại diện cho
miền thời gian của tín hiệu y và Φ là biểu diễn cho miền tần số.

16


Đối với mỗi cặp tùy ý (Ψ.Φ), một hiện tượng thú vị xảy ra: chỉ α hoặc β có tính
chất thưa. Tuy nhiên, điều này rõ ràng là phụ thuộc vào khoảng cách giữa Ψ và Φ, vì nếu
cả hai là như nhau, chúng ta có thể dễ dàng xây dựng y từ một trong các cột Ψ và nhận
được một giá trị nhỏ nhất có thể trong cả α và β . Do đó, để xác định giá trị gần đúng giữa

chúng, chúng ta cần một hệ số liên kết lẫn nhau giữa chúng:
Định nghĩa 7. Đối với ma trận A được xây dựng từ một cặp cơ sở trực giao Ψ và Φ,
chúng ta xác định hệ số liên kết µ(A) là cực đại của tích vô hướng giữa các cột từ hai cơ
sở này.
proximity(Ψ, Φ) = µ(A) = max1≤i,j≤n | ΨTi Φj |
(1.4.2)
Chú ý: Hệ số liên kết của hai ma trận cơ sở trực giao thỏa mãn điều kiện:
√1
n

≤ µ(A) ≤ 1

Định lý 3. Đối với mỗi cặp ngẫu nhiên các cơ sở trực giao Ψ , Φ với hệ số liên kết µ(A),
và cho một vector y bất kỳ khác 0 có các vector biểu diễn thưa α và β trong các cơ sở
tương ứng, thì ta có bất đẳng thức sau:
Nguyên lý bất định 1:
α

0

+

β

0≥

2
µ(A)

(1.4.3)


b. Sự không chắc chắn của các nghiệm dự phòng (Uncertainty of Redundant Solutions)[8]
Định lý 4. Giả sử x1 ,x2 là 2 nghiệm phân biệt của hệ phương trình tuyến tính [Ψ, Φ]x = y
khi đó chỉ có thể có tối đa không quá một nghiệm thưa và thỏa mãn nguyên tắc không
chắc chắn sau:
Nguyên lý bất định 2:
x1

0

+

x2

0≥

2
µ(A)

(1.4.4)

Tiếp theo, chúng ta tìm hiểu về mối liên hệ giữa tính chất không chắc chắn và tính
duy nhất nghiệm

17


1.4.2

Mối liên hệ giữa tính chất không chắc chắn với tính duy nhất

nghiệm

Định lý 5. Nếu một nghiệm của hệ phương trình [Ψ, Φ]x = y có ít hơn

1
phần tử khác
µ(A)

0, thì ta khẳng định nghiệm này là nghiệm thưa duy nhất của hệ.

1.5
1.5.1

Phân tích tính duy nhất nghiệm trong trường hợp tổng quát
Tính duy nhất nghiệm thông qua Spark

Một tính chất rất quan trọng cho việc nghiên cứu tính duy nhất nghiệm là hệ số
Spark của ma trận A, được đưa ra bởi Donoho và Elad vào năm 2003. Spark là một cách
để mô tả không gian null của một ma trận A sử dụng chuẩn 0 . Chúng ta bắt đầu với định
nghĩa sau:
Định nghĩa 8. Spark của một ma trận A là số lượng các cột phụ thuộc tuyến tính nhỏ
nhất của ma trận A.
Định lý sau sẽ cho ta một tiêu chuẩn đơn giản để kiểm tra tính duy nhất của nghiệm
thưa dựa vào spark.
Định lý 6. (Tính duy nhất nghiệm - spark): Nếu một hệ phương trình tuyến tính Ax = y
có một nghiệm x thỏa mãn điều kiện x
của hệ

1.5.2


0<

spark(A)
, khi đó x là nghiệm thưa duy nhất
2

Tính duy nhất nghiệm thông qua mối liên kết lẫn nhau (Uniqueness via the Mutual - Coherence)

Khi chúng ta giải quyết bài toán P0 , giá trị của Spark thực sự khó ước lượng, vì
vậy chúng ta quan tâm đến những cách đơn giản để đảm bảo tính duy nhất nghiệm. Một
cách rất đơn giản là khai thác mối liên kết lẫn nhau của ma trận A, được định nghĩa bằng
cách khái quát định nghĩa cho trường hợp A là kết hợp cả hai cơ sở trực chuẩn. Trong
trường hợp đơn giản trên, việc tính toán cho ma trận Gram AT A dẫn tới:

18


AT A =

I

ΨT Φ

ΦT Ψ

I

Như vậy, mối liên kết lẫn nhau được xác định theo định nghĩa trên đối với trường
hợp này thu được là giá trị tuyệt đối cực đại của các phần tử nằm ngoài đường chéo của
ma trận Gram này. Tương tự như vậy, chúng tôi có định nghĩa khái quát khái niệm này

như sau:
Định nghĩa 9. Một liên kết lẫn nhau của một ma trân A là giá trị tuyệt đối lớn nhất được
chuẩn hóa của tích vô hướng giữa các vector cột khác nhau của ma trận A. Ta ký hiệu
cột thứ k của ma trận A là ak , mối liên kết lẫn nhau được cho bởi:
µ(A) = max1≤i,j≤m,i=j

| aTi aj |
ai 2 aj

(1.5.1)
2

Mối liên kết lẫn nhau là một cách để mô tả sự phụ thuộc lẫn nhau giữa các cột của
ma trận A. Đối với một ma trận unitary, các cột là các cặp trực giao, vì vậy mối liên kết
lẫn nhau là 0. Đối với ma trận tổng quát với số cột nhiều hơn hàng m > n, µ là số dương,
và chúng ta mong muốn giá trị nhỏ nhất có thể gần giá trị 0.
Chúng ta đã thấy rằng đối với ma trận A được tạo thành từ hai cơ sở trực giao
A = [Ψ, Φ] mối liên kết lẫn nhau thỏa mãn điều kiện √1n ≤ µ(A) ≤ 1. Khi xét các ma trận
trực giao ngẫu nhiên có kích thước n × m, các tác giả Donoho và Huo đã chỉ ra rằng các
ma trận này xu hướng không liên kết, với ý nghĩa rằng µ(An,m ) thường tỷ lệ thuận với
log nm
n với n −→ ∞. Các tác giả cũng chỉ ra rằng đối với ma trận có hạng đầy đủ và có
kích thước n × m có mối liên kết lẫn nhau bị chặn dưới bởi cận:
µ≥

m−n
n(m − 1

Mối liên kết lẫn nhau thì tương đối dễ tính và nhờ vậy ta có một đánh giá cận dưới
của spark như sau:

Bổ đề: Đối với bất kỳ ma trận A ∈ Rn×m , ta nói mối quan hệ giữa spark và mối liên kết
lẫn nhau như sau:
1
spark(A) ≥ 1 +
(1.5.2)
µ(A)

Định lý sau đưa ra một tiêu chuẩn để kiểm tra tính duy nhất nghiệm thưa của hệ

19


phương trình dựa trên mối liên kết lẫn nhau
Định lý 7. (Unique - Mutual - Coherence): Nếu một hệ phương trình tuyến tính Ax = y
có một nghiệm x thỏa mãn ràng buộc x

0<

20

1
1
(1 +
), thì nghiệm này là duy nhất.
2
µ(A)


Chương 2
2.1


Một số thuật toán giải bài toán biểu
diễn thưa và ứng dụng

Thuật toán Orthogonal Matching Pursuit (OMP)

2.1.1

Thuật toán MP với ma trận từ điển A tùy ý [1]

Giả sử ma trận A có spark(A) > 2 và bài toán biểu diễn thưa (bài toán tối ưu P0 )
có nghiệm duy nhất thỏa mãn x 0 = 1. Khi đó y có thể biểu diễn tuyến tính thông qua
một cột của ma trận A. Chúng ta xác định cột này bằng cách áp dụng m lần thử cho mỗi
cột của ma trận A. Lần thử thứ j có thể thực hiện bởi tìm giá trị nhỏ nhất:
(j) = aj zj − y

Dẫn đến
zj∗

2
2

(2.1.1)

aTj y

=

(2.1.2)


2
2

aj

Khi đó sai số trở thành:
(j) = minzj
= y

2
2

= y

2
2

2
2

aj zj − y
(aTj )2 y
−2
aj 22
(aTj y)2
−
aj 22

+


aTj y

aj
T
(aj y)2
aj 22

a
2 j
2

−y

2
2

(2.1.3)

Nếu sai số là 0, chúng ta tìm được nghiệm phù hợp, vì vậy phép thử được thực
hiện đơn giản là aj 22 y 22 = (aTj y)2 (tương đương với bất đẳng thức Cauchy-Schwartz
trong trường hợp dấu bằng xảy ra). Độ phức tạp của thuật toán là O(mn).
Trong trường hợp tổng quát, giả sử rằng A có Spark(A) > 2k0 và bài toán tối ưu
P0 có nghiệm thỏa mãn x 0 = k0 . Khi đó y là 1 tổ hợp tuyến tính của k0 cột của ma
k0
trận A. Có thể liệt kê (m
k0 ) = O(m ) tập gồm k0 cột từ ma trận A và kiểm thử một tập.
Độ phức tạp của thuật toán là O(mk0 nk02 ). Do đó, thay vì giải trực tiếp bài toán biểu diễn
thưa chúng ta sử dụng thuật toán tham để tìm nghiệm xấp xỉ.
Thuật toán tham thay vì tìm kiếm lời giải tối ưu toàn cục bằng cách vét cạn thì tìm
kiếm lời giải tối ưu địa phương ở mỗi bước đi. Bắt đầu từ x0 = 0, thuật toán lặp cho đến


21


bước thứ k thì được xấp xỉ xk , bằng cách duy trì một tập các cột hỗ trợ được khởi tạo ban
đầu là tập rỗng và tại mỗi bước tập các cột hỗ trợ được mở rộng bằng cách thêm một cột.
Cột được thêm vào tập các cột hỗ trợ tại mỗi bước là cột được lựa chọn làm giảm tối đa
số dư chuẩn 2 của vector dư sai số hiện tại trong số các cột còn lại không thuộc tập hỗ
trợ. Điều này được thực hiện bằng cách lựa chọn một cột từ ma trận A không thuộc tập
hỗ trợ có độ tương quan tốt nhất với vector dư hiện tại r. Sau khi xây dựng một xấp xỉ
bao gồm cả cột mới, số dư chuẩn 2 được đánh giá, nếu nó đạt đến một ngưỡng qui định
thuật toán kết thúc.
Thuật toán MP được trình bày như sau:

22


Bài toán Một nghiệm xấp xỉ của bài toán biểu diễn thưa P0 được phát biểu
như sau:
Tìm một nghiệm của phương trình dưới xác định Ax = y có giá trị x 0
nhỏ nhất.
Tham số đầu vào: Cho 1 ma trận A, vector y , sai số 0
Tham số đầu ra: Một nghiệm của bài toán biểu diễn thưa P0 .
Các bước thực hiện của thuật toán MP
1. Khởi tạo: k = 0
Thiết đặt:
- Khởi tạo nghiệm x0 = 0
- Khởi tạo số dư r0 = y − Ax0 = y
- Khởi tạo nghiệm hỗ trợ S 0 = Support{x0 } = ∅
2. Lặp chính: tăng k lên 1 và thực hiện các bước sau:

Quét: Tính lỗi (j) = minzj aj zj − rk−1 22 với tất cả j sử dụng lựa chọn tối ưu
aTj rk−1
∗
z =
aj 22
- Cập nhật Support: Tìm giá trị nhỏ nhất, j0 của ε(j) :
∀1 ≤ j ≤ m, ε(j0 ) ≤ ε(j) và cập nhật S k = S k ∪ {j0 }
- Cập nhật nghiệm tạm thời: Đặt xk = xk−1 và cập nhật xk (j0 ) = xk (j0 ) + zj∗
- Cập nhật số dư: tính toán rk = y − Axk = rk−1 − zj∗0 aj0
3. Dừng: nếu rk 2 < ε0 ngược lại quay lại bước 2
4. Kết quả: nghiệm có được là xk sau khi thực hiện k lần lặp
Bảng 1: Thuật toán Matching Pursuit (MP)

23