The Restricted Isometry Property of Subsampled Fourier Matrices

DOI10.1007/978-3-319-45282-1_11zbMath1379.46014arXiv1507.01768OpenAlexW4300634415MaRDI QIDQ5278293

Ishay Haviv, Oded Regev

Publication date: 13 July 2017

Published in: Lecture Notes in Mathematics, Journal of Topology and Analysis (Search for Journal in Brave)

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

zbMATH Keywords

samplingembeddinglatticesFourier matrixrestricted isometry propertyflat tori

Mathematics Subject Classification ID

Inequalities; stochastic orderings (60E15) Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Norms of matrices, numerical range, applications of functional analysis to matrix theory (15A60) Embeddings of discrete metric spaces into Banach spaces; applications in topology and computer science (46B85)

Related Items (15)

Derandomized compressed sensing with nonuniform guarantees for \(\ell_1\) recovery ⋮ Sigma delta quantization with harmonic frames and partial Fourier ensembles ⋮ Improved bounds for the RIP of Subsampled Circulant matrices ⋮ An Inequality for Gaussians on Lattices ⋮ Least distortion Euclidean embeddings of flat tori ⋮ Sampling numbers of smoothness classes via \(\ell^1\)-minimization ⋮ Random points are good for universal discretization ⋮ Unnamed Item ⋮ An Introduction to Compressed Sensing ⋮ Comparison of Metric Spectral Gaps ⋮ Real-valued embeddings and sketches for fast distance and similarity estimation ⋮ Quantitative bi-Lipschitz embeddings of bounded-curvature manifolds and orbifolds ⋮ Sparse recovery in bounded Riesz systems with applications to numerical methods for PDEs ⋮ Compressed dictionary learning ⋮ Fast and memory-optimal dimension reduction using Kac's walk

Uses Software

• PDCO
• CoSaMP

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The Gelfand widths of \(\ell_p\)-balls for \(0 < p \leq 1\)
• Korkin-Zolotarev bases and successive minima of a lattice and its reciprocal lattice
• The complexity of the covering radius problem
• The restricted isometry property and its implications for compressed sensing
• CoSaMP: Iterative signal recovery from incomplete and inaccurate samples
• A simple proof of the restricted isometry property for random matrices
• Fast dimension reduction using Rademacher series on dual BCH codes
• On Lovász' lattice reduction and the nearest lattice point problem
• New bounds in some transference theorems in the geometry of numbers
• The inapproximability of lattice and coding problems with preprocessing
• Nonembeddability theorems via Fourier analysis
• Tail bounds via generic chaining
• Suprema of Chaos Processes and the Restricted Isometry Property
• An Almost Optimal Unrestricted Fast Johnson-Lindenstrauss Transform
• Computational Complexity of Certifying Restricted Isometry Property
• Certifying the Restricted Isometry Property is Hard
• New and Improved Johnson–Lindenstrauss Embeddings via the Restricted Isometry Property
• Lattice problems in NP ∩ coNP
• Decoding by Linear Programming
• Stable recovery of sparse overcomplete representations in the presence of noise
• Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?
• Atomic Decomposition by Basis Pursuit
• The Fast Johnson–Lindenstrauss Transform and Approximate Nearest Neighbors
• An Improved Estimate in the Restricted Isometry Problem
• On Model-Based RIP-1 Matrices
• The Computational Complexity of the Restricted Isometry Property, the Nullspace Property, and Related Concepts in Compressed Sensing
• Restricted Isometry of Fourier Matrices and List Decodability of Random Linear Codes
• Worst‐Case to Average‐Case Reductions Based on Gaussian Measures
• Stable signal recovery from incomplete and inaccurate measurements
• On the list decodability of random linear codes with large error rates

This page was built for publication: The Restricted Isometry Property of Subsampled Fourier Matrices