论文部分内容阅读
【摘 要】经典的香农采样定理认为，为了不失真地恢复模拟信号，采样频率应该不小于奈奎斯特频率（即模拟信号频谱中的最高频率）的两倍。但是其中除了利用到信号是有限带宽的假设外，没利用任何的其它先验信息，采集到的数据存在很大程度的冗余。Donoho等人提出的压缩感知方法（Compressed Sensing或Compressive Sampling，CS）充分运用了大部分信号在预知的一组基上可以稀疏表示这一先验信息，利用随机投影实现了在远低于奈奎斯特频率的采样频率下对压缩数据的直接采集。该方法不仅为降低采样频率提供了一种新思路，也为其它科学领域的研究提供了新的契机。该文综述性地阐述了压缩感知方法的基本原理，给出了其中的一些约束问题和估计方法，并介绍压缩感知理论的相关问题——矩阵填充，最后讨论了其未来可能的应用前景。
【关键词】压缩感知；贪婪算法；线性规划；随机投影
1.引言
当前大部分数据采集系统都是基于传统的香农采样定理来设计，按照这种方式采集的数据能够充分表示原始信号，但是它们存在较大的冗余。因此，这些方法往往导致采集数据的泛滥和传感器的浪费。研究如何根据信号的一些特征来实现低于乃奎斯特采样频率的采集，以减少所需采集的数据量具有重要的意义。在过去的30年里，从噪声中提取正弦信号的方法吸引了许多科学家的关注，但是利用信号的可压缩性进行数据采样却是一个新兴的课题。其起源于对具有有限信息率信号（finite-rate-of-innovation signal，即单位时间内具有有限自由度的信号）进行采集的研究，利用固定的结构性基函数（structured fixed deterministic sampling kernels）以两倍于新息率而不是两倍于奈奎斯特采样频率对连续信号进行采集。Donoho等人提出的压缩感知方法是一种可以广泛应用于可压缩信号的采集方法。该方法所需要的传感器数目大大减少，采集到的数据也具有更小的冗余度。因此，该理论提出后立即吸引了众多科学家的关注，目前我国关于压缩感知方法的研究也已开始起步，相信不久将有更多的人加入到关于压缩感知的研究行列。
压缩感知采集方法并不是对数据直接进行采集，而是通过一组特定波形去感知信号，即将信号投影到给定波形上面（衡量与给定波形的相关度），感知到一组压缩数据，最后利用最优化的方法实现对压缩数据解密，估计出原始信号的重要信息。压缩感知关键的问题是如何给定用来感知信号的波形才能有效地恢复出原始信号的重要信息。涉及的关键因素在于给定的波形要与可以用来压缩原始信号的波形组均不相干，并且不相干程度越高，感知数据包含的信息量越大，为准确获取重建原始信号所需的感知数据量就越少。Tao等人提出的受限等距性（Restricted Isometry Property，RIP）[2，3]、一致不确定性原理（Uniform Uncertainty Principle，UUP）和准确重构原理（Exact Reconstruction Principle，ERP）[4，5]进一步回答了如何从压缩数据中方便地提取信号有用信息的充分条件。
2.压缩感知中的信息获取方法
本节我们将讨论从感知到的数据中估计原始信号的几种常见实用方法：基追踪算法（Basis Pursuit，BP）、贪婪算法（Matching Pursuit，MP）、迭代阈值算法（iterative threshholding methods，iterative shrinkage algorithm）等。
2.1 基追踪算法
首先需要指出的是基追踪算法并不是一个最优化原则，其原理是上述讨论的给定一些限制条件后，通过极小化z，范数町以获得最稀疏的解。与之问题等价的标准线性规划问题为
极小化Z范数的方法能够有效解决压缩感知中的恢复问题，但是当结合其它的一些先验知识后，该问题可以被更加有效地解决。在此，我们仅简单介绍贝叶斯压缩感知方法（Bayesian compressed Sensing，BCS）和基于模型的压缩感知方法（model based compressed sensing）。Ji等人提出的BCS借助传统的贝叶斯方法和机器学习中的主动学习方法（active learning），通过将关于稀疏性的先验信息用垂直先验分布（hierarchical prior）来建模，提出了自适应的感知方法以及相应的恢复方法。而Baraniuk等人提出的针对基于模型可压缩信号（model compressible signals）的压缩感知方法中利用小波树模型和块稀疏模型，仅需要与稀疏程度相当的测度数即可实现信号的鲁棒性恢复。
2.2 矩阵填充问题
矩阵填充理论与压缩感知理论相比，压缩感知理论利用的是信号在一组基下的稀疏性，而矩阵填充理论利用的是利用矩阵特征值的稀疏性（即低秩性）。假设一个秩为r的低秩矩阵X，坩硒是一个将矩阵中位于支撑域以外的元素投影成零的正交投影。即：
那么，x能够通过如下的最优化方法从部分观测y中准确的重构出来：
该问题的求解同样是一个NP难问题。当部分观测是从矩阵X中随机选取的元素时，Candes指出该问题可以通过如下的凸规划问题加以求解：
实际上，部分观测矩阵l，是矩阵X在一些随机矩阵上的随机投影时，矩阵X同样可以从观测矩阵l中准确地重构出来。Ma等人进一步指出，当一个低秩的矩阵被稀疏噪声污染的时候，利用噪声的稀疏性和矩阵的低秩特性，同样能够把原始矩阵准确地重构出来，该理论被成功地用于人脸识别和视频跟踪中。
3.应用
CS方法还被用到信道编码中误差控制的研究中。在文献[7]中，根据信道传输中的误差是稀疏的，即不足所有传输的数据会出现错误，按照压缩感知理论构建了误差纠正机制。在图像处理分析方面，压缩感知方法也被广泛应用。在Wright等人提出的基于压缩感知方法的人脸识别算法中，人脸识别问题看成是找待测图像的特征在训练集合中稀疏表示，然后运用了CS理论中的恢复方法对该问题进行了求解。基于压缩感知方法的超分辨率算法也由Yang等人提出。高分辨率图像认为可由一组训练得到的冗余基稀疏表示，然后利用压缩感知理论中的恢复方法从低分辨率图像中估计出这些表示系数，进而可以得到一个超分辨率后的图像。Cai等人[363针对运动去模糊中的卷积核在curvelet小波变换下的稀疏性，并结合图像在框架小波基上的稀疏性获得了不错的恢复效果。除此之外，压缩感知方法还被广泛引入到通信口7-38]、地理信息数据分析‘引导、超光谱成像、雷达D1-423和生命科学等领域。 4.结束语
本文简要介绍了一种刚刚兴起的可以在亚奈奎斯特频率进行采样的数据采集方法——压缩感知方法。该方法主要依赖于如下事实：与原始数据的有限次随机投影中包含了原始信号的足够信息；给定一定的约束条件，极小化范数总是导致一个最稀疏的解。该方法已经被广泛应用于数据采集、误差修正、图像处理等问题中。但是该方法目前还处在起步阶段，还有一些问题有待于进一步解决和完善，如：如何实现快速的数据采集以及在不同应用背景下更加有效的重构。
参考文献：
[1] Donoho D L.Compressed sensing.IEEE Transactions onlnformation Theory·2006·52（4）：1289—1306.
[2]Baraniuk R et a1.A simple proof of the restricted isometry property for random matrices.Constructive Approximation，2008，28（3）：253-263.
[3]Candes E J。The restricted isometry property and its implications for compressed sensing.Comptes Rendus Mathematique，2008。346（9—10）：589-592.
[4]Candes E J et a1.Robust uncertainty principles：Exact signal reconstruction from highly incomplete frequency information.IEEE Transactions on Information Theory，2006，52（2）：489—509.
[5]Candes E J，Tao T.Near-optimal signal recovery from randora projections l UniversaI encoding strategies？ IEEE Transactionson Information Theory.2006，52（12）：5406—5425.
[6]Romberg J.Imaging via compressive sampling.IEEE Signal Processing Magazine，2008t 25（2）：14—20.
[7]Candes EJ，Tao T.Decoding by linear programming.IEEE Transactions on Information Theory，2005，51（3）：4203—4215.
注：
本文为四川省科技厅国际合作基金项目2012HH0021资助。
【关键词】压缩感知；贪婪算法；线性规划；随机投影
1.引言
当前大部分数据采集系统都是基于传统的香农采样定理来设计，按照这种方式采集的数据能够充分表示原始信号，但是它们存在较大的冗余。因此，这些方法往往导致采集数据的泛滥和传感器的浪费。研究如何根据信号的一些特征来实现低于乃奎斯特采样频率的采集，以减少所需采集的数据量具有重要的意义。在过去的30年里，从噪声中提取正弦信号的方法吸引了许多科学家的关注，但是利用信号的可压缩性进行数据采样却是一个新兴的课题。其起源于对具有有限信息率信号（finite-rate-of-innovation signal，即单位时间内具有有限自由度的信号）进行采集的研究，利用固定的结构性基函数（structured fixed deterministic sampling kernels）以两倍于新息率而不是两倍于奈奎斯特采样频率对连续信号进行采集。Donoho等人提出的压缩感知方法是一种可以广泛应用于可压缩信号的采集方法。该方法所需要的传感器数目大大减少，采集到的数据也具有更小的冗余度。因此，该理论提出后立即吸引了众多科学家的关注，目前我国关于压缩感知方法的研究也已开始起步，相信不久将有更多的人加入到关于压缩感知的研究行列。
压缩感知采集方法并不是对数据直接进行采集，而是通过一组特定波形去感知信号，即将信号投影到给定波形上面（衡量与给定波形的相关度），感知到一组压缩数据，最后利用最优化的方法实现对压缩数据解密，估计出原始信号的重要信息。压缩感知关键的问题是如何给定用来感知信号的波形才能有效地恢复出原始信号的重要信息。涉及的关键因素在于给定的波形要与可以用来压缩原始信号的波形组均不相干，并且不相干程度越高，感知数据包含的信息量越大，为准确获取重建原始信号所需的感知数据量就越少。Tao等人提出的受限等距性（Restricted Isometry Property，RIP）[2，3]、一致不确定性原理（Uniform Uncertainty Principle，UUP）和准确重构原理（Exact Reconstruction Principle，ERP）[4，5]进一步回答了如何从压缩数据中方便地提取信号有用信息的充分条件。
2.压缩感知中的信息获取方法
本节我们将讨论从感知到的数据中估计原始信号的几种常见实用方法：基追踪算法（Basis Pursuit，BP）、贪婪算法（Matching Pursuit，MP）、迭代阈值算法（iterative threshholding methods，iterative shrinkage algorithm）等。
2.1 基追踪算法
首先需要指出的是基追踪算法并不是一个最优化原则，其原理是上述讨论的给定一些限制条件后，通过极小化z，范数町以获得最稀疏的解。与之问题等价的标准线性规划问题为
极小化Z范数的方法能够有效解决压缩感知中的恢复问题，但是当结合其它的一些先验知识后，该问题可以被更加有效地解决。在此，我们仅简单介绍贝叶斯压缩感知方法（Bayesian compressed Sensing，BCS）和基于模型的压缩感知方法（model based compressed sensing）。Ji等人提出的BCS借助传统的贝叶斯方法和机器学习中的主动学习方法（active learning），通过将关于稀疏性的先验信息用垂直先验分布（hierarchical prior）来建模，提出了自适应的感知方法以及相应的恢复方法。而Baraniuk等人提出的针对基于模型可压缩信号（model compressible signals）的压缩感知方法中利用小波树模型和块稀疏模型，仅需要与稀疏程度相当的测度数即可实现信号的鲁棒性恢复。
2.2 矩阵填充问题
矩阵填充理论与压缩感知理论相比，压缩感知理论利用的是信号在一组基下的稀疏性，而矩阵填充理论利用的是利用矩阵特征值的稀疏性（即低秩性）。假设一个秩为r的低秩矩阵X，坩硒是一个将矩阵中位于支撑域以外的元素投影成零的正交投影。即：
那么，x能够通过如下的最优化方法从部分观测y中准确的重构出来：
该问题的求解同样是一个NP难问题。当部分观测是从矩阵X中随机选取的元素时，Candes指出该问题可以通过如下的凸规划问题加以求解：
实际上，部分观测矩阵l，是矩阵X在一些随机矩阵上的随机投影时，矩阵X同样可以从观测矩阵l中准确地重构出来。Ma等人进一步指出，当一个低秩的矩阵被稀疏噪声污染的时候，利用噪声的稀疏性和矩阵的低秩特性，同样能够把原始矩阵准确地重构出来，该理论被成功地用于人脸识别和视频跟踪中。
3.应用
CS方法还被用到信道编码中误差控制的研究中。在文献[7]中，根据信道传输中的误差是稀疏的，即不足所有传输的数据会出现错误，按照压缩感知理论构建了误差纠正机制。在图像处理分析方面，压缩感知方法也被广泛应用。在Wright等人提出的基于压缩感知方法的人脸识别算法中，人脸识别问题看成是找待测图像的特征在训练集合中稀疏表示，然后运用了CS理论中的恢复方法对该问题进行了求解。基于压缩感知方法的超分辨率算法也由Yang等人提出。高分辨率图像认为可由一组训练得到的冗余基稀疏表示，然后利用压缩感知理论中的恢复方法从低分辨率图像中估计出这些表示系数，进而可以得到一个超分辨率后的图像。Cai等人[363针对运动去模糊中的卷积核在curvelet小波变换下的稀疏性，并结合图像在框架小波基上的稀疏性获得了不错的恢复效果。除此之外，压缩感知方法还被广泛引入到通信口7-38]、地理信息数据分析‘引导、超光谱成像、雷达D1-423和生命科学等领域。 4.结束语
本文简要介绍了一种刚刚兴起的可以在亚奈奎斯特频率进行采样的数据采集方法——压缩感知方法。该方法主要依赖于如下事实：与原始数据的有限次随机投影中包含了原始信号的足够信息；给定一定的约束条件，极小化范数总是导致一个最稀疏的解。该方法已经被广泛应用于数据采集、误差修正、图像处理等问题中。但是该方法目前还处在起步阶段，还有一些问题有待于进一步解决和完善，如：如何实现快速的数据采集以及在不同应用背景下更加有效的重构。
参考文献：
[1] Donoho D L.Compressed sensing.IEEE Transactions onlnformation Theory·2006·52（4）：1289—1306.
[2]Baraniuk R et a1.A simple proof of the restricted isometry property for random matrices.Constructive Approximation，2008，28（3）：253-263.
[3]Candes E J。The restricted isometry property and its implications for compressed sensing.Comptes Rendus Mathematique，2008。346（9—10）：589-592.
[4]Candes E J et a1.Robust uncertainty principles：Exact signal reconstruction from highly incomplete frequency information.IEEE Transactions on Information Theory，2006，52（2）：489—509.
[5]Candes E J，Tao T.Near-optimal signal recovery from randora projections l UniversaI encoding strategies？ IEEE Transactionson Information Theory.2006，52（12）：5406—5425.
[6]Romberg J.Imaging via compressive sampling.IEEE Signal Processing Magazine，2008t 25（2）：14—20.
[7]Candes EJ，Tao T.Decoding by linear programming.IEEE Transactions on Information Theory，2005，51（3）：4203—4215.
注：
本文为四川省科技厅国际合作基金项目2012HH0021资助。