Restricted Isometry Property for General p-Norms

DOI10.1109/TIT.2016.2598296MaRDI QIDQ2976590zbMATH OpenFDO

Authors Zeyuan Allen Zhu, Rati Gelashvili, Ilya Razenshteyn

Publication date 28 April 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Abstract: The Restricted Isometry Property (RIP) is a fundamental property of a matrix which enables sparse recovery. Informally, an $mimesn$ matrix satisfies RIP of order $k$ for the $el{l}_p$ norm, if $|Ax{|}_{p}approx|x{|}_p$ for every vector $x$ with at most $k$ non-zero coordinates. For every $1leqp<infty$ we obtain almost tight bounds on the minimum number of rows $m$ necessary for the RIP property to hold. Prior to this work, only the cases $p=1$, $1+1/logk$, and $2$ were studied. Interestingly, our results show that the case $p=2$ is a "singularity" point: the optimal number of rows $m$ is $widetildeTheta(k^p)$ for all $pin[1,infty)setminus2$, as opposed to $widetildeTheta(k)$ for $k=2$. We also obtain almost tight bounds for the column sparsity of RIP matrices and discuss implications of our results for the Stable Sparse Recovery problem.

Cited in

(12)

• The global convergence of the nonlinear power method for mixed-subordinate matrix norms
• Robust sub-Gaussian estimation of a mean vector in nearly linear time
• Low rank matrix recovery with impulsive noise
• Restricted isometry property for matrices whose entries are random variables belonging to some Orlicz spaces L_U()
• Certifying the Restricted Isometry Property is Hard
• On low-risk heavy hitters and sparse recovery schemes
• Low rank matrix recovery with adversarial sparse noise
• The trimmed Lasso: sparse recovery guarantees and practical optimization by the generalized soft-min penalty
• Stable and robust $\ell_p$-constrained compressive sensing recovery via robust width property
• On the tensor spectral \(\mathbf{p}\)-norm and its higher order power method
• Robust sparse recovery with sparse Bernoulli matrices via expanders
• Robust outlier bound condition to phase retrieval with adversarial sparse outliers

This page was built for publication: Restricted Isometry Property for General p-Norms

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