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\le p\le c_1\log d$ we construct a random vector $X\in R^d$ with iid, mean-zero, variance $1$ coordinates, that satisfies ${\sup }_{t\in S^{d-1}}\Vert <X,t>{\Vert }_{L_q}\le c_2\sqrt{q}$ for every $2\le q\le p$. We show that if $m\le c_3\sqrt{p}{d}^{1/p}$ and $\tilde{\Gamma }:R^d\to R^m$ is the column-normalized matrix generated by $m$ independent copies of $X$, then with probability at least $1-2\exp (-c_{4}m)$, $\tilde{\Gamma }$ does not satisfy the exact reconstruction property of order $2$.

References in corpus (1)

• Simultaneous analysis of Lasso and Dantzig selector