AI & ML
A Nonadaptive Sparse Fourier Transform in Every Dimension
arXiv cs.NA0 views
arXiv:2611.25334v1 Announce Type: cross Abstract: Let $G=(\mathbb{Z}/2^a\mathbb{Z})^d$, of order $N=2^{ad}$. Given point-query access to any complex signal $X$ with Fourier transform $\hat{X}$ over $G$, we provide a randomized algorithm that constructs a $k$-sparse estimate $\widetilde{X}$ via non-adaptive queries such that, with large probability, $\|\widetilde{X}-\hat{X}\|_2^2 \leq C \cdot \|H_k(\hat{X})-\hat{X}\|_2^2$, for an absolute constant $C>0$, where $H_k(\cdot)$ denotes the best $k$-sparse approximation. The constant $C$ can be improved to any desired $1+\varepsilon$ by either supplying a constant-factor estimate on the $k$-sparse tail norm or allowing an arbitrarily small additive error term $\delta \|\hat{X}\|_2^2$ on the right-hand side. With a supplied tail estimate, we can also satisfy an $\ell_\infty/\ell_2$ heavy hitters guarantee. For fixed $\delta$, the number of samples is $O((k/\varepsilon^2)(\log N)\log(k/\varepsilon))$, and the recovery algorithm requires a polynomial in $(k/\varepsilon)\log N$ exact operations. The algorithm naturally extends to $G=(\mathbb{Z}/b^a\mathbb{Z})^d$ for any fixed integer $b>1$.
Source:https://arxiv.org/abs/2611.25334PreviousAccelerating Diffusion Maps on a Quantum Computer: Spectral Filtering and Galerkin PDE SolversNextFinite-difference least square methods for solving Hamilton-Jacobi equations using neural networks
Related posts
How we tell parents what a teen's AI chat was about, without showing them the chat
0dev.to
GitHub Actions GITHUB_TOKEN: 11 Tags Pushed, 0 Release Workflows Ran
0dev.to

I can't believe the podcast I learned to code with is back!
0dev.to
Practice unaided and AI-assisted coding as two different skills
0dev.to
Best Semrush AI Visibility Toolkit Alternatives in 2026 (prices checked)
0dev.to
More of the AI in Your Product May Run on the User's Own Device
0dev.to