壓縮感知

维基百科,自由的百科全书
跳转至: 导航搜索

压缩感知(Compressed sensing),也被称为压缩采样(Compressive sampling)或稀疏采样(Sparse sampling),是一种寻找欠定线性系统的稀疏解的技术。压缩感知被应用于电子工程尤其是信号处理中,用于获取和重构稀疏或可压缩的信号。這個方法利用訊號稀疏的特性,相較於奈奎斯特理論,得以從較少的測量值還原出原來整個欲得知的訊號。核磁共振就是一個可能使用此方法的應用。这一方法至少已经存在了四十年,由于David DonohoEmmanuel Candès陶哲轩的工作,最近这个领域有了长足的发展。近幾年,為了因應即將來臨的第五代移動通信系統,壓縮感知技術也被大量應用在無線通訊系統之中,獲得了大量的關注以及研究。

概览[编辑]

信号处理领域中的一个常见问题就是从一系列的采样中重建原本的信号。一般而言,未被采样的部分信号,是不可能重建出來的。然而通过借助对于信号(性质)的预先了解或合理假设,完美地通过一系列采样重建原信号就成为了可能。随着科学的发展,数学家们逐步增进了如何作出合理假设的能力,并慢慢了解到在何种情况下可将这些假设一般化、推广化。

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

在2004年左右,Emmanuel Candès陶哲轩David Donoho证明了在已知信号稀疏性的情况下,可能凭借较采样定理所规定更少的采样数重建原信号,这一理论也是压缩感知的基石。

問題定義[编辑]

一般來說,一個常見的線性系統問題,有m個方程式, n個未知數,可以被定義如下:

在通訊系統之中,y是被收到的訊號,而s則是要被重建的訊號,一般來說會有以下兩種情況:

1.,也就是說方程式的數量大於等於未知數的數量,這種情況發生的時候就可以利用最小平方法(least squares, LS)去求得最接近的解,求得的解如下:

擬反矩陣(pseudo inverse matrix)。

2.,也就是未知數的數量比方程式的數量來的多,这个方程组就被称为欠定线性系统,一般而言有无数个解,因此我們無法使用最小平方法去求得要重建的訊號。

但是,如果这个欠定线性系统只有唯一一个稀疏解,那么我们可以利用压缩感知理论和方法来寻找这个解。值得注意的是,並不是所有欠定线性方程组都具有稀疏解。

舉例來說,是一個欠定線性系統,我們會有無限多個解可以滿足這個方程式,然而當我們加入稀疏性的特性之後,也就是說之間只有一個有值,另外一個必定為0,我們就可以很輕易地得到這個欠定線性系統的解為或是,這個就是壓縮感知的最主要的精神所在。

從下圖我們可以輕易地了解,當解具有稀疏的特性時,就可以從欠定線性系統有無限多組解的情況變成可以利用最小平方法找出解的情況。

稀疏性[编辑]

一個向量的稀疏性可以被定義如下:

也就是計算一個向量之中非零的個數,舉例來說,如果,因此目標的解就會變成如下:

希望能在非零個數越少的情況之下,找到最有可能的解。然而在实际中,最优化L0范数是一个NP难的问题,需要穷举s中非零值的所有排列可能,因而无法求解。通常采取的手段是对L1范数进行最优化求解,优化目标则变为:

或是使用匹配追踪系列算法、迭代阈值法以及专门处理二维图像问题的最小全变分法等求得次最优解的算法进行计算。

取样方法[编辑]

在理论上,为了确保信号重建的准确度,需要令所采用的取样矩阵各行列之间相干性(coherence)尽量地低,且须矩阵元素(element)取值随机性尽量地高。

考虑到以上原因,最为标准的做法是采用相同独立分布随机高斯矩阵(identical independent distributed random Gaussian matrix)对待处理信号进行取样,即可确保在信号具有足够稀疏性的前提下得到较佳的压缩感知重建效果。

但是在采用相同独立分布随机高斯矩阵时,所需要的数据存储量过于庞大——每个矩阵元素都要单独记录,且数据类型一般为浮点数——这就促进了简化取样矩阵的研究;目前被提出的简化取样矩阵主要包括两种:结构简化采样矩阵与数值简化采样矩阵。

结构简化采样矩阵[编辑]

一种基本的结构简化采样矩阵是Toeplitz矩阵

其中

在采用Toeplitz矩阵进行压缩感知取样时,便可以只在系统内存中储存第一行与第一列的矩阵元素,大大降低了储存成本,为算法的硬件实现降低了门槛。

数值简化采样矩阵[编辑]

数值简化采样矩阵普遍将原有的、按照高斯分布随机取值的采样矩阵元素以数值上更为简单的元素取代,但在分布上维持矩阵元素的分布随机性——即缩减了储存浮点数这一方面的成本。

一种较为基本的数值简化采样矩阵是0-1伯努利矩阵,其中的元素仅有0和1两种,分布模式为相同独立的伯努利分布(identical independent Bernoulli distribution)。

对于每一个矩阵元素,该分布的概率质量函数为:

求解/重构方法[编辑]

压缩感知利用了很多信号中所存在的冗余(换言之,这些信号并非完全是噪声)。具体而言,很多信号都是“稀疏”的;在适当的表示域中,它们的很多系数都是等于或约等于零。

在信号获取阶段,压缩感知在信号并不稀疏的域对信号进行线性测量。

为了从线性测量中重构出原来的信号,压缩感知求解一个称为L1-范数正则化的最小二乘问题。从理论上可以证明,在某些条件下,这个正则化最小二乘问题的解正是原欠定线性系统的稀疏解。

基追踪[编辑]

基追踪(basis pursuit[1])是一种信号重建演算法,被广泛地用于压缩感知领域,属于数学最优化问题的范畴,形式为

其中s是n×1向量,表示输出(信号),y是m×1的测量向量,Am×n的“转换矩阵”或稱作“测量矩阵”,其中M < N

基追踪常在需要完美满足欠定线性方程组系统中时被应用,且要求解在L1基准下为最稀疏的。

若应用情景允许降低对完美恢复的要求,以换取更加稀疏的解s降噪基追踪(basis pursuit denoising[2])更为适用。

匹配追踪[编辑]

匹配追踪(Matching pursuit[3])是一种稀疏近似运算,旨在找到多维数据在某个超完备字典(dictionary)上映射的“最佳匹配”。其基本的概念就是要用来自的函数组(称为基元,或atom)的加权和来表示希尔伯特空间上的信号

其中表示被选取基元的序数,是每个基元的加权常数。对于固定的字典,匹配追踪会先找到与信号间内积最大的一个基元,再减去该基元带来的影响,然后重复找寻影响力次大的基元直到信号被较好地分解。

相较而言,以傅里叶级数表示的信号来说,字典是构建于正弦基函数之上的。信号处理领域中傅里叶分析的主要缺点就在于它只能提取出信号中常存的特征,而不能适应当前的分析目标信号

若采用一组极端保险、带有大量冗余的字典,我们就能够找到可以完美匹配信号的函数组。在对信号进行编码与压缩时,最好是能够找到一组映射,使加权和中的大部分系数都接近零(具有“稀疏性”)。

正交匹配追蹤(Orthogonal Matching Pursuit)[编辑]

正交匹配追蹤是一個用來解決壓縮感知問題的演算法,在一定的複雜度之下有不錯的表現,他背後最主要的想法是源自於貪婪演算法(Greedy Algorithm),以下將逐步解說。

首先這個問題被定義為:y=Ax,目標是要藉由已知的y向量、A矩陣,來還原x向量,他會利用疊代的方式,逐步找出x向量當中最有可能是非零的位置。

一開始會有一個空集合,以及剩餘的部分,每次疊代都會從找出一個A矩陣投影到剩餘有最大值的位置,把這個位置加到之中,並從當中移除,最後再更新剩餘。利用疊代的方式,不斷地找出x向量當中最有可能非零的位置,直到達到演算法停止條件。

在正交匹配追踪算法的基础上,Needell等人提出了正则正交匹配追踪(Regularized Orthogonal Matching Pursuit,ROMP)算法对于所有满足约束等距性条件的矩阵和所有稀疏信号进行重构。之后,引入回溯思想的压缩采样匹配追踪(Compressive Sampling Matching Pursuit,CoSaMP)算法被提出。

在实际应用中,稀疏信号非零元素个数K往往是未知的,而上述的匹配追踪算法都是建立在稀疏度K已知的基础上,因此出现了对K自适应的稀疏自适应匹配追踪(Sparsity Adaptive Matching Pursuit,SAMP)算法,它通过固定步长来逐步逼近进行重建,可以在稀疏度K未知的情况下获得较好的重建效果。

相關應用[编辑]

压缩感知与包括欠定系统群验稀疏编码复用稀疏采样等。在成像科技领域,亦有许多技术如(编码孔计算摄影学)与压缩感知相关。亦有许多在不同技术完成度下将压缩感知实现的案例。

摄影学[编辑]

压缩感知技术被用于手机摄像头传感器设计中。这一技术使得在获取图像时所耗费的能量大大降低,可达原先耗费的15分之一——当然,需要引入复杂的解压算法;这一运算可能会需要脱机状态下的预先安装、设置。

压缩感知亦被用于实现单像素摄影。贝尔实验室运用了这一技术,用无镜片单像素相机在栅格中随机选取的孔隙处拍照,以达到成像效果。随着拍照次数的逐渐增多,照片质量也会逐步提高;一般来说,这种技术较之传统的摄影成像技术仅仅需要一小部分的数据占用量,且能完全避免与镜片或聚焦相关的故障或失常;参见[4]

全息成像[编辑]

压缩感知可被用于增加通过单幅全息图中所能得到的立体像素的数量改进全息摄影技术中的图像重建问题。在光学全息图或毫米波全息图采样率不足的情况下,这一技术也能够被用于图像检索以作出改善。

面部识别[编辑]

压缩感知目前被用于面部识别应用之中,参见Engineers Test Highly Accurate Face Recognition

核磁共振成像[编辑]

压缩感知被用于缩短核磁共振成像中的扫描时间,参见[5][6][7];其中涉及的重建方法包括ISTA、FISTA、SISTA等。

网络诊断[编辑]

压缩感知在被用于旨在利于网络管理网络诊断应用中时带来了极佳成效。对网络延时的估计和网络拥塞的探知均可被归纳、建模为非定性的线性方程组系统,其中的参数矩阵正是所分析网络的路由选择矩阵。此外,在互联网情景中,网络路由矩阵常常能够满足压缩感知技术所要求的几个基本要素:低相关性、稀疏性及(可能的)R.I.P条件,请参见[8]

短红外摄影[编辑]

目前,基于压缩感知技术的商用短红外相机已被推出[9] 。这些相机的光敏度大约从0.9µm到1.7µm,在上述波段上,人类的肉眼是无效的。

無線通訊系統[编辑]

物聯網的情境之下,裝置的數量會大幅增加,而因為資源有限,所以用來辨別裝置的展頻碼(m)會少於裝置的數量(n),因此會使得整個系統變成欠定的線性系統,然而這些裝置大部分的時候都是處於休息、監測的狀態,並不會一直傳送訊息給基地台,因此就有了稀疏的性質,利用壓縮感知的技術就能分辨出處於活動狀態的裝置,並解出其所傳送的訊號。

參考資料[编辑]

  • Candès, E.J., & Wakin, M.B., An Introduction To Compressive Sampling, IEEE Signal Processing Magazine, V.21, March 2008
  • J. Choi et al., "Compressive Sensing for Wireless Communications: Useful Tips and Tricks", IEEE Commun. Survey and Tutorials.
  • C. Bockelmann, H. F. Schepker, and A. Dekorsy, "Compressive sensing based multi‐user detection for machine‐to‐machine communication," Transactions on Emerging Telecommunications Technologies, vol. 24, no. 4, pp. 389-400, 2013.
  • F. Monsees, C. Bockelmann, D. Wubben, and A. Dekorsy, "Sparsity aware multiuser detection for machine to machine communication," 2012 IEEE Globecom Workshops, Anaheim, CA, 2012, pp. 3-7.

外部链接[编辑]