Randomness-in-Structured Ensembles for compressed sensing of images

Leading compressed sensing (CS) methods require m = O (k log(n)) compressive samples to perfectly reconstruct a k-sparse signal x of size n using random projection matrices (e.g., Gaussian or random Fourier matrices). For a given m, perfect reconstruction usually requires high complexity methods, such as Basis Pursuit (BP), which has complexity O(n³). Meanwhile, low-complexity greedy algorithms do not achieve the same level of performance (as BP) in terms of the quality of the reconstructed signal for the same m. In this paper, we introduce a new CS framework, which we refer to as Randomness-in-Structured Ensemble (RISE) projection. RISE projection matrices enable compressive sampling of image coefficients from random locations within the k-sparse image vector while imposing small structured overlaps. We prove that RISE-based compressed sensing requires only m = ck samples (where c is not a function of n) to perfectly recover a k-sparse image signal. For the case of n ¿ O(k²), the complexity of our solver is O(nk) which is less than the complexity of the popular greedy algorithm Orthogonal Matching Pursuit (OMP). Moreover, in practice we only need m = 2 k samples to reconstruct the signal. We present simulation results that demonstrate the RISE framework´s ability to recover the original image with higher than 50 dB PSNR, whereas other leading approaches (such as BP) can achieve PSNR values around 30 dB only.