Khôi phục tín hiệu ổn định từ các phép đo không đầy đủ và không chính xác

Giả sử chúng ta muốn khôi phục một vector x₀ ∈ ℝ^𝓂 (ví dụ, một tín hiệu số hoặc hình ảnh) từ các quan sát không đầy đủ và bị ô nhiễm y = A x₀ + e; A là một ma trận 𝓃 × 𝓂 với số hàng ít hơn nhiều so với số cột (𝓃 ≪ 𝓂) và e là một hạng mục lỗi. Liệu có thể khôi phục chính xác x₀ dựa trên dữ liệu y không?

Để khôi phục x₀, chúng tôi xem xét giải pháp x^# cho vấn đề chuẩn hóa 𝓁₁ trong đó ϵ là kích thước của hạng mục lỗi e. Chúng tôi chỉ ra rằng nếu A tuân theo một nguyên lý không chắc chắn đồng nhất (với các cột có chuẩn đơn vị) và nếu vector x₀ đủ thưa thớt, thì giải pháp nằm trong mức độ nhiễu

Ví dụ đầu tiên, giả sử rằng A là một ma trận ngẫu nhiên Gaussian; thì việc khôi phục ổn định xảy ra đối với hầu hết các A như vậy với điều kiện rằng số lượng các phần tử không bằng 0 của x₀ khoảng cùng một thứ tự với số lượng quan sát. Như là một ví dụ thứ hai, giả sử người ta quan sát một vài mẫu Fourier của x₀; thì việc khôi phục ổn định xảy ra cho hầu hết mọi tập hợp 𝓃 hệ số với điều kiện rằng số lượng phần tử không bằng 0 có thứ tự khoảng 𝓃/(log 𝓂)⁶.

Trong trường hợp hạng mục lỗi biến mất, việc khôi phục tất nhiên là chính xác, và công trình này thực sự cung cấp những cái nhìn mới vào hiện tượng khôi phục chính xác được thảo luận trong các tài liệu trước đó. Phương pháp này cũng giải thích lý do tại sao người ta có thể khôi phục rất gần như tín hiệu thưa thớt xấp xỉ. © 2006 Wiley Periodicals, Inc.