Fast and Robust Compressive Sensing Method Using Mixed Hadamard Sensing Matrix

The paper presents a novel class of sensing matrix that provides great speed-up of virtually any compressed sensing (CS) algorithm. It combines separable structure and maximal incoherence with any fixed basis. The former enables fast matrix-vector computation which is the most computationally expensive part of most CS algorithms; the latter guarantees a good restricted isometry property bound and high quality of CS recovery. Even greater speed-up is achieved by using Hadamard or Fourier matrixes in the construction. The construction of the sensing matrix is incorporated in a Split Bregman method of total variation minimization. The resulting algorithm is not only much faster than any published CS method; it also demonstrates high quality CS recovery of images with the number of measurements as low as 5% of the number of pixels, in the presence of high measurement noise (up to 20% of measurement standard deviation).