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

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