On the design of maximally incoherent sensing matrices for compressed sensing using orthogonal bases and its extension for biorthogonal bases case

Compressive Sensing (CS) allows for reconstructing sparse signals within a low acceptable error using less measurements than stipulated by the Nyquist criterion. This CS paradigm rests on the assumption that there is a basis in which the signal is sparse, and one employs random measurements by means of projections on a sensing matrix reconstructing the signal from these measurements through l1l1-norm minimization on the sparsity basis. In this work, we propose a method to design sensing matrices with minimum coherence to a given sparsifying orthogonal basis. We provide a mathematical proof of the optimality in terms of coherence minimization for the proposed sensing matrices. This result is extended for biorthogonal bases in order to provide sensing matrices with low coherence, that have advantages when compared to Noiselets in a CS paradigm. Experimental results in an image compression setup show that the proposed sensing matrices provide superior rate-distortion results than Noiselets. These results indicate that the proposed sensing matrices tend to outperform Noiselets when sensing natural images.