壓縮感知

}}

}}

{{Expert|time=2015-12-14T03:36:22+00:00}}

{{Expert|time=2015-12-14T03:36:22+00:00}}

”’压缩感知”’（Compressed sensing），也被称为压缩采样（Compressive sampling）或稀疏采样（Sparse sampling），是一种寻找[[wikipedia:Underdetermined_system|欠定]]线性系统的稀疏解的技术。压缩感知被应用于[[电子工程]]尤其是[[信号处理]]中，用于获取和重构稀疏或可压缩的信号。這個方法利用訊號[[稀疏]]的特性，相較於[[奈奎斯特频率|奈奎斯特理論]]，得以從較少的測量值還原出原來整個欲得知的訊號。[[核磁共振成像|核磁共振]]就是一個可能使用此方法的應用。这一方法至少已经存在了四十年，由于 [https://en.wikipedia.org/wiki/Emmanuel_Candès Emmanuel Candès]、[https://en.wikipedia.org/wiki/David_Donoho David Donoho]、[https://jrom.ece.gatech.edu/ Justin Romberg] 和 [[陶哲轩]] 的工作，最近这个领域有了长足的发展。

”’压缩感知”’（Compressed sensing），也被称为压缩采样（Compressive sampling）或稀疏采样（Sparse sampling），是一种寻找欠定线性系统的稀疏解的技术。压缩感知被应用于[[电子工程]]尤其是[[信号处理]]中，用于获取和重构稀疏或可压缩的信号。這個方法利用訊號稀疏的特性，相較於[[奈奎斯特频率|奈奎斯特理論]]，得以從較少的測量值還原出原來整個欲得知的訊號。[[核磁共振成像|核磁共振]]就是一個可能使用此方法的應用。这一方法至少已经存在了四十年，由于{{le|Emmanuel Candès|Emmanuel Candès}}、[[戴維·多諾霍]]、Justin Romberg和[[陶哲轩]]的工作，最近这个领域有了长足的发展。

== 概览 ==

== 概览 ==

信号处理领域中的一次较早的突破是奈奎斯特[[采样定理]]的提出。这一定理证明了若信号的最高频率小于采样频率的一半，便可完美地从采样结果中恢复原本信号，因此定義了采样定理取樣頻率的下限。这种数据获取模式先采样再压缩，需要大量的时间压缩和空间存储数据，这限制了高速信号处理的发展，也给硬件的实时处理带来了极大的挑战。

信号处理领域中的一次较早的突破是奈奎斯特[[采样定理]]的提出。这一定理证明了若信号的最高频率小于采样频率的一半，便可完美地从采样结果中恢复原本信号，因此定義了采样定理取樣頻率的下限。这种数据获取模式先采样再压缩，需要大量的时间压缩和空间存储数据，这限制了高速信号处理的发展，也给硬件的实时处理带来了极大的挑战。

在2006年左右，[https://en.wikipedia.org/wiki/Emmanuel_Candès Emmanuel Candès]、[https://en.wikipedia.org/wiki/David_Donoho David Donoho]、[https://jrom.ece.gatech.edu/ Justin Romberg] 和 [[陶哲轩]] 证明了在已知信号稀疏性的情况下，可能凭借较采样定理所规定更少的采样数重建原信号，这一理论也是压缩感知的基石。

在2006年左右，{{le|Emmanuel Candès|Emmanuel Candès}}、[[戴維·多諾霍]]、Justin Romberg和[[陶哲轩]] 证明了在已知信号稀疏性的情况下，可能凭借较采样定理所规定更少的采样数重建原信号，这一理论也是压缩感知的基石。

===基追踪===

===基追踪===

基追踪（basis pursuit[https://en.wikipedia.org/wiki/Basis_pursuit]）是一种信号重建演算法，被广泛地用于压缩感知领域，属于数学最优化问题的范畴，形式为<math>\min_s \|s\|_1 \quad \mbox{subject to} \quad y = Hs</math>。

{{le|基追踪|basis pursuit}}是一种信号重建演算法，被广泛地用于压缩感知领域，属于数学最优化问题的范畴，形式为<math>\min_s \|s\|_1 \quad \mbox{subject to} \quad y = Hs</math>。

其中s是n×1向量，表示输出（信号），”y”是m×1的测量向量，”H”是”m”×n的“转换矩阵”或稱作“测量矩阵”，其中”M” < ”N”。

其中s是n×1向量，表示输出（信号），”y”是m×1的测量向量，”H”是”m”×n的“转换矩阵”或稱作“测量矩阵”，其中”M” < ”N”。

基追踪常在需要完美满足欠定线性方程组系统中<math>y=Hs</math>时被应用，且要求解在”L”₁基准下为最稀疏的。

基追踪常在需要完美满足欠定线性方程组系统中<math>y=Hs</math>时被应用，且要求解在”L”₁基准下为最稀疏的。

若应用情景允许降低对完美恢复的要求，以换取更加稀疏的解”s”，[[降噪基追踪]]（basis pursuit denoising[https://en.wikipedia.org/wiki/Basis_pursuit_denoising]）更为适用。

若应用情景允许降低对完美恢复的要求，以换取更加稀疏的解”s”，{{le|降噪基追踪|basis pursuit denoising}}更为适用。

===匹配追踪===

===匹配追踪===

匹配追踪（Matching pursuit[https://en.wikipedia.org/wiki/Matching_pursuit]）是一种稀疏近似运算，旨在找到多维数据在某个超完备字典（dictionary）<math>D</math>上映射的“最佳匹配”。其基本的概念就是要用来自<math>D</math>的函数组<math>g_{\gamma_n}</math>（称为基元，或atom）的加权和来表示[[希尔伯特空间]]<math>H</math>上的信号<math>f</math>：

{{le|匹配追踪|Matching pursuit}}是一种稀疏近似运算，旨在找到多维数据在某个超完备字典（dictionary）<math>D</math>上映射的“最佳匹配”。其基本的概念就是要用来自<math>D</math>的函数组<math>g_{\gamma_n}</math>（称为基元，或atom）的加权和来表示[[希尔伯特空间]]<math>H</math>上的信号<math>f</math>：

<math> f(t) = \sum_{n=0}^{+\infty} a_n g_{\gamma_n}(t)</math>

<math> f(t) = \sum_{n=0}^{+\infty} a_n g_{\gamma_n}(t)</math>