NDLI: Improved sparse fourier approximation results: faster implementations and stronger guarantees

Content Provider	Springer Nature Link
Author	Segal, Ben Iwen, M. A.
Copyright Year	2012
Abstract	We study the problem of quickly estimating the best k-term Fourier representation for a given periodic function f: [0, 2π] → ℂ. Solving this problem requires the identification of k of the largest magnitude Fourier series coefficients of f in worst case k $^{2}$ · log$^{ O(1)}$ N time. Randomized sublinear-time Monte Carlo algorithms, which have a small probability of failing to output accurate answers for each input signal, have been developed for solving this problem (Gilbert et al. 2002, 2005). These methods were implemented as the Ann Arbor Fast Fourier Transform (AAFFT) and empirically evaluated in Iwen et al. (Commun Math Sci 5(4):981–998, 2007). In this paper we present a new implementation, called the Gopher Fast Fourier Transform (GFFT), of more recently developed sparse Fourier transform techniques (Iwen, Found Comput Math 10(3):303–338, 2010, Appl Comput Harmon Anal, 2012). Experiments indicate that GFFT is faster than AAFFT. In addition to our empirical evaluation, we also consider the existence of sublinear-time Fourier approximation methods with deterministic approximation guarantees for functions whose sequences of Fourier series coefficents are compressible. In particular, we prove the existence of sublinear-time Las Vegas Fourier Transforms which improve on the recent deterministic Fourier approximation results of Iwen (Found Comput Math 10(3):303–338, 2010, Appl Comput Harmon Anal, 2012) for Fourier compressible functions by guaranteeing accurate answers while using an asymptotically near-optimal number of function evaluations.
Starting Page	239
Ending Page	263
Page Count	25
File Format	PDF
ISSN	10171398
Journal	Numerical Algorithms
Volume Number	63
Issue Number	2
e-ISSN	15729265
Language	English
Publisher	Springer US
Publisher Date	2012-07-26
Publisher Place	Boston
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Fourier analysis Sparse approximation Fast Fourier transforms Randomized algorithms Numeric Computing Algorithms Algebra Theory of Computation Numerical Analysis
Content Type	Text
Resource Type	Article
Subject	Applied Mathematics

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Rapidly computing sparse Legendre expansions via sparse Fourier transforms

A deterministic sparse FFT algorithm for vectors with small support

Singular integral transforms and fast numerical algorithms

A New Class of Fully Discrete Sparse Fourier Transforms: Faster Stable Implementations with Guarantees

The sparse cardinal sine decomposition and its application for fast numerical convolution

Image deblurring by sparsity constraint on the Fourier coefficients

Numerical integration using sparse grids

Efficient Trefftz collocation algorithms for elliptic problems in circular domains

Numerical approximation of homoclinic chaos

Improved sparse fourier approximation results: faster implementations and stronger guarantees

Similar Documents

Rapidly computing sparse Legendre expansions via sparse Fourier transforms

A deterministic sparse FFT algorithm for vectors with small support

Singular integral transforms and fast numerical algorithms

A New Class of Fully Discrete Sparse Fourier Transforms: Faster Stable Implementations with Guarantees

The sparse cardinal sine decomposition and its application for fast numerical convolution

Image deblurring by sparsity constraint on the Fourier coefficients

Numerical integration using sparse grids

Efficient Trefftz collocation algorithms for elliptic problems in circular domains

Numerical approximation of homoclinic chaos

Improved sparse fourier approximation results: faster implementations and stronger guarantees