Column normalization of a random measurement matrix

DOI10.1214/17-ECP100zbMATH Open1390.62087arXiv1702.06278MaRDI QIDQ1748563FDOQ1748563

Authors: Shahar Mendelson 

Publication date: 11 May 2018

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

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$.

Full work available at URL: https://arxiv.org/abs/1702.06278

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

zbMATH Keywords

sparse recoverycolumn normalization

Mathematics Subject Classification ID

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

Cites Work

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

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)