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

Roast My Dev Desktop: Zero Minimalism, Maximum Chaos
0dev.to
랩트 모네로 붕괴: 익숙한 신뢰 배신 이야기
0dev.to
Why has it become harder and harder to type one-handed on smartphones these days?
0dev.to
내 PDF 문서를 로컬 LLM에게 검색시키기 — RAG 실전 구축
0dev.to
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