A strong restricted isometry property, with an application to phaseless compressed sensing

DOI10.1016/J.ACHA.2015.06.004MaRDI QIDQ905910zbMATH OpenOpenAlexFDO

Authors Vladislav Voroninski, Zhiqiang Xu

Publication date 28 January 2016

Published in Applied and Computational Harmonic Analysis (Search for Journal in Brave)

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

zbMATH Keywords

compressed sensingrestricted isometry propertyphase retrievalsignal recoveryJohnson-Lindenstrauss lemmacompressed phaseless sensing

Mathematics Subject Classification ID

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

Abstract: The many variants of the restricted isometry property (RIP) have proven to be crucial theoretical tools in the fields of compressed sensing and matrix completion. The study of extending compressed sensing to accommodate phaseless measurements naturally motivates a strong notion of restricted isometry property (SRIP), which we develop in this paper. We show that if $Ainmathbb{R}^{mimesn}$ satisfies SRIP and phaseless measurements $|A{x}_0|=b$ are observed about a $k$-sparse signal $x_{0}inmathbb{R}^n$, then minimizing the $el{l}_1$ norm subject to $|Ax|=b$ recovers $x_0$ up to multiplication by a global sign. Moreover, we establish that the SRIP holds for the random Gaussian matrices typically used for standard compressed sensing, implying that phaseless compressed sensing is possible from $O(klog(n/k))$ measurements with these matrices via $el{l}_1$ minimization over $|Ax|=b$. Our analysis also yields an erasure robust version of the Johnson-Lindenstrauss Lemma.

Recommendations

• The restricted isometry property for random block diagonal matrices
• The restricted isometry property and its implications for compressed sensing
• Compressed sensing: how sharp is the restricted isometry property?
• Stable signal recovery from phaseless measurements
• A generalization of the restricted isometry property and applications to compressed sensing

Cites work

• A simple proof of the restricted isometry property for random matrices
• Compressive Phase Retrieval via Generalized Approximate Message Passing
• Decoding by Linear Programming
• Interactions between compressed sensing random matrices and high dimensional geometry
• New and Improved Johnson–Lindenstrauss Embeddings via the Restricted Isometry Property
• Numerically erasure-robust frames
• On signal reconstruction without phase
• On the minimum of several random variables
• Painless reconstruction from magnitudes of frame coefficients
• Phase retrieval for sparse signals
• Phase retrieval via matrix completion
• Phaselift: exact and stable signal recovery from magnitude measurements via convex programming
• Robustly Stable Signal Recovery in Compressed Sensing With Structured Matrix Perturbation
• Sparse Representation of a Polytope and Recovery of Sparse Signals and Low-Rank Matrices
• Sparse signal recovery from quadratic measurements via convex programming
• Stable signal recovery from incomplete and inaccurate measurements
• The restricted isometry property and its implications for compressed sensing
• Uniform uncertainty principle for Bernoulli and subgaussian ensembles

Cited in

(29)

• The restricted isometry property for random block diagonal matrices
• The gap between the null space property and the restricted isometry property
• A new bound on the block restricted isometry constant in compressed sensing
• A theoretical perspective of solving phaseless compressive sensing via its nonconvex relaxation
• Restricted isometry property of principal component pursuit with reduced linear measurements
• On the Absence of Uniform Recovery in Many Real-World Applications of Compressed Sensing and the Restricted Isometry Property and Nullspace Property in Levels
• Uniqueness and stability for the solution of a nonlinear least squares problem
• Compressive phase retrieval: Optimal sample complexity with deep generative priors
• Generalized notions of sparsity and restricted isometry property. I: A unified framework
• Phaseless compressive sensing using partial support information
• Compressed sensing with restricted isometry property
• The sampling complexity on nonconvex sparse phase retrieval problem
• A geometric analysis of phase retrieval
• The \( \ell _1 \)-analysis in phase retrieval with redundant dictionary
• Sparse phase retrieval via ℓp (0 < p ≤ 1) minimization
• Influences of preconditioning on the mutual coherence and the restricted isometry property of Gaussian/Bernoulli measurement matrices
• Stable recovery of weighted sparse signals from phaseless measurements via weighted l₁ minimization
• Restricted isometry properties and nonconvex compressive sensing
• The recovery of complex sparse signals from few phaseless measurements
• Stable signal recovery from phaseless measurements
• Stable and robust $\ell_p$-constrained compressive sensing recovery via robust width property
• On the strong restricted isometry property of Bernoulli random matrices
• On phaseless compressed sensing with partially known support
• Robustness properties of dimensionality reduction with Gaussian random matrices
• Affine phase retrieval for sparse signals via \(\ell_1\) minimization
• A generalization of the restricted isometry property and applications to compressed sensing
• Phase retrieval: theory, model and algorithms
• The restricted isometry property and its implications for compressed sensing
• The sparsest solution of the union of finite polytopes via its nonconvex relaxation

Describes a project that uses

Uses Software

• PhaseLift

This page was built for publication: A strong restricted isometry property, with an application to phaseless compressed sensing

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