Efficient $k$-Sparse Band–Limited Interpolation with Improved Approximation Ratio

We thank the reviewer for the thoughtful comments and the recommendation for acceptance. We appreciate your recognizing our results are strong and worthwhile. Below, we address the weakness and questions.

W1: Version of Fourier transform

Thank you for the question. Our main results focus on the one‑dimensional continuous sparse Fourier transform on a regular grid. When discussing techniques, however, we sometimes describe them in a dimension‑agnostic way, which may have caused confusion. In the revision we will clarify this distinction, tighten the wording, and ensure the notation remains consistent throughout.

W2: The notion of ‘’band-limited’’

Thank you for raising this point. In our paper, “band‑limited signal” specifically means a signal that is both band‑limited and $k$-sparse in the Fourier domain. We will clarify this in the revision by consistently writing ‘’$k$-sparse band‑limited signal.”

W3 & W4: The form of measurements and the band limit $F$ are mentioned implicitly in the text.

Thanks for pointing out this. We will define these notations more in a clearer way.

W5: The informal version of theorems.

For brevity and readability, we included only an informal version of main theorems in the main text. We agree, however, that more precise statements should appear there. In the revision, we will explicitly state that the guarantee holds with high probability in the main theorems.

Typos

Thanks for spotting the typos. We will fix them in the revised version.

We sincerely thank you for your time and valuable comments. We hope that the above clarifications address your concerns, and we are happy to discuss further if needed.

We thank the reviewer for the thoughtful comments and the recommendation for acceptance. We appreciate that you highlight the first polynomial‑time algorithm with an improved approximation ratio, the clear definitions and presentation, and the subtle two‑stage composition that enables the sharper bound on each stage. Below, we address the weakness and questions.

W1: Proofs are deferred to Appendix.

To keep the main text streamlined, we placed the detailed proof in the appendix while keeping every theorem’s key steps and proof sketch in the technique overview. We will try to improve the presentation and readability of the algorithms in the revised version. Thanks for pointing this out.

W2: Novelty

Thanks for the question. We would like to clarify the novelty and contribution of our paper. Although the high‑level pipeline resembles prior work, our multiplicative noise‑cancellation analysis breaks the long‑standing $>100$ constant barrier, cutting the worst‑case approximation ratio to $\approx 5$ within a small factor of the information‑theoretic optimum. Achieving this required new, tighter energy bounds and a refined sketch‑distillation step that eliminates the additive‑error accumulation present in all earlier methods. This, in turn, demands a more delicate control of error propagation across stages, which we believe is nontrivial.

W3: Empirical validation

Thank you for your question regarding the real-world empirical validation of our algorithms. While empirical validation would be interesting, demonstrating these guarantees experimentally would require a substantial engineering effort and domain‑specific datasets that lie outside the paper’s scope since our primary contribution is intentionally theoretical. We focused on rigorous analysis and proofs. We would like to clarify that our work is purely a theoretical study, which does have a large place in the top machine learning conferences, like NeurIPS, ICLR, and ICML. For instance, NeurIPS accepts papers [1,2,3,4], all of which are entirely theoretical and do not contain any experiments. Moreover, ICLR and ICML also accepted papers [5,6], which are purely theoretical. Our work is similar to theoretical studies like [6], concentrating on the theoretical aspects of Fourier transform.

Q1: Extension to high dimension

Our present algorithm is formulated for one‑dimensional signals. The main challenge for extending it to high dimension setting is the curse of dimensionality since naively treating a $d$-dimensional signal as a flattened $1$-dimensional signal would inflate both sample and time complexity exponentially in $d$. A more scalable route is to exploit structure, e.g., separable band‑pass filters and tensor‑product sketching, so that each dimension is processed independently before a joint sparse regression stage. This would raise complexity only by a factor polynomial in $d$. Whether the same order of constant factor accuracy can be preserved requires a more detailed analysis. Formalising this extension is an interesting direction for future work.

Q2: Detailed run time analysis

Thanks for the question. Since our focus is on developing the high-accuracy algorithm, we didn’t include the detailed runtime analysis of some less important parameters. In fact, the major runtime cost of our high‑accuracy algorithm come from sketch distillation and solving weighted regression. With carefulled analysis, in sketch distillation first, our algorithm repeats the constant‑factor loop just $\Theta(1/\epsilon)$ times so every candidate signal’s energy is preserved within a $(1+\epsilon)$ factor, incurring only $\Theta(\epsilon^{-1} k)$ arithmetic operations and samples. The weighted regression involves a $k \times k$ weighted least‑squares system, which costs $k^\omega$ time using fast matrix multiplication where $\omega$ is the exponent of matrix multiplication and $\omega \approx 2.37$. Thus the $\mathrm{poly}(\epsilon^{-1},k)$ can be roughly expressed as $O(\epsilon^{-1}k^\omega)$.

Q3: Effects of parameters

Our guarantees depend on the noise level only through the composite term $\mathcal{N}^2 = \\|g\\|_T^2+\delta \\|x^*\\|_T^2$. Hence SNR enters linearly: doubling the noise variance roughly doubles every error term. With respect to frequency gap, the theory requires a minimum separation of $\eta \geq \Omega(1/T)$ to avoid aliasing. Hence the $\log(FT)$ factor in runtime can be replaced with $\log(F/\eta)$.

We sincerely thank you for your time and valuable comments. We hope that the above clarifications address your concerns, and we are happy to discuss further if needed.

[1] Alman, J., & Song, Z. Fast attention requires bounded entries. NeurIPS’23.

[2] Sarlos, T., Song, X., Woodruff, D., & Zhang, R. Hardness of low rank approximation of entrywise transformed matrix products. NeurIPS’23.

[3] Dexter, G., Drineas, P., Woodruff, D., & Yasuda, T. Sketching algorithms for sparse dictionary learning: PTAS and turnstile streaming. NeurIPS’23.

[4] Song, Z., Vakilian, A., Woodruff, D., & Zhou, S. On Socially Fair Low-Rank Approximation and Column Subset Selection. NeurIPS’24

[5] Kim, J., & Suzuki, T. Transformers Provably Solve Parity Efficiently with Chain of Thought. In The Thirteenth International Conference on Learning Representations. ICLR’25

[6] Li, X., Song, Z., & Xie, S. Deterministic sparse fourier transform for continuous signals with frequency gap. ICML’25.

Thank you very much for your detailed reply. I have no other questions about this paper. Based on your reply, I have raised the scores for "Quality" and "Importance", and changed the Rating to "Accept".

Thank you for the constructive review and recommendation for acceptance. We appreciate your recognition of our rigorous framework, technical contributions, and theoretical analysis. Below, we address the noted weaknesses and questions.

W1: The notion of approximation ratio

Thanks for pointing this out. The approximation ratio is the standard terminology in approximation algorithms, which refers to the factor by which an algorithm's solution deviates from the optimal solution for a given computational problem. In our setting, it quantifies how much larger the reconstruction error $\\|y-x^*\\|_T$​ can be, relative to the best achievable error. We will define it clearer in our revised version.

W2: Assumption on $k$-sparsity in the frequency domain.

This is an interesting question. In fact, as quoted from [7]: “Many applications rely on the fact that most of the Fourier coefficients of the signals are small or equal to zero, i.e., the signals are (approximately) sparse. Thus it is very natural to study the setting where the Fourier spectrum is approximately $k$-sparse, and it has been studied over the last two decades, see [6,7,8,9,10].

W3: Numerical issue.

Thank you for flagging the potential numerical challenges. Our present work concentrates on the algorithm design and theoretical guarantees. We defer the development of a robust, industrial‑grade implementation to future work.

W4 & Q1: Extension to high dimension

Yes, our present algorithm is formulated for one‑dimensional signals. The main challenge for extending it to high dimension setting is the curse of dimensionality since naively treating a $d$-dimensional signal as a flattened $1$-dimensional signal would inflate both sample and time complexity exponentially in $d$. A more scalable route is to exploit structure, e.g., separable band‑pass filters and tensor‑product sketching, so that each dimension is processed independently before a joint sparse regression stage. This would raise complexity only by a factor polynomial in $d$. Whether the same order of constant factor accuracy can be preserved requires a more detailed analysis. Formalising this extension is an interesting direction for future work.

W5: Empirical validation

Thank you for your question regarding the real-world empirical validation of our algorithms. While empirical validation would be interesting, demonstrating these guarantees experimentally would require a substantial engineering effort and domain‑specific datasets that lie outside the paper’s scope since our primary contribution is intentionally theoretical. We focused on rigorous analysis and proofs. We would like to clarify that our work is purely a theoretical study, which does have a large place in the top machine learning conferences, like NeurIPS, ICLR, and ICML. For instance, NeurIPS accepts papers [1,2,3,4], all of which are entirely theoretical and do not contain any experiments. Moreover, ICLR and ICML also accepted papers [5,6], which are purely theoretical. Our work is similar to theoretical studies like [6], concentrating on the theoretical aspects of Fourier transform.

W6: Detail analysis of scalability

Since our focus is on developing the high-accuracy algorithm, we didn’t include the detailed runtime analysis of some less important parameters. In fact, the major runtime cost of our high‑accuracy algorithm come from sketch distillation and solving weighted regression. With carefulled analysis, in sketch distillation first, our algorithm repeats the constant‑factor loop just $\Theta(1/\epsilon)$ times so every candidate signal’s energy is preserved within a $(1+\epsilon)$ factor, incurring only $\Theta(\epsilon^{-1} k)$ arithmetic operations and samples. The weighted regression involves a $k \times k$ weighted least‑squares system, which costs $k^\omega$ time using fast matrix multiplication where $\omega$ is the exponent of matrix multiplication and $\omega \approx 2.37$. Thus the $\mathrm{poly}(\epsilon^{-1},k)$ can be roughly expressed as $O(\epsilon^{-1}k^\omega)$. Evaluating the algorithm’s scalability in real‑world deployments is an engaging avenue for future work. Thank you for raising this point.

We sincerely thank you for your time and valuable comments. We hope that the above clarifications address your concerns, and we are happy to discuss further if needed.

Reference

[1] Alman, J., & Song, Z. Fast attention requires bounded entries. NeurIPS’23.

[2] Sarlos, T., Song, X., Woodruff, D., & Zhang, R. Hardness of low rank approximation of entrywise transformed matrix products. NeurIPS’23.

[3] Dexter, G., Drineas, P., Woodruff, D., & Yasuda, T. Sketching algorithms for sparse dictionary learning: PTAS and turnstile streaming. NeurIPS’23.

[4] Song, Z., Vakilian, A., Woodruff, D., & Zhou, S. On Socially Fair Low-Rank Approximation and Column Subset Selection. NeurIPS’24

[5] Kim, J., & Suzuki, T. Transformers Provably Solve Parity Efficiently with Chain of Thought. In The Thirteenth International Conference on Learning Representations. ICLR’25

[6] Li, X., Song, Z., & Xie, S. Deterministic sparse fourier transform for continuous signals with frequency gap. ICML’25.

[7] Indyk, P., & Kapralov, M. Sample-optimal Fourier sampling in any constant dimension. FOCS’14

[8] Price, E., & Song, Z. A robust sparse Fourier transform in the continuous setting. FOCS’15

[9] Hassanieh, H., Indyk, P., Katabi, D., & Price, E. Nearly optimal sparse Fourier transform. STOC’12.

[10] Hassanieh, H., Indyk, P., Katabi, D., & Price, E. Simple and practical algorithm for sparse Fourier transform. SODA’12

Thank you for the insightful review and recommending for acceptance. We are glad that you find our results are remarkable and the paper is well-written. Below, we address your concerns and questions.

W1: Lack of empirical validation.

Thank you for your question regarding the real-world empirical validation of our algorithms. While empirical validation would be interesting, demonstrating these guarantees experimentally would require a substantial engineering effort and domain‑specific datasets that lie outside the paper’s scope since our primary contribution is intentionally theoretical. We focused on rigorous analysis and proofs. We would like to clarify that our work is purely a theoretical study, which does have a large place in the top machine learning conferences, like NeurIPS, ICLR, and ICML. For instance, NeurIPS accepts papers [1,2,3,4], all of which are entirely theoretical and do not contain any experiments. Moreover, ICLR and ICML also accepted papers [5,6], which are purely theoretical. Our work is similar to theoretical studies like [6], concentrating on the theoretical aspects of Fourier transform.

W2: Connection with ML conferences.

In recent years, Fourier transform has also emerged as a powerful tool within machine learning research, inspiring diverse models and algorithms [7,8,9,10,11,12]. Due to its significance in both theory and practice, finding an efficient algorithm to compute the Fourier transform is of utmost importance, especially for machine learning. The most remarkable one is the random feature method [13], which has extensive applications in neural networks [14,15,16].

Q1: It is not clear if a minimum frequency separation is required here or only k-sparsity suffices. What is the usual order of the four sources of error? Is anyone more dominant the others?

Thank you for pointing this out. Yes, consistent with the standard continuous‑SFT literature, our analysis assumes an $\Omega(1/T)$ minimum separation between any two true frequencies. We might miss this in the condition and will fix it in the revised version.

Q2: What is the usual order of the four sources of error? Is anyone more dominant the others?

In prior works, the heavy‑cluster truncation error $E_1$ is always the dominant contributor because it scales as $\mathcal{N}^4$​. The sampling‑and‑regression error $E_3$ is the next‑largest, growing only linearly with $\mathcal{N}$, so it can approach, but rarely surpass, $E_1$ when the SNR is low. Polynomial approximation $E_2$ is proportional to the chosen tolerance $\delta$ and stays much smaller. In our proposed scheme, all structural errors scale only linearly in $\mathcal{N}$, so their sizes are determined by the leading constants. The weighted‑regression term is largest, $E_{3}^{\text{new}} \leq (4+\epsilon)\mathcal{N}$ . Next comes the energy of frequencies that fail the reinforced cluster condition, $E_{1.5} \leq (2+\epsilon)\mathcal{N}$, followed by the initial heavy‑cluster truncation, $E_{1}^{\text{new}} \leq (1+\epsilon)\mathcal{N}$. The polynomial‑approximation error remains proportional to the chosen tolerance $\delta$ and stays much smaller. Hence the typical hierarchy is $E_{3}^{\text{new}} \geq E_{1.5} \geq E_{1}^{\text{new}} \gg E_{2}$.

Q3: There are many signals which are multi-band. Would it be a simple extension of this work? Multi-band spectral recovery is a well-investigated topic using atomic norm minimization. Some prior works also employ mild prior knowledge in such cases. See the (separate) works of Weiyu Xu and Gongguo Tang on this.

Thank you for pointing out the works on multi-band spectral recovery. We will cite these works in the revised version and discuss the potential extension in the revised version. We believe a detailed, formal treatment of this extension, along with a comparison to atomic‑norm guarantees, is an interesting direction for future work.

We sincerely thank you for your time and valuable comments. We hope that the above clarifications address your concerns, and we are happy to discuss further if needed.

Reference

[1] Alman, J., & Song, Z. Fast attention requires bounded entries. NeurIPS’23.

[2] Sarlos, T., Song, X., Woodruff, D., & Zhang, R. Hardness of low rank approximation of entrywise transformed matrix products. NeurIPS’23.

[3] Dexter, G., Drineas, P., Woodruff, D., & Yasuda, T. Sketching algorithms for sparse dictionary learning: PTAS and turnstile streaming. NeurIPS’23.

[4] Song, Z., Vakilian, A., Woodruff, D., & Zhou, S. On Socially Fair Low-Rank Approximation and Column Subset Selection. NeurIPS’24

[5] Kim, J., & Suzuki, T. Transformers Provably Solve Parity Efficiently with Chain of Thought. In The Thirteenth International Conference on Learning Representations. ICLR’25

[6] Li, X., Song, Z., & Xie, S. Deterministic sparse fourier transform for continuous signals with frequency gap. ICML’25.

[7] Lee, J. D., Shen, R., Song, Z., Wang, M., and Yu, z. Generalized leverage score sampling for neural networks. NeurIPS’20

[8] Choromanski, K. M., Likhosherstov, V., Dohan, D., Song, X., Gane, A., Sarlos, T., Hawkins, P., Davis, J. Q., Mohiuddin, A., Kaiser, L., Belanger, D. B., Colwell, L. J., and Weller, A. Rethinking attention with performers. InInternational Conference on Learning Representations . ICLR’ 2021

[9] Li, Z., Kovachki, N. B., Azizzadenesheli, K., Liu, B., Bhattacharya, K., Stuart, A., and Anandkumar, A. Fourier neural operator for parametric partial differential equations. ICLR’ 21

[10] Yang R, Cao L, YANG J. Rethinking fourier transform from a basis functions perspective for long-term time series forecasting. NeurIPS’24

[11] Alman, J. and Song, Z. Fast rope attention: Combining the polynomial method and fast Fourier transform. arXiv preprint arXiv:2505.11892, 2025

[12] Yu, E., Lu, J., Yang, X., Zhang, G., and Fang, Z. Learning robust spectral dynamics for temporal domain generalization. arXiv preprint arxiv: 2505.12585, 2025

[13] Rahimi, A., & Recht, B. Random features for large-scale kernel machines. NeurIPS'07

[14] Yehudai, G., & Shamir, O. On the power and limitations of random features for understanding neural networks. NeurIPS'19

[15] Frei, S., Chatterji, N. S., & Bartlett, P. L. Random feature amplification: Feature learning and generalization in neural networks. JMLR, 2023.

[16] Sato, R., Yamada, M., & Kashima, H. Random features strengthen graph neural networks. ICDM'21