Explicit universal sampling sets in finite vector spaces

DOI10.1016/J.ACHA.2016.06.001zbMATH Open1380.94060arXiv1507.06849OpenAlexW2205098157MaRDI QIDQ2399652FDOQ2399652

Authors: Lucia Morotti 

Publication date: 24 August 2017

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

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))$.

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

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

zbMATH Keywords

compressed sensingFourier analysisfinite vector spaces

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (16)

• Sketching with Kerdock's Crayons: Fast Sparsifying Transforms for Arbitrary Linear Maps
• A deterministic algorithm for constructing multiple rank-1 lattices of near-optimal size
• A deterministic sparse FFT for functions with structured Fourier sparsity
• A sample efficient sparse FFT for arbitrary frequency candidate sets in high dimensions
• Recovering Wavelet Coefficients from Binary Samples Using Fast Transforms
• A new class of fully discrete sparse Fourier transforms: faster stable implementations with guarantees
• High-dimensional sparse FFT based on sampling along multiple rank-1 lattices
• Title not available (Why is that?)
• Sparse harmonic transforms: a new class of sublinear-time algorithms for learning functions of many variables
• Sparse harmonic transforms. II: Best \(s\)-term approximation guarantees for bounded orthonormal product bases in sublinear-time
• Sampling Boolean functions over Abelian groups and applications
• The uniform sparse FFT with application to PDEs with random coefficients
• Self-avoiding generating sequences for Fourier lattice designs
• Examples of sets with large trigonometric sums
• 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

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)