Column normalization of a random measurement matrix

Original · EN

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 ≤ c₁ d we construct a random vector X ∈ Rᵈ with iid, mean-zero, variance 1 coordinates, that satisfies ₜ ∈ ₛᵈ⁻¹ <X,t>ₗq ≤ c₂√q for every 2≤ q ≤ p. We show that if m ≤ c₃√pd¹/ᵖ and Γ:Rᵈ → Rᵐ is the column-normalized matrix generated by m independent copies of X, then with probability at least 1-2(-c₄m), Γ does not satisfy the exact reconstruction property of order 2.