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

DOI10.1016/J.ACHA.2015.06.004zbMATH Open1338.94024arXiv1404.3811OpenAlexW2962922269MaRDI QIDQ905910FDOQ905910

Authors: Vladislav Voroninski, Zhiqiang Xu 

Publication date: 28 January 2016

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

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.

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

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

zbMATH Keywords

compressed sensingrestricted isometry propertyphase retrievalsignal recoveryJohnson-Lindenstrauss lemmacompressed phaseless sensing

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (30)

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

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)