Compressed sensing (original) (raw)
Compressed sensing (also known as compressive sensing, compressive sampling, or sparse sampling) is a signal processing technique for efficiently acquiring and reconstructing a signal, by finding solutions to underdetermined linear systems. This is based on the principle that, through optimization, the sparsity of a signal can be exploited to recover it from far fewer samples than required by the Nyquist–Shannon sampling theorem. There are two conditions under which recovery is possible. The first one is sparsity, which requires the signal to be sparse in some domain. The second one is incoherence, which is applied through the isometric property, which is sufficient for sparse signals.
| Property | Value |
|---|---|
| dbo:abstract | Komprimované snímání (anglicky compressed sensing nebo také compressive sampling) je metoda snímání a rekonstrukce signálu, která za předpokladu řídkosti signálu ve vhodné reprezentaci vede ke snížení počtu měření . Z pohledu matematiky se jedná o řešení nedourčené soustavy lineárních rovnic se snahou o nalezení řešení s co nejmenším počtem nenulových koeficientů. Schéma úlohy Oproti obvyklému přístupu ke snímání dat, kdy nejprve musíme nasbírat veškerá data, poté provést vhodnou transformaci a následně zachovat jen ty koeficienty, které nesou dostatečné množství informace, při komprimovaném snímání stačí snímat signál pouze tolikrát, kolik je skutečně třeba pro následnou rekonstrukci (snímání a komprimace jsou tedy jediným nedělitelným procesem). Signál z předpokládáme řídký v nějakém slovníku (bázi či framu) Ψ (z = Ψx, x je řídké) a provedeme malý počet měření, které mají charakter lineárních kombinací složek signálu. Proces snímání lze tedy zapsat jako y = Pz = PΨx. Zde P je tzv. měřicí matice rozměru m×N, kde m ≪ N. Fáze rekonstrukce signálu je pak řešením problému: Tento problém je již nelineární a časově velmi náročný, dokonce NP-těžký , a proto jej nelze řešit přímo. Jednou z možností je nahradit -normu nějakou jinou (např. ), takové metody se pak nazývají relaxační a patří mezi ně především Basis Pursuit (BP), Least Angle Regression homotopy method (LARS) a Iterative Reweighted Least Squares (IRLS). Druhou skupinu metod tvoří hladové (greedy) algoritmy, které iterativně aproximují signál hledáním nejvýznamnějších atomů ze slovníku. Výhodou těchto metod je nízká složitost, bohužel však není zaručeno dosažení globálního minima. Zástupci této kategorie jsou Matching Pursuit (MP), Orthogonal Matching Pursuit (OMP) a další modifikace. Mimo tyto dvě kategorie existují algoritmy hybridní, využívající rysy obou předchozích skupin (např. A*OMP) . Aplikace komprimovaného snímání zahrnují zpracování obrazu (např. rychlé snímání v magnetické rezonanci nebo tzv. jednopixelová kamera ), odšumování signálů (denoising), odstraňování rozmazání (deblurring), doplňování chybějící informace v signálu (inpainting) , nové metody radiolokace , optimalizace ekvalizace v bezdrátových OFDM kanálech , korekční kódování v komunikačních technologiích nebo pokusy o konstrukci nových typů A/D převodníků . (cs) Compressed sensing (also known as compressive sensing, compressive sampling, or sparse sampling) is a signal processing technique for efficiently acquiring and reconstructing a signal, by finding solutions to underdetermined linear systems. This is based on the principle that, through optimization, the sparsity of a signal can be exploited to recover it from far fewer samples than required by the Nyquist–Shannon sampling theorem. There are two conditions under which recovery is possible. The first one is sparsity, which requires the signal to be sparse in some domain. The second one is incoherence, which is applied through the isometric property, which is sufficient for sparse signals. (en) Compressed Sensing oder komprimierte Erfassung (auch compressive sensing, compressive sampling oder sparse sampling) ist ein Verfahren zur Erfassung und Rekonstruierung dünnbesetzter (englisch sparse) Signale oder Informationsquellen. Diese lassen sich aufgrund ihrer Redundanz ohne wesentlichen Informationsverlust komprimieren. Dies wird bei der Abtastung der Signale zur deutlichen Verringerung der Abtastrate im Vergleich zu herkömmlichen Verfahren effizient genutzt. (de) L'acquisition comprimée (en anglais compressed sensing) est une technique permettant de trouver la solution la plus parcimonieuse d'un système linéaire sous-déterminé. Elle englobe non seulement les moyens pour trouver cette solution mais aussi les systèmes linéaires qui sont admissibles. En anglais, elle porte le nom de Compressive sensing, Compressed Sampling ou Sparse Sampling. (fr) 圧縮センシング（英語: Compressed Sensing）とは、観測対象データがある表現空間では「スパース(疎)」であると仮定して、必要とする未知数の数よりも少ない観測データから、ある条件の下で対象を復元する手法。 (ja) Compressed sensing (espressione della lingua inglese, noto anche come compressive sensing, compressive sampling e sparse sampling) indica una tecnica per trovare soluzioni sparse di un sistema di equazioni lineari sottodeterminato. In elettrotecnica, in particolare nella teoria dei segnali, la tecnica di compressed sensing implica un processo di acquisizione e di ricostruzione di un segnale elettrico che è supposto essere sparso o comprimibile. (it) Compressed sensing, также известное как compressive sensing, compressive sampling и sparse sampling — это методика получения и восстановления сигнала, используя знания о его предыдущих значениях, которые разрежены или сжаты. Эта область обработки сигналов существует на протяжении 40 лет, но только недавно получила широкое признание, в том числе благодаря нескольким важным результатам, сделанным Дэвидом Донохо, Emmanuel Candès, Justin Romberg и Теренсом Тао. (ru) 压缩感知（Compressed sensing），也被称为压缩采样（Compressive sampling）或稀疏采样（Sparse sampling），是一种寻找的稀疏解的技术。压缩感知被应用于电子工程尤其是信号处理中，用于获取和重构稀疏或可压缩的信号。這個方法利用訊號稀疏的特性，相較於奈奎斯特理論，得以從較少的測量值還原出原來整個欲得知的訊號。核磁共振就是一個可能使用此方法的應用。这一方法至少已经存在了四十年，由于、戴維·多諾霍、Justin Romberg和陶哲轩的工作，最近这个领域有了长足的发展。 (zh) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Underdetermined_equation_system.svg?width=300 |
| dbo:wikiPageExternalLink | https://web.archive.org/web/20150504060355/http:/ugcs.caltech.edu/~srbecker/wiki/Main_Page http://www.brainshark.com/brainshark/brainshark.net/portal/title.aspx%3Fpid=zAvz9F41cz0z0 http://www.brainshark.com/brainshark/brainshark.net/portal/title.aspx%3Fpid=zCdz10BfTRz0z0 http://www.brainshark.com/brainshark/brainshark.net/portal/title.aspx%3Fpid=zCgzXgcEKz0z0 http://www.brainshark.com/sps http://arquivo.pt/wayback/20160516193158/http:/dsp.rice.edu/cs/ https://www.ams.org/happening-series/hap7-pixel.pdf https://www.wired.com/magazine/2010/02/ff_algorithm/all/1 |
| dbo:wikiPageID | 11403316 (xsd:integer) |
| dbo:wikiPageLength | 46760 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1123545338 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Robert_Tibshirani dbr:Sampling_(signal_processing) dbr:Scanning_transmission_electron_microscopy dbr:Total_variation_regularization dbr:Basis_(linear_algebra) dbr:Bell_Labs dbr:David_Donoho dbr:Aperture_synthesis dbr:Rice_University dbr:Internet dbr:Peak_signal-to-noise_ratio dbr:L0_norm dbr:L2_norm dbr:Compressed_sensing_in_speech_signals dbr:Matrix_multiplication dbr:Low-density_parity-check_code dbr:Tomography dbr:Emmanuel_Candès dbr:Function_(mathematics) dbr:Functional_(mathematics) dbr:George_Dantzig dbr:George_W._Brown_(academic) dbr:Gradient dbr:Underdetermined_system dbr:Basis_pursuit dbr:Basis_pursuit_denoising dbr:Lp_norm dbr:Lp_space dbr:Magnetic_resonance_imaging dbr:Signal_processing dbr:Structural_similarity dbr:Computational_photography dbr:Computational_statistics dbr:Matching_pursuit dbr:Least_squares dbr:Linear_programming dbr:Network_tomography dbc:Information_theory dbc:Linear_algebra dbc:Mathematics_in_medicine dbc:Signal_estimation dbr:F-space dbr:Facial_recognition_system dbr:Abuse_of_terminology dbr:Non-negative dbr:Network_congestion dbr:Network_delay dbr:Terence_Tao dbr:Radio_astronomy dbr:Variable_splitting dbc:Mathematical_optimization dbr:L1_norm dbr:Coded_aperture dbr:Holography dbr:Transmission_electron_microscopy dbr:CLEAN_(algorithm) dbr:Pierre-Simon_Laplace dbr:Sparse_matrix dbr:Group_testing dbr:Nyquist–Shannon_sampling_theorem dbr:Real_number dbr:Lossy_compression dbr:Multiplexing dbr:Network_management dbr:Simplex_algorithm dbr:Total_variation dbr:Robust_statistics dbr:Whittaker–Shannon_interpolation_formula dbr:Voxel dbr:Noiselet dbr:System_of_linear_equations dbr:Median-unbiased_estimator dbr:Μm dbr:Sparse_approximation dbr:Linear_program dbr:Pseudo-inverse dbr:Astronomical_interferometry dbr:Signal_(electronics) dbr:Matrix_equation dbr:Integrable_function dbr:Lasso_regression dbr:Sparse_coding dbr:Sparsity dbr:Justin_Romberg dbr:File:Augmented_Lagrangian.png dbr:File:Edge_preserving_TV.png dbr:File:IRLS.png dbr:File:Orthogonal_Matching_Pursuit.gif dbr:File:Underdetermined_equation_system.svg |
| dbp:wikiPageUsesTemplate | dbt:Authority_control dbt:Citation_needed dbt:Math dbt:Reflist dbt:Refn dbt:See_also dbt:Short_description dbt:Pp-semi |
| dct:subject | dbc:Information_theory dbc:Linear_algebra dbc:Mathematics_in_medicine dbc:Signal_estimation dbc:Mathematical_optimization |
| gold:hypernym | dbr:Technique |
| rdf:type | owl:Thing dbo:TopicalConcept |
| rdfs:comment | Compressed sensing (also known as compressive sensing, compressive sampling, or sparse sampling) is a signal processing technique for efficiently acquiring and reconstructing a signal, by finding solutions to underdetermined linear systems. This is based on the principle that, through optimization, the sparsity of a signal can be exploited to recover it from far fewer samples than required by the Nyquist–Shannon sampling theorem. There are two conditions under which recovery is possible. The first one is sparsity, which requires the signal to be sparse in some domain. The second one is incoherence, which is applied through the isometric property, which is sufficient for sparse signals. (en) Compressed Sensing oder komprimierte Erfassung (auch compressive sensing, compressive sampling oder sparse sampling) ist ein Verfahren zur Erfassung und Rekonstruierung dünnbesetzter (englisch sparse) Signale oder Informationsquellen. Diese lassen sich aufgrund ihrer Redundanz ohne wesentlichen Informationsverlust komprimieren. Dies wird bei der Abtastung der Signale zur deutlichen Verringerung der Abtastrate im Vergleich zu herkömmlichen Verfahren effizient genutzt. (de) L'acquisition comprimée (en anglais compressed sensing) est une technique permettant de trouver la solution la plus parcimonieuse d'un système linéaire sous-déterminé. Elle englobe non seulement les moyens pour trouver cette solution mais aussi les systèmes linéaires qui sont admissibles. En anglais, elle porte le nom de Compressive sensing, Compressed Sampling ou Sparse Sampling. (fr) 圧縮センシング（英語: Compressed Sensing）とは、観測対象データがある表現空間では「スパース(疎)」であると仮定して、必要とする未知数の数よりも少ない観測データから、ある条件の下で対象を復元する手法。 (ja) Compressed sensing (espressione della lingua inglese, noto anche come compressive sensing, compressive sampling e sparse sampling) indica una tecnica per trovare soluzioni sparse di un sistema di equazioni lineari sottodeterminato. In elettrotecnica, in particolare nella teoria dei segnali, la tecnica di compressed sensing implica un processo di acquisizione e di ricostruzione di un segnale elettrico che è supposto essere sparso o comprimibile. (it) Compressed sensing, также известное как compressive sensing, compressive sampling и sparse sampling — это методика получения и восстановления сигнала, используя знания о его предыдущих значениях, которые разрежены или сжаты. Эта область обработки сигналов существует на протяжении 40 лет, но только недавно получила широкое признание, в том числе благодаря нескольким важным результатам, сделанным Дэвидом Донохо, Emmanuel Candès, Justin Romberg и Теренсом Тао. (ru) 压缩感知（Compressed sensing），也被称为压缩采样（Compressive sampling）或稀疏采样（Sparse sampling），是一种寻找的稀疏解的技术。压缩感知被应用于电子工程尤其是信号处理中，用于获取和重构稀疏或可压缩的信号。這個方法利用訊號稀疏的特性，相較於奈奎斯特理論，得以從較少的測量值還原出原來整個欲得知的訊號。核磁共振就是一個可能使用此方法的應用。这一方法至少已经存在了四十年，由于、戴維·多諾霍、Justin Romberg和陶哲轩的工作，最近这个领域有了长足的发展。 (zh) Komprimované snímání (anglicky compressed sensing nebo také compressive sampling) je metoda snímání a rekonstrukce signálu, která za předpokladu řídkosti signálu ve vhodné reprezentaci vede ke snížení počtu měření . Z pohledu matematiky se jedná o řešení nedourčené soustavy lineárních rovnic se snahou o nalezení řešení s co nejmenším počtem nenulových koeficientů. Schéma úlohy (cs) |
| rdfs:label | Komprimované snímání (cs) Compressed Sensing (de) Compressed sensing (en) Compressed sensing (it) Acquisition comprimée (fr) 圧縮センシング (ja) Compressive sensing (ru) 壓縮感知 (zh) |
| rdfs:seeAlso | dbr:Total_variation_denoising |
| owl:sameAs | freebase:Compressed sensing wikidata:Compressed sensing dbpedia-cs:Compressed sensing dbpedia-de:Compressed sensing dbpedia-fa:Compressed sensing dbpedia-fr:Compressed sensing dbpedia-it:Compressed sensing dbpedia-ja:Compressed sensing dbpedia-no:Compressed sensing dbpedia-ru:Compressed sensing dbpedia-tr:Compressed sensing dbpedia-zh:Compressed sensing https://global.dbpedia.org/id/2WEh3 |
| prov:wasDerivedFrom | wikipedia-en:Compressed_sensing?oldid=1123545338&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Orthogonal_Matching_Pursuit.gif wiki-commons:Special:FilePath/Augmented_Lagrangian.png wiki-commons:Special:FilePath/Edge_preserving_TV.png wiki-commons:Special:FilePath/IRLS.png wiki-commons:Special:FilePath/Underdetermined_equation_system.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Compressed_sensing |
| is dbo:knownFor of | dbr:Emmanuel_Candès dbr:Richard_Baraniuk dbr:Ronald_DeVore |
| is dbo:wikiPageDisambiguates of | dbr:CS |
| is dbo:wikiPageRedirects of | dbr:Total_variation_reconstruction dbr:Applications_of_compressed_sensing dbr:Compressed_Sensing dbr:Compressive_sampling dbr:Compressive_sensing dbr:Sparse_recovery dbr:Justin_Romberg |
| is dbo:wikiPageWikiLink of | dbr:Epistasis dbr:Multivariate_optical_computing dbr:M-theory_(learning_framework) dbr:Total_variation_reconstruction dbr:Bregman_method dbr:David_Donoho dbr:DOME_project dbr:Verification-based_message-passing_algorithms_in_compressed_sensing dbr:Deep_learning dbr:Detection_theory dbr:Inverse_problem dbr:List_of_numerical_analysis_topics dbr:Piotr_Indyk dbr:Nullspace_property dbr:Compressed_sensing_in_speech_signals dbr:Mila_Nikolova dbr:Olgica_Milenkovic dbr:Quantum_tomography dbr:Emmanuel_Candès dbr:Coralia_Cartis dbr:Underdetermined_system dbr:Applications_of_compressed_sensing dbr:Basis_pursuit dbr:Basis_pursuit_denoising dbr:Lp_space dbr:Magnetic_resonance_imaging dbr:Stanley_Osher dbr:Computational_imaging dbr:Yves_Meyer dbr:Fauzia_Ahmad dbr:Overdetermined_system dbr:Matching_pursuit dbr:Matrix_completion dbr:Babak_Hassibi dbr:Disjunct_matrix dbr:Gitta_Kutyniok dbr:Hadamard_matrix dbr:Iran_Workshop_on_Communication_and_Information_Theory dbr:Johnson–Lindenstrauss_lemma dbr:Landweber_iteration dbr:Least_squares dbr:Daniel_K._Sodickson dbr:Florent_Krzakala dbr:Iterative_reconstruction dbr:Iteratively_reweighted_least_squares dbr:Kalman_filter dbr:Wavelet dbr:Mutual_coherence_(linear_algebra) dbr:Matroid_girth dbr:Restricted_isometry_property dbr:Babel_function dbr:Terence_Tao dbr:Jens_Eisert dbr:Joel_Tropp dbr:T._Tony_Cai dbr:Coded_exposure_photography dbr:Taxicab_geometry dbr:Richard_Baraniuk dbr:Augmented_Lagrangian_method dbr:Philip_Batchelor dbr:Spectroscopy dbr:Group_testing dbr:Bubacarr_Bah dbr:Nyquist–Shannon_sampling_theorem dbr:Raymond_Paley dbr:CS dbr:Yonina_Eldar dbr:Spectral_density_estimation dbr:Super-resolution_imaging dbr:Compressed_Sensing dbr:Image_destriping dbr:Ghost_imaging dbr:Namrata_Vaswani dbr:Multiscale_geometric_analysis dbr:Total_variation_denoising dbr:Noiselet dbr:Nonuniform_sampling dbr:Ronald_DeVore dbr:Leslie_Ying dbr:SAMV_(algorithm) dbr:Sparse_approximation dbr:Sparse_dictionary_learning dbr:Structured_sparsity_regularization dbr:Compressive_sampling dbr:Compressive_sensing dbr:Sparse_recovery dbr:Justin_Romberg |
| is dbp:knownFor of | dbr:Richard_Baraniuk dbr:Ronald_DeVore |
| is foaf:primaryTopic of | wikipedia-en:Compressed_sensing |
