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

chaos processcompressed sensingGabor systemrandom matrixrestricted isometry propertytime-frequency analysis

Mathematics Subject Classification ID

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

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.

Review text

The authors investigate a random Gabor system which is a structured \(n\times n^2\) matrix whose columns are obtained by taking all possible time-frequency shifts of a fixed random vector. The random Gabor system has many potential applications including channel identification, underwater communications, high-resolution radar, as well as matrix probing problems. Their approach is related to a recent restricted isometry analysis of the partial random circulant matrix. This approach involves an estimate of the covering numbers of the set of unit-norm \(s\)-spars vectors with respect to two metrics induced by the random process. The main results of this paper is to prove probabilistic estimates for the restricted isometry constants of a matrix whose columns consist of time-frequency shifts of a random vector. Roughly speaking, they show that the \(s\)th-order restricted isometry constant of the associated \(n\times n^2\) Gabor synthesis matrix is small, provided that \(s\leq cn^{2/3}\log^2n\). It is worth to say that the proof depends on an estimate for the expected supremum of a second-order chaos.

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

• 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
• Compressed Sensing and Redundant Dictionaries
• 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
• scientific article; zbMATH DE number 49190 (Why is no real title available?)
• 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

(22)

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

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)