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