Dynamic SFT with Structured Measurements: Fast Queries, Fast Updates, Provable Guarantees

Yang Cao, Zhao Song
Conference on Parsimony and Learning, PMLR 328:795-825, 2026.

Abstract

The sparse Fourier transform typically proceeds in two stages: frequency estimation and signal estimation. The first recovers the set of frequencies from noisy time-domain samples; the second constructs their corresponding magnitudes. In most methods, signal estimation is only approximate and depends on the frequencies identified in the first stage. In this paper, we study a complementary question: given access to an oracle that returns the exact magnitude for any queried frequency, what is the minimum number of oracle calls needed to perform a sparse Fourier transform? For an n-point discrete Fourier transform, the naive approach queries all n frequencies. We design the first algorithm that requires only $o(n)$ oracle invocations. We further complement this upper bound with a lower bound, derived using tools from computational complexity.

Cite this Paper

BibTeX
@InProceedings{pmlr-v328-cao26a, title = {Dynamic SFT with Structured Measurements: Fast Queries, Fast Updates, Provable Guarantees}, author = {Cao, Yang and Song, Zhao}, booktitle = {Conference on Parsimony and Learning}, pages = {795--825}, year = {2026}, editor = {Burkholz, Rebekka and Liu, Shiwei and Ravishankar, Saiprasad and Redman, William and Huang, Wei and Su, Weijie and Zhu, Zhihui}, volume = {328}, series = {Proceedings of Machine Learning Research}, month = {23--26 Mar}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v328/main/assets/cao26a/cao26a.pdf}, url = {https://proceedings.mlr.press/v328/cao26a.html}, abstract = {The sparse Fourier transform typically proceeds in two stages: frequency estimation and signal estimation. The first recovers the set of frequencies from noisy time-domain samples; the second constructs their corresponding magnitudes. In most methods, signal estimation is only approximate and depends on the frequencies identified in the first stage. In this paper, we study a complementary question: given access to an oracle that returns the exact magnitude for any queried frequency, what is the minimum number of oracle calls needed to perform a sparse Fourier transform? For an n-point discrete Fourier transform, the naive approach queries all n frequencies. We design the first algorithm that requires only $o(n)$ oracle invocations. We further complement this upper bound with a lower bound, derived using tools from computational complexity.} }
Endnote
%0 Conference Paper %T Dynamic SFT with Structured Measurements: Fast Queries, Fast Updates, Provable Guarantees %A Yang Cao %A Zhao Song %B Conference on Parsimony and Learning %C Proceedings of Machine Learning Research %D 2026 %E Rebekka Burkholz %E Shiwei Liu %E Saiprasad Ravishankar %E William Redman %E Wei Huang %E Weijie Su %E Zhihui Zhu %F pmlr-v328-cao26a %I PMLR %P 795--825 %U https://proceedings.mlr.press/v328/cao26a.html %V 328 %X The sparse Fourier transform typically proceeds in two stages: frequency estimation and signal estimation. The first recovers the set of frequencies from noisy time-domain samples; the second constructs their corresponding magnitudes. In most methods, signal estimation is only approximate and depends on the frequencies identified in the first stage. In this paper, we study a complementary question: given access to an oracle that returns the exact magnitude for any queried frequency, what is the minimum number of oracle calls needed to perform a sparse Fourier transform? For an n-point discrete Fourier transform, the naive approach queries all n frequencies. We design the first algorithm that requires only $o(n)$ oracle invocations. We further complement this upper bound with a lower bound, derived using tools from computational complexity.
APA
Cao, Y. & Song, Z.. (2026). Dynamic SFT with Structured Measurements: Fast Queries, Fast Updates, Provable Guarantees. Conference on Parsimony and Learning, in Proceedings of Machine Learning Research 328:795-825 Available from https://proceedings.mlr.press/v328/cao26a.html.

Related Material