Article

Near-optimal sparse fourier representations via sampling

Authors:

S. Muthukrishnan,

M. StraussAuthors Info & Claims

STOC '02: Proceedings of the thiry-fourth annual ACM symposium on Theory of computing

Pages 152 - 161

https://doi.org/10.1145/509907.509933

Published: 19 May 2002 Publication History

Abstract

(MATH) We give an algorithm for finding a Fourier representation R of B terms for a given discrete signal signal A of length N, such that $\|\signal-\repn\|_2^2$ is within the factor (1 +ε) of best possible $\|\signal-\repn_\opt\|_2^2$. Our algorithm can access A by reading its values on a sample set T ⊆[0,N), chosen randomly from a (non-product) distribution of our choice, independent of A. That is, we sample non-adaptively. The total time cost of the algorithm is polynomial in B log(N)log(M)ε (where M is the ratio of largest to smallest numerical quantity encountered), which implies a similar bound for the number of samples.

References

[1]

D. Achlioptas, F. McSherry: Fast computation of low rank matrix. STOC 2001: 611--618.

Digital Library

[2]

N. Alon and Y. Mansour. ∈-discrepancy sets and their application for interpolation of sparse polynomials. Information Processing Letters, (54)6, 337--342, 1995.

Digital Library

[3]

S. Ar, R. Lipton, R. Rubinfeld, and M. Sudan. Reconstructing Algebraic Functions from Mixed Data. SIAM J. Comput. 28(2): 487-510 (1998).

Digital Library

[4]

N. Alon, Y. Matias, and M. Szegedy. The Space Complexity of Approximating the Frequency Moments. In Proceedings of the 28th Annual ACM Symposium on Theory of Computing (STOC), pp. 20--29, May 1996.

Digital Library

[5]

D. Donoho and P. Stark. Uncertainty principles and signal recovery. SIAM J. Appl. (MATH)., vol. 49, no. 3, pp. 906--931, June 1989.

Digital Library

[6]

A. Frieze, R. Kannan and S. Vempala. Fast Monte-Carlo Algorithms for Finding Low-Rank Approximations. Proc. of the 39th Foundations of Computer Science (FOCS '98), Palo Alto, 1998.

Digital Library

[7]

A. C. Gilbert, S. Guha, P. Indyk, Y. Kotidis, S. Muthukrishnan, and M. J. Strauss. Fast, Small-Space Algorithms for Approximate Histogram Maintenance. 2001, these proceedings.

Digital Library

[8]

W. B. Johnson and J. Lindenstrauss. Extensions of Lipshitz mapping into Hilbert space. Contemporary (MATH)ematics, 26 189--206, 1984.

[9]

T. H. Körner. Divergence of decreasing rearranged Fourier series. Annals of (MATH)ematics 144, pp. 167--180, 1996.

[10]

E. Kaltofen and L. Yagati. Improved Sparse Multivariate Polynomial Interpolation Algorithms. International Symposium on Symbolic and Algebraic Computation. Proc. ISSAC 1988, Springer-Verlag LNCS 358, 1988, pp. 467--474.

Digital Library

[11]

E. Kushilevitz, Y. Mansour: Learning Decision Trees Using the Fourier Sprectrum. STOC 1991: 455-464.

Digital Library

[12]

N. Linial, Y. Mansour, N. Nisan. Constant Depth Circuits, Fourier Transform, and Learnability. JACM 40(3): 607-620 (1993).

Digital Library

[13]

S. Mallat and Z. Zhang. Matching pursuits with time-frequency dictionaries. IEEE Transactions on Signal Processing, vol. 41, no. 12, pp. 3397--3415, 1993.

Digital Library

[14]

Y. Mansour. Learning Boolean Functions via the Fourier Transform. In Theoretical Advances in Neural Computation and Learning, (V.P. Roychodhury and K-Y. Siu and A. Orlitsky, ed.), 391--424 (1994).

[15]

W. A. Pearlman and R. M. Gray. Source coding of the discrete Fourier transform IEEE Trans. Inform. Theory, vol.~24, pp. 683--692, November 1978.

[16]

C. E. Shannon. Communications in the presence of noise. Proc. of the IRE (37), 10--21, January 1949.

[17]

H. J. Weaver. Applications of Discrete and Continuous Fourier Analysis. Wiley, 1983.

Digital Library

Cited By

Gross CIwen M(2024)Sparse Spectral Methods for Solving High-Dimensional and Multiscale Elliptic PDEsFoundations of Computational Mathematics10.1007/s10208-024-09649-8Online publication date: 2-Apr-2024
https://doi.org/10.1007/s10208-024-09649-8
Zhang GGao Y(2024)Structured Measurement Matrices Based on Deterministic Fourier Matrices and Gram MatricesCircuits, Systems, and Signal Processing10.1007/s00034-024-02692-443:8(5121-5138)Online publication date: 10-May-2024
https://doi.org/10.1007/s00034-024-02692-4
Olsak OJaros J(2023)On the Usage of the Sparse Fourier Transform in Ultrasound Propagation SimulationProceedings of the 2023 10th International Conference on Bioinformatics Research and Applications10.1145/3632047.3632064(107-113)Online publication date: 22-Sep-2023
https://dl.acm.org/doi/10.1145/3632047.3632064
Show More Cited By

Index Terms

Near-optimal sparse fourier representations via sampling

Recommendations

Sparse fourier transform in any constant dimension with nearly-optimal sample complexity in sublinear time
STOC '16: Proceedings of the forty-eighth annual ACM symposium on Theory of Computing

We consider the problem of computing a k-sparse approximation to the Fourier transform of a length N signal. Our main result is a randomized algorithm for computing such an approximation (i.e. achieving ℓ₂/ℓ₂ sparse recovery guarantees using Fourier ...
Nearly optimal sparse fourier transform
STOC '12: Proceedings of the forty-fourth annual ACM symposium on Theory of computing

We consider the problem of computing the k-sparse approximation to the discrete Fourier transform of an n-dimensional signal. We show: An O(k log n)-time randomized algorithm for the case where the input signal has at most k non-zero Fourier ...
(Nearly) sample-optimal sparse Fourier transform
SODA '14: Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms

We consider the problem of computing a k-sparse approximation to the discrete Fourier transform of an n-dimensional signal. Our main result is a randomized algorithm that computes such an approximation using O(k log n(log log n)^O(1)) signal samples in ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC '02: Proceedings of the thiry-fourth annual ACM symposium on Theory of computing

May 2002

840 pages

ISBN:1581134959

DOI:10.1145/509907

Conference Chair:
John Reif
Duke University

Copyright © 2002 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 19 May 2002

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

STOC02

Sponsor:

SIGACT

STOC02: Symposium on the Theory of Computing

May 19 - 21, 2002

Quebec, Montreal, Canada

Acceptance Rates

STOC '02 Paper Acceptance Rate 91 of 287 submissions, 32%;

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

139
Total Citations
View Citations
200
Total Downloads

Downloads (Last 12 months)30
Downloads (Last 6 weeks)4

Reflects downloads up to 10 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Gross CIwen M(2024)Sparse Spectral Methods for Solving High-Dimensional and Multiscale Elliptic PDEsFoundations of Computational Mathematics10.1007/s10208-024-09649-8Online publication date: 2-Apr-2024
https://doi.org/10.1007/s10208-024-09649-8
Zhang GGao Y(2024)Structured Measurement Matrices Based on Deterministic Fourier Matrices and Gram MatricesCircuits, Systems, and Signal Processing10.1007/s00034-024-02692-443:8(5121-5138)Online publication date: 10-May-2024
https://doi.org/10.1007/s00034-024-02692-4
Olsak OJaros J(2023)On the Usage of the Sparse Fourier Transform in Ultrasound Propagation SimulationProceedings of the 2023 10th International Conference on Bioinformatics Research and Applications10.1145/3632047.3632064(107-113)Online publication date: 22-Sep-2023
https://dl.acm.org/doi/10.1145/3632047.3632064
Xu DLi WShi JFeng B(2023)SA-CCSNet: Saliency-Aware Cascade Network for Image Compressed Sensing2023 IEEE 6th International Conference on Pattern Recognition and Artificial Intelligence (PRAI)10.1109/PRAI59366.2023.10331938(764-770)Online publication date: 18-Aug-2023
https://doi.org/10.1109/PRAI59366.2023.10331938
Rodríguez-Maldonado JPosadas-Castillo CZambrano-Serrano E(2022)Alternative Method to Estimate the Fourier Expansions and Its Rate of ChangeMathematics10.3390/math1020383210:20(3832)Online publication date: 17-Oct-2022
https://doi.org/10.3390/math10203832
Li BHou XJiang ZChen J(2022)Two Efficient Sparse Fourier Algorithms Using the Matrix Pencil MethodElectronics10.3390/electronics1115229111:15(2291)Online publication date: 22-Jul-2022
https://doi.org/10.3390/electronics11152291
Fuchs TGross DKrahmer FKueng RMixon D(2022)Sketching with Kerdock's CrayonsSIAM Journal on Matrix Analysis and Applications10.1137/21M143899243:2(939-952)Online publication date: 1-Jan-2022
https://dl.acm.org/doi/10.1137/21M1438992
Chen SMoitra AKhuller SVassilevska Williams V(2021)Algorithmic foundations for the diffraction limitProceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing10.1145/3406325.3451078(490-503)Online publication date: 15-Jun-2021
https://dl.acm.org/doi/10.1145/3406325.3451078
Jiang ZChen JLi B(2021)Empirical Evaluation of Typical Sparse Fast Fourier Transform AlgorithmsIEEE Access10.1109/ACCESS.2021.30950719(97100-97119)Online publication date: 2021
https://doi.org/10.1109/ACCESS.2021.3095071
Kämmerer LKrahmer FVolkmer T(2021)A sample efficient sparse FFT for arbitrary frequency candidate sets in high dimensionsNumerical Algorithms10.1007/s11075-021-01162-189:4(1479-1520)Online publication date: 7-Dec-2021
https://doi.org/10.1007/s11075-021-01162-1
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents