Suprema of chaos processes and the restricted isometry property

DOI10.1002/CPA.21504zbMATH Open1310.94024arXiv1207.0235OpenAlexW2117790027MaRDI QIDQ2929397FDOQ2929397

Felix Krahmer, Holger Rauhut, Shahar Mendelson

Publication date: 12 November 2014

Published in: Communications on Pure and Applied Mathematics (Search for Journal in Brave)

Abstract: We present a new bound for suprema of a special type of chaos processes indexed by a set of matrices, which is based on a chaining method. As applications we show significantly improved estimates for the restricted isometry constants of partial random circulant matrices and time-frequency structured random matrices. In both cases the required condition on the number $m$ of rows in terms of the sparsity $s$ and the vector length $n$ is $mgtrsimslo{g}^{2}slo{g}^{2}n$.

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

Mathematics Subject Classification ID

Gaussian processes (60G15) Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Random matrices (probabilistic aspects) (60B20)

Cites Work

• Title not available (Why is that?)
• Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?
• Atomic Decomposition by Basis Pursuit
• New concentration inequalities in product spaces
• Stable signal recovery from incomplete and inaccurate measurements
• A simple proof of the restricted isometry property for random matrices
• Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
• Uniform Central Limit Theorems
• Compressed sensing
• Iterative hard thresholding for compressed sensing
• CoSaMP: Iterative signal recovery from incomplete and inaccurate samples
• Invertibility of ``large submatrices with applications to the geometry of Banach spaces and harmonic analysis
• The Generic Chaining
• Sparse Recovery With Orthogonal Matching Pursuit Under RIP
• Concentration inequalities using the entropy method
• On sparse reconstruction from Fourier and Gaussian measurements
• Random vectors in the isotropic position
• New and Improved Johnson–Lindenstrauss Embeddings via the Restricted Isometry Property
• The sizes of compact subsets of Hilbert space and continuity of Gaussian processes
• Toeplitz Compressed Sensing Matrices With Applications to Sparse Channel Estimation
• Regularity of Gaussian processes
• Compressive Sensing
• Compressive Sensing by Random Convolution
• Restricted isometries for partial random circulant matrices
• Reconstruction and subgaussian operators in asymptotic geometric analysis
• Hard Thresholding Pursuit: An Algorithm for Compressive Sensing
• Non commutative Khintchine and Paley inequalities
• New bounds on the restricted isometry constant \(\delta _{2k}\)
• Uncertainty in time-frequency representations on finite Abelian groups and applications
• High-Resolution Radar via Compressed Sensing
• Inequalities of Bernstein-Jackson-type and the degree of compactness of operators in Banach spaces
• The restricted isometry property for time-frequency structured random matrices
• Identification of Matrices Having a Sparse Representation
• Sparsity in time-frequency representations
• On decoupling, series expansions, and tail behavior of chaos processes
• A variant of the Johnson-Lindenstrauss lemma for circulant matrices
• Johnson-Lindenstrauss lemma for circulant matrices**

Cited In (56)

• Some notes on concentration for \(\alpha\)-subexponential random variables
• Fast Metric Embedding into the Hamming Cube
• Modewise operators, the tensor restricted isometry property, and low-rank tensor recovery
• Forty years of frequent items
• Title not available (Why is that?)
• Uniform Hanson-Wright type concentration inequalities for unbounded entries via the entropy method
• Compressed dictionary learning
• On polynomial chaos expansion via gradient-enhanced \(\ell_1\)-minimization
• A Novel Compressed Sensing Scheme for Photoacoustic Tomography
• Near-optimal mean estimators with respect to general norms
• Compressive Sensing with Redundant Dictionaries and Structured Measurements
• Derandomizing restricted isometries via the Legendre symbol
• Fast and RIP-optimal transforms
• Derandomized compressed sensing with nonuniform guarantees for \(\ell_1\) recovery
• Sparse Model Uncertainties in Compressed Sensing with Application to Convolutions and Sporadic Communication
• Hanson-Wright inequality in Banach spaces
• Quantized compressed sensing for random circulant matrices
• Conjugate gradient acceleration of iteratively re-weighted least squares methods
• Quantization of compressive samples with stable and robust recovery
• The restricted isometry property of block diagonal matrices for group-sparse signal recovery
• Low rank tensor recovery via iterative hard thresholding
• Deterministic convolutional compressed sensing matrices
• On the geometry of polytopes generated by heavy-tailed random vectors
• Optimal Injectivity Conditions for Bilinear Inverse Problems with Applications to Identifiability of Deconvolution Problems
• Uniform recovery from subgaussian multi-sensor measurements
• Sampling of operators
• The restricted isometry property for random block diagonal matrices
• Cosparsity in Compressed Sensing
• Book Review: A mathematical introduction to compressive sensing
• Endpoint Results for Fourier Integral Operators on Noncompact Symmetric Spaces
• Interpolation via weighted \(\ell_{1}\) minimization
• Quantization and Compressive Sensing
• Super-resolution radar
• Optimal fast Johnson-Lindenstrauss embeddings for large data sets
• Toward a unified theory of sparse dimensionality reduction in Euclidean space
• Improved bounds for the RIP of Subsampled Circulant matrices
• Robust Width: A Characterization of Uniformly Stable and Robust Compressed Sensing
• Noncommutative Bennett and Rosenthal inequalities
• Spectral Methods for Passive Imaging: Nonasymptotic Performance and Robustness
• Short-Term Memory Capacity in Networks via the Restricted Isometry Property
• Uniform recovery of fusion frame structured sparse signals
• Refined analysis of sparse MIMO radar
• Tensor Regression Using Low-Rank and Sparse Tucker Decompositions
• Cornerstones of Sampling of Operator Theory
• Robust recovery of low-rank matrices with non-orthogonal sparse decomposition from incomplete measurements
• An Introduction to Compressed Sensing
• Sparsity and incoherence in orthogonal matching pursuit
• Improved bounds for sparse recovery from subsampled random convolutions
• Robust Phase Retrieval Algorithm for Time-Frequency Structured Measurements
• Real-valued embeddings and sketches for fast distance and similarity estimation
• Non-Cartesian spiral binary sensing matrices
• Discrete uncertainty principles and sparse signal processing
• The Restricted Isometry Property of Subsampled Fourier Matrices
• Proof methods for robust low-rank matrix recovery
• Quantized Compressed Sensing: A Survey
• Compressive time-of-flight 3D imaging using block-structured sensing matrices

Uses Software

• CoSaMP

This page was built for publication: Suprema of chaos processes and the restricted isometry property

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