稀疏随机矩阵的观测次数下界

Lower Bounds on the Number of Measurements of Sparse Random Matrices

  • 摘要: 压缩感知理论中的稀疏重构问题,要将一个高维信号从它的低维投影中恢复出来,通常选用稠密随机矩阵作为观测矩阵来解决这一问题。而某些稀疏随机矩阵作为观测矩阵也可以达到这一目的。稀疏随机矩阵的特点是,在编码和重构过程中都具有较低的计算复杂度,更新方便,且对存储容量的要求较低。该文基于压缩感知理论,分别对列重固定、行重固定以及一般的稀疏随机矩阵进行了研究,当这些稀疏随机矩阵满足有限等距性质时,推导了观测次数应满足的下界条件,并对三种矩阵的性能进行了分析。以二值稀疏随机矩阵为特例,进行了仿真实验。实验结果显示,结论给出的观测次数下界是比较紧的,并验证了列重固定、行重固定的稀疏随机矩阵作为观测矩阵的可行性和实用性。

     

    Abstract: Sparse recovery problem in the theory of compressed sensing is to recover a high-dimensional signal from its low-dimensional projection, and a dense random matrix is usually used as the measurement matrix to solve this problem. While some sparse random matrices as the measurement matrices can also achieve this goal. Sparse random matrices have several attractive properties, like low computational complexity in both encoding and recovery, easy incremental updates, and low storage requirement. Based on the theory of compressed sensing, this paper investigates sparse random matrices with fixed column sparsity or fixed row sparsity and general sparse random matrices respectively, and when these sparse random matrices satisfy the restricted isometry property, the lower bound conditions that the number of measurements should satisfy are deduced, and the performance of three matrices is analysed. Binary sparse random matrices are taken as a special example to do simulation experiments. Numerical results show that, the lower bounds on the number of measurements given by this paper are tight, and the feasibility and practicability of sparse random matrices with fixed column sparsity or fixed row sparsity as the measurement matrices are verified.

     

/

返回文章
返回