Column normalization of a random measurement matrix

DOI10.1214/17-ECP100MaRDI QIDQ1748563zbMATH OpenFDO

Authors Shahar Mendelson

Publication date 11 May 2018

Published in Electronic Communications in Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1702.06278, https://projecteuclid.org/euclid.ecp/1519722243

zbMATH Keywords

sparse recoverycolumn normalization

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Random matrices (probabilistic aspects) (60B20) Nonparametric inference (62G99)

Abstract: In this note we answer a question of G. Lecu'{e}, 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 $2leqpleq{c}_{1}logd$ we construct a random vector $Xin{R}^d$ with iid, mean-zero, variance $1$ coordinates, that satisfies $su{p}_{tin{S}^{d-1}}|<X,t>{|}_{L_q}leq{c}_{2}sqrtq$ for every $2leqqleqp$. We show that if $mleq{c}_{3}sqrtp{d}^{1/p}$ and $ildeGamma:R^{d}o{R}^m$ is the column-normalized matrix generated by $m$ independent copies of $X$, then with probability at least $1-2exp(-c_{4}m)$, $ildeGamma$ does not satisfy the exact reconstruction property of order $2$.

Recommendations

• Sparse recovery properties of discrete random matrices
• Sparse recovery under weak moment assumptions
• Nonuniform sparse recovery with subgaussian matrices
• Norms of random submatrices and sparse approximation
• Column randomization and almost-isometric embeddings

Cites work

• A mathematical introduction to compressive sensing
• Learning without concentration
• Simultaneous analysis of Lasso and Dantzig selector
• Smallest singular value of random matrices and geometry of random polytopes
• Sparse recovery under weak moment assumptions
• Statistics for high-dimensional data. Methods, theory and applications.

Cited in

(1)

• Sparse recovery properties of discrete random matrices

This page was built for publication: Column normalization of a random measurement matrix

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1748563)