Toeplitz矩阵有限等距特性研究

在压缩感知热潮的影响下,观测矩阵的有限等距特性（restricted isometry property, RIP）也受到广泛关注。大多数理论研究表明高斯随机矩阵是满足RIP特性的,但由于其存储成本较高,物理实现较复杂,在实际使用中托普利兹（Toeplitz）随机矩阵由于可以使用快速离散傅里叶变换实现而受到青睐。该文将图论中点均匀着色定理和盖尔圆盘定理应用于压缩感知中,对托普利兹观测矩阵的RIP特性进行了证明,证明结果表明,由服从某种特定概率分布的项构造的Toeplitz矩阵以较大概率满足有限等距特性。最后,对最小二乘算法（least square,LS）、线性最小均方误差（linear minimum mean square error,LMMSE）算法和高斯观测矩阵的压缩感知算法以及Toeplitz观测矩阵的压缩感知算法进行了对比分析,Toeplitz观测矩阵的压缩感知算法在性能方面要优于高斯观测矩阵的压缩感知算法和传统算法,运算复杂度方面要优于高斯随机矩阵,为压缩感知实现无失真地重构原始信号提供了理论和应用参考。

Research on the restricted isometry property for Toeplitz matrix

The restricted isometry property (RIP) of the sensing matrix has recently received a lot of attention under the rubric of compressive sensing. Most studies have shown that a Gaussian random sensing matrix satisfies the RIP in theory. However, due to its high cost of storage and complex physical implementation, the Toeplitz sensing matrix is more in favored than the Gauss sensing matrix in actual. Because it can be implemented by the fast discrete Fourier transform. Proof of the RIP for the sensing matrix exploiting graph theory and the Gergorin’s disc theorem is given. The results show that the Toeplitz random matrix satisfies the RIP with high probability. And the least square (LS), linear minimum mean square error （LMMSE）, compressive sensing algorithm with the Gauss sensing matrix and compressive sensing algorithm with Toeplitz sensing matrix channel estimation algorithm are compared. The simulation results show that the Toeplitz sensing matrix has a superiority over the Gauss sensing matrix on computation complexity and the traditional channel estimation method on performance and computation complexity. It provides a theoretical and realistic foundation for reconstructing the original signal losslessly.