Near-optimal sparse fourier representations via sampling

DOI10.1145/509907.509933zbMath1192.94078OpenAlexW2012365979WikidataQ60204983 ScholiaQ60204983MaRDI QIDQ3579182

No author found.

Publication date: 5 August 2010

Published in: Proceedings of the thiry-fourth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/509907.509933

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Sampling theory in information and communication theory (94A20)

Related Items

Improved sparse Fourier approximation results: Faster implementations and stronger guarantees, Book Review: A mathematical introduction to compressive sensing, Matrix sparsification and the sparse null space problem, A sublinear algorithm for the recovery of signals with sparse Fourier transform when many samples are missing, Sketching with Kerdock's Crayons: Fast Sparsifying Transforms for Arbitrary Linear Maps, List-decoding Barnes-Wall lattices, Performance of the multiscale sparse fast Fourier transform algorithm, Guaranteed recovery of planted cliques and dense subgraphs by convex relaxation, Multigrid with Rough Coefficients and Multiresolution Operator Decomposition from Hierarchical Information Games, Detecting the large entries of a sparse covariance matrix in sub-quadratic time, A recursive procedure for density estimation on the binary hypercube, Rapidly computing sparse Legendre expansions via sparse Fourier transforms, Spectral compressive sensing, A deterministic sparse FFT for functions with structured Fourier sparsity, Testing periodicity, Combinatorial sublinear-time Fourier algorithms, High-dimensional sparse Fourier algorithms, Nuclear norm minimization for the planted clique and biclique problems, Unnamed Item, Compressed sensing and best 𝑘-term approximation, CoSaMP: Iterative signal recovery from incomplete and inaccurate samples, Private multiparty sampling and approximation of vector combinations, What's the frequency, Kenneth?: sublinear Fourier sampling off the grid, Periodicity and Cyclic Shifts via Linear Sketches, Random sampling of sparse trigonometric polynomials. II: Orthogonal matching pursuit versus basis pursuit, A simple proof of the restricted isometry property for random matrices, Compressive sensing-based wind speed estimation for low-altitude wind-shear with airborne phased array radar, Theoretical and experimental analysis of a randomized algorithm for sparse Fourier transform analysis, Unnamed Item, A note on the high-dimensional sparse Fourier transform in the continuous setting*, A sample efficient sparse FFT for arbitrary frequency candidate sets in high dimensions, A multiscale sub-linear time Fourier algorithm for noisy data