Column normalization of a random measurement matrix

In this note we answer a question of G. Lecué, by showing that column normalization of a random matrix with iid entries need not lead to good sparse recovery properties, even if the generating random variable has a reasonable moment growth. Specifically, for every 2 ≤ p ≤ c1 log d we construct a random vector X ∈ R^d with iid, mean-zero, variance 1 coordinates, that satisfies sup_t∈S^d-1 ∥(X, t)∥L_q ≤ c₂√q for every 2 ≤ q ≤ p. We show that if m ≤ c₃√ppd^1/p and Γ: R^d → R^m is the column-normalized matrix generated bymindependent copies of X, then with probability at least 1-2 exp(-c₄m), Γ does not satisfy the exact reconstruction property of order 2.