Abstract: Random measurement matrix with low sparsity adopted in projections of high-dimensional data onto low-dimensional subspaces in compressive sensing theory has demerits of high computation complexity and low quality reconstructed image. A fast reconstruction algorithm of compressive sensing image based on adjacency matrix of bipartite graph is proposed. Based on the condition of satisfying RIP （Restricted Isoetry Property）, the proposed algorithm makes full use of sparsity and intrinsic features of adjacency matrix of bipartite graph to achieve decrease of time complexity from O（N·log N） in traditional algorithms to O（N）. Experiments demonstrate the proposed algorithm further improves computational performance as well as obtains high reconstructed image quality, especially for images with smooth changes of color or intensity.

Key words: compressive sensing, sensing matrix, bipartite graph, adjacency matrix, sparse matrix

摘要： 针对压缩传感中高维投影计算采用稀疏性较差的普通随机测量矩阵，从而导致计算复杂度高，重构性能不佳这一难题，提出一种基于二分图邻接矩阵的压缩传感图像快速重建算法。该算法在满足测量矩阵的RIP条件下，充分利用二分图邻接矩阵的稀疏性与二值性，将时间复杂度由传统算法的O（N·log N）降低至O（N）。实验结果表明，算法在保证图像重构质量情况下大大提高了运算性能，尤其对于色彩（灰度）变化平缓图像，该算法性能更加优越。

关键词: 压缩传感, 量测矩阵, 二分图, 邻接矩阵, 稀疏矩阵