基于膨胀图的压缩感知

Compressed sensing has been widely studied in recent years, but still faces many problems in real-world applications, such as the low-complexity reconstruction of high-dimensional signals. Conventional reconstruction algorithms, including convex optimization algorithms and greedy iterative algorithms, usually involve a great amount of operations on matrix multiplication and inversion, thus inefficient for high-dimensional signals. Recent studies have shown that the expander graph-based compressed sensing allows signals to be reconstructed with linear complexity and with better performance than conventional algorithms at low compression ratios, thus suitable for the compression of high-dimensional signals. Currently, the efficient construction of expander graphs remains a challenge. Common expanders are usually generated with random binary matrices, whose performance cannot be guaranteed. This project aims to provide a class of expanders with deterministic structure and explicit performance, and develop efficient reconstruction algorithms for such expanders.

压缩感知理论近年来已被广泛研究，然而在实际应用中仍面临诸多问题，如高维信号的低复杂度重建。传统的重建算法，如凸优化算法和贪婪迭代算法，一般都涉及大量的矩阵相乘和求逆运算，复杂度较高。近期研究表明，基于膨胀图的压缩感知能够实现信号的线性复杂度重建，并且其在低压缩率下的信号重建性能优于传统的重建算法，因而非常适合高维信号的压缩。目前，膨胀图的有效构造仍是一个研究难点。常用的膨胀图一般由随机二值矩阵生成，性能无法得到保证。本课题拟给出一类结构确定、性能良好的膨胀图，并结合其结构特征，给出高效的信号重建算法。

压缩感知理论近年来已被广泛研究，然而在实际应用中仍面临诸多问题，如高维信号的低复杂度重建。传统的重建算法，如凸优化算法和贪婪迭代算法，一般都涉及大量的矩阵相乘和求逆运算，复杂度较高。近期研究表明，基于膨胀图的压缩感知能够实现信号的线性复杂度重建，并且其在低压缩率下的信号重建性能优于传统的重建算法，因而非常适合高维信号的压缩。目前，膨胀图的有效构造仍是一个研究难点。常用的膨胀图一般由随机二值矩阵生成，性能无法得到保证。本课题给出了一类结构参数明确、理论性能良好的膨胀图，并结合其结构特征，给出了高效的信号重建算法。