The restricted isometry property for time-frequency structured random matrices

DOI10.1007/S00440-012-0441-4MaRDI QIDQ365713zbMATH OpenOpenAlexFDO

Authors Götz E. Pfander, Holger Rauhut, Joel A. Tropp

Publication date 9 September 2013

Published in Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1010.1847, https://arxiv.org/abs/1106.3184

zbMATH Keywords

random matrixcompressed sensingtime-frequency analysisGabor systemrestricted isometry propertychaos process

Mathematics Subject Classification ID

Nontrigonometric harmonic analysis involving wavelets and other special systems (42C40) Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Random matrices (probabilistic aspects) (60B20)

Abstract: We establish the restricted isometry property for finite dimensional Gabor systems, that is, for families of time--frequency shifts of a randomly chosen window function. We show that the $s$-th order restricted isometry constant of the associated $nimes{n}^2$ Gabor synthesis matrix is small provided $sleqc,n^{2/3}/lo{g}^{2}n$. This improves on previous estimates that exhibit quadratic scaling of $n$ in $s$. Our proof develops bounds for a corresponding chaos process.

Recommendations

• The restricted isometry property of subsampled Fourier matrices
• Suprema of chaos processes and the restricted isometry property
• Sparsity in time-frequency representations
• A conditional construction of restricted isometries

Cites work

• scientific article; zbMATH DE number 49190 (Why is no real title available?)
• A discrete model for the efficient analysis of time-varying narrowband communication channels
• A simple proof of the restricted isometry property for random matrices
• An introduction to frames and Riesz bases
• Complex sequences with low periodic correlations (Corresp.)
• Compressed Sensing and Redundant Dictionaries
• Compressed sensing
• Compressive sampling
• Compressive sensing
• Compressive sensing and structured random matrices
• Concentration inequalities using the entropy method
• Counting faces of randomly projected polytopes when the projection radically lowers dimension
• Foundations of time-frequency analysis
• Grassmannian frames with applications to coding and communication
• High-Resolution Radar via Compressed Sensing
• Identification of Matrices Having a Sparse Representation
• Inequalities of Bernstein-Jackson-type and the degree of compactness of operators in Banach spaces
• Level Sets and Extrema of Random Processes and Fields
• Linear independence of Gabor systems in finite dimensional vector spaces
• Matrix probing and its conditioning
• Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?
• New concentration inequalities in product spaces
• On sparse reconstruction from Fourier and Gaussian measurements
• Operator Khintchine inequality in non-commutative probability
• Restricted isometries for partial random circulant matrices
• Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
• Sparse Legendre expansions via _1-minimization
• Sparsity in time-frequency representations
• Stability Results for Random Sampling of Sparse Trigonometric Polynomials
• Stable signal recovery from incomplete and inaccurate measurements
• The Gelfand widths of \(\ell_p\)-balls for \(0 < p \leq 1\)
• The Generic Chaining
• Toeplitz Compressed Sensing Matrices With Applications to Sparse Channel Estimation
• Uncertainty in time-frequency representations on finite Abelian groups and applications

Cited in

(21)

• Compressive Sensing
• Structured random measurements in signal processing
• Cornerstones of sampling of operator theory
• Preconditioning filter bank decomposition using structured normalized tight frames
• Theoretical frame properties of wave-packet matrices over prime fields
• Sparse recovery in probability via \(l_q\)-minimization with Weibull random matrices for \(0 < q\leq 1\)
• Nonlinear approximation with nonstationary Gabor frames
• Efficient algorithms for the discrete Gabor transform with a long FIR window
• Theory and applications of compressed sensing
• The restricted isometry property of subsampled Fourier matrices
• Quantization of compressive samples with stable and robust recovery
• The Faber-Krahn inequality for the short-time Fourier transform
• Sampling of operators
• Stability of the elastic net estimator
• Donoho-Logan large sieve principles for modulation and polyanalytic Fock spaces
• The Restricted Isometry Property for Banded Random Matrices
• Quasi-linear compressed sensing
• Improved bounds for sparse recovery from subsampled random convolutions
• Suprema of chaos processes and the restricted isometry property
• Group-invariant max filtering
• Constructing tight Gabor frames using CAZAC sequences

Describes a project that uses

Uses Software

• CoSaMP

This page was built for publication: The restricted isometry property for time-frequency structured random matrices

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