基于LDPC码的压缩感知测量矩阵构造及性能分析

Compressed sensing (CS) is a novel signal sampling theory and becomes a research focus in the areas of information theory and signal processing recently. The construction of measurement matrices is one of the main concerns in CS. At present, the frequently-used random measurement matrix has many drawbacks, e.g., large storage costs, not easy to be realized by hardware, and there is no guarantee that a specific realization of random matrices works. As a result, the deterministic construction of measurement matrices is necessary. Among them, binary measurement matrices from error-correcting codes, such as LDPC codes, attract lots of interests. Good parity-check matrices of LDPC codes are usually good measurement matrices in CS. In this project, we study the CS theory together with LDPC codes, focus on the the deterministic construction and reconstruction performance analysis of binary measurement matrices. The main contents of the project include revealing the relations between LDPC codes and CS; constructing binary sparse quasi-cyclic measurement matrices with good performance, strong structures and flexible parameters; evaluating the performance of binary measurement matrices under the basis pursuit and OMP algorithms; by employing the strong structures of binary measurement matrices, lowering the complexity of measuring and reconstructing algorithms, etc. These works on measurement matrices are very important for the CS basic theory and its practical applications.

压缩感知作为一种新颖的信号采样理论，已成为近年来信息论和信号处理领域研究的一大热点。测量矩阵的构造是压缩感知基本理论的主要问题之一，目前常用的随机测量矩阵存在存储开销大、不易于进行硬件实现等弱点，同时其性能也不能得到确定性的保证，故有必要构造确定性测量矩阵。在测量矩阵的确定性构造中，基于纠错码、特别是LDPC码构造的二元稀疏矩阵引起了人们的极大兴趣，好的LDPC码校验矩阵常常是好的压缩感知测量矩阵。本课题致力于将LDPC码与压缩感知理论有机结合，着重研究二元测量矩阵的确定性构造并分析其重建性能，主要包括：揭示LDPC码与压缩感知之间的联系；构造性能优良、结构性强、参数灵活的二元稀疏准循环测量矩阵；分析二元测量矩阵在基追踪、OMP等重建算法下的性能；结合二元测量矩阵的结构化特性，降低现有测量或重建算法的复杂度，等等。这些关于测量矩阵的工作对于拓展压缩感知基本理论并推进其实用化具有重要意义。

压缩感知（CS）理论是近年来兴起的一种新颖的信号采样理论，该理论指出：只要使用合适的测量矩阵对稀疏信号进行线性测量，然后通过求解一个凸优化问题就能以大概率重建原始信号。CS理论是信息论和信号处理等领域的研究热点，构造合适的测量矩阵是CS理论中的主要问题之一，人们需要构造存储开销小、硬件实现简单、性能优异而稳定的确定性测量矩阵，并对所构造的测量矩阵进行重建性能分析。Dimakis等人指出 LDPC码与CS之间具有紧密的联系，特别是LDPC码的校验矩阵和线性规划译码与CS中的测量矩阵和重建算法关系密切。本课题致力于将LDPC码与压缩感知（CS）理论进行有机结合，着重研究二元CS测量矩阵的确定性构造并分析其重建性能，主要包括：1. 揭示LDPC码与压缩感知之间的联系；2.借鉴有结构LDPC码的构造方法，利用代数和组合等工具构造结构性强、参数灵活、性能良好的二元测量矩阵；3. 从Spark、RIP、NSP等多个角度结合二元矩阵的特点分析测量矩阵在 l1-优化和OMP等重建算法下的性能；4. 结合二元测量矩阵的结构化特性，降低现有存储、测量或重建算法的复杂度，等等。我们在研究中借鉴有结构LDPC码中有限几何码的构造方法，利用代数和组合等工具构造各种二元稀疏准循环测量矩阵，相关结果发表在信号处理领域顶级期刊IEEE Trans. Signal Processing。借鉴LDPC码中校验矩阵性能的分析方法，我们设计了新的列相关性度量指标，来更好的设计压缩感知二元测量矩阵，相关结果发表在信号处理领域顶级期刊IEEE Trans. Signal Processing。我们从Spark、RIP、NSP等多个角度结合二元矩阵的特点分析CS测量矩阵在 l1-优化和OMP等重建算法下的性能，特别是改进精确重建保证或近似重建保证的有关理论结果，从理论上分析所构造矩阵的性能，相关结果发表在信息与通信领域顶级期刊IEEE Trans. Information Theory。我们从校验矩阵的角度研究局部修复码得到了很好的结果，发表在信息与通信领域顶级期刊IEEE Trans. Information Theory。这些工作将对压缩感知的理论研究和实际应用产生重要影响，具有重要的理论意义和应用价值。