精华内容
下载资源
问答
  • 传统的信号采样必须遵循香农采样定理, 产生的大量数据造成了存储空间的浪费。压缩感知( CS) 提出一种新的采样理 论, 它能够以远低于奈奎斯特采样速率采样信号。
  • 压缩感知:理论与应用(一)

    千次阅读 2019-04-30 14:07:00
    文章目录摘要1、引言1.1 压缩感知问题1.2 稀疏性:是否为合理假设?1.3 恢复算法:优化理论及其它1.4 感知矩阵:允许多少自由度?1.5 压缩感知:Quo Vadis?1.6 概述 摘要   压缩感知是2006年新引入的研究...

    本文主要摘自:Gitta Kutyniok, Compressed Sensing: Theory and Applications, March 12, 2012.

    摘要

      压缩感知是2006年新引入的研究领域,从那时起已经成为应用数学、计算机科学和电气工程等领域的重要概念。它出人意料地预测到,通过使用有效的算法,可以从以前被认为是高度不完整的线性测量中恢复出高维信号,只要这种高维信号能够以适当的基(或frame)来进行稀疏表示。本文将作为对压缩感知进行介绍和综述。

    1、概述

      压缩感知的研究起源于2006年Donoho[18]和Cand´es, Romberg, Tao[11]这两篇突破性论文。如今,在仅仅6年之后,已经有1000多篇文章探讨了大量的压缩感知理论。此外,这种方法被广泛应用于天文学、生物学、医学、雷达和地震学等领域。

    [18] D. L. Donoho. Compressed sensing. IEEE Trans. Inform. Theory, 52:1289–1306, 2006.
    [11] E. Cand`es, J. Romberg, and T. Tao. Robust uncertainty principles: Exact signal reconstruction from highly incomplete Fourier information. IEEE Trans. Inform. Theory,
    52:489-509, 2006.

      压缩感知的关键思想是通过凸优化从很少的非自适应的线性测量中恢复稀疏信号。换个角度,与高维稀疏向量经过降维后的精确恢复相关。再换个角度,我们可以把这个问题看作是,计算一个信号相对于一个超完备系统的稀疏系数向量。压缩感知的理论基础与其它应用领域的方法有联系,如应用谐波分析、frame理论、几何泛函分析、数值线性代数、最优化理论和随机矩阵理论等。
      有趣的是,关于稀疏恢复问题的研究,实际上可以追溯到90年代早期的论文,如[24],以及后来著名的Donoho与Huo的论文[21]以及Donoho与Elad的论文[19]。当前面提到的两篇介绍压缩感知的基础论文发表时,术语“压缩感知”最初用于随机感知矩阵,因为这些矩阵允许最小数量的非自适应的线性测量。目前,“压缩感知”这一术语与“稀疏恢复”这一术语的通用互换性越来越高,这也是我们在本文中将采用的观点。

    [19] D. L. Donoho and M. Elad. Optimally sparse representation in general (nonorthogonal) dictionaries via l 1 l^1 l1 minimization, Proc. Natl. Acad. Sci. USA, 100:2197–2202, 2003.
    [21] D. L. Donoho and X. Huo. Uncertainty principles and ideal atomic decomposition. IEEE Trans. Inform. Theory, 47:2845–2862, 2001.
    [24] D. L. Donoho and P. B. Starck. Uncertainty principles and signal recovery. SIAM J.Appl. Math., 49:906–931, 1989.

    1.1 压缩感知问题

      为了精确地描述这个问题,令 x = ( x i ) i = 1 n ∈ R n {\bf x}=(x_i)^n_{i=1}\in {\mathbb R}^n x=(xi)i=1nRn为有用信号。作为先验信息,我们或者假定 x \bf x x本身为稀疏的,这意味着它只有很少的非零系数,即
    ∣ ∣ x ∣ ∣ 0 : = # { i : x i = ̸ 0 } ||{\bf x}||_0:=\#\{ i:{x_i} { = \not } 0 \} x0:=#{i:xi≠0}很小;或者假定存在一个标准正交基(或frame) Φ \Phi Φ使得 x = Φ c {\bf x}=\Phi \bf c x=Φc,这里 c \bf c c为稀疏的。对于后者,我们假设 Φ \Phi Φ是以正交基或frame的元素作为列向量的矩阵。事实上,frame由于具有冗余因而提供了比标准正交基更多的灵活性,也因此改进了稀疏特性,故frame比标准正交基更常用。有时稀疏性的概念被弱化了,在我们在第2节中对此进行精确说明之前,我们姑且将其称为近似稀疏。进一步,假设 A \bf A A m × n m\times n m×n矩阵,通常称为感知矩阵或测量矩阵。本文中,即使没有明确提及,我们也总是假设 m &lt; n m \lt n m<n A \bf A A的所有列都不为零。
      因此压缩感知问题可以描述如下:从知识(knowledge)
    y = A x \bf y=Ax y=Ax中恢复 x \bf x x,或者从知识(knowledge) y = A Φ c \bf y=A\Phi c y=AΦc中恢复 c \bf c c。在这两种情况下,我们都面临着一个不确定的线性方程组,其稀疏性是要恢复向量的先验信息。这引出如下问题:

    • 用什么样的模型来描述信号和稀疏性是恰当的?
    • 合适的感知矩阵是什么样的?
    • 如何根据算法恢复信号?
    • 信号恢复的时间和精度如何?
        在本节中,我们将对这些问题进行简要讨论,作为后续章节的基础。

    1.2 稀疏性:是否为合理假设?

      作为第一个考虑,人们可能会质疑稀疏性是否确实是一个合理的假设。由于真实数据的复杂性,当然只有启发式的答案是可能的。
      如果取一幅自然图像,众所周知,小波通常提供稀疏近似[45]。可以清楚地看到,大多数系数在绝对值上都很小,用较深的颜色表示。
      根据信号的不同,可以使用各种表示系统来提供稀疏近似值,并不断扩展。事实上,最近的研究表明,小波系统并不能提供大多数自然图像的最佳稀疏近似值,但新型的shearlets系统却能做到这一点[42,41]。因此,假设对要被感知或压缩的信号有一些先知,通常来说,已具备了分析良好的表示系统。如果不是这样的话,可以使用更多的数据敏感方法,例如字典学习算法,该算法针对给定的测试信号集,计算合适的表示系统。

    [45]S. G. Mallat. A wavelet tour of signal processing. Academic Press, Inc., San Diego, CA, 1998.
    [42]G. Kutyniok and W.-Q Lim. Compactly supported shearlets are optimally sparse. J. Approx. Theory, 163:1564–1589, 2011.
    [41]G. Kutyniok and D. Labate. Shearlets: Multiscale Analysis for Multivariate Data. Birkh¨auser, Boston, 2012.

      基于已有应用, x \bf x x通常本身已经是稀疏的。例如在数字通信中,对具有 n n n根天线和 m m m个用户的蜂窝网络建模时,或者在基因组学研究中,用 n n n名患者的 m m m个基因进行试验。在第一种情况下,很少的用户在特定的时间内有持续的呼叫;在第二种情况下,很少的基因是实际活跃的。因此, x \bf x x稀疏本身也是一个非常自然的假设。
      在压缩感知文献中,大多数的结果事实上都假设 x \bf x x本身是稀疏的,并考虑 y = A x \bf y=Ax y=Ax。很少量的文章研究了合并稀疏正交基或frame的问题[55,9]。本文中也将考虑 x \bf x x本身为稀疏的。应该强调的是,“精确”的稀疏性往往过于严格或不自然,需要考虑到减弱的稀疏性概念。另一方面,有时,例如小波系数的树结构,非零系数的一些结构信息是已知的,这导致了不同的结构化稀疏模型。第2部分对这类模型进行了综述。

    1.3 恢复算法:优化理论及其它

      令 x \bf x x为稀疏向量,显然,我们可以通过解优化问题
    ( P 0 ) min ⁡ x ∣ ∣ x ∣ ∣ 0   s u b j e c t   t o   y = A x . (P_0)\qquad \min_{\bf x}||{\bf x}||_0 {\rm \ subject\ to}\ \bf y=Ax. (P0)xminx0 subject to y=Ax.来从 y \bf y y中恢复 x \bf x x.
      由于不可避免的组合搜索,该算法是NP难[48]。基础论文[14]中的主要思想是将 ℓ 0 \ell_0 0范数用最接近的凸范数来替换,即 ℓ 1 \ell_1 1范数。由此引出下面的最小化问题,即基追踪:
    ( P 1 ) min ⁡ x ∣ ∣ x ∣ ∣ 1   s u b j e c t   t o   y = A x . (P_1)\qquad \min_{x}||{\bf x}||_1 {\rm \ subject\ to}\ \bf y=Ax. (P1)xminx1 subject to y=Ax..  由于 ℓ 1 \ell_1 1球的形状, ℓ 1 \ell_1 1最小化确实促进了稀疏性。何时“ ℓ 0 = ℓ 1 \ell_0=\ell_1 0=1”成立是压缩感知的关键。提供了充分必要条件,这不仅取决于原始矢量 x \bf x x的稀疏性,还取决于感知矩阵 A \bf A A的不相干性,这将在第3部分进行精确说明。
      由于对于非常大的数据集,即使当求解器与压缩感知问题特殊结构相适应时 ℓ 1 \ell_1 1最小化也通常是不可行的,因而提出了各种其他类型的恢复算法。这些算法可以大致分为凸优化算法、贪婪算法和组合算法(参见第5节),每种算法都有各自的优缺点。

    1.4 感知矩阵:允许多少自由度?

      如前所述,感知矩阵需要满足某些特定的松散的条件,例如,一个小的所谓互相干。如果允许我们自由选择感知矩阵,最好的选择是随机矩阵,如高斯iid矩阵、均匀随机正交投影或伯努利矩阵,请参见示例[11]。

    [11]E. Cand`es, J. Romberg, and T. Tao. Robust uncertainty principles: Exact signal recon- struction from highly incomplete Fourier information. IEEE Trans. Inform. Theory, 52:489-509, 2006.

      关于是否能够通过精心构造使得确定性矩阵具有相似特性,这仍然是一个悬而未决的问题(更多细节见第4节)。目前,Rauhut等人正在采取不同的方法来解决这个问题,例如[53]或[54]中的结构化随机矩阵。此外,大多数应用不允许自由选择感知矩阵并强制使用特殊结构的矩阵。典型情况是数据分离,这是感知矩阵必须由两个或多个正交基或帧组成[32,第11章],或者对于高分辨率雷达,感知矩阵必须具有特定的时频结构[36]。

    [53]G. Pfander, H. Rauhut, and J. Tropp. The restricted isometry property for time- frequency structured random matrices. Preprint, 2011.
    [54]H. Rauhut, J. Romberg, and J. Tropp. Restricted isometries for partial random circu- lant matrices. Appl. Comput. Harmonic Anal., 32:242–254, 2012.
    [32]Y. C. Eldar and G. Kutyniok. Compressed Sensing: Theory and Applications. Cam- bridge University Press, 2012.
    [36]M. Herman and T. Strohmer. High Resolution Radar via Compressed Sensing. IEEE Trans. Signal Proc., 57:2275–2284, 2009.

    1.5 压缩感知:Quo Vadis?

      目前,除了一些深层次的问题,如具有与随机矩阵相似性质的确定性感知矩阵的构造外,还建立了核心理论。
      目前可以用现有的各种结果来确定的一个主要研究方向,就是加入了额外的稀疏特性可以产生结构化的稀疏性,参见第2部分。另一个主要方向是将压缩感知问题扩展或转换为其它问题,例如matrix compltion,请参见[10]。此外,我们目前正在见证压缩感知思想向各种应用领域(如雷达分析、医学成像、分布式信号处理和数据量化)的扩散;请参见[32]了解概述。这些应用所需的约束条件,对该领域提出了有趣的挑战,从而反过来引发了新的理论问题。最后,我们观察到,由于特别是快速稀疏恢复算法的需要,即与来自其他研究领域的数学家(如优化理论家、数值线性代数学家或随机矩阵理论家)更密切地合作成为趋势。

    [30]M. Elad and A. M. Bruckstein. A generalized uncertainty principle and sparse repre- sentation in pairs of bases. IEEE Trans. Inform. Theory, 48:2558–2567, 2002.
    [32]Y. C. Eldar and G. Kutyniok. Compressed Sensing: Theory and Applications. Cam- bridge University Press, 2012.

      最新研究方向的三个例子描述如下。首先,虽然压缩感知理论的重点是数字化的数据,但有必要发展一个类似的关于连续量的理论。到目前为止最又希望的两种方法是Eldar等人的[47]和Hansen等人的[1]。第二,与将合成系数的 ℓ 1 \ell_1 1范数最小化的基追踪方法相比,其它几种方法,如缺失数据恢复方法,是将分析系数的 ℓ 1 \ell_1 1范数最小化,而不是将合成系数的 ℓ 1 \ell_1 1范数最小化(见第6.1.2和6.2.2小节)。这两个最小化问题之间的关系还很不清楚,最近引入的共稀疏概念[49]是一种很有意思的方法。第三,在压缩感知的背景下,利用frame作为稀疏化系统已成为越来越受关注的话题,我们参考了最初的论文[9]。

    [47]M. Mishali, Y. C. Eldar, and A. Elron. Xampling: Signal Acquisition and Processing in Union of Subspaces. IEEE Trans. Signal Proc., 59:4719-4734, 2011.
    [1]B. Adcock and A. C. Hansen. Generalized sampling and infinite dimensional com- pressed sensing. Preprint, 2012.
    [49]S. Nam, M. E. Davies, M. Elad, and R. Gribonval. The Cosparse Analysis Model and Algorithms. Preprint, 2012.
    [9]E. J. Cand`es, Y. C. Eldar, D. Needell, and P. Randall. Compressed Sensing with Co- herent and Redundant Dictionaries. Appl. Comput. Harmon. Anal., 31:59–73, 2011.

      读者可以参阅网页(http://dsp.rice.edu/cs),其中包含了压缩感知领域的大多数已发表论文,这些论文被细分为不同的主题。我们还想让读者注意最近的书[29]和[32]以及文章[7]。

    [29]M. Elad. Sparse and Redundant Representations. Springer, New York, 2010.
    [32]Y. C. Eldar and G. Kutyniok. Compressed Sensing: Theory and Applications. Cam- bridge University Press, 2012.
    [7]A. M. Bruckstein, D. L. Donoho, and A. Elad. From sparse solutions of systems of equations to sparse modeling of signals and images. SIAM Rev., 51:34–81, 2009.

    1.6 章节结构

    第2部分首先讨论不同的稀疏模型,包括结构化稀疏和稀疏化字典。第3部分将以 ℓ 1 \ell_1 1最小化作为恢复策略,提出精确恢复的必要和充分条件。感知矩阵设计的微妙性是第4部分的重点。第5部分介绍了稀疏恢复的其他算法方法。最后,第6部分将讨论数据分离等应用。

    展开全文
  • 压缩感知原理简介

    万次阅读 多人点赞 2019-07-15 21:51:23
    压缩感知,compressed sensing又称compressed sampling,是在采样过程中完成了数据压缩的过程。 压缩感知在信号采样的过程中,用很少的采样点,实现了和全采样一样的效果。 信号采样 学过通信原理或信号与系统的都...

    压缩感知——简介

    压缩感知,compressed sensing又称compressed sampling,是在采样过程中完成了数据压缩的过程
    压缩感知在信号采样的过程中,用很少的采样点,实现了和全采样一样的效果。

    压缩感知——信号采样

    学过通信原理或信号与系统的都知道奈奎斯特采样定理,即想让采样之后的数字信号完整保留原始信号中的信息,采样频率必须大于信号中最高频率的2倍。原因是时域以τ为间隔进行采样,频域会以1/τ为周期发生周期延拓。那么如果采样频率低于两倍的信号最高频率,信号在频域频谱搬移后就会发生混叠。
    2004年,Candes,陶哲轩和Donoho提出了压缩感知理论,该理论认为:如果信号是稀疏的,那么它可以由远低于采样定理要求的采样点重建恢复。
    突破的关键就在于采样的方式。当我们说“采样频率”的时候,意味着做的是等间距采样,数字信号领域通常都是做等间距采样,也服从奈奎斯特采样定律。
    在这里插入图片描述
    但是压缩感知采用不等间距采样,比如采用随机亚采样(图b上方的红点),那么这时候频域就不再是以固定周期进行延拓了,而是会产生大量不相关(incoherent)的干扰值。如图c,最大的几个峰值还依稀可见,只是一定程度上被干扰值覆盖。这些干扰值看上去非常像随机噪声,但实际上是由于三个原始信号的非零值发生能量泄露导致的(不同颜色的干扰值表示它们分别是由于对应颜色的原始信号的非零值泄露导致的)
    之所以随机亚采样会有这样的效果,可以理解成随机采样使得频谱不再是整齐地搬移,而是一小部分一小部分胡乱地搬移,频率泄露均匀地分布在整个频域,因而泄漏值都比较小,从而有了恢复的可能。

    压缩感知——信号恢复

    压缩感知——两个前提条件

    刚刚的例子之所以能够实现最终信号的恢复,是因为它满足了两个前提条件:

    1. 这个信号在频域只有3个非零值,所以可以较轻松地恢复出它们。
    2. 采用了随机亚采样机制,因而使频率泄露均匀地分布在整个频域。
      这两点对应了CS的两个前提条件——稀疏性(sparsity)不相关性(incoherence)
      稀疏性可以简单直观地理解为:若信号在某个域中只有少量非零值,即信号在某个域中非零点远远小于信号总点数,那么它在该域稀疏,该域也被称为信号的稀疏域
      因此,第一个前提条件要求信号必须在某一个变换域具有稀疏性。比如例子中,信号在频域是稀疏的,因而可以通过所述的重建方法轻松地在稀疏域(频域)复原出原信号。
      然而通常信号在变换域中不会呈现完全的稀疏性。其实只要它近似满足稀疏性,即大部分值趋于零,只有少量大的非零值,就可以认为它是可压缩信号,可以对它进行CS亚采样。
      对于之前讲的例子,如果它在频域中不稀疏,我们可以做DWT、DCT等,找到它的稀疏变换。

    前提条件1——稀疏性在这里插入图片描述

    前提条件2——非相关性/等距约束性

    在讲第二个前提条件之前,需要引入必要的数学表达。
    在这里插入图片描述
    上面这张图把亚采样的过程用矩阵的方式表达出来:
    如图,x是为长度N的一维信号,也就是原信号,稀疏度为k。此刻它是未知的。
    Φ为观测矩阵,对应着亚采样这一过程。它将高维信号x投影到低维空间,是已知的。
    y=Φx为长度M的一维测量值,也就是亚采样后的结果。显然它也是已知的。
    因此,压缩感知问题就是在已知测量值y和测量矩阵Φ的基础上,求解欠定方程组y=Φx得到原信号x。
    然而,一般的自然信号x本身并不是稀疏的,需要在某种稀疏基上进行稀疏表示。令x=Ψs,Ψ为稀疏基矩阵,s为稀疏系数。
    于是最终方程就变成了:y=ΦΨs。已知y、Φ、Ψ,求解s。
    y=ΦΨs有点长,我们把ΦΨ合并成一个矩阵,称之为传感矩阵。即令Θ=ΦΨ ,则y=ΘS。问题即为,已知y和Θ,求解S
    对应到一开始的例子中:
    x就是三个正弦信号叠加在一起的原信号a;
    稀疏矩阵Ψ就是傅里叶变换,将信号变换到频域S;
    观测矩阵Φ就是我们采用的随机亚采样方式;
    y就是最终的随机亚采样的结果c。
    在这里插入图片描述
    求解出S后,由x=Ψs即可得到恢复出的原信号x。
    然而在正常情况下,方程的个数远小于未知数的个数,方程是没有确定解的,无法重构信号。但是,由于信号是K稀疏,如果上式中的Φ满足有限等距性质(RIP),则K个系数就能够从M个测量值准确重构(得到一个最优解)。
    陶哲轩和Candès证明了RIP是观测矩阵要满足的准确要求。但是,要确认一个矩阵是否满足RIP非常复杂。于是Baraniuk证明:RIP的等价条件是观测矩阵和稀疏表示基不相关(incoherent)。即压缩感知的第二个前提条件。
    在这里插入图片描述
    在这里插入图片描述
    那怎样找到不相关的观测矩阵呢?陶哲轩和Candès又证明: 独立同分布的高斯随机测量矩阵可以成为普适的压缩感知测量矩阵。
    于是满足高斯分布的随机测量矩阵就成了CS最常用的观测矩阵。
    对于二维信号,往往就采用二维高斯随机测量采样矩阵对图像进行亚采样。
    对于一维信号,采用前文提到的随机不等间距的亚采样即可。

    压缩感知——重建方法

    信号采样后需要将其恢复。CS的重建也就是求解欠定方程组y=ΘS的方法。这是一个零范数(l0)最小化问题,是一个NP完全问题(没有快速解法的问题),因此往往转换成一范数(l1)最小化的求解,或者用一些近似估计的算法。
    匹配追踪是一种典型的算法。以上文中的例子为例:
    (1) 由于原信号的频率非零值在亚采样后的频域中依然保留较大的值,其中较大的两个可以通过设置阈值,检测出来(图a)。
    (2) 然后,假设信号只存在这两个非零值(图b),则可以计算出由这两个非零值引起的干扰(图c)。
    (3) 用a减去c,即可得到仅由蓝色非零值和由它导致的干扰值(图d),再设置阈值即可检测出它,得到最终复原频域(图e)
    (4) 如果原信号频域中有更多的非零值,则可通过迭代将其一一解出。
    在这里插入图片描述

    扩展:图像压缩与压缩感知

    信号的稀疏性已经在图像压缩领域有了很广泛的应用。利用信号的稀疏性,可以对信号进行压缩。如图像压缩领域的JPEG格式,就是将图像变换到离散余弦域,得到近似稀疏矩阵,只保留较大的值,从而实现压缩。
    图像压缩和压缩感知这两个概念有着本质上的区别。
    图像压缩是先进行了全采样,然后再变换域丢弃小系数,完成压缩;
    而压缩感知不同,它的思想其实从图像压缩中借鉴了很多:既然全采样了还要再丢弃,我们为什么不能直接少采样一些点?因此,压缩感知直接进行了亚采样,然后再用算法消除亚采样导致的伪影。可以说,压缩感知直接在采样时就完成了压缩
    在这里插入图片描述
    这种直接减少采样点,采集完后重建的方式,相比于图像压缩的全采用之后再压缩的方式,对于很多情形,比如照相机拍摄照片,并没有优势。因为所有像素的采集在一瞬间就都完成了。但是对于一些采集比较慢的情形,比如核磁共振成像,CS就可以发挥巨大优势。原本一副MRI图像常常需要几十秒,速度慢也是MRI的一大缺陷。而应用CS技术后,只需要采集全采样几分之一的数据,就可以重建出原图。这样就可以把成像速度提高好几倍,同时对图像质量影响不大。

    总结

    什么是压缩感知:
    如果一个信号在某个变换域是稀疏的,那么就可以用一个与变换基不相关的观测矩阵将变换所得高维信号投影到一个低维空间上,然后通过求解一个优化问题就可以从这些少量的投影中以高概率重构出原信号。
    压缩感知理论主要包括三部分:
    (1)信号的稀疏表示;
    (2)设计测量矩阵,要在降低维数的同时保证原始信号x的信息损失最小;
    (3)设计信号恢复算法,利用M个观测值无失真地恢复出长度为N的原始信号。

    从06年提出至今,已经发展出了很多算法,原来的基于l1 minimization的BP算法很慢,现在都是快速算法,而且求解算法也从纯优化方面扩展到了estimation方面,有很多基于贝叶斯估计的方法了,目前最火的也是Donoho他们组搞得AMP算法,是用Graph model里面的message passing算法通过近似求解MMSE(MAP)解。在测量矩阵方面,也已经设计出了各种矩阵,除了i.i.d. Gaussian的矩阵还有很多正交的矩阵,比如partial random DFT/DCT 矩阵。对信号的要求也从稀疏变成了存在某种结构,比如low rank,group sparse等等。(2017年进展)

    压缩感知和矩阵填充

    矩阵填充的要领是通过低秩矩阵中的已知要素还原出该矩阵的其他未知要素的进程。这几年,关于矩阵填充方法的理论研究成为压缩感知技术的一个研究热点。在实际的应用领域中涉及对高维数据的分析与处理,可以运用矩阵填充的方法来解决。其过程主要是:通过观测到的局部数据来准确填充缺失数据,从而获得完整数据矩阵的过程。
    压缩感知和矩阵填充都是稀疏约束下的反问题,压缩感知利用信号本身或在变换域中的稀疏约束性求解欠定方程,矩阵填充利用矩阵的低秩约束性求解欠定方程。
    压缩感知理论的核心问题是信号的稀疏表示、观测矩阵的设计和重构算法,信号本身或在变换域中的系数越稀疏,观测矩阵和稀疏基构成的压缩感知矩阵的受限等距常数越小,则压缩感知的性能越好。
    矩阵填充理论的核心问题是矩阵的低秩特性、非相干特性和重构算法,寻找性能良好的重构算法一直是矩阵填充理论中的一个研究重点。此外,压缩感知的应用领域已经拓展得较为广泛,但矩阵填充的应用尚处于起步阶段,挖掘矩阵填充的应用,进而将矩阵填充和压缩感知结合起来进行应用方面的探索,是非常重要和有意义的课题。
    压缩感知的性能取决于3个要素:信号的稀疏性、压缩感知矩阵的非相干性和重构算法的快速有效性。
    矩阵填充性能也取决于3个要素:矩阵的低秩性、矩阵的不相关性和重构算法的快速有效性。

    低秩矩阵

    还记得我们怎么手工求矩阵的秩吗?为了求矩阵A的秩,我们是通过矩阵初等变换把A化为阶梯型矩阵,若该阶梯型矩阵有r个非零行,那A的秩rank(A)就等于r。从物理意义上讲,矩阵的秩度量的就是矩阵的行列之间的相关性。如果矩阵的各行或列是线性无关的,矩阵就是满秩的,也就是秩等于行数。回到上面线性方程组来说吧,因为线性方程组可以用矩阵描述嘛。秩就表示了有多少个有用的方程了。上面的方程组有3个方程,实际上只有2个是有用的,一个是多余的,所以对应的矩阵的秩就是2了。
    OK。既然秩可以度量相关性,而矩阵的相关性实际上就表示了矩阵的结构信息。如果矩阵之间各行的相关性很强,那么就表示这个矩阵实际可以投影到更低维的线性子空间,也就是用几个向量就可以完全表达了,它就是低秩的。所以我们总结的一点就是:如果矩阵表达的是结构性信息,例如图像、用户-商品推荐表等等,那么这个矩阵各行之间存在这一定的相关性,那这个矩阵一般就是低秩的。
    如果X是一个m行n列的数值矩阵,rank(X)是X的秩,假如rank (X)远小于m和n,则我们称X是低秩矩阵。低秩矩阵每行或每列都可以用其他的行或列线性表出,可见它包含大量的冗余信息。利用这种冗余信息,可以对缺失数据进行恢复,也可以对数据进行特征提取。

    应用

    矩阵填充越来越多的应用在协同滤波、系统识别、无线传感网络、视频去噪、人脸识别、医学成像等领域,正在发挥着巨大的作用。特别是在室内定位中的 应用越来越多,是当下的研究热点之一。

    参考网址:
    形象易懂讲解算法II——压缩感知(非常好)
    AndyJee:浅谈压缩感知系列——博客园(非常丰富)
    压缩感知理论
    机器学习——低秩矩阵分解中低秩的意义、矩阵填补、交叉验证

    展开全文
  • 早期压缩感知在光学成像领域应用主要集中在空域压缩成像。近年来,更多的空域压缩成像采用阵列式探测器取代单元探测器采集测量值。同时,压缩成像的研究也从二维空间拓展到三维测距、高速成像、多光谱成像、关联成像...
  • 首先介绍了压缩感知在无线传感网络领域的发展及研究现状,然后从压缩感知仿真实验和实例、压缩感知的测量方案、压缩感知的解压缩方案、压缩感知在无线传感网络的具体应用四个方面阐明了压缩感知在无线传感网络领域的...
  • 压缩感知理论在图像处理领域应用压缩感知在图像处理方面的应用论文,系统的介绍了压缩感知技术,很适合初学者。
  • 2.介绍了情感识别中所涉及的压缩感知理论、语音识别关键技术和人脸识别的关键技术。采用小波基对人脸图像进行特征提取,同时采用DCT基的压缩感知稀疏化来处理语音信号。 3.经过建模和仿真给出相应的图像和语音处理...
  • 压缩感知中贪婪算法

    2018-04-17 14:09:54
    这里主要是压缩感知的贪婪算法,通过omp来实现doa的估计,主要应用在阵列信号处理领域
  • 本文首先介绍了单比特压缩感知的发展和研究现状,然后从检测和不检测观测符号两个方面对重构算法进行了分析,接着从单比特压缩感知的成像领域、无线传感器网络领域、医学图像领域和信号传输领域四个应用领域进行分析...
  • 压缩感知及其资料

    2018-08-27 18:12:23
    动态压缩感 (Dynamic compressed sensing, DCS) 知由视频信号处理问题引出, 是压缩感知 (Compressed sensing, CS) 理论研究领域中新兴起的一个研究分支, ... 最后, 讨论动态压缩感知应用, 并对其研究前景进行展望.
  • 【新智元导读】DeepMind提出一种全新的“深度压缩感知”框架,将压缩感知与深度学习相结合,显著提高了信号恢复的性能和速度,并提出一种改进GAN的新方法。 压缩感知(CS)是一种优雅的框架,用于从压缩信号中恢复...

    https://www.toutiao.com/a6694045305064653324/

     

    DeepMind论文:深度压缩感知,新框架提升GAN性能

     

    【新智元导读】DeepMind提出一种全新的“深度压缩感知”框架,将压缩感知与深度学习相结合,显著提高了信号恢复的性能和速度,并提出一种改进GAN的新方法。

    压缩感知(CS)是一种优雅的框架,用于从压缩信号中恢复稀疏信号。

    例如,CS可以利用自然图像的结构,仅从少量的随机测量中恢复图像。

    CS具有灵活性和数据效率高的优点,但由于其稀疏性和昂贵的重建过程,CS的应用受到限制。

    那么,将CS与深度学习的思想相结合,是否能得到更优雅的框架呢?

    近日,DeepMind的Yan Wu,Mihaela Rosca,Timothy Lillicrap等研究人员在ICML 2019发表论文Deep Compressed Sensing,基于前人将CS和神经网络生成器结合起来的方法,提出一个全新的框架。

    DeepMind论文:深度压缩感知,新框架提升GAN性能

     

    深度压缩感知(DCS)框架通过联合训练生成器和通过元学习优化重建过程,显著提高了信号恢复的性能和速度。作者探索了针对不同目标的测量训练,并给予最小化测量误差推导出一系列模型。

    作者表示:“我们证明了,生成对抗网络(GANs)可以被视为这个模型家族中的一个特例。借鉴CS的思想,我们开发了一种使用来自鉴别器的梯度信息来改进GAN的新方法。”

    压缩感知,一种优雅的框架

    压缩感知是什么呢?

    有人这样评价道:

    压缩感知是信号处理领域进入 21 世纪以来取得的最耀眼的成果之一,并在磁共振成像、图像处理等领域取得了有效应用。压缩感知理论在其复杂的数学表述背后蕴含着非常精妙的思想。基于一个有想象力的思路,辅以严格的数学证明,压缩感知实现了神奇的效果,突破了信号处理领域的金科玉律 —— 奈奎斯特采样定律。即,在信号采样的过程中,用很少的采样点,实现了和全采样一样的效果。[1]

    编码和解码是通信中的核心问题。压缩感知(CS)提供了将编码和解码分离为独立的测量和重建过程的框架。与常用的自动编码模型(具有端到端训练的编码器和解码器对)不同,CS通过在线优化从低维测量重建信号。

    该模型架构具有高度的灵活性和采样效率:高维信号可以从少量随机测量数据中重建,几乎不需要或根本不需要任何训练

    CS已经成功地应用于测量噪声大、成本高的场景,如MRI。它的采样效率使得诸如“单像素相机”的开发成为可能,可以从单个光传感器重全分辨率的图像。

    然而,尤其是在现代深度学习方法蓬勃发展的大规模数据处理中,CS的广泛应用受到了它的稀疏信号假设和重建优化过程缓慢的阻碍。

    最近,Bora et al. (2017)将CS与单独训练的神经网络生成器相结合。虽然这些预训练的神经网络没有针对CS进行优化,但它们表现出的重建性能优于现有的方法,如Lasso (Tibshirani, 1996)。

    在本文中,我们提出一种深度压缩感知框架(deep compressed sensing,DCS),在此框架中,神经网络可以从头开始训练,用于测量和在线重建。

    我们证明,深度压缩感知框架可以自然地生成一系列模型,包括GANs,可以通过训练具有不同目标的测量函数推导得出。

    这项工作的贡献如下:

    • 我们展示了如何在CS框架下训练深度神经网络。
    • 结果表明,与以往的模型相比,元学习重建方法具有更高的精度和快几个数量级的速度。
    • 我们开发了一种新的基于潜在优化的GAN训练算法,提高了GAN的性能。
    • 我们将这个新框架扩展到训练半监督GAN,并表明潜在优化会产生具有语义意义的潜在空间。

    深度压缩感知:结合深度神经网络

    我们首先展示了将元学习与Bora et al. (2017)的模型相结合的好处。然后将测量矩阵推广到参数化的测量函数,包括深度神经网络。

    之前的工作依赖于 random projection作为测量函数,而我们的方法通过将RIP作为训练目标来学习测量函数。然后,我们通过在测量上添加RIP之外的其他特性,得到了两个新的模型,包括一个带有鉴别器引导的潜在优化的GAN模型,这导致了更稳定的训练动态和更好的结果。

    压缩感知与元学习

    我们假设CSGM(Bora et al. 2017)的运行时效率和性能可以通过使用元学习训练潜在的优化过程、通过梯度下降步骤的反向传播来提高。

    CS模型的潜在优化过程可能需要数百个或数千个梯度下降步骤。通过使用元学习来优化这个优化过程,我们的目标是用更少的更新来实现类似的结果。

    为此,我们训练模型参数,以及潜在的优化程序,以尽量减低预期的测量误差:

    DeepMind论文:深度压缩感知,新框架提升GAN性能

     

    我们的算法如下:

    DeepMind论文:深度压缩感知,新框架提升GAN性能

    算法1:元学习压缩感知

    具有学习测量函数的深度压缩感知

    在算法1中,我们使用RIP属性来训练生成器。我们可以使用相同的方法,并加强RIP属性来学习测量函数F本身,而不是使用random projection。

    下面的算法2总结了这个扩展算法。我们称之为深度压缩感知(DCS) ,以强调测量和重建可以是深度神经网络。

    DeepMind论文:深度压缩感知,新框架提升GAN性能

    算法2:深度压缩感知

    实验和结果

    表2和表3总结了我们的模型以及Bora等人的基准模型的结果。

    DeepMind论文:深度压缩感知,新框架提升GAN性能

     

    表2:使用不同测量函数的MNIST测试数据的重建损失。除了第一行之外,所有行都来自我们的模型。“±”表示测试样本间的标准差。(L)表示习得的测量函数,越低越好。

    DeepMind论文:深度压缩感知,新框架提升GAN性能

     

    表3:使用不同测量函数的CelebA测试数据的重建损失。除了第一行之外,所有行都来自我们的模型。“±”表示测试样本间的标准差。(L)表示习得的测量函数,越低越好。

    可以看到,DCS的性能明显优于基准。此外,虽然基线模型使用了数千个梯度下降步骤,并且多次重启,但是我们只使用了3个步骤,没有重启,大幅提高了效率。

    有趣的是,对于固定的函数F,随机线性投影的表现优于神经网络。这个实证结果符合压缩感知文献中描述的随机投影的最优性,以及更通用的Johnson-Lindenstrauss定理。

    更多结果如下:

    DeepMind论文:深度压缩感知,新框架提升GAN性能

     

    表4:与 Spectral Normalised GANs的比较。

    DeepMind论文:深度压缩感知,新框架提升GAN性能

     

    图2:利用随机线性投影(上)、训练线性投影(中)和训练神经网络(下)的10个测量的重建。

    DeepMind论文:深度压缩感知,新框架提升GAN性能

     

    图3:使用0(左)、3(中)和5(右)个梯度下降步骤进行潜在优化的CS-GAN样本。采用0步骤的CS-GAN相当于原始GAN。

    DeepMind论文:深度压缩感知,新框架提升GAN性能

     

    图4:在CIFAR训练期间的Inception Score(越高越好)和FID分数(越低越好)。

    论文地址:

    https://arxiv.org/pdf/1905.06723.pdf

    参考:

    [1]形象易懂讲解算法 II—— 压缩感知

    https://zhuanlan.zhihu.com/p/22445302

    展开全文
  • 首先根据压缩感知理论的特点将其应用于图像融合领域, 并采用Min-TV 的方法重构图像; 然后对NSCT 进行分解, 其计算量较大的带通子带系数采用基于压缩感知理论的图像融合方法; 最后对低通融合图像和带通融合图像进行...
  • 本文综述了CS理论框架及关键技术问题,并着重介绍了信号稀疏变换、观测矩阵设计和重构算法三个方面的最新进展,评述了其中的公开问题,对研究中现存的难点问题进行了探讨,最后介绍了CS理论的应用领域.
  • 压缩感知l1重建算法matlab代码稀疏引力波 稀疏方法(和压缩感测)应用于重力波信号处理 如果不是稀疏方法,互联网将是一个漂亮但相对空白的地方。 大多数有损压缩方法(例如,在图像的情况下)基于以下观察结果:...
  • 压缩感知文献10篇

    2016-08-30 15:55:59
    收集了10篇有关压缩感知的文献,包括原理、及其在各个领域应用,pdf格式,适合从事相关研究工作人员阅读参考
  • 压缩感知英文综述

    2014-09-09 10:17:58
    国际上出现的压缩感知理论( Compre ss e d S e ns i ng, CS ) 为缓解这些压力提供了解决方法. 本文综述了 CS 理论框架及关键 技术问题, 并着重介绍了信号稀疏变换、 观测矩阵设计和重构算法三个方面的最新进展, 评述...
  • 压缩感知技术

    千次阅读 2019-01-21 17:15:11
    纯学习的态度分享博客: ...——————————————————————————————————————————————...1、压缩感知与单像素相机(陶哲轩,Terence Tao) 原文链接:http://songshuhui.net/archi...

    纯学习的态度分享博客:
    源博文链接 https://www.cnblogs.com/AndyJee/p/5045668.html

    —————————————————————————————————————————————————————
    分享两篇来自科学松鼠会的科普性文章:

    1、压缩感知与单像素相机(陶哲轩,Terence Tao)

    原文链接:http://songshuhui.net/archives/11006

    2、填补空白:用数学方法将低分辨率图像变成高分辨率图像(Jordan Ellenberg)

    原文链接:http://songshuhui.net/archives/38054

    英文名:Fill in the Blanks: Using Math to Turn Lo-Res Datasets Into Hi-Res Samples

    英文链接:http://songshuhui.net/archives/35169

    一、压缩感知与单像素相机
    木遥按:这是数学家陶哲轩在他自己的blog上写的一篇科普文章,讨论的是近年来在应用数学领域里最热门的话题之一:压缩感知(compressed sensing)。所谓压缩感知,最核心的概念在于试图从原理上降低对一个信号进行测量的成本。比如说,一个信号包含一千个数据,那么按照传统的信号处理理论,至少需要做一千次测量才能完整的复原这个信号。这就相当于是说,需要有一千个方程才能精确地解出一千个未知数来。但是压缩感知的想法是假定信号具有某种特点(比如文中所描述得在小波域上系数稀疏的特点),那么就可以只做三百次测量就完整地复原这个信号(这就相当于只通过三百个方程解出一千个未知数)。可想而知,这件事情包含了许多重要的数学理论和广泛的应用前景,因此在最近三四年里吸引了大量注意力,得到了非常蓬勃的发展。陶哲轩本身是这个领域的奠基人之一(可以参考《陶哲轩:长大的神童》一文),因此这篇文章的权威性毋庸讳言。另外,这也是比较少见的由一流数学家直接撰写的关于自己前沿工作的普及性文章。需要说明的是,这篇文章是虽然是写给非数学专业的读者,但是也并不好懂,也许具有一些理工科背景会更容易理解一些。

    【作者 Terence Tao;译者 山寨盲流,他的更多译作在这,那;校对 木遥】

    最近有不少人问我究竟"压缩感知"是什么意思(特别是随着最近这个概念名声大噪),所谓“单像素相机”又是怎样工作的(又怎么能在某些场合比传统相机有优势呢)。这个课题已经有了大量文献,不过对于这么一个相对比较新的领域,还没有一篇优秀的非技术性介绍。所以笔者在此小做尝试,希望能够对非数学专业的读者有所帮助。

    具体而言我将主要讨论摄像应用,尽管压缩传感作为测量技术应用于比成像广泛得多的领域(例如天文学,核磁共振,统计选取,等等),我将在帖子结尾简单谈谈这些领域。

    相机的用途,自然是记录图像。为了简化论述,我们把图像假设成一个长方形阵列,比如说一个1024x2048像素的阵列(这样就总共是二百万像素)。为了省略彩色的问题(这个比较次要),我们就假设只需要黑白图像,那么每个像素就可以用一个整型的灰度值来计量其亮度(例如用八位整型数表示0到255,16位表示0到65535)。

    接下来,按照最最简化的说法,传统相机会测量每一个像素的亮度(在上述例子中就是二百万个测量值),结果得到的图片文件就比较大(用8位灰度值就是2MB,16位灰度就是4MB)。数学上就认为这个文件是用超高维矢量值描绘的(在本例中就是约二百万维)。

    在我开始讲“压缩感知”这个新故事之前,必须先快速回顾一下“老式压缩”的旧故事。(已经了解图像压缩算法的读者可以跳过这几段。)

    上述的图片会占掉相机的很多存储空间(上传到计算机里还占磁盘空间),在各种介质之间传输的时候也要浪费时间。于是,相机带有显著压缩图像的功能就顺理成章了(通常能从2MB那么大压缩到十分之一——200KB的一小坨)。关键是尽管“所有图片”所构成的空间要占用2MB的“自由度”或者说“熵”,由“有意义的图片”所构成的空间其实要小得多,尤其是如果人们愿意降低一点图像质量的话。(实际上,如果一个人真的利用所有的自由度随机生成一幅图片,他不大可能得到什么有意义的图像,而是得到相当于电视荧屏上的静电雪花那样的随机噪声之类。)

    怎么样压缩图像?方式多种多样,其中有些非常先进,不过我来试试用一种不太高科技的(而且也不太精确的)说法来描述一下这些先进技术。图像通常都含有大片无细节部分–比如在风景照里面,将近一半的画面都可能被单色的天空背景占据。我们假设提取一个大方块,比方说100x100像素,其中完全是同一颜色的——假设是全白的吧。无压缩时,这个方块要占10000字节存储空间(按照8位灰度算);但是我们可以只记录这个方块的维度和坐标,还有填充整个方块的单一颜色;这样总共也只要记录四五个字节,省下了可观的空间。不过在现实中,压缩效果没有这么好,因为表面看来没有细节的地方其实是有着细微的色差的。所以,给定一个无细节方块,我们记录其平均色值,就把图片中这一块区域抽象成了单色色块,只留下微小的残余误差。接下来就可以继续选取更多色彩可见的方块,抽象成单色色块。最后剩下的是亮度(色彩强度)很小的,肉眼无法察觉的细节。于是就可以抛弃这些剩余的细节,只需要记录那些“可见”色块的大小,位置和亮度。日后则可以反向操作,重建出比原始图像质量稍低一些,占空间却小得多的复制图片。

    其实上述的算法并不适合处理颜色剧烈变动的情况,所以在实际应用中不很有效。事实上,更好的办法不是用均匀色块,而是用“不均匀”的色块——比方说右半边色彩强度平均值大于左半边这样的色块。这种情况可以用(二维)Haar小波系统来描述。后来人们又发现一种"更平滑的"小波系统更能够避免误差,不过这都是技术细节,我们就不深入讨论了。然而所有这些系统的原理都是相同的:把原始图像表示为不同“小波(类似于上文中的色块)”的线性叠加,记录显著的(高强度的)小波的系数,放弃掉(或者用阈值排除掉)剩下的小波系数。这种“小波系数硬阈值”压缩算法没有实际应用的算法(比如JPEG 2000标准中所定义的)那么精细,不过多少也能描述压缩的普遍原理。

    总体来讲(也是非常简化的说法),原始的1024x2048图像可能含有两百万自由度,想要用小波来表示这个图像的人需要两百万个不同小波才能完美重建。但是典型的有意义的图像,从小波理论的角度看来是非常稀疏的,也就是可压缩的:可能只需要十万个小波就已经足够获取图像所有的可见细节了,其余一百九十万小波只贡献很少量的,大多数观测者基本看不见的“随机噪声”。(这也不是永远适用:含有大量纹理的图像–比如毛发、毛皮的图像——用小波算法特别难压缩,也是图像压缩算法的一大挑战。不过这是另一个故事了。)

    接下来呢,如果我们(或者不如说是相机)事先知道两百万小波系数里面哪十万个是重要的,那就可以只计量这十万个系数,别的就不管了。(在图像上设置一种合适的“过滤器”或叫“滤镜”,然后计量过滤出来的每个像素的色彩强度,是一种可行的系数计量方法。)但是,相机是不会知道哪个系数是重要的,所以它只好计量全部两百万个像素,把整个图像转换成基本小波,找出需要留下的那十万个主导基本小波,再删掉其余的。(这当然只是真正的图像压缩算法的一个草图,不过为了便于讨论我们还是就这么用吧。)

    那么,如今的数码相机当然已经很强大了,没什么问题干吗还要改进?事实上,上述的算法,需要收集大量数据,但是只需要存储一部分,在消费摄影中是没有问题的。尤其是随着数据存储变得很廉价,现在拍一大堆完全不压缩的照片也无所谓。而且,尽管出了名地耗电,压缩所需的运算过程仍然算得上轻松。但是,在非消费领域的某些应用中,这种数据收集方式并不可行,特别是在传感器网络中。如果打算用上千个传感器来收集数据,而这些传感器需要在固定地点呆上几个月那么长的时间,那么就需要尽可能地便宜和节能的传感器——这首先就排除了那些有强大运算能力的传感器(然而——这也相当重要——我们在接收处理数据的接收端仍然需要现代科技提供的奢侈的运算能力)。在这类应用中,数据收集方式越“傻瓜”越好(而且这样的系统也需要很强壮,比如说,能够忍受10%的传感器丢失或者各种噪声和数据缺损)。

    这就是压缩传感的用武之地了。其理论依据是:如果只需要10万个分量就可以重建绝大部分的图像,那何必还要做所有的200万次测量,只做10万次不就够了吗?(在实际应用中,我们会留一个安全余量,比如说测量30万像素,以应付可能遭遇的所有问题,从干扰到量化噪声,以及恢复算法的故障。)这样基本上能使节能上一个数量级,这对消费摄影没什么意义,对传感器网络而言却有实实在在的好处。

    不过,正像我前面说的,相机自己不会预先知道两百万小波系数中需要记录哪十万个。要是相机选取了另外10万(或者30万),反而把图片中所有有用的信息都扔掉了怎么办?

    解决的办法简单但是不太直观。就是用非小波的算法来做30万个测量——尽管我前面确实讲过小波算法是观察和压缩图像的最佳手段。实际上最好的测量其实应该是(伪)随机测量——比如说随机生成30万个“滤镜”图像并测量真实图像与每个滤镜的相关程度。这样,图像与滤镜之间的这些测量结果(也就是“相关性”)很有可能是非常小非常随机的。但是——这是关键所在——构成图像的2百万种可能的小波函数会在这些随机的滤镜的测量下生成自己特有的“特征”,它们每一个都会与某一些滤镜成正相关,与另一些滤镜成负相关,但是与更多的滤镜不相关。可是(在极大的概率下)2百万个特征都各不相同;更有甚者,其中任意十万个的线性组合仍然是各不相同的(以线性代数的观点来看,这是因为一个30万维线性子空间中任意两个10万维的子空间极有可能互不相交)。因此,基本上是有可能从这30万个随机数据中恢复图像的(至少是恢复图像中的10万个主要细节)。简而言之,我们是在讨论一个哈希函数的线性代数版本。

    然而这种方式仍然存在两个技术问题。首先是噪声问题:10万个小波系数的叠加并不能完全代表整幅图像,另190万个系数也有少许贡献。这些小小贡献有可能会干扰那10万个小波的特征,这就是所谓的“失真”问题。第二个问题是如何运用得到的30万测量数据来重建图像。

    我们先来关注后一个问题。如果我们知道了2百万小波中哪10万个是有用的,那就可以使用标准的线性代数方法(高斯消除法,最小二乘法等等)来重建信号。(这正是线性编码最大的优点之一——它们比非线性编码更容易求逆。大多数哈希变换实际上是不可能求逆的——这在密码学上是一大优势,在信号恢复中却不是。)可是,就像前面说的那样,我们事前并不知道哪些小波是有用的。怎么找出来呢?一个单纯的最小二乘近似法会得出牵扯到全部2百万系数的可怕结果,生成的图像也含有大量颗粒噪点。要不然也可以代之以一种强力搜索,为每一组可能的10万关键系数都做一次线性代数处理,不过这样做的耗时非常恐怖(总共要考虑大约10的17万次方个组合!),而且这种强力搜索通常是NP完备的(其中有些特例是所谓的“子集合加总”问题)。不过还好,还是有两种可行的手段来恢复数据:

    • 匹配追踪:找到一个其标记看上去与收集到的数据相关的小波;在数据中去除这个标记的所有印迹;不断重复直到我们能用小波标记“解释”收集到的所有数据。

    • 基追踪(又名L1模最小化):在所有与录得数据匹配的小波组合中,找到一个“最稀疏的”,也就是其中所有系数的绝对值总和越小越好。(这种最小化的结果趋向于迫使绝大多数系数都消失了。)这种最小化算法可以利用单纯形法之类的凸规划算法,在合理的时间内计算出来。

    需要注意到的是,这类图像恢复算法还是需要相当的运算能力的(不过也还不是太变态),不过在传感器网络这样的应用中这不成问题,因为图像恢复是在接收端(这端有办法连接到强大的计算机)而不是传感器端(这端就没办法了)进行的。

    现在已经有严密的结果显示,对原始图像设定不同的压缩率或稀疏性,这两种算法完美或近似完美地重建图像的成功率都很高。匹配追踪法通常比较快,而基追踪算法在考虑到噪声时则显得比较准确。这些算法确切的适用范围问题在今天仍然是非常热门的研究领域。(说来遗憾,目前还没有出现对P不等于NP问题的应用;如果一个重建问题(在考虑到测量矩阵时)是NP完备的,那它刚好就不能用上述算法解决。)

    由于压缩传感还是一个相当新的领域(尤其是严密的数学结果刚刚出现),现在就期望这个技术应用到实用的传感器上还为时尚早。不过已经有概念验证模型出现了,其中最著名的是Rice大学研制的单像素相机。

    最后必须提到的是,压缩传感技术是一种抽象的数学概念,而不是具体的操作方案,它可以应用到成像以外的许多领域。以下只是其中几个例子:

    • 磁共振成像(MRI)。在医学上,磁共振的工作原理是做许多次(但次数仍是有限的)测量(基本上就是对人体图像进行离散拉东变换(也叫X光变换)),再对数据进行加工来生成图像(在这里就是人体内水的密度分布图像)。由于测量次数必须很多,整个过程对患者来说太过漫长。压缩传感技术可以显著减少测量次数,加快成像(甚至有可能做到实时成像,也就是核磁共振的视频而非静态图像)。此外我们还可以以测量次数换图像质量,用与原来一样的测量次数可以得到好得多的图像分辨率。

    • 天文学。许多天文现象(如脉冲星)具有多种频率震荡特性,使其在频域上是高度稀疏也就是可压缩的。压缩传感技术将使我们能够在时域内测量这些现象(即记录望远镜数据)并能够精确重建原始信号,即使原始数据不完整或者干扰严重(原因可能是天气不佳,上机时间不够,或者就是因为地球自传使我们得不到全时序的数据)。

    • 线性编码。压缩传感技术提供了一个简单的方法,让多个传送者可以将其信号带纠错地合并传送,这样即使输出信号的一大部分丢失或毁坏,仍然可以恢复出原始信号。例如,可以用任意一种线性编码把1000比特信息编码进一个3000比特的流;那么,即使其中300位被(恶意)毁坏,原始信息也能完全无损失地完美重建。这是因为压缩传感技术可以把破坏动作本身看作一个稀疏的信号(只集中在3000比特中的300位)。

    许多这种应用都还只停留在理论阶段,可是这种算法能够影响测量和信号处理中如此之多的领域,其潜力实在是振奋人心。笔者自己最有成就感的就是能看到自己在纯数学领域的工作(例如估算傅立叶子式的行列式或单数值)最终具备造福现实世界的前景。

    二、填补空缺——压缩感知
    红猪按(by 木遥)

    压缩感知是近年来极为热门的研究前沿,在若干应用领域中都引起瞩目。关于这个题目,松鼠会已经翻译了两篇文章,一篇来自于压缩感知技术最初的研究者陶哲轩(链接),一篇来自威斯康辛大学的数学家艾伦伯格(本文正文)。这两篇文章都是普及性的,但是由于作者是专业的研究人员,所以事实上行文仍然偏于晦涩。因此我不揣冒昧,在这里附上一个画蛇添足的导读,以帮助更多的读者更好了解这个新颖的研究领域在理论和实践上的意义。

    压缩感知从字面上看起来,好像是数据压缩的意思,而实则出于完全不同的考虑。经典的数据压缩技术,无论是音频压缩(例如 mp3),图像压缩(例如 jpeg),视频压缩(mpeg),还是一般的编码压缩(zip),都是从数据本身的特性出发,寻找并剔除数据中隐含的冗余度,从而达到压缩的目的。这样的压缩有两个特点:第一、它是发生在数据已经被完整采集到之后;第二、它本身需要复杂的算法来完成。相较而言,解码过程反而一般来说在计算上比较简单,以音频压缩为例,压制一个 mp3 文件的计算量远大于播放(即解压缩)一个 mp3 文件的计算量。

    稍加思量就会发现,这种压缩和解压缩的不对称性正好同人们的需求是相反的。在大多数情况下,采集并处理数据的设备,往往是廉价、省电、计算能力较低的便携设备,例如傻瓜相机、或者录音笔、或者遥控监视器等等。而负责处理(即解压缩)信息的过程却反而往往在大型计算机上进行,它有更高的计算能力,也常常没有便携和省电的要求。也就是说,我们是在用廉价节能的设备来处理复杂的计算任务,而用大型高效的设备处理相对简单的计算任务。这一矛盾在某些情况下甚至会更为尖锐,例如在野外作业或者军事作业的场合,采集数据的设备往往曝露在自然环境之中,随时可能失去能源供给或者甚至部分丧失性能,在这种情况下,传统的数据采集-压缩-传输-解压缩的模式就基本上失效了。

    压缩感知的概念就是为了解决这样的矛盾而产生的。既然采集数据之后反正要压缩掉其中的冗余度,而这个压缩过程又相对来说比较困难,那么我们为什么不直接「采集」压缩后的数据?这样采集的任务要轻得多,而且还省去了压缩的麻烦。这就是所谓的「压缩感知」,也就是说,直接感知压缩了的信息。

    可是这看起来是不可能的事情。因为压缩后的数据并不是压缩前的数据的一个子集,并不是说,本来有照相机的感光器上有一千万个像素,扔掉其中八百万个,剩下的两百万个采集到的就是压缩后的图像,──这样只能采集到不完整的一小块图像,有些信息被永远的丢失了而且不可能被恢复。如果要想采集很少一部分数据并且指望从这些少量数据中「解压缩」出大量信息,就需要保证:第一:这些少量的采集到的数据包含了原信号的全局信息,第二:存在一种算法能够从这些少量的数据中还原出原先的信息来。

    有趣的是,在某些特定的场合,上述第一件事情是自动得到满足的。最典型的例子就是医学图像成像,例如断层扫描(CT)技术和核磁共振(MRI)技术。对这两种技术稍有了解的人都知道,这两种成像技术中,仪器所采集到的都不是直接的图像像素,而是图像经历过全局傅立叶变换后的数据。也就是说,每一个单独的数据都在某种程度上包含了全图像的信息。在这种情况下,去掉一部分采集到的数据并不会导致一部分图像信息永久的丢失(它们仍旧被包含在其它数据里)。这正是我们想要的情况。

    上述第二件事就要归功于陶哲轩和坎戴的工作了。他们的工作指出,如果假定信号(无论是图像还是声音还是其他别的种类的信号)满足某种特定的「稀疏性」,那么从这些少量的测量数据中,确实有可能还原出原始的较大的信号来,其中所需要的计算部分是一个复杂的迭代优化过程,即所谓的「L1-最小化」算法。

    把上述两件事情放在一起,我们就能看到这种模式的优点所在。它意味着:我们可以在采集数据的时候只简单采集一部分数据(「压缩感知」),然后把复杂的部分交给数据还原的这一端来做,正好匹配了我们期望的格局。在医学图像领域里,这个方案特别有好处,因为采集数据的过程往往是对病人带来很大麻烦甚至身体伤害的过程。以 X 光断层扫描为例,众所周知 X 光辐射会对病人造成身体损害,而「压缩感知」就意味着我们可以用比经典方法少得多的辐射剂量来进行数据采集,这在医学上的意义是不言而喻的。

    这一思路可以扩展到很多领域。在大量的实际问题中,我们倾向于尽量少地采集数据,或者由于客观条件所限不得不采集不完整的数据。如果这些数据和我们所希望重建的信息之间有某种全局性的变换关系,并且我们预先知道那些信息满足某种稀疏性条件,就总可以试着用类似的方式从比较少的数据中还原出比较多的信号来。到今天为止,这样的研究已经拓展地非常广泛了。
    但是同样需要说明的是,这样的做法在不同的应用领域里并不总能满足上面所描述的两个条件。有的时候,第一个条件(也就是说测量到的数据包含信号的全局信息)无法得到满足,例如最传统的摄影问题,每个感光元件所感知到的都只是一小块图像而不是什么全局信息,这是由照相机的物理性质决定的。为了解决这个问题,美国 Rice 大学的一部分科学家正在试图开发一种新的摄影装置(被称为「单像素照相机」),争取用尽量少的感光元件实现尽量高分辨率的摄影。有的时候,第二个条件(也就是说有数学方法保证能够从不完整的数据中还原出信号)无法得到满足。这种时候,实践就走在了理论前面。人们已经可以在算法上事先很多数据重建的过程,但是相应的理论分析却成为了留在数学家面前的课题。

    但是无论如何,压缩感知所代表的基本思路:从尽量少的数据中提取尽量多的信息,毫无疑问是一种有着极大理论和应用前景的想法。它是传统信息论的一个延伸,但是又超越了传统的压缩理论,成为了一门崭新的子分支。它从诞生之日起到现在不过五年时间,其影响却已经席卷了大半个应用科学。

    译者:Armeny 原文 校对:拟南芥、剃刀、木遥

    扩展阅读:数字图像的压缩与恢复/奥卡姆剃刀

    2009年早春,斯坦福大学露西尔·帕卡德儿童医院的一组医生把一名两岁男孩送进磁共振成像[f1] 扫描仪。这个将被我称为布赖斯的男孩身处巨洞般的金属仪器中,看上去是那么弱小无助。他被施以全身麻醉,一根弯弯曲曲的管子从他的咽喉联接到扫描仪傍的呼吸机上。十个月前, 布赖斯接受了肝脏移植术,来自捐献者的部分肝脏取代了他自己的已坏死的肝脏。他的康复情况一度不错。但是,最近的实验室测试结果令人担忧,他的身体出现了问题——可能一条或者全部的两条胆管被堵住了。

    帕卡德医院的儿童放射科医生施里亚斯·瓦萨纳瓦拉需要高精度的扫描结果来告诉他问题出在哪,但是这将意味着他的小病人在扫描过程中不得不保持绝对静止。哪怕布赖斯只是呼吸了一次,成像结果都会变得模糊。要避免上述情况,就需要进行足够深的麻醉让病人停止呼吸。进行一次标准的磁共振成像检测需要两分钟时间,但如果麻醉师真的让布赖斯在这么长时间里停止呼吸,那么带来的问题将远远超过他肝脏的小毛病。

    不过,瓦萨纳瓦拉和他的电子工程师同事迈克尔·勒斯蒂格打算使用一种快得多的新扫描方法,名曰“压缩感知”。这种技术可能是当今应用数学界最热门的话题了。未来,它可能会改变我们寻找遥远星系的方式。而现在,这种技术使得瓦萨纳瓦拉和勒斯蒂格只需要40秒就可以采集到精确重建布赖斯肝脏图像所需的数据。

    压缩感知的发现纯属偶然。2004年2月,伊曼纽尔·坎迪斯正在自己的电脑上看着Shepp-Logan图像(译注:这是医学图像处理领域用来进行仿真测试的标准模拟图像,由一些大大小小的椭圆模拟生物器官)打发时间。这幅通常被计算机科学家和工程师用于测试成像算法的标准图像,看起来就像《第三类接触》里那个搞笑地将眉毛扬起的外星人。坎迪斯,斯坦福大学教授,曾在加州理工学院工作过,打算用一个严重失真的模型图像作为磁共振成像仪不能精确扫描而产生的非清晰图像来进行实验。他想到一种名为L1(校对注:这里虽然原文用的是小写,但是在中文上下文中用小写则极易同11混淆,而数学上这里大小写都可以用)范数极小化的数学技术可能有助于清除小部分斑痕。他按下一个键,算法运行起来了。

    坎迪斯希望屏幕上的模型图像变得稍微清晰一些。但是,他突然发现用残缺的数据渲染出来的图像是那么细腻完美,对每个细节而言都是如此,这简直就像变魔术一样。太不可思议了,他认为。“这就好像,你给了我十位银行账号的前三位,然后我能够猜出接下来的七位数字。”他说。他尝试在不同类型的模型图像上重新进行这个实验,结果都非常好。

    在博士后贾斯廷·龙伯格的帮助下,坎迪斯提出了一个粗略的理论。之后,他在黑板上向加州大学洛杉矶分校的同事陶哲轩介绍了自己的理论。坎迪斯在结束讨论离开的时候觉得陶哲轩对此持怀疑态度,毕竟,图像清晰度的提高也太离谱了。然而,第二天晚上,陶哲轩给坎迪斯送去关于他们之前讨论的问题的一叠笔记。这叠笔记为他们共同发表的第一篇论文奠定了基础。在随后的两年中,他们写了更多文章。

    上面介绍的是压缩感知技术的开端,这个数学界的全新领域改变了人们处理大规模数据集的方式。仅仅六年时光,它为上千篇论文提供了灵感,吸引了数百万美元的联邦基金。2006年,坎迪斯在这一领域内的工作为他赢得了奖金值50万美元的沃特曼奖,这是美国国家科学基金授予研究者的最高荣誉。其原因是显而易见的。想象一下,磁共振成像仪可以在几秒钟的时间里生成原本需要花费一个小时才能生成的图像;军用软件截获敌方通信的能力得到极大加强;传感器能够解析遥远星际的无线电波。突然之间,数据的采集、操作以及解析都变得容易了。

    压缩感知的原理是这样的:你有一张图片,假设是总统的肾脏图片,这不是关键。图片由一百万个像素构成。对传统成像来说,你不得不进行一百万次量度。而采用压缩感知技术,你只需要量度一小部分,好比说从图像的不同部分随机抽取十万个像素。从这里开始,有大量的实际上是无穷多的方式填充那剩余的九十万个像素点。

    寻找那个唯一正确的表示方式的关键在于一种叫稀疏度的概念。所谓稀疏度,是描述图像的复杂性或者其中所缺的一种数学方法。一幅由少数几个简单、可理解的元素(例如色块或者波浪线构成的图片)是稀疏的;满屏随机、散乱的点阵则不是稀疏的。原来在无限多的可能性中,最简单、最稀疏的那幅图像往往就是正解,至少很接近正解。

    但是,怎样进行数字运算,才能快速获得最稀疏的图像呢?分析所有可能的情况太费时间。然而,坎迪斯和陶哲轩知道最稀疏的图像是用最少的成分构成的,并且,他们可以用L1范数极小化技术迅速找到它。

    这样,在输入不完整的图像后,算法开始试着用大色块来填充空白区。如果有一团绿色的像素点聚集在一起,算法可能会用一个大的绿色矩形填充它们之间的空间;而如果是一团黄色的像素点,那么就用黄色的矩形来填充。在不同颜色交错散布的区域,算法会使用越来越小的矩形或其他形状填充各种颜色之间的空间。算法会重复这样的过程,最终,得到一幅由最少的可能的色块构成的图像,它的一百万像素都已被彩色填满。

    并不能绝对保证这样的图像就是最稀疏的,或者正是你所试图重建的那个。但是坎迪斯和陶哲轩已经从数学上证明了,它的错误率是无穷小的。算法运行可能还是需要几个小时,但是,让电脑多跑一个小时,总好过让孩子在额外的一分钟里停止呼吸。

    压缩感知已经产生了令人惊叹的科学影响。这是因为每一个有趣的信号都是稀疏的,只要你能够正确定义它的稀疏性。例如,钢琴和弦的乐音是一小组不超过五个纯音符的组合。在所演奏的音频中,只有少部分频率包含有效的音乐信息,而其余大部分频段是一片无声地带。因此,你可以用压缩感知技术从“欠采样”的老旧唱片中重建出当时的乐章,而不用担心失去了由特定频率构成的声波的信息。只需要你手头的材料,就可以用L1范数极小化法以稀疏方式填补空白,从而获得与原音一般无二的旋律。

    带着建筑师式的眼睛,顶着略显蓬松的头发,坎迪斯散发着时尚极客的气息。这个39岁的法国人语气温和,但是面对他认为不达标的事情绝不妥协。“不,不,他说的没有道理。”当我提到压缩感知领域某个和他有些观点有着细小差别的专家的工作时,他如是说,“不,不,不,不。那没有道理,没道理,是错的。”

    坎迪斯曾经预见,将来会有大量应用技术是以他的研究成果作为理论基础的。他举例说道,在未来,这项技术不会仅仅用在磁共振成像仪上。例如,数码相机收集了大量信息,然后压缩图像。但是,至少在压缩感知技术可用的情况下,压缩是一种极大的浪费。如果你的相机记录了大量的数据,却在压缩时丢弃了其中的90%,那么为什么不在一开始就只记录10%的数据从而节省电池电量和内存?对于您的孩子的数码快照,费电可能没什么大不了,你只要插上电源为相机充电就可以了。“但是,当废电池多到可以环绕木星,”坎迪斯说,“结果就不是那么简单了”。同样,如果你希望自己的相机能够拍摄万亿像素的照片而不是几百万像素,你就必须使用压缩感知技术。

    从信息的小样本中收集有用数据的能力也引起了军方的重视:比如,敌方通信可能从一个频率跳到另一个频率。但是,还没有一种硬件设备能以足够快的速度扫描整个频域。但是无论在什么情况下,对手的信号都是稀疏的,是由频段内极少数的某种简单信号构成的,出现在一些相对较小却未知的频段。这意味着压缩感知可以用来从“噼啵”声中区分来自任意波段的敌人的交谈。所以不出意外的,美国国防部先进计划研究署正在支持压缩感知技术的研究。

    压缩感知不仅可以用于解决现在的技术难题。将来,它还将帮助我们处理已存储的大量信息。每天,全世界都要产生数不清的数据,我们希望这些数据安全、有效、可恢复地保存起来。目前,我们大部分的视听信息都是用复杂的压缩格式存储起来的。如果有一天,这种格式被淘汰了,你不得不进行痛苦的格式转换。但是坎迪斯相信,在拥有压缩感知技术的未来,对于采用高成本红外技术拍摄的天文图像,只需要拍摄到20%的像素就可以了。因为我们一开始就只记录了极少部分的数据,所以不需要再进行压缩。那么我们只需要逐步改进数据的解析算法,而不是数据的压缩算法,就可以精确地恢复出原始图像了。

    上面说的都是将来的事情。今天,压缩感知技术已经改写了我们获取医学信息的方式。在GE医疗集团的参与下,威斯康辛大学的一个研究小组正在把压缩感知技术与HYPR和VIPR技术结合,以提高特定种类磁共振扫描的速度,在某种情况下可以达到原来的几千倍。(我是这所大学的教员,但是没有参与这项研究。)GE医疗集团还在实验一种新的方法,有希望利用压缩感知技术大大改善对癌症病人代谢动力学的观测。同时,帕卡德医院应用了压缩感知技术,使磁共振成像仪的图像记录速度提升为传统扫描仪的三倍。

    这对于两岁的布赖斯来说恰好够用。瓦萨纳瓦拉在控制室发出工作信号,麻醉师给男孩注射了一点镇静剂,然后关掉了呼吸机。男孩的呼吸立刻停止了。瓦萨纳瓦拉开始扫描,而麻醉师监视着布赖斯的心率和血氧水平。40秒钟之后,扫描结束,布赖斯没有出现明显的缺氧情况。当天晚些时候,压缩感知算法从粗略的扫描中生成了清晰的图像,能让瓦萨纳瓦拉看清双侧胆管的堵塞情况。一名介入放射科医生将一根弯曲的导线依次插入双侧胆管中,轻轻清除淤塞,并为男孩安装了让胆汁恰当流出的细小导管。正是数学与医学的结合,才使得布赖斯的检测结果又恢复了正常。

    原文作者:

    Jordan Ellenberg (ellenber@math.wisc.edu), 是威斯康辛大学的数学副教授。原文发表在《连线》杂志三月号上。
    数学怎样得出那些颗粒:压缩感知技术是一种从低分辨率样本中重建高精度数据的数学工具。它可以用来重现古老的音乐录音、寻找敌人的无线电信号,并更加迅速地完成磁共振成像。这里展示的是它如何处理照片。

    在这里插入图片描述

    [f1]坚持用‘磁共振’的原因:1)MRI直译就是磁共振成像;2)现代人谈‘核’色变,而传统‘核磁共振’中的‘核’其实指的是原子核。因为‘核磁共振’这个名字让我们在招募fMRI实验被试时困难重重……赶明儿打算写个磁共振成像原理给大家做科普,希望以后招被试容易些……

    展开全文
  • 压缩感知学习笔记1—综述

    千次阅读 2016-12-19 23:11:06
    压缩感知是近年来极为热门的研究前沿,在若干应用领域中都引起瞩目。最近粗浅地看了这方面一些研究,对于Compressive Sensing有了初步理解,在此分享一些资料与精华。本文针对陶哲轩和Emmanuel Candes上次到北京的...
  • 1 压缩感知的背景 大约有70%的信息是通过人眼获得的视频和图像信息 视频图像信息是人类最重要的获取信息的方式。 视频图像信息丰富数据量大 信号采样传输存储有巨大的压力 在数据的存储和传输方面, 传统的做法是...
  • 压缩感知

    千次阅读 2020-07-23 23:03:58
    一,什么是压缩感知(CS) compressed sensing又称compressed sampling,CS是一个针对信号采样的技术,它通过一些手段,实现了“压缩的采样”,准确说是在采样过程中完成了数据压缩的过程。 因此我们首先要从信号...
  • 以雷达稀疏信号的压缩测量及重构为主线,本文综述了压缩感知理论在雷达目标探测与识别中的研究进展,分析了压缩感知理论在PD雷达、穿墙雷达、MIMO雷达、雷达目标参数估计、雷达成像以及目标识别等领域的潜在应用,描述...
  • 压缩感知作为现代信号处理的最新进展,在认知无线电到等领域中的应用潜力巨大。
  • 压缩感知介绍

    2020-05-01 22:47:58
    压缩感知(压缩传感,Compressive Sensing, Compressed sensing)理论是近年来信号处理领域诞生的一种新的信号处理理论,由D. Donoho(美国科学院院士)、E. Candes(Ridgelet, Curvelet创始人)及华裔科学家T. Tao(2006...
  • 压缩感知(compressed sensing)的通俗解释

    万次阅读 多人点赞 2017-02-16 21:01:51
    作者:咚懂咚懂咚 来源: 知乎 ... ----------------------------...在我看来,压缩感知是信号处理领域进入21世纪以来取得的最耀眼的成果之一,并在磁共振成像、图像处理等领域取得了有效应用压缩感知理论在其复杂的...
  • 压缩感知测量矩阵构造方法研究

    万次阅读 多人点赞 2017-08-03 10:23:11
    记得刚拿到这个题目时,满脑子都是黑人问号,压缩感知到底是个什么东东?也正是因为它,我第一次接触到博客这个强大的东西,在这里搜索关于CS的资料的同时,发现了很多有意思的东西,这里大神云集,能学的东西太多了...
  • 单位代码: 10293 密 级 公开 硕 士 专 业 学 位 论 文 论文题目压缩感知算法及其在矢量量化中的应用 学?号 20109230 姓?名 普晶晶 导?师 赵生妹 专业学位类别 工程硕士 类申请 型 全日制? 在职 专?领域 业( 论文提交...
  • 压缩感知信号重构算法的实验对比研究,傅少武,吴键,进入21世纪后无线传感器网络被广泛应用于各个领域,但是无线传感器网络节点的处理能力和低电池能耗这两大缺陷也更明显的暴露在眼�
  • 摘要 获取项目源文件,联系Q:1415736481,可指导...近年来出现的压缩感知理论(Compressed Sensing,CS)则不受制于奈奎斯特采样定律,它是采用非自适应线性投影来保持信号的原始结构,以直接采集压缩后的数据的方式...
  • 压缩感知人脸识别

    2013-10-31 13:35:36
    作为计算机视觉与生物信息学等交叉学科研究热点之一,人脸识别技术为 国家公共安全、人机交互等核心应用领域的信息化进程提供技术支撑,在学术 界和工业界引起高度关注。

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 15,046
精华内容 6,018
关键字:

压缩感知应用领域