Column normalization of a random measurement matrix

Abstract

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≤c1logd we construct a random vector X∈ℝd with iid, mean-zero, variance 1 coordinates, that satisfies supt∈Sd−1‖⟨X,t⟩‖Lq≤c2q‾√ for every 2≤q≤p. We show that if m≤c3p‾√d1/p and Γ̃ :ℝd→ℝm is the column-normalized matrix generated by m independent copies of X, then with probability at least 1−2exp(−c4m), Γ̃ does not satisfy the exact reconstruction property of order 2. Show more