Coherence of randomly pre-conditioned matrices

In many applications of compressed sensing, coherence of the matrix A plays an important role in theoretical guarantees for obtaining sparse solutions to linear system of equations, y = Ax. For a given matrix G with trivial right null space, the system Gy = GAx is equivalent. In this paper we establish that if G is a random matrix with i.i.d. realizations of Gaussian or Bernoulli random variables then the coherence of GA cannot be made smaller than the coherence of A with very high probability, in the limit when the row size of G tends to infinity. A similar result is also shown when G is a square random Gaussian matrix and its row size tends to infinity