A case for orthogonal measurements in linear inverse problems

We investigate the random matrices that have orthonormal rows and provide a comparison to matrices with independent Gaussian entries. We find that, orthonormality provides an inherent advantage for the conditioning. In particular, for any given subset S of ℝⁿ, we show that orthonormal matrices have better restricted eigenvalues compared to Gaussians. We consider implications of this result for the linear inverse problems; in particular, we investigate the noisy sparse estimation setup and applications to restricted isometry property. We relate our findings to the results known for Gaussian processes and precise undersampling theorems. We then discuss and illustrate universality of the noise robustness behavior for partial unitary matrices including Hadamard and Discrete Cosine Transform.