压缩感知中采样与重建的理论及算法研究

针对压缩感知中的采样与重建进行理论与算法研究。主要针对稀疏Fourier三角多项式与Toeplitz矩阵情形，因为此两种情形具有广泛的应用背景。对于稀疏Fourier三角多项式，当前主要是随机采样方法。我们拟采用数论中的方法构造确定性采样，从而使采样矩阵具有较好的性质。针对此类采样，拟构造与之相应的子线性复杂度算法，从而可精确重建稀疏三角多项式。研究随机Toeplitz采样矩阵的RIP性质，并构造与之相应的快速重建算法。考虑上述采样与重建方法的个例最优性及稳定性。此外，拟研究在一类"字典"或框架表示下具有稀疏特征的信号采样、重建算法，以及数据量化对采样与重建方法的影响。并最终将上述方法用于阵列雷达处理和高分辨稀疏成像中。

压缩感知主要利用信号的特征，如在一组基底表示下稀疏等，从而可减少观测次数。本项目主要针对压缩感知中的基础理论与算法方面进行了研究。重建算法方面，与压缩感知中流行的L1解码相比，贪婪算法通常具有速度上的优势。但由于贪婪算法是数据驱动的算法，相应理论结果较少。我们针对压缩感知中流性的正交多匹配追击算法进行了分析，证明了其可在s步内恢复一个s稀疏信号。在压缩感知中，所观测到的数据需要进行量化，而最简单的量化方式是记录观测值的符号。那么，通过观测值的符号对信号进行恢复被称为1-位压缩感知。针对1-位压缩感知，设计了求解1-位压缩感知的快速 STrMP 算法。数值试验表明，该算法在速度上优于现有算法，在计算结果的精确度上也与现有最好算法相当。压缩感知中另外一个关键问题是采样矩阵的构造与设计。采样方面，部分Fourier观测矩阵的构造是压缩感知中的一个基本性问题，文献中的方法主要是基于随机方法。利用了有限域中的著名的Katz指数和定理，我们构造了一类确定性的观测矩阵，并证明了其具有优良的恢复性质。其中，针对确定性观测矩阵中的一些问题，对Katz指数和定理进行了改进。数值实验表明，所构造的确定性矩阵优于流行的随机部分Fourier矩阵；利用数论中的Weil指数和定理，考虑了稀疏代数多项式的采样，并研究了稀疏插值的理论基础。压缩感知中，很多时候人们难以得到具体的观测值，而只能得到无相位观测值。那么，利用无相位观测值对信号进行恢复是一个重要的问题。针对此类问题，我们将压缩感知中的一些基本结果，包括零空间性质，RIP性质等扩展到无相位观测。特别是，我们定义了强RIP性质，并证明了高斯随机矩阵满足强RIP性质。在相位恢复问题中，一个基本问题就是最小观测次数问题。针对此类问题，我们首先研究了低秩矩阵最小观测次数问题。对该问题，比较有名的是Eldar－Needell －Plan猜想。该猜想宣称：若恢复秩不超过ｒ的　n　阶矩阵的　最小观测次数为4nr-4r^2 。借助代数几何中行列式代数簇的次数及维数公式，我们证明了该猜想对复矩阵成立。对于实矩阵情形，我们构造了一个反例，表明在４阶情形，该猜想并不成立。进而否定的回答了2n-1次观测是否为最小的公开问题。项目共接收发表14篇论文，其中11篇发表于SCI检索期刊上。