On the linear independence of spikes and sines

DOI10.1007/S00041-008-9042-0zbMATH Open1184.46012arXiv0709.0517OpenAlexW2015386996WikidataQ59750752 ScholiaQ59750752MaRDI QIDQ734952FDOQ734952

Authors: Joel A. Tropp 

Publication date: 14 October 2009

Published in: The Journal of Fourier Analysis and Applications (Search for Journal in Brave)

Abstract: The purpose of this work is to survey what is known about the linear independence of spikes and sines. The paper provides new results for the case where the locations of the spikes and the frequencies of the sines are chosen at random. This problem is equivalent to studying the spectral norm of a random submatrix drawn from the discrete Fourier transform matrix. The proof involves depends on an extrapolation argument of Bourgain and Tzafriri.

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

Recommendations

• Sparse recovery properties of discrete random matrices
• Uniform uncertainty principle for Bernoulli and subgaussian ensembles
• Some random Fourier matrices and their singular values
• Spectral measures of spiked random matrices
• The Restricted Isometry Property of Subsampled Fourier Matrices

zbMATH Keywords

discrete Fourier transformrandom submatrix

Mathematics Subject Classification ID

Random matrices (algebraic aspects) (15B52) Local spectral properties of linear operators (47A11) Probabilistic methods for one variable harmonic analysis (42A61) Approximation by arbitrary nonlinear expressions; widths and entropy (41A46) Probabilistic methods in Banach space theory (46B09)

Cites Work

• Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?
• Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
• Title not available (Why is that?)
• Sparsity and incoherence in compressive sampling
• The random paving property for uniformly bounded matrices
• An uncertainty principle for cyclic groups of prime order
• Uncertainty Principles and Signal Recovery
• Title not available (Why is that?)
• Title not available (Why is that?)
• Operator Khintchine inequality in non-commutative probability
• Random vectors in the isotropic position
• Title not available (Why is that?)
• Random sampling of sparse trigonometric polynomials
• On the conditioning of random subdictionaries
• Quantitative robust uncertainty principles and optimally sparse decompositions
• Monotone Convergence of Binomial Probabilities and a Generalization of Ramanujan's Equation
• A generalized uncertainty principle and sparse representation in pairs of bases
• Signal Recovery and the Large Sieve
• Chebyshev approximation to zero
• Polynomials of fixed sign that deviate least from zero in the spaces \(L_ p\)

Cited In (14)

• Deterministic matrices matching the compressed sensing phase transitions of Gaussian random matrices
• Sharp recovery bounds for convex demixing, with applications
• Computing Sparse Representations of Multidimensional Signals Using Kronecker Bases
• Filtered Gradient Algorithms for Inverse Design Problems of One-Dimensional Burgers Equation
• Inversion of Band-Limited Discrete Fourier Transforms of Binary Images: Uniqueness and Algorithms
• Well-posedness of the permutation problem in sparse filter estimation with \(\ell^p\) minimization
• A Donoho-Stark criterion for stable signal recovery in discrete wavelet subspaces
• On uncertainty principles in the finite dimensional setting
• Discrete uncertainty principle in quaternion setting and application in signal reconstruction
• Donoho-Logan large sieve principles for modulation and polyanalytic Fock spaces
• On the conditioning of random subdictionaries
• Uncertainty principles with discrete quaternion Fourier transforms
• Discrete uncertainty principles and sparse signal processing
• Limiting empirical singular value distribution of restrictions of discrete Fourier transform matrices

This page was built for publication: On the linear independence of spikes and sines

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