Explicit universal sampling sets in finite vector spaces

DOI10.1016/J.ACHA.2016.06.001zbMATH1380.94060OpenAlexW2205098157MaRDI QIDQ2399652FDOQ2399652

Authors Lucia Morotti

Publication date 24 August 2017

Published in Applied and Computational Harmonic Analysis (Search for Journal in Brave)

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

zbMATH Keywords

compressed sensingFourier analysisfinite vector spaces

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Abstract: In this paper we construct explicit sampling sets and present reconstruction algorithms for Fourier signals on finite vector spaces $G$, with $|G|=p^r$ for a suitable prime $p$. The two sets have sizes of order $O(p{t}^2{r}^2)$ and $O(p{t}^2{r}^{3}log(p))$ respectively, where $t$ is the number of large coefficients in the Fourier transform. The algorithms approximate the function up to a small constant of the best possible approximation with $t$ non-zero Fourier coefficients. The fastest of the algorithms has complexity $O(p^2{t}^2{r}^{3}log(p))$.

Recommendations

• On sparse reconstruction from Fourier and Gaussian measurements
• (Nearly) sample-optimal sparse Fourier transform
• Combinatorial sublinear-time Fourier algorithms
• Sampling of bandlimited functions on unions of shifted lattices
• A Generalized Sampling Theorem for Locally Compact Abelian Groups

Cites work

• scientific article; zbMATH DE number 3577144 (Why is no real title available?)
• A mathematical introduction to compressive sensing
• Combinatorial sublinear-time Fourier algorithms
• Decoding by Linear Programming
• Deterministic constructions of compressed sensing matrices
• Explicit constructions of RIP matrices and related problems
• On sparse reconstruction from Fourier and Gaussian measurements
• On the design of deterministic matrices for fast recovery of Fourier compressible functions
• Stable signal recovery from incomplete and inaccurate measurements
• The Computational Complexity of the Restricted Isometry Property, the Nullspace Property, and Related Concepts in Compressed Sensing

Cited in

(17)

• scientific article; zbMATH DE number 2116381 (Why is no real title available?)
• A deterministic sparse FFT for functions with structured Fourier sparsity
• A sample efficient sparse FFT for arbitrary frequency candidate sets in high dimensions
• Sparse harmonic transforms. II: Best \(s\)-term approximation guarantees for bounded orthonormal product bases in sublinear-time
• High-dimensional sparse FFT based on sampling along multiple rank-1 lattices
• Accuracy of algebraic Fourier reconstruction for shifts of several signals
• Sparse harmonic transforms: a new class of sublinear-time algorithms for learning functions of many variables
• Recovering Wavelet Coefficients from Binary Samples Using Fast Transforms
• A sampling theory for compact sets in Euclidean space
• Sparse Fourier transforms on rank-1 lattices for the rapid and low-memory approximation of functions of many variables
• The uniform sparse FFT with application to PDEs with random coefficients
• Sketching with Kerdock's crayons: fast sparsifying transforms for arbitrary linear maps
• Self-avoiding generating sequences for Fourier lattice designs
• Sampling Boolean functions over Abelian groups and applications
• A new class of fully discrete sparse Fourier transforms: faster stable implementations with guarantees
• Examples of sets with large trigonometric sums
• A deterministic algorithm for constructing multiple rank-1 lattices of near-optimal size

This page was built for publication: Explicit universal sampling sets in finite vector spaces

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