Xem mã nguồn của Bổ đề Johnson–Lindenstrauss

Trong toán học, '''bổ đề Johnson–Lindenstrauss''' là một mệnh đề về việc ánh xạ một tập hợp các điểm trong [[không gian Euclide|không gian Euclid]] nhiều chiều về không gian ít chiều. Bổ đề khẳng định rằng với mọi tập hợp điểm trong [[không gian Euclide|không gian Euclid]], đều tồn tại cách ánh xạ các điểm này vào không gian có số chiều nhỏ hơn số điểm rất nhiều và không phụ thuộc số chiều ban đầu sao cho khoảng cách giữa các điểm gần như được giữ nguyên.

Bổ đề này có nhiều ứng dụng trong [[cảm biến nén]], [[học đa tạp]], [[giảm chiều]], và [[nhúng metric]]. Trong nhiều trường hợp, dữ liệu (chẳng hạn như văn bản hay hình ảnh) có thể được xem là các điểm trong không gian nhiều chiều. Tuy nhiên các thuật toán xử lý chúng thường chậm đi nhiều khi số chiều tăng lên. Do đó một phương pháp để làm tăng tốc độ thuật toán là làm giảm số chiều của dữ liệu trong khi vẫn giữ được thông tin quan trọng trong chúng. Bổ đề Johnson–Lindenstrauss là một kết quả cổ điển về vấn đề này.

== Phát biểu ==
Với mọi 0&nbsp;<&nbsp;''ε''&nbsp;<&nbsp;1, tập hợp ''X'' gồm ''m'' điểm trong '''R'''<sup>''N''</sup>, và một số nguyên {{nowrap begin}}''n'' > ''n''<sub>&thinsp;0</sub> = O(ln(''m'')&thinsp;/&thinsp;''ε''<sup>&thinsp;2</sup>){{nowrap end}}, tồn tại một hàm [[liên tục Lipschitz|Lipschitz]] ''ƒ''&nbsp;:&nbsp;'''R'''<sup>''N''</sup>&nbsp;→&nbsp;'''R'''<sup>''n''</sup> sao cho

: <math>(1-\varepsilon)\|u-v\|^2 \leq \|f(u) - f(v)\|^2 \leq (1+\varepsilon)\|u-v\|^2</math>

với mọi ''u'',&nbsp;''v''&nbsp;∈ ''X''.

Một cách chứng minh bổ đề là chọn ''ƒ'' là phép chiếu xuống một không gian ngẫu nhiên ''n'' chiều trong '''R'''<sup>''N''</sup>, và sử dụng hiện tượng [[tập trung độ đo]].

Số chiều của bổ đề là chặt cho tới thừa số log(1/''ε''), nghĩa là tồn tại ''m'' điểm sao cho để giữ nguyên khoảng cách giữa các điểm tới thừa số {{math|1+&epsilon;}}, cần sử dụng

: <math> \Omega\left(\frac{\log(m)}{\varepsilon^2\log (1/\varepsilon)}\right)</math>

chiều.<ref>{{harvtxt|Alon|2003}}</ref>

== Chú thích ==
{{Tham khảo}}

==Tham khảo==

* {{chú thích|first1=D.|last1=Achlioptas|url=http://people.ee.duke.edu/~lcarin/p93.pdf|contribution=Database-friendly random projections|series=Proc. 20-th Annual ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems|year=2001|pages=274&ndash;281}}
* {{chú thích|first1=N.|last1=Alon|url=http://www.math.tau.ac.il/~nogaa/PDFS/extremal1.pdf|title=Problems and results in extremal combinatorics&mdash;I|journal=Discrete Math.|volume=273|year=2003|pages=31&ndash;53}}
* {{chú thích tạp chí|first1=R.|last1=Baraniuk|first2=M.|last2=Davenport|first3=R.|last3=DeVore|first4=M.|last4=Wakin|url=http://dsp.rice.edu/files/cs/JL_RIP.pdf|title=A simple proof of the restricted isometry property for random matrices|journal=Constructive Approximation|volume=28|issue=3|pages=253&ndash;263|year=2008|doi=10.1007/s00365-007-9003-x}}{{Liên kết hỏng|date=2021-02-09 |bot=InternetArchiveBot }}
* {{cite techreport|first1=S.|last1=Dasgupta|first2=A.|last2=Gupta|url=http://www-cse.ucsd.edu/~dasgupta/papers/jl-tr.ps|title=An elementary proof of the Johnson–Lindenstrauss lemma|number=99–006|institution=U. C. Berkeley|year=1999}}
* {{chú thích tạp chí|first1=W.|last1=Johnson|first2=J.|last2=Lindenstrauss|title=Extensions of Lipschitz mappings into a Hilbert space|journal=Contemporary Mathematics|volume=26|pages=189&ndash;206|year=1984}}

[[Thể loại:Bổ đề]]
[[Thể loại:Giải tích toán học]]
[[Thể loại:Hình học mêtric]]

[[en:Johnson&ndash;Lindenstrauss lemma]]