Improved approximation guarantees for sublinear-time Fourier algorithms

DOI10.1016/J.ACHA.2012.03.007MaRDI QIDQ1762319zbMATH OpenOpenAlexWikidataFDO

Authors M. A. Iwen

Publication date 23 November 2012

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

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

zbMATH Keywords

approximation algorithmsfast Fourier transformsFourier analysissignal recoverytrigonometric approximation

Mathematics Subject Classification ID

Trigonometric approximation (42A10) Fourier and Fourier-Stieltjes transforms and other transforms of Fourier type (42A38) Numerical methods for trigonometric approximation and interpolation (65T40) Numerical methods for discrete and fast Fourier transforms (65T50)

Abstract: In this paper modified variants of the sparse Fourier transform algorithms from [14] are presented which improve on the approximation error bounds of the original algorithms. In addition, simple methods for extending the improved sparse Fourier transforms to higher dimensional settings are developed. As a consequence, approximate Fourier transforms are obtained which will identify a near-optimal k-term Fourier series for any given input function, $f:[0,2pi]->C,inO(k^{2}cdot{D}^4)$ time (neglecting logarithmic factors). Faster randomized Fourier algorithm variants with runtime complexities that scale linearly in the sparsity parameter k are also presented.

Review text

This paper develops fast methods for finding near-optimal nonlinear approximations to the Fourier transform of a given continuous and periodic function \(f:\;[0,2\pi]^D\to\mathbb C\). Suppose that \(f\) is a band limited so that its Fourier transform, \(\hat f:\;\mathbb Z^D\to \mathbb C\), is zero for all \(\omega\notin [-N/2,N/2]^D\), where \(N^D\) is large. An optimal \(k\)-term trigonometric approximation to \(f\) is given by \[ f_k^{\text{opt}}({\mathbf x})=\sum_{j=1}^k\hat f (\omega_j)e^{i\omega_j{\mathbf x}}, \] where \(\omega_1,\dots,\omega_{N^D}\in (-N/2,N/2]^D\bigcap\mathbb Z^D\) are ordered by the magnitudes of their coefficients so that \[ |\hat f(\omega_1)|\geq|\hat f(\omega_2)|\geq\dots\geq |\hat f(\omega_{N^D})|. \] The optimal \(k\)-term approximation error is then \(\|f-f_k^{\text{opt}}\|_2=\|\hat f-\hat f_k^{\text{opt}}\|_2\). Suppose \(k\in\mathbb N\) is given. The goal of this paper is to develop fast Fourier approximation schemes that are guaranteed to always return a near-optimal trigonometric polynomial, \(y_k:\;[0,2\pi]^D\to\mathbb C\), having \(\|f-y_k\|_2\approx\|\hat f-\hat f_k^{\text{opt}}\|_2\).

Recommendations

• Improved sparse Fourier approximation results: Faster implementations and stronger guarantees
• Combinatorial sublinear-time Fourier algorithms
• Nearly optimal sparse Fourier transform
• scientific article; zbMATH DE number 55678
• Sparse Fourier transforms on rank-1 lattices for the rapid and low-memory approximation of functions of many variables

Cited in

(35)

• A tighter bound for FFd algorithm
• Deterministic sparse FFT for M-sparse vectors
• A deterministic sparse FFT for functions with structured Fourier sparsity
• High-dimensional sparse Fourier algorithms
• 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
• Deterministic sparse sublinear FFT with improved numerical stability
• A deterministic algorithm for constructing multiple rank-1 lattices of near-optimal size
• 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
• A sample efficient sparse FFT for arbitrary frequency candidate sets in high dimensions
• Compressed sensing with sparse binary matrices: instance optimal error guarantees in near-optimal time
• Sparse fast DCT for vectors with one-block support
• Real sparse fast DCT for vectors with short support
• A sparse fast Fourier algorithm for real non-negative vectors
• System identification in dynamical sampling
• Improved sparse Fourier approximation results: Faster implementations and stronger guarantees
• 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
• A deterministic sparse FFT algorithm for vectors with small support
• On the Fourier Extension of Nonperiodic Functions
• Sparse high-dimensional FFT based on rank-1 lattice sampling
• Upper and Lower Bounds on Time-Space Tradeoffs for Computations with Embedded Fast Fourier Transforms
• A note on the high-dimensional sparse Fourier transform in the continuous setting
• Sketching with Kerdock's crayons: fast sparsifying transforms for arbitrary linear maps
• Rapidly computing sparse Legendre expansions via sparse Fourier transforms
• Sparse Fourier transform in any constant dimension with nearly-optimal sample complexity in sublinear time
• scientific article; zbMATH DE number 7053345 (Why is no real title available?)
• Lower Memory Oblivious (Tensor) Subspace Embeddings with Fewer Random Bits: Modewise Methods for Least Squares
• Performance of the multiscale sparse fast Fourier transform algorithm
• Nonlinear approximation in bounded orthonormal product bases
• Deterministic sparse Fourier transform with an _ guarantee
• SCAN-MUSIC: an efficient super-resolution algorithm for large-scale single snapshot line spectral estimation
• A sublinear algorithm for the recovery of signals with sparse Fourier transform when many samples are missing
• Combinatorial sublinear-time Fourier algorithms

This page was built for publication: Improved approximation guarantees for sublinear-time Fourier algorithms

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