Sơ lược về bài toán biểu diễn thưa
Trong những năm gần đây, bài toán "Nén cảm biến (CS)" đã thu hút sự chú ý của nhiều nhà khoa học Khái niệm "Biểu diễn thưa" được phát triển từ bài toán này, với Donoho là người đầu tiên đề xuất những khái niệm cơ bản về nén cảm biến.
Lý thuyết nén cảm biến cho thấy rằng tín hiệu thưa có thể được phục hồi chính xác chỉ với một số lượng nhỏ giá trị đo, ít hơn nhiều so với các lý thuyết lấy mẫu trước đây như định lý lấy mẫu Shannon Candes và cộng sự đã chứng minh tính đúng đắn của lý thuyết này, cho phép tái tạo tín hiệu bằng cách sử dụng một số hệ số trong biến đổi Fourier Baraniuk đã phân tích các trường hợp cụ thể và trình bày nhiều thuật toán khôi phục khác nhau, tạo nền tảng cho lý thuyết nén cảm biến và hỗ trợ nghiên cứu trong tương lai Lý thuyết nén cảm biến bao gồm ba thành phần chính: lý thuyết biểu diễn thưa, độ đo mã hóa và các thuật toán khôi phục, trong đó lý thuyết biểu diễn thưa được coi là điều kiện tiên quyết quan trọng để giải quyết nhiều vấn đề phức tạp trong các lĩnh vực khác nhau.
Bài toán biểu diễn thưa có nhiều ứng dụng thực tiễn và thu hút sự quan tâm của nhiều nhà khoa học Các thuật toán dựa trên lý thuyết này không chỉ tiết kiệm thời gian mà còn thuận tiện trong việc lưu trữ mẫu, giúp giải quyết hiệu quả các vấn đề liên quan đến xử lý tín hiệu.
Trong phần tiếp theo, chúng ta sẽ khám phá bài toán biểu diễn thưa và các kỹ thuật phổ biến được sử dụng để giải quyết vấn đề này.
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:
-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 ∈ R m×n
Giả sử ma trận A có hạng đầy đủ, phương trình (1.2.1) sẽ có vô số nghiệm Trong các bài toán kỹ thuật, việc chọn ra nghiệm tốt nhất từ những nghiệm của phương trình này là rất cần thiết Để thực hiện điều đó, chúng ta cần một hàm đo lường chất lượng J(x) nhằm xếp hạng các nghiệm theo một số tiêu chí nhất định Dựa trên xếp hạng này, chúng ta sẽ chọn ra nghiệm mong muốn Cụ thể, bài toán cần giải quyết là tìm bx = argmin J(x) thỏa mãn điều kiện Ax = y (1.2.2).
Ta có bài toán thay thế như sau:
P 0 :b x = arg min x k x k 0 thỏa mãn điều kiệnAx = y (1.2.3)
Trong thực tế, dữ liệu thu được có thể chứa nhiễu, và chúng ta không thể mong đợi tìm ra nghiệm hoàn hảo cho bài toán Ax = y Thay vào đó, sẽ có sai số giữa Abx và y, dẫn đến bài toán thay thế như sau: tìm bx = arg min x k x k 0 thỏa mãn k Ax − y k 2 6 Để hiểu rõ hơn về sự phức tạp của bài toán này, ta xem xét phương pháp giải trực tiếp cho bài toán biểu diễn thưa Tập hỗ trợ ký hiệu là sup(x) bao gồm các phần tử khác 0 trong x Với L = 1, ta xem xét tất cả các tập hỗ trợ {Si} I i=1 gồm L phần tử Đối với mỗi tập hỗ trợ, 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ể thực hiện bằng cách giải bài toán bình phương tối thiểu (Least-Squares).
Nếu kết quả thu được nhỏ hơn ngưỡng đã định, chúng ta đã tìm ra nghiệm cho bài toán và có thể kết thúc quá trình Ngược lại, nếu không có tập hỗ trợ nào giúp giảm sai số xuống dưới ngưỡng, bài toán vẫn chưa có lời giải.
Lđược tăng lên và quá trình thực hiện được lặp lại.
Trong bài toán biểu diễn thưa với m = 0, giả sử kích thước tập hỗ trợ L = 15 và thời gian giải quyết bài toán bình phương tối thiểu LS là 10 −9 giây, chúng ta sẽ mất khoảng 7.5 × 10^23 năm để giải quyết Thời gian này phản ánh độ phức tạp hàm mũ của bài toán, được xác định là thuộc lớp NP-HARD Do đó, để giải quyết bài toán biểu diễn thưa, việc sử dụng các thuật toán xấp xỉ là cần thiết.
Kiến thức trang bị [11]
Một số định nghĩa
TậpA ⊂ X được gọi là tập lồi, nếu:
Giả sử Dlà 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)
Giả sửf:X −→ (−∞, +∞], khi đóf là hàm lồi khi và chỉ khi
X i=1 λ i x igọi là tổ hợp lồi củax 1 , , x n ∈ R n nếu: λ i ≥ 0, ∀i, n
Chof : R n −→ R ∪ {+∞} Ta nóix ∗ ∈ R n là dưới đạo hàm củaf tạixnếu
Ký hiệu tập hợp tất cả các đạo hàm củaf tại xlà∂f (x) Định lý 1 Cho f là hàm lồi, khả dưới vi phân trên R n , khi đó y ∈ arg min x∈R n f (x)
Phân phối đều, phân phối chuẩn Gauss
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ủaX xác định bởi: f (x) =
VậyX 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
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 σ √
Các tham số đặc trưng của biến ngẫu nhiên có phân bố chuẩn
Tích vô hướng, các định nghĩa và tính chất của không gian Hilbert 13
Tích vô hướng trên không gian vector X là một ánh xạ từ X × X vào trường số K (K = R hoặc K = C) và cần thỏa mãn một số điều kiện quan trọng Đầu tiên, với mọi vector x trong X, giá trị hx, xi phải lớn hơn hoặc bằng 0, và chỉ bằng 0 khi x là vector không Thứ hai, tích vô hướng phải đối xứng, nghĩa là hy, xi = hx, yi (trong trường hợp K = R) Thứ ba, nó phải thỏa mãn tính chất phân phối, tức là hx + x0, yi = hx, yi + hx0, yi cho mọi x, x0, y trong X Cuối cùng, tích vô hướng phải tuân theo tính chất tuyến tính, cụ thể là hλx, yi = λhx, yi cho mọi x, y trong X và λ thuộc R.
Từ tính chất 1 và tính chất 4 ta cũng có: hx 0 , y + y 0 i = hx, yi + hx, y 0 i , hx, λyi = λhx, yi
2 Nếu h., i là một tích vô hướng trên X thì ánh xạ x −→p
(hx, xi) là một chuẩn trên X , gọi là chuẩn sinh bởi tích vô hướng
3 Nếu h., i là tích vô hướng trên X thì cặp (X, h., i) 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, h., i) luôn được gắn với chuẩn sinh bởi h., i Nếu không gian định chuẩn tương ứng đầy đủ thì ta nói (X, h., i) 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:
2 Giả sửα =Pm i=1 a i α i β =Pn i=1 b j β i thì
Nếu là một tích vô hướng trên V thì ánh xạ α −→ √
< α, α >, là một chuẩn trênV, gọi là chuẩn sinh bởi tích vô hướng.
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:|< α, β >|6 k α k k β k
∇ k α + β k 2 + k α − β k 2 = 2(k α k 2 + k β k 2 )(Đẳng thức hình bình hành)
Sự trực giao: Định nghĩa 2 Cho không gian với tích vô hướng, ( V, < , > ) và α, β ∈ V , y ∈ X ,
∇ 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 k α − β k= inf β 0 ∈M k α − β 0 k
Độ 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à k α k là số thực không âm, xác định như sau: k α k= √
Ví dụ:E = R n ,x = (x 1 , , x n ) ∈ R n thìk x k=p x 2 1 + + x n 2 Đị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(α) = kαk.kβk
Hai vectorα, β ∈ E gọi là trực giao, ký hiệu làα ⊥ β nếu< α, β >= 0
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à a i ⊥ a j ∀i 6= 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: hα i , α j i =
1 i = j Một cơ sở củaElà hệ trực chuẩn được gọi là cơ sở trực chuẩn củaE.
Nếuα 1 , , α m ∈ Elà một hệ trực giao, không chứa vector 0 củaEthì hệ:u 1 = kα α 1
Phép chuẩn hóa một hệ vector trực giao, ký hiệu là 2 k, ,u m = kα α m m k, là một quy trình quan trọng trong không gian E Nếu α 1, , α m là một cơ sở trực giao của E, thì việc chuẩn hóa cơ sở này sẽ dẫn đến một cơ sở trực chuẩn cho E.
Chú ý: Một hệ vector trực giao không chứa vector không thì độc lập tuyến tính
Phép biến đổi trực giao
Ma trận vuông A được gọi là ma trận trực giao nếu ma trận nghịch đảo A −1 bằng ma trận chuyển vị A T Trong không gian vector Euclide E, một phép biến đổi tuyến tính f được định nghĩa để mô tả các tính chất của ma trận trực giao.
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à:
Tính chất cơ bản của phép biển đổi trực giao được nêu trong định lý 2, theo đó, nếu f là biến đổi tuyến tính của không gian vector Euclide E, thì các khẳng định liên quan đến f sẽ tương đương với nhau.
- 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
Tính chất không chắc chắn và tính duy nhất nghiệm của bài toán
Trường hợp hai ma trận trực giao
Trong bài toán (P 0 ), chúng ta xem xét ma trận A được tạo thành từ hai ma trận trực giao, Ψ và Φ, chẳng hạn như A = [I, F], với I là ma trận đơn vị và F là ma trận Fourier Trong trường hợp này, hệ phương trình y = Ax trở thành hệ phương trình dưới xác định, dẫn đến việc mỗi tín hiệu y có thể được biểu diễn theo nhiều cách khác nhau, dưới dạng 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 (các cột của ma trận Fourier) Một nghiệm thưa của phương trình này là cách biểu diễn tín hiệu thông qua tổ hợp tuyến tính của một số sinusoids và một số spikes.
Trong phần này, chúng tôi khẳng định rằng một tín hiệu không thể được biểu diễn đồng thời cả về thời gian và tần số Giả sử có một vector không phải là vector y và tập cơ sở trực giao Ψ và Φ, thì 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 Ψ và các cột của ma trận Φ, cụ thể là y = Ψα = Φβ.
Rõ ràng rằng α và β được xác định duy nhất, trong đó Ψ là ma trận đơn vị và Φ là ma trận biến đổi Fourier Khi đó, ma trận Ψ đại diện cho mỗi cặp (Ψ, Φ), dẫn đến hiện tượng thú vị là chỉ một trong hai α hoặc β có tính chất thưa, phụ thuộc vào khoảng cách giữa Ψ và Φ Nếu cả hai ma trận giống nhau, chúng ta có thể dễ dàng xây dựng y từ một trong các cột của Ψ và đạt được giá trị nhỏ nhất cho cả α và β Để xác định giá trị gần đúng giữa chúng, cần có hệ số liên kết lẫn nhau giữa hai ma trận Định nghĩa 7 nêu rõ rằng đối với ma trận A được xây dựng từ cặp cơ sở trực giao Ψ và Φ, 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, được tính bằng công thức proximity(Ψ, Φ) = à(A) = max 1≤i,j≤n | Ψ T i Φ j | 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 nhất định.
Định lý 3 chỉ ra rằng, với mỗi cặp cơ sở trực giao Ψ và Φ có hệ số liên kết à(A), và cho một vector y khác 0 với các vector biểu diễn thưa α và β trong các cơ sở tương ứng, thì bất đẳng thức sau đây được áp dụng: 1 n ≤ à(A) ≤ 1.
Nguyên lý bất định 1 chỉ ra rằng k α k 0 + k β k 0 ≥ 2, thể hiện sự không chắc chắn của các nghiệm dự phòng Theo Định lý 4, nếu x 1 và x 2 là hai nghiệm phân biệt của hệ phương trình tuyến tính [Ψ, Φ]x = y, thì chỉ có thể tồn tại tối đa một nghiệm thưa, đồng thời phải thỏa mãn nguyên tắc không chắc chắn.
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
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
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 à(A) phần tử khỏc
0, thì ta khẳng định nghiệm này là nghiệm thưa duy nhất của hệ.
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
Hệ số Spark của ma trận A, được giới thiệu bởi Donoho và Elad vào năm 2003, là một tính chất quan trọng trong nghiên cứu tính duy nhất của nghiệm Spark mô tả không gian null của ma trận A dựa trên chuẩn `0 Theo định nghĩa, Spark của 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 này Định lý 6 cung cấp một tiêu chuẩn đơn giản để kiểm tra tính duy nhất của nghiệm thưa, cho biết rằng nếu 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 k x k 0 < spark(A), thì nghiệm đó là duy nhất.
2 , khi đó x là nghiệm thưa duy nhất của hệ
Tính duy nhất nghiệm thông qua mối liên kết lẫn nhau (Unique-
ness via the Mutual - Coherence)
Khi giải quyết bài toán P0, việc ước lượng giá trị của Spark trở nên khó khăn, do đó, chúng ta cần tìm những phương pháp đơn giản để đảm bảo tính duy nhất của nghiệm Một trong những phương pháp hiệu quả là khai thác mối liên kết giữa các phần tử của ma trận A, được định nghĩa từ việc tổng quát hóa định nghĩa cho trường hợp A là sự kết hợp của hai cơ sở trực chuẩn Trong trường hợp đơn giản này, việc tính toán ma trận Gram AT A sẽ dẫn đến kết quả mong muốn.
Mối liên kết lẫn nhau được xác định 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 Định nghĩa khái quát cho mối liên kết lẫn nhau của 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 Cột thứ k của ma trận A được ký hiệu là a_k, và mối liên kết lẫn nhau được tính toán bằng công thức: à(A) = max 1≤i,j≤m,i≠j.
Mối liên kết lẫn nhau thể hiện sự phụ thuộc giữa các cột của ma trận A Trong ma trận unitary, các cột là trực giao, dẫn đến mối liên kết lẫn nhau bằng 0 Đối với ma trận tổng quát với số cột nhiều hơn số hàng (m > n), chúng ta mong muốn giá trị mối liên kết lẫn nhau nhỏ nhất có thể, gần với 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
Mối liên kết lẫn nhau của ma trận A = [Ψ, Φ] thỏa mãn điều kiện √ 1 n ≤ à(A) ≤ 1 Trong nghiên cứu về các ma trận trực giao ngẫu nhiên có kích thước n × m, Donoho và Huo đã chỉ ra rằng các ma trận này có xu hướng không liên kết, với à(A n,m) thường tỷ lệ thuận với plog nm khi n → ∞ Họ cũng cho biết rằng đối với ma trận có hạng đầy đủ và kích thước n × m, mối liên kết lẫn nhau bị chặn dưới bởi cận: à ≥ r 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ổ đề về ma trận A ∈ R n×m chỉ ra rằng mối quan hệ giữa spark và mối liên kết lẫn nhau được thể hiện qua công thức spark(A) ≥ 1 + 1 à(A) Định lý 7, được gọi là Định lý Tính duy nhất - Mối liên kết - Tính đồng nhất, cung cấp tiêu chuẩn để kiểm tra tính duy nhất của nghiệm thưa trong hệ phương trình tuyến tính Ax = y, với điều kiện rằng nghiệm x thỏa mãn ràng buộc k x k 0 < 1.
2 (1 + 1 à(A) ) , thỡ nghiệm này là duy nhất.
Một số thuật toán giải bài toán biểu diễn thưa và ứng dụng 21
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 Acóspark(A) lớn hơn 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 kxk0 = 1, ta có thể biểu diễn tuyến tính thông qua một cột của ma trận A Để xác định cột này, ta sẽ thực hiện m lần thử cho mỗi cột của ma trận A, trong đó lần thử thứ j được thực hiện bằng cách tìm giá trị nhỏ nhất.
Khi đó sai số trở thành:
Nếu sai số bằng 0, nghiệm phù hợp sẽ được tìm thấy Phép thử đơn giản là \( a_j k^2 = (a^T j y)^2 \), tương đương với bất đẳng thức Cauchy-Schwartz khi 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 Acó Spark(A) > 2k 0 và bài toán tối ưu
P 0 có nghiệm thỏa mãn kxk 0 = k 0 Khi đó y là 1 tổ hợp tuyến tính của k 0 cột của ma trận A Có thể liệt kê ( m k
Để kiểm thử một tập hợp k₀ cột từ ma trận A, ta sử dụng thuật toán với độ phức tạp O(m k₀ n k₀²) Thay vì giải quyết trực tiếp bài toán biểu diễn thưa, chúng ta áp dụng thuật toán tham để tìm nghiệm xấp xỉ.
Thuật toán tham lam tìm kiếm lời giải tối ưu địa phương thay vì tối ưu toàn cục bằng cách lặp lại quá trình từ x0 = 0 Tại mỗi bước k, thuật toán xấp xỉ xk bằng cách duy trì và mở rộng một tập cột hỗ trợ, bắt đầu từ một tập rỗng Cột được thêm vào tập cột hỗ trợ ở mỗi bước là cột có khả năng giảm tối đa số dư chuẩn `2 của vector dư sai số hiện tại, chọn từ các cột không thuộc tập hỗ trợ Việc lựa chọn này dựa trên độ tương quan tốt nhất với vector dư hiện tại r từ ma trận A Sau khi xây dựng xấp xỉ mới, số dư chuẩn `2 được đánh giá và nếu đạt ngưỡng quy định, thuật toán sẽ kết thúc.
Thuật toán MP được trình bày như sau:
Bài toán Một nghiệm xấp xỉ của bài toán biểu diễn thưa P 0 đượ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ị kx k 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 P 0
Các bước thực hiện của thuật toán MP
- Khởi tạo số dư r 0 = y −Ax 0 = y
- Khởi tạo nghiệm hỗ trợ S 0 = Support{x 0 }= ∅
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) = min z j ka j z j −r k−1 k 2 2 với tất cả j sử dụng lựa chọn tối ưu z ∗ = a T j r k−1 k a j k 2 2
- Cập nhật Support: Tìm giá trị nhỏ nhất, j 0 của ε(j) :
- Cập nhật nghiệm tạm thời: Đặt x k = x k−1 và cập nhật x k (j 0 ) = x k (j 0 ) + z j ∗
- Cập nhật số dư: tính toán r k = y −Ax k = r k−1 −z j ∗
3 Dừng: nếu k r k k 2 < ε 0 ngược lại quay lại bước 2
4 Kết quả: nghiệm có được là x k sau khi thực hiện k lần lặp
Bảng 1: Thuật toán Matching Pursuit (MP)
Thuật toán MP là một phương pháp đơn giản và trực quan để tìm nghiệm thưa cho hệ phương trình tuyến tính chưa xác định Tuy nhiên, nó có tốc độ hội tụ chậm, yêu cầu một số lượng lớn phép lặp không giới hạn để đạt được nghiệm Độ phức tạp tính toán của thuật toán MP được xác định là O(mnk), trong đó k là số lần lặp cần thiết để đạt được nghiệm cuối cùng.
2.1.2 Thuật toán Orthogonal Matching Pursuit (OMP)[2]
Thuật toán MP ít được áp dụng do độ phức tạp tăng theo số lần lặp cần thiết để đạt kết quả Để cải thiện hạn chế này, thuật toán OMP (Orthogonal Matching Pursuit) đã ra đời, nhằm giảm số lần lặp bằng cách thêm bước trực giao hóa OMP kế thừa nhiều bước từ MP, trong đó tại mỗi lần lặp, xấp xỉ được tính bằng cách chiếu trực giao y lên tập các vector cột đã chọn thông qua giải bài toán bình phương tối thiểu, nhằm đạt xấp xỉ tốt nhất Trong OMP, các chỉ số của các cột đã chọn được lưu giữ trong tập hỗ trợ S k, và các cột này được gọi là các cột hỗ trợ.
OMP tương tự như MP ở điểm khởi đầu từ nghiệm bằng 0 và khởi tạo số dư bằng vector r Trong mỗi lần lặp, OMP chọn cột từ ma trận A có độ tương quan tốt nhất với vector dư r và gán chỉ số của cột đó vào tập hỗ trợ S_k Sau đó, OMP xác định các phần tử khác 0 của vector nghiệm x bằng cách giải bài toán bình phương tối thiểu trên các cột hỗ trợ, đồng thời tính sai số của vector dư hiện tại Quá trình này lặp lại cho đến khi sai số nhỏ hơn một hằng số ε đã định Khi OMP kết thúc, vector y được tạo ra từ tập các cột hỗ trợ, và trong mỗi bước lặp, thuật toán đảm bảo rằng vector dư r luôn trực giao với tất cả các cột hỗ trợ, do đó không có cột nào được chọn hai lần.
Thuật toán OMP trình bày như sau:
Tham số đầu vào: Cho một ma trận A , vector y , sai số ε 0
Tham số đầu ra: Nghiệm xấp xỉ thưa của bài toán P 0
- Khởi tạo số dư r 0 = y −Ax 0 = y
- Khởi tạo nghiệm hỗ trợ S 0 = Support{x 0 }= ∅
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) = min z j ka j z j −r k−1 k 2 2 với tất cả j sử dụng lựa chọn tối ưu z ∗ = a T j r k−1 k a j k 2 2
- Cập nhật hỗ trợ: Tìm giá trị nhỏ nhất j 0 của ε(j) : ∀j 6= S k−1 , ε(j 0 ) ≤ε(j) và cập nhật S k = S k−1 ∪ {j 0 }
- Cập nhật nghiệm tạm thời: Đặt x k giá trị nhỏ nhất của k Ax−y k 2 2 phụ thuộc vào Support{x} = S k
- Cập nhật số dư: tính toán r k = y −Ax k
3 Dừng: nếu k r k k 2 < ε 0 ngược lại quay lại bước 2
4 Kết quả: Nghiệm có được là x k sau khi thực hiện k lần lặp
Bảng 2: Thuật toán ORTHOGONAL MATCHING PURSUIT (OMP)
Tìm sai số nhỏ nhấtε(i)tương đương với tìm giá trị nhỏ nhất của các tích vô hướng giữa số dưr k−1 và các vector chuẩn hóa của ma trậnA.
Trong quá trình cập nhật nghiệm tạm thời, chúng ta tối thiểu hóa biểu thức k Ax − y k 2 2 với biến x trên tập hỗ trợ S k Ma trận A S k được ký hiệu với kích thước n× | S k |, bao gồm các cột từ ma trận A có chỉ số thuộc tập hỗ trợ Do đó, bài toán đặt ra là tìm giá trị nhỏ nhất của k A S k x.
Sk − y k 2 2 trong đóx S k là một vector thành phần khác 0 của vectorx. Nghiệm của bài toán là nghiệm của phương trình
A T S k (A S k x S k − y) = A S k x S k r k = 0 (2.1.5) Công thức tính số dư ở lần lặp thứklà r k = y − Ax k = y − A S k x S k
Công thức trên chỉ ra rằng các cột trong A là phần tử của tập hỗ trợ S k, và chúng trực giao với số dư r k còn lại Do đó, trong lần lặp tiếp theo, các cột này sẽ không được chọn lại.
Cho ma trận A = [a₁, a₂, , aₙ] với aᵢ ∈ Rᵐ, vector y được định nghĩa là tổ hợp tuyến tính của hai cột a₁ và a₂ với các hệ số nghiệm (x₁, x₂): y = x₁a₁ + x₂a₂ Thuật toán OMP bắt đầu bằng việc xác định cột có giá trị tương quan cao nhất với vector dư hiện tại, khởi đầu bằng vector y Nếu giá trị tương quan của y với a₁ lớn hơn a₂, thuật toán sẽ chọn a₁ Tiếp theo, OMP dịch chuyển theo hướng của a₁, tạo ra vector dư r₁, mà trực giao với a₁ và có chỉ số đại diện cho tập hỗ trợ Sₖ Ở lần lặp thứ hai, một cột mới có giá trị tương quan với r₁ được chọn, dẫn đến việc chọn a₂ và thêm chỉ số của nó vào Sₖ Vector y sau đó được chiếu lên không gian sinh bởi a₁ và a₂ để tìm các hệ số nghiệm hiện tại x₂(1) và x₁(2) Sau lần lặp thứ hai, vector dư r₂ = 0, cho thấy y thuộc không gian sinh của a₁ và a₂, từ đó thuật toán OMP kết thúc và trả về vector x₂ là nghiệm cuối cùng.
Hình 1: Ví dụ minh họa thuật toán OMP
Cho H là không gian Hilbert và A là ma trận với các vector cột thứ j là a j ∈ H được chuẩn hóa, nghĩa là (k a j k 2 = 1, j ∈ {1, 2, , m}) Ký hiệu V là không gian sinh của các vector cột của ma trận A Ma trận A được coi là một từ điển đầy đủ nếu và chỉ nếu V = H, trong đó W là phần bù trực giao của V trong H Các phép chiếu trực giao lên H được thực hiện dựa trên các đặc tính này.
Trong bài viết này, chúng ta xem xét sự hội tụ của thuật toán OMP với định lý 8, trong đó cho vector y ∈ H, vector dư r k của thuật toán OMP thỏa mãn điều kiện lim k−→+∞ k r k − P w y k= 0 Xấp xỉ tại bước thứ k của vector y được ký hiệu là y b k và được xác định bởi yb k = P V y với k=0,1,2, Thuật toán OMP cho phép phục hồi tín hiệu thưa với xác suất cao trong tối đa k bước lặp, dẫn đến độ phức tạp tính toán là O(mnk) Do đó, OMP là một phương pháp hiệu quả để tìm nghiệm thưa cho các phương trình tuyến tính dưới xác định khi độ thưa tương đối nhỏ.
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
Tìm hướng trong thuật toán OMP dựa trên phân tích QR
Trong thuật toán OMP, mỗi cột chỉ được chọn và thêm vào tập hỗ trợ một lần, trong khi thuật toán MP cho phép một cột được chọn nhiều lần Do đó, thuật toán MP cần nhiều lần lặp hơn OMP để hội tụ và tìm ra nghiệm cuối cùng Tuy nhiên, chi phí tính toán cho mỗi bước lặp của OMP lại cao hơn so với MP.
Thuật toán OMP hiện nay hoạt động hiệu quả nhất nhờ vào phân tích QR Trong quá trình này, ma trận A S k được phân tích để đạt được kết quả tối ưu.
Trong đóQ S k ∈ R n×m là một ma trận unitary vàR S k là một ma trận tam giác trên. Phương trình (2.1.6) trở thành:
Công thức A T S k A S k x S k = (Q S k R S k ) T Q S k R S k x S k = A T S k y cho thấy mối liên hệ giữa các biến Nếu chúng ta đặt z S k = R S k y S k, việc thực hiện thuật toán OMP trở nên hiệu quả hơn, vì không cần tính toán x S k trong mỗi lần lặp Điều này giúp đơn giản hóa quy trình và tối ưu hóa hiệu suất của thuật toán.
Thuật toán Least Angle Regression (LARS) [1]
Trước khi, trình bày về thuật toán LARS cải biên chúng ta trình bày chi tiết về thuật toán LARS cơ bản
2.2.1 Thuật toán LARS cơ bản
LARS, được đề xuất bởi Efron, Hastie, Johnstone và Tibshirani, là một mô hình thuật toán chọn dùng để giải hệ tuyến tính dưới xác định Thuật toán này hoạt động dựa trên ý tưởng cơ bản là tìm kiếm các biến quan trọng trong một tập dữ liệu lớn, giúp tối ưu hóa quá trình hồi quy và cải thiện độ chính xác của mô hình.
LARS cơ bản bắt đầu bằng cách khởi tạo vector nghiệm với tất cả các phần tử bằng 0 và vector dư r bằng vector đo lường y Tập hỗ trợ I được thiết lập là tập rỗng Trong mỗi lần lặp, một cột mới từ ma trận A được chọn và chỉ số của nó được thêm vào tập hỗ trợ Ở bước lặp đầu tiên, LARS chọn cột j có độ tương quan cao nhất với vector dư hiện tại r, đảm bảo rằng góc giữa vector dư r và vector cột j nhỏ hơn so với góc giữa r và các cột khác trong ma trận A.
Thuật toán LARS điều chỉnh hệ số liên kết với cột được chọn theo cách phù hợp, dẫn đến giảm giá trị tương quan tuyệt đối của cột đó với số dư hiện tại khi hệ số tăng LARS thực hiện các bước nhỏ theo hướng cột cho đến khi xuất hiện một cột mới có giá trị tương quan tuyệt đối với vector dư hiện tại Quá trình này tiếp tục cho đến khi không còn cột nào có tương quan với vector dư hiện tại Thuật toán luôn chọn hướng cập nhật với các vector cột có chỉ số trong tập hỗ trợ có góc bằng nhau và nhỏ nhất Ví dụ cụ thể sẽ được sử dụng để minh họa quá trình thực hiện của thuật toán LARS.
Thuật toán LARS cơ bản bắt đầu bằng việc khởi tạo vector nghiệm là vector 0 và vector dư là vector đo lường y Thuật toán này chọn cột a1 trước tiên do sự tương quan tuyệt đối giữa a1 và vector dư nhỏ hơn so với a2 Sau đó, LARS di chuyển theo hướng của a1 với kích thước bước γ1, để đảm bảo a1 và a2 có cùng tương quan với vector dư trong vòng lặp tiếp theo Khi vector nghiệm được cập nhật, hệ số nghiệm x1(1) = γ1 Ở vòng lặp thứ hai, thuật toán thêm cột thứ hai vào tập hỗ trợ và tiếp tục di chuyển theo hướng đẳng giác của a1 và a2, với kích thước bước γ2 tạo ra vector y Thuật toán kết thúc khi vector dư còn lại là 0, và các hệ số nghiệm được tính là x2(1) = γ1 + γ2d2(1) và x2(2) = γ2d2(2), trong đó d2 là hướng cập nhật ở vòng lặp thứ hai.
Thuật toán LARS yêu cầu tính toán hai tham số quan trọng: vector hướng cập nhật d đẳng giác liên quan đến các cột hỗ trợ và kích thước bước dịch chuyển γ, một đại lượng vô hướng được nhân với hướng cập nhật d để cập nhật vector nghiệm x.
Hình ảnh mô tả các bước thực hiện của thuật toán LARS cho ví dụ 2.1
Hình 9: Quá trình thực hiện của thuật toán LARS
Phần tiếp theo sẽ trình bày chi tiết về cách tìm hướng cập nhật và bước dịch chuyển a Cách tìm hướng cập nhật
Trong phần này chúng ta sẽ trình bày chi tiết về cách tìm hướng cập nhật đẳng giác với các cột hỗ trợ:
Hướng cập nhật cần tạo với các cột hỗ trợ các góc bằng nhau theo hướng của vector dư r Để tìm hướng cập nhật d t ∈ R n ở vòng lặp thứ t, chúng ta chiếu vector dư r(t−1) lên không gian sinh của các vector cột hỗ trợ Điều này được thực hiện bằng cách giải phương trình chuẩn tắc, với c t = A T I r t−1, từ đó xác định các cột hỗ trợ có vector tương quan c t(I) = A T I r t−1.
Trong mỗi vòng lặp của thuật toán LARS, các cột hỗ trợ có giá trị tương quan tuyệt đối giống nhau với vector dư, được biểu thị bằng thông số λ t Do đó, chúng ta có thể phân tích c t (I) theo công thức: c t (I) = λ t sign(c t (I)).
Bằng cách sử dụng phương trình (2.2.4), phương trình (2.2.3) có thể được viết lại như sau:
A T I A I x = λ t sign(c t (I)) (2.2.5) λ t là 1 số vô hướng, chia cả hai vế của phương trình (2.2.5) cho giá trịλ t dẫn đến:
Trong phương trình (2.2.6), d_t(I) = x/λ_t là một thành phần của vector hướng cập nhật d_t tương ứng, chỉ giữ lại các thành phần của tập hỗ trợ I Mục tiêu là tính toán các phần tử của vector d_t(I) sao cho giá trị tương quan tuyệt đối của cột hỗ trợ giảm đều sau mỗi bước lặp Thuật toán LARS thiết lập các phần tử còn lại của vector hướng cập nhật không thuộc tập hỗ trợ bằng 0 (d_t(I_c) = 0) Trong mỗi vòng lặp, LARS tính toán kích thước bước đi γ phù hợp để cập nhật hệ số của nghiệm tương ứng với tập hỗ trợ, cho phép chọn một cột từ tập không hỗ trợ để kết hợp vào tập hỗ trợ trong vòng lặp tiếp theo, đảm bảo các cột hỗ trợ và cột được chọn có cùng giá trị tương quan tuyệt đối với vector dư hiện tại.
Nguồn gốc của biểu thức hình thái đóng (closed-form) để tính kích thước bước đi λ được trình bày trong bài báo LARS Trong phần này, chúng tôi sẽ trình bày chi tiết nguồn gốc của biểu thức này Giả sử thuật toán LARS đang thực hiện tại bước lặp thứ t, và chúng ta cần tính kích cỡ bước λ t phù hợp Vector dư tại bước lặp t được tính bằng công thức: r t = y − Ax t (2.2.7).
Tại bước lặp thứ t, vector dư được tính bằng công thức r t = r t−1 − A(x t − x t−1 ) Để tìm mối liên hệ giữa vector dư hiện tại và trước đó, ta trừ phương trình trước đó để có r t − r t−1 = y − Ax t − y + Ax t−1 Mỗi vòng lặp, LARS cập nhật vector nghiệm theo công thức x t = x t−1 + γ t d t.
Bởi vìd(I c ) = 0, phương trình (2.2.12) có thể được biểu diễn đơn giản như sau: r t = r t−1 − γ t A I d t (I) (2.2.13) Vector tương quanctrong vòng lặp tiếp theo được tính như sau: c t+1 = A T r t (2.2.14)
Bằng cách áp dụng phương trình (2.2.13) vào (2.2.14), ta có thể biểu diễn giá trị của c t+1 bằng công thức c t+1 = A T (r t−1 − γ t Ad t (I)) = c t − γ t A t A I d t (I) Trong mỗi vòng lặp của LARS, tham số γ thể hiện giá trị tương quan tuyệt đối của các cột hỗ trợ, và thực tế γ là giá trị tương quan tuyệt đối lớn nhất trong vector tương quan Điều này có thể được diễn đạt bằng công thức k c k ∞ = max(| c(1) |, | c(2) |, , | c(n) |).
Do đó,λở vòng lặpt + 1được tính như sau: λ t+1 =| c t+1 (I) | Bằng cách sử dụng phương trình (2.2.15), chúng ta được: λ t+1 =| c t (I) − γ t A t A I d t (I) | (2.2.17)
Từ (2.2.6), ta có: d t (I) = (A t I A I ) −1 sign(c t (I)) (2.2.18) Bằng cách thếd t (I)của (2.2.18) vào (2.2.7) ta thu được: λ t+1 =| c t (I) − γ t A t A I (A t A I ) −1 sign(c t (I )) | λ t+1 =| c t (I) − γ t sign(c t (I )) | (2.2.19) Thế (2.2.4)vào (2.2.19): λ t+1 =| λ t sign(c t (I)) − γ t sign(c t (I)) | λ t+1 =| sign(c t (I))(λ t − γ t ) | λ t+1 =| (λ t − γ t ) | (2.2.20)
Trong mỗi vòng lặp, cần lưu ý rằng giá trị tương quan tuyệt đối của các cột hỗ trợ được giảm đều, tức là giá trị λ được giảm ở mỗi vòng Thuật toán LARS chọn kích thước bước dịch chuyển nhỏ nhất để đảm bảo có một cột từ tập không hỗ trợ được thêm vào tập hỗ trợ ở vòng lặp tiếp theo Do đó, giá trị γ t nên được chọn là một số dương và nhỏ hơn λ t Với việc lựa chọn tham số thích hợp, phương trình (2.2.20) có thể đơn giản hóa thành λ t+1 = λ t − γ t (2.2.21).
Ta giả sử, tại vòng lặp tiếp theot + 1, cột thứiđược thêm vào tập hỗ trợ Khi đó, giá trị tương quan tuyệt đối của nó phải bằngλ t+1
| c t+1 (I) |= λ t+1 (2.2.22) Ở đâyi ∈ I t c vàI t c là tập không hỗ trợ ở vòng lặpt.
Sử dụng phương trình (2.2.15), sự tương quan của cột i có thể được tính bằng phương trình sau: c t+1 (i) = c t (i) − γ t a T i A I d t (I) (2.2.23) Bằng cách thế phương trình (2.2.23) và (2.2.21) vào phương trình (2.2.22), ta có:
Thuật toán LARS cơ bản xác định kích thước bước dịch chuyển γ t là số dương nhỏ nhất, giúp kết hợp một cột từ tập không hỗ trợ I c vào tập hỗ trợ I ở vòng lặp tiếp theo t + 1 Cụ thể, γ t được tính bằng công thức: γ t = min i∈I c { λ t − c t (i).
Chúng ta chỉ xét bài toán cực tiểu (2.2.4) trên các phần tử là số dương với tất cả các giá trịiđược xét.
Sau khi cập nhật hướng và kích cỡ bước γ t, thuật toán LARS cơ bản tiến hành cập nhật vector nghiệm theo phương trình (2.2.11) và tính toán số dư mới theo phương trình (2.2.7) Quá trình này được lặp lại cho đến khi không còn cột nào trong tập không hỗ trợ có mối tương quan với vector dư hiện tại Khi γ hướng tới 0 và không còn cột tương quan, thuật toán LARS cơ bản sẽ kết thúc và vector x t sẽ là nghiệm cần tìm Tóm lại, thuật toán LARS cơ bản có thể được tổng kết như vậy.
Input: vector y ∈ R m , ma trận A∈ R m×n , và ngưỡng giới hạn cho số dư
Yêu cầu: xấp xỉ vector y bằng cách sử dụng ít số cột của ma trận A nhất.
Các bước của thuật toán bao gồm:
3)Tính giá trị tuyệt đối lớn nhất của các phần từ thuộc vector tương quan: λ t =kc t k ∞
4) Nếu λ t = 0 hoặc gần như rất nhỏ, LARS kết thúc và vector x t là kết quả trả về cuối cùng Nếu không thì thực hiện các bước sau đây.
6) Giải phương trình chuẩn tắc để tìm các phần tử hỗ trợ của vector hướng cập nhật: A T I A I d t (I) =sign(c t (I)) Ở đây sign (c t (I)) trả về dấu của các phần tử thuộc tập hỗ trợ của vector tương quan c t
7) Đặt các phần tử không thuộc tập hộ trợ của vector hướng cập nhật là 0: d t (I c ) = 0
8) Tính toán kích thước bước dịch chuyển: γ t = min i∈I c { λ 1−a t −c T t (i) i v t},λ t +c t (i)
10) Tính toán vector dư mới r t = y −Ax t
11)Nếu k r t k 2 < , kết thúc trả về x = x t là nghiệm cuối cùng.
Ngược lại tăng biến lặp t = t+ 1và quay lại bước 2
Bảng 6: Thuật toán LARS cơ bản
2.2.2 Thuật toán LARS cải biên để giải quyết bài toán LASSO
Thuật toán LARS cải biên
Trong một số trường hợp, chúng ta giải bài toán cực tiểu hóa với tiêu chuẩn` 1:
Tìm min x k x k 1thỏa mãn điều kiện Ax = y