Near-optimal sparse fourier representations via sampling
Explore this paper's citation graph
Summary
An algorithm for finding a Fourier representation of B for a given discrete signal signal A, such that A is within the factor (1 +ε) of best possible \|-_\|_2^2.
- Type
- article
- Published
- 2002-05-19
- Cited by
- 292
- References
- 19
- OpenAlex
- https://openalex.org/W2012365979
- Semantic Scholar
- https://api.semanticscholar.org/CorpusID:14320243
Keywords
Fourier transform, SIGNAL (programming language), Sampling (signal processing), Mathematics, Representation (politics)
References
- Fast Monte-Carlo algorithms for finding low-rank approximations
- Chaotic communications in the presence of noise
- Applications of Discrete and Continuous Fourier Analysis
- epsilon-Discrepancy Sets and Their Application for Interpolation of Sparse Polynomials
- Constant depth circuits, Fourier transform, and learnability
- Fast, small-space algorithms for approximate histogram maintenance
- Learning decision trees using the Fourier spectrum
- Fast computation of low rank matrix approximations
- Uncertainty principles and signal recovery
- Source coding of the discrete Fourier transform
- Matching pursuits with time-frequency dictionaries
- Reconstructing algebraic functions from mixed data
- Divergence of decreasing rearranged Fourier series
- Reconstructing Algebraic Functions from Mixed Data
- Communications in the presence of noise
- Abstract The
- Fast computation of low rank matrix.
- Improved Sparse Multivariate Polynomial Interpolation Algorithms
- Learning Boolean Functions via the Fourier Transform
- Extensions of Lipschitz mappings into Hilbert space
Cited by
- Robust convex relaxation for the planted clique and densest k-subgraph problems
- Non-uniform sampling: algorithms and architectures
- Deterministic Compressed Sensing
- The Johnson-Lindenstrauss Lemma Meets Compressed Sensing
- Efficient sparse approximation methods for medical imaging
- Deterministic Sparse Fourier Approximation via Fooling Arithmetic Progressions.
- Sublinear Time Algorithms for the Sparse Recovery Problem
- Sparse Image Reconstruction and Artifact Correction of Multi-Dimensional Spectroscopic Imaging Data
- On the computational power of quantum computers
- Adaptive, Hands-Off Stream Mining (CMU-CS-02-205)
- Sparse fourier transform in any constant dimension with nearly-optimal sample complexity in sublinear time
- Sparsity-based methods for processing of radar signals
- FBG sensing signal dealing with improved orthogonal subspace pursuit method
- Why Gabor frames? Two fundamental measures of coherence and their role in model selection
- Simple and practical algorithm for sparse Fourier transform
- A Fourier-Analytic Approach to Reed–Muller Decoding
- Adaptive sub-linear Fourier algorithms
- Recovery of Compressive Sensed Images With Piecewise Autoregressive Modeling
- Decodability of group homomorphisms beyond the johnson bound
- Features extraction for PSK signals recognition using nonuniform compressive samples based on high order transformation