2017/02/21 by Shahar Mendelson, Mendelson, Shahar
Mathematics · #FOS: Computer and information sciences #Machine Learning (stat.ML) #Mathematical Analysis and Transform Methods #Random Matrices and Applications #Spectral Theory in Mathematical Physics
paper · pdf · doi:10.48550/arxiv.1702.06278
openalex publication_date 2017/02/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 ≤ c1log d we construct a random vector X ∈ Rd with iid, mean-zero, variance 1 coordinates, that satisfies supt ∈ Sd-1 ‖‖Lq ≤ c2√(q) for every 2≤ q ≤ p. We show that if m ≤ c3√(p)d1/p and Γ:Rd → Rm 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.