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

Communications on Pure and Applied Mathematics - Tập 59 Số 8 - Trang 1207-1223 - 2006
Emmanuel J. Candès1, Justin Romberg1, Terence Tao2
1Applied and Computational Mathematics, California Institute of Technology, Pasadena, CA 91125
2Department of Mathematics, University of California at Los Angeles, Los Angeles, CA 90095

Tóm tắt

Tóm tắtGiả sử chúng ta muốn khôi phục một vector x0 ∈ ℝ𝓂 (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 x0 + 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 x0 dựa trên dữ liệu y không?Để khôi phục x0, chúng tôi xem xét giải pháp x# cho vấn đề chuẩn hóa 𝓁1 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 x0 đủ 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 x0 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 x0; 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 𝓂)6.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.

Từ khóa


Tài liệu tham khảo

10.1017/CBO9780511804441

Candès E. J., Quantitative robust uncertainty principles and optimally sparse decompositions, Found Comput Math

10.1109/TIT.2005.862083

10.1109/TIT.2005.858979

Candès E. J., Near‐optimal signal recovery from random projections and universal encoding strategies, IEEE Trans Inform Theory

10.1137/S1064827596304010

10.1137/S003614450037906X

10.1109/18.119733

Donoho D. L., Compressed sensing, IEEE Trans Inform Theory

Donoho D. L., For most large undetermined systems of linear equations the minimal 𝓁1‐norm near‐solution is also the sparsest near‐solution, Comm Pure Appl Math

Donoho D. L., For most large undetermined systems of linear equations the minimal 𝓁1‐norm solution is also the sparsest solution, Comm Pure Appl Math

10.1073/pnas.0437847100

10.1109/TIT.2005.860430

10.1109/18.959265

Gilbert A. C.;Muthukrishnan S.;Strauss M.Improved time bounds for near‐optimal sparse Fourier representations. DIMACS Technical Report 2004‐49 October2004.

Goldfarb D., Second‐order cone programming based methods for total variation image restoration. Technical report, Columbia University, 2004

10.1016/0167-2789(92)90242-F

10.1016/0885-064X(91)90002-F

Tropp J., Just relax: Convex programming methods for identifying sparse signals in noise, IEEE Trans Inform Theory

Zou J., Theoretical and experimental analysis of a randomized algorithm for sparse Fourier transform analysis, J Computational Phys

Thông tin
Thông tin xuất bản

Communications on Pure and Applied Mathematics

Tập 59 Số 8

1207-1223

Thông tin tác giả