信号重构：CS技术保证与算法效率探讨

信号的重构是应用CS技术的重要保证。对信号进行重构最直接的方法是通过l0范数求解，但由于Y的维数低，从Y中求解出稀疏系数θ是一个NP难问题，求解的数值不稳定且直接求解较为复杂。为了解决这个问题，当观测矩阵Φ与稀疏基矩阵Ψ满足RIP条件时，Donoho等人提出用l1范数代替l0范数进行求解，即

式中，‖‖p表示lp范数，min（　）表示求最小值，θ′是系数θ的估计值。l1范数是一个凸优化问题，可以转化成线性规划问题求解。(www.xing528.com)

目前，典型的重构算法主要可分为三类：①凸优化算法，将非凸问题转化为凸问题实现求解，主要包括梯度投影法、基追踪（Basis Pursuit，BP）法和最小角度回归（Least Angle Regression，LARS）法等。该类算法需要的测量数最少，重构精度高，但计算复杂度高且效率较低。②贪婪算法，通过选择合适的原子并经过逐步递增的方法逼近信号矢量，主要包括匹配跟踪（Matching Pursuit，MP）法、正交匹配跟踪（Orthogonal Matching Pursuit，OMP）法及其改进算法等。该类算法虽重构精度不及凸优化算法，但原理较为简单，计算复杂度较低且效率高，已经成为常用的算法。③组合算法，通过分组检测来重建信号，代表算法有傅里叶采样（Fourier Sampling，FS）法、链追踪（Chaining Pursuit，CP）法等。该类算法虽比前两类算法更快更有效，但要求测量对象中包含特殊结构并且观测矩阵是稀疏的，应用较少。此外，还有将稀疏信号重构问题转化为统计问题的贝叶斯学习（Sparse Bayesian Learning，SBL）算法和FOCUSS（Focal Under Determined Sys-tem Solution）算法等。