\documentclass[11pt]{article} \usepackage[utf8]{inputenc} \usepackage[T1]{fontenc} \usepackage{lmodern} \usepackage{microtype} \usepackage{amsmath,amssymb,amsthm,mathtools} \usepackage{enumitem} \usepackage[margin=1in]{geometry} \usepackage[colorlinks=true,linkcolor=blue,citecolor=blue,urlcolor=blue]{hyperref} \theoremstyle{plain} \newtheorem{theorem}{Theorem}[section] \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{corollary}[theorem]{Corollary} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{question}[theorem]{Question} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \DeclareMathOperator{\Var}{Var} \DeclareMathOperator{\diag}{diag} \DeclareMathOperator{\spanop}{span} \newcommand{\R}{\mathbb{R}} \newcommand{\E}{\mathbb{E}} \newcommand{\Prb}{\mathbb{P}} \newcommand{\eps}{\varepsilon} \newcommand{\wtO}{\widetilde O} \title{Diameter-Free Pointwise Gaussian KDE\\ in Near-Additive Query Time\thanks{This work was produced within the Bolzano project (\url{https://bolzano.app}), using AI systems for mathematical research and manuscript preparation. The listed authors contributed to the project and the preparation of this release. The manuscript received only limited human checking.}} \author{Mat\v{e}j Kripner \qquad V\'{a}clav Rozho\v{n} \qquad Robert \v{S}\'{a}mal\\[0.4em] Martin \v{S}indel\'{a}\v{r} \qquad Adri\'{a}n Z\'{a}me\v{c}n\'{i}k} \date{} \hypersetup{ pdftitle={Diameter-Free Pointwise Gaussian KDE in Near-Additive Query Time}, pdfauthor={Matěj Kripner, Václav Rozhoň, Robert Šámal, Martin Šindelář, Adrián Zámečník}, pdfsubject={A norm-uniform Fastfood variance bound for pointwise Gaussian kernel-density estimation}, pdfkeywords={Gaussian KDE, random Fourier features, Fastfood, structured random features, Walsh--Hadamard transform} } \usepackage{xcolor} % Collection typography. \geometry{a4paper,hmargin=23mm,vmargin=25mm} \definecolor{BolzanoInk}{HTML}{24445C} \hypersetup{colorlinks=true,linkcolor=BolzanoInk,citecolor=BolzanoInk, urlcolor=BolzanoInk,pdfauthor={Matěj Kripner, Václav Rozhoň, Robert Šámal, Martin Šindelář, Adrián Zámečník},pdflang={en-US}} \urlstyle{same} \setlength{\emergencystretch}{1em} \let\BolzanoBibliography\thebibliography \renewcommand{\thebibliography}[1]{\BolzanoBibliography{#1}\raggedright} \begin{document} \maketitle \begin{abstract} Wagner asked whether Gaussian kernel density estimation in $\mathbb R^d$ admits query time $\widetilde O(d+\eps^{-2})$ without dependence on the diameter of the data. We answer this affirmatively for each fixed query: a randomized data structure answers a query to additive error $\eps$ with probability $1-\delta$ in time $O((d+\eps^{-2})\log(d+1)\log(2/\delta))$, independently of the number of data points and of their diameter. The key ingredient is a variance bound for a Fastfood-type structured Fourier block that holds uniformly in the norm of the displacement. \end{abstract} \section{Introduction} \subsection{Background and the source problem} For a nonempty finite dataset $X\subset\R^d$ and bandwidth $\sigma>0$, the Gaussian kernel mean at a query $y$ is \[ K_X(y)=\frac1{|X|}\sum_{x\in X}k_\sigma(x,y), \qquad k_\sigma(x,y)=\exp(-\|x-y\|_2^2/\sigma^2). \] The computational problem is to preprocess $X$ so that this mean can be approximated without scanning the dataset at each query. Dense random Fourier features~\cite{rahimirecht2007} separate the dependence on $|X|$ from the query: store the average feature vector of the data, then take its inner product with the feature vector of $y$. For constant success probability, $O(\eps^{-2})$ independent bounded features suffice for additive error $\eps$. Evaluating their dense projections, however, costs $O(d\eps^{-2})$. The desired improvement is to replace this product by a sum, up to logarithmic factors. Wagner~\cite[Def.~1.1]{wagner2026} formulates the guarantee for each fixed query, with probability over the randomized preprocessing. If data and queries lie in a region of diameter $\Delta$, write $\Delta_\sigma=\Delta/\sigma$. His Table~1 compares the classical RFF bound with $\wtO(d+\eps^{-4})$ from fast dimension reduction followed by RFF~\cite[Thm.~E.2 and Cor.~E.3]{backurs2024}, and with $\wtO(d+\Delta_\sigma^2\eps^{-2})$ from Fastfood-type features~\cite{lss2013}. Wagner's fast spherical embedding gives $\wtO(d+\eps\Delta_\sigma^2+\eps^{-3})$ \cite[Thms.~1.2--1.3]{wagner2026}. The discussion then asks the following question. The section number in its heading refers to the arXiv preprint; the same question appears in Section~6 of the published ICML version. \begin{question}[Wagner, Section~7] \label{question:source} Is a Gaussian KDE query-time bound $\wtO(d+\eps^{-2})$ possible with only polylogarithmic, or no, dependence on the effective diameter $\Delta_\sigma$? More generally, what is the optimal trade-off between $\eps$ and $\Delta_\sigma$? \end{question} Theorem~\ref{thm:main} gives an affirmative answer to the existence question with no diameter dependence. It uses the pointwise quantifiers of Wagner's Definition~1.1: $y$ is fixed independently of the preprocessing randomness. The theorem is not an optimality lower bound for all possible data structures, and it does not settle the stronger problem of simultaneous accuracy throughout a query domain. \subsection{Main results} The main statements are as follows. \begin{enumerate}[label=(\arabic*)] \item Theorem~\ref{thm:main} gives query time $O((d+\eps^{-2})\log(d+1)\log(2/\delta))$ and storage $O((d+\eps^{-2})\log(2/\delta))$, independently of $|X|$ and diameter. Preprocessing costs $|X|$ times the feature-evaluation bound. \item Proposition~\ref{prop:block} bounds the variance of one structured Fourier block by $5/D$ for every fixed displacement, regardless of its norm. Lemma~\ref{lem:kdelift} transfers this estimate to an arbitrary dataset. \item Proposition~\ref{prop:badz} gives a one-block witness explaining why the sign-cancellation argument cannot be made uniform by choosing a displacement after the signs are revealed. \end{enumerate} The computation model charges constant cost for real arithmetic and trigonometric evaluation, as specified in Section~\ref{sec:main}. No finite-precision bit-complexity or empirical speedup claim is made. \subsection{Why the diameter disappears} The fast map shares randomness among many features. Let $D$ be the next power of two at least $d$, let $H$ be the normalized Walsh--Hadamard matrix, and let $G$ and $B$ be independent diagonal matrices with independent standard Gaussian and Rademacher entries, respectively. After padding a displacement to $z\in\R^D$, use \[ W=\sqrt D\,HGH B, \qquad Y(z)=\frac1D\sum_{i=1}^D\cos((Wz)_i). \] Two fast Hadamard transforms evaluate an entire block in $O(D\log(D+1))$ time. Each row is marginally standard Gaussian, so $Y(z)$ is unbiased for $e^{-\|z\|_2^2/2}$. The difficulty is that these rows are correlated: their number alone does not guarantee a variance reduction by $D$. The useful cancellation occurs before taking a supremum over displacements. Index coordinates by $\mathbb F_2^{\log_2 D}$. Conditional on $B$, rows separated by $\ell$ have projection covariance \[ \rho_\ell=\sum_r b_rb_{r+\ell}z_rz_{r+\ell}. \] Their cosine covariance is $e^{-\|z\|_2^2}(\cosh\rho_\ell-1)$. Bounding its growth in isolation loses the decay of the Gaussian kernel at large distances. Keeping that decay, Lemma~\ref{lem:damping} gives \[ e^{-\|z\|_2^2}(\cosh\rho_\ell-1) \le \frac{2\rho_\ell^2}{(1+\|z\|_2^2)^2}. \] The exact identity $\E_B\sum_{\ell\ne0}\rho_\ell^2 =2(\|z\|_2^4-\|z\|_4^4)$ now cancels the potentially large norm factor. The resulting $5/D$ bound holds for every fixed $z$, with a constant independent of its length. Minkowski's inequality lifts it to the data average even though all data points use the same map. Independent blocks give constant success probability, and independent median copies reduce the failure probability to $\delta$. \subsection{Related work and the scope of the improvement} \paragraph{Fast kernel summation.} In low dimension, the fast Gauss transform of Greengard and Strain~\cite{greengard1991} evaluates Gaussian sums by series expansions, with cost growing exponentially in $d$. In high dimension, hashing-based estimators of Charikar and Siminelakis~\cite{charikar2017} and their refinements~\cite{ckns2020} give multiplicative approximations with query time sublinear in $|X|$ that depends on a lower bound on the density. The present problem asks instead for additive error with query time independent of $|X|$, the regime of random Fourier features~\cite{rahimirecht2007}. Fast structured projections built from randomized Hadamard transforms originate in the fast Johnson--Lindenstrauss transform of Ailon and Chazelle~\cite{ailon2009}. \paragraph{Fast structured Fourier features.} The matrix above is a permutation-free Fastfood block without the additional radial scaling. Fastfood already supplies marginal Gaussianity, unbiasedness, fast evaluation and the conditional $\cosh$ covariance calculation~\cite[Lem.~3 and Thms.~4--5]{lss2013}. For its usual block, which also contains a random permutation, the published variance bound has a remainder $C(\alpha)/n$ for $n$ frequencies at normalized distance $\alpha$, where \[ C(\alpha)=6\alpha^4(e^{-\alpha^2}+\alpha^2/3). \] Its growth as $\alpha\to\infty$ does not give the diameter-free conclusion. The expanded Fastfood manuscript retains this remainder and also gives a concentration bound proportional to the displacement length \cite[Thm.~9, Cor.~10, and Thm.~11]{lss2014}. The contribution here is the norm-uniform completion using damping and the exact signed autocorrelation identity, rather than a new general Fourier-feature architecture. The broader structured-matrix framework of Choromanski and Sindhwani includes Fastfood and circulant or Toeplitz-like maps; its Theorems~4.1--4.2 are stated for bounded inputs and involve coherence and structural parameters~\cite{choromanski2016}. \paragraph{Orthogonal features.} Orthogonal random features reduce Gaussian-kernel estimation error through dependence of a different kind~\cite{orf2016}. Their scaled Haar construction and its variance analysis should be distinguished from the fast triple-Hadamard construction SORF. For SORF, Theorem~3 of \cite{orf2016} bounds bias by $6\alpha/\sqrt d$ and the accompanying discussion leaves tight variance and concentration guarantees open. Choromanski, Rowland, and Weller analyze structured orthogonal embeddings for dimensionality reduction and the angular kernel~\cite{rom2017}. Further RBF variance comparisons include a Gaussian improvement for each fixed displacement length in sufficiently high dimension \cite[Cor.~3.4]{geometry2018}. These results explain important benefits of orthogonality but do not supply the all-norm variance estimate for the nonorthogonal Gaussian block used here. Radial scaling also matters: Demni and Kadri compute a Bessel-kernel expectation for Haar orthogonal features without Gaussian radial scaling~\cite[Thm.~2]{demnikadri2024}; that model is distinct from the unbiased Gaussian features used here. \paragraph{A signed-circulant variance claim.} Feng, Hu, and Liao state an independent-feature variance formula for signed circulant projections~\cite[Thm.~2, Eq.~(12)]{feng2015}. The following explicit calculation shows why that formula cannot substitute for the variance proof below. Let $d\ge2$, let $C$ be a circulant matrix generated by independent $N(0,\tau^2)$ entries, set $P=\diag(s_1,\ldots,s_d)C$, and take $v=(t/\sqrt d)\mathbf1$ with $t,\tau>0$. All coordinates of $Cv$ equal one Gaussian variable $Z$ of variance $\nu^2=t^2\tau^2$. Since cosine is even, \[ \frac1d\sum_{j=1}^d\cos((Pv)_j)=\cos Z, \qquad \Var(\cos Z)=\frac12(1-e^{-\nu^2})^2. \] There is no factor $1/d$. The zero covariance of the signed projections does not make them independent: their joint distribution is a mixture of Gaussian pairs. This counterexample concerns exactly the cosine estimator in Theorem~2; the random-phase feature map in that paper's Eq.~(9) is a separately defined estimator. \paragraph{Coresets and query quantifiers.} Uniform approximation by a small data subset is a different objective. Phillips and Tai obtain $O(\eps^{-2})$-size KDE coresets independent of dimension and diameter~\cite{phillipstai2018}. Direct evaluation on such a subset still takes $O(d\eps^{-2})$ time. For fixed $d>1$, Tai obtains size $O_d(\eps^{-1})$~\cite{tai2022}; the hidden dependence on dimension does not yield the high-dimensional bound sought here. Recent work on query-oblivious softmax-attention coresets likewise uses a simultaneous query guarantee and a different normalized kernel sum \cite{cohen2026}. In contrast, the present preprocessing supports each independently fixed query, and a fixed batch of $s$ queries by replacing the amplification factor with $O(\log(2s/\delta))$. A query chosen after inspecting the random map is outside that guarantee. \section{The pointwise KDE theorem} \label{sec:main} \begin{theorem}[Pointwise Gaussian KDE without diameter dependence] \label{thm:main} Let $d\ge1$, let $\varnothing\ne X\subset\R^d$ be finite, let $\sigma>0$, and let \[ k_\sigma(x,y)=\exp\left(-\frac{\|x-y\|_2^2}{\sigma^2}\right). \] For every $0<\eps<1$ and $0<\delta<1$, there is a randomized KDE data structure such that, for every fixed query $y\in\R^d$, \[ \Prb\left[ \left| \frac1{|X|}\sum_{x\in X}k_\sigma(x,y)-\widetilde E(y) \right|<\eps \right]> 1-\delta. \] Its query time is \[ O\bigl((d+\eps^{-2})\log(D+1)\log(2/\delta)\bigr), \] where $D$ is the next power of two at least $d$. It uses $O((d+\eps^{-2})\log(2/\delta))$ stored real numbers. In particular the query time is $\wtO(d+\eps^{-2})$ and has no dependence on the effective diameter $\Delta_\sigma$. Its preprocessing time is \[ O\bigl(|X|(d+\eps^{-2})\log(D+1)\log(2/\delta)\bigr). \] \end{theorem} The theorem is proved in Sections~\ref{sec:block} and~\ref{sec:kde}. Padding vectors by zeros allows us to work in $\R^D$, where $D=2^m$ and $d\le D<2d$ for $d\ge1$. The query-time bound counts ordinary arithmetic operations and evaluations of sine and cosine. As in standard random-feature KDE structures, the data structure stores the empirical feature mean. \section{A fast Gaussian block} \label{sec:block} Let $H$ be the normalized $D\times D$ Walsh--Hadamard matrix. Index rows and columns by the group $\mathbb F_2^m$, so \[ H_{ij}=D^{-1/2}\chi_i(j),\qquad \chi_i(j)=(-1)^{i\cdot j}. \] Let $B=\diag(b_r)$, where the $b_r$ are independent random signs, and let $G=\diag(g_j)$, where the $g_j$ are independent standard Gaussian random variables. All variables in $B$ and $G$ are mutually independent. Define \[ W=\sqrt D\,HGH B. \] For a fixed displacement $z\in\R^D$, define the one-block estimator \[ Y(z)=\frac1D\sum_{i\in\mathbb F_2^m}\cos((Wz)_i). \] The goal of this section is to prove \[ \E Y(z)=e^{-\|z\|_2^2/2},\qquad \Var(Y(z))\le \frac{5}{D}. \] \begin{lemma}[Row marginals] \label{lem:row} For every row index $i$, conditional on $B$, the $i$th row $w_i$ of $W$ is distributed as $N(0,I_D)$. \end{lemma} \begin{proof} Let $h_j^T$ denote the $j$th row of $H$. The vectors $h_j^T B$ form an orthonormal basis, because $H$ is orthogonal and $B$ is diagonal with signs. The $i$th row of $W$ is \[ w_i^T=\sqrt D\,e_i^T H G H B =\sum_{j\in\mathbb F_2^m}\chi_i(j)\,g_j\,h_j^T B. \] This is a Gaussian linear combination of an orthonormal basis with independent $N(0,1)$ coefficients, up to deterministic signs. Hence $w_i\sim N(0,I_D)$ conditional on $B$. \end{proof} \begin{lemma}[Walsh covariance parameters] \label{lem:rho} Fix $z\in\R^D$, set $t=\|z\|_2$, and put $a=HBz$. For $R_i=(Wz)_i$, conditional on $B$ the vector $R=(R_i)_i$ is centered Gaussian, $\Var(R_i\mid B)=t^2$, and for $i\ne k$, \[ \operatorname{Cov}(R_i,R_k\mid B)=\rho_{i+k}, \] where \[ \rho_\ell=\sum_{r\in\mathbb F_2^m} b_r b_{r+\ell}z_r z_{r+\ell}. \] For $\ell=0$ this formula gives $\rho_0=t^2$. \end{lemma} \begin{proof} Since $a=HBz$, \[ R_i=\sqrt D\sum_j H_{ij}g_j a_j. \] Thus \[ \operatorname{Cov}(R_i,R_k\mid B) =D\sum_j H_{ij}H_{kj}a_j^2. \] For $i=k$ this is $\sum_j a_j^2=\|z\|_2^2$, because $HB$ is orthogonal. For $i\ne k$, write $\ell=i+k$ in $\mathbb F_2^m$. Expanding $a_j=D^{-1/2}\sum_r\chi_j(r)b_rz_r$ gives \[ \begin{aligned} D\sum_j H_{ij}H_{kj}a_j^2 &=\sum_j \chi_{i+k}(j)a_j^2 \\ &=D^{-1}\sum_{r,s} b_rb_sz_rz_s \sum_j\chi_j(\ell+r+s). \end{aligned} \] Walsh orthogonality makes the inner sum equal to $D$ exactly when $s=r+\ell$ and zero otherwise. The displayed formula follows. \end{proof} \begin{lemma}[Cosine covariance identity] \label{lem:coscov} For centered jointly Gaussian random variables $U,V$ with common variance $t^2$ and covariance $\rho$, \[ \operatorname{Cov}(\cos U,\cos V)=e^{-t^2}(\cosh\rho-1). \] Consequently, \[ \Var(Y(z)) = \frac{(1-e^{-t^2})^2}{2D} +\frac{e^{-t^2}}{D}\, \E_B\sum_{\ell\ne0}(\cosh\rho_\ell-1). \] \end{lemma} \begin{proof} The identity $\cos u\cos v=(\cos(u+v)+\cos(u-v))/2$ and the formula $\E\cos Z=e^{-\Var(Z)/2}$ for centered Gaussian $Z$ give \[ \E[\cos U\cos V] =\frac12 e^{-(2t^2+2\rho)/2} +\frac12 e^{-(2t^2-2\rho)/2} =e^{-t^2}\cosh\rho. \] Also $\E\cos U=\E\cos V=e^{-t^2/2}$, proving the covariance identity. Condition on $B$ and apply the identity to the Gaussian vector $R=(Wz)_i$. For each fixed $\ell$, exactly $D$ ordered pairs $(i,k)$ satisfy $i+k=\ell$. Therefore \[ \Var_G(Y(z)\mid B) =\frac{e^{-t^2}}{D}\sum_\ell(\cosh\rho_\ell-1). \] The conditional mean is $e^{-t^2/2}$ by Lemma~\ref{lem:row}, independent of $B$, so the law of total variance introduces no additional term. The $\ell=0$ term is \[ \frac{e^{-t^2}}{D}(\cosh t^2-1) =\frac{(1-e^{-t^2})^2}{2D}, \] which gives the formula. \end{proof} \begin{lemma}[Signed autocorrelation moment] \label{lem:second} For fixed $z\in\R^D$ and $t=\|z\|_2$, \[ |\rho_\ell|\le t^2\quad\text{for every }\ell, \] and \[ \E_B\sum_{\ell\ne0}\rho_\ell^2 =2(t^4-\|z\|_4^4)\le 2t^4. \] \end{lemma} \begin{proof} The deterministic bound follows from Cauchy--Schwarz: \[ |\rho_\ell| \le \sum_r |z_r||z_{r+\ell}| \le \left(\sum_r z_r^2\right)^{1/2} \left(\sum_r z_{r+\ell}^2\right)^{1/2} =t^2. \] For $\ell\ne0$, expand \[ \rho_\ell^2 = \sum_{r,s}z_rz_{r+\ell}z_sz_{s+\ell} b_rb_{r+\ell}b_sb_{s+\ell}. \] The expectation over independent signs is nonzero exactly when the unordered pairs $\{r,r+\ell\}$ and $\{s,s+\ell\}$ coincide, which happens for $s=r$ or $s=r+\ell$. Thus \[ \E_B\rho_\ell^2=2\sum_r z_r^2z_{r+\ell}^2. \] Summing over nonzero $\ell$ gives \[ \E_B\sum_{\ell\ne0}\rho_\ell^2 =2\sum_r z_r^2\sum_{\ell\ne0}z_{r+\ell}^2 =2\sum_r z_r^2(t^2-z_r^2) =2(t^4-\|z\|_4^4). \] \end{proof} \begin{lemma}[Gaussian damping] \label{lem:damping} For every $a\ge0$ and every real $u$ with $|u|\le a$, \[ e^{-a}(\cosh u-1)\le \frac{2u^2}{(1+a)^2}. \] \end{lemma} \begin{proof} The case $a=0$ is immediate. Assume $a>0$. The identity \[ \cosh s-1=s^2\int_0^1(1-r)\cosh(rs)\,dr \] shows that $(\cosh s-1)/s^2$ is nondecreasing for $s>0$. Hence, for $|u|\le a$, \[ \cosh u-1\le u^2\frac{\cosh a-1}{a^2}. \] Multiplying by $e^{-a}$ and using \[ e^{-a}(\cosh a-1)=\frac{(1-e^{-a})^2}{2} \] gives \[ e^{-a}(\cosh u-1) \le \frac{u^2}{2}\left(\frac{1-e^{-a}}{a}\right)^2. \] If $01-\delta$, as required by the strict inequality in the source definition. For one block, computing $Wu_y=\sqrt D\,HGHBu_y$ uses two fast Walsh--Hadamard transforms and diagonal multiplications, for time $O(D\log D)$. The trigonometric evaluations and inner-product contribution cost $O(D)$. Since \[ qD\le D+20\eps^{-2} \] and $D<2d$ for $d\ge1$, one constant-success copy has query time \[ O\bigl((d+\eps^{-2})\log(D+1)\bigr). \] Median amplification multiplies this by $O(\log(2/\delta))$. The concatenated feature mean and the random diagonal entries require $O((d+\eps^{-2})\log(2/\delta))$ stored real numbers. Computing and accumulating these features for every point of $X$ takes \[ O\bigl(|X|(d+\eps^{-2})\log(D+1)\log(2/\delta)\bigr) \] preprocessing time. The construction and proof never use a diameter bound on the data or query region, so no $\Delta_\sigma$ dependence appears. \end{proof} \begin{corollary}[Fixed finite query batches] Let $y_1,\ldots,y_s$ be fixed independently of the preprocessing randomness. Running the data structure with per-query failure probability $\delta/s$ answers all $s$ queries correctly with probability at least $1-\delta$, with per-query time multiplied only by the factor $O(\log(2s/\delta))$ in the median step. \end{corollary} \begin{proof} Apply Theorem~\ref{thm:main} to each fixed $y_j$ with failure probability $\delta/s$ and take a union bound. \end{proof} \section{Why the statement is pointwise} \label{sec:uniform} The proof above uses cancellation in the random signs $B$ for each fixed displacement $z$ before the preprocessing randomness is sampled. It does not imply that a single realized block has small variance uniformly over all possible directions. The following calculation makes the distinction explicit. \begin{proposition}[A one-block nonuniformity witness] \label{prop:badz} Fix a realization of the sign matrix $B$ in one Fastfood block, leaving $G$ random. For any $t>0$, define $z\in\R^D$ by \[ z_r=t\,b_r/\sqrt D. \] Then $\|z\|_2=t$, every nonzero signed autocorrelation satisfies $\rho_\ell=t^2$, and \[ Y(z)=\cos(tg_0), \] where $g_0$ is the Gaussian diagonal entry indexed by the trivial Walsh character. \end{proposition} \begin{proof} The norm identity is immediate. For $\ell\ne0$, \[ \rho_\ell = \sum_r b_rb_{r+\ell} \left(t b_r/\sqrt D\right) \left(t b_{r+\ell}/\sqrt D\right) = t^2. \] Also $Bz=(t/\sqrt D)\mathbf 1$, so $HBz=te_0$, where $e_0$ is the coordinate of the trivial Walsh character. Therefore \[ Wz=\sqrt D\,HG(te_0)=\sqrt D\,t g_0 H e_0=tg_0\mathbf 1, \] and every cosine summand equals $\cos(tg_0)$. In particular, \[ \Var_G(Y(z))=\frac12\left(1-e^{-t^2}\right)^2, \] which is bounded away from zero for fixed $t>0$ independently of $D$. \end{proof} Thus the theorem should not be read as a uniform guarantee over a continuum of queries after the randomness is fixed, nor as an adaptive guarantee for queries chosen after inspecting the random structure or as a function of earlier answers. This matches the pointwise quantifiers in \cite[Def.~1.1]{wagner2026}. Proposition~\ref{prop:badz} concerns one realized block only. It is not a lower bound for the average of independent blocks or for the median-amplified data structure in Theorem~\ref{thm:main}; it only shows that the signed autocorrelation cancellation cannot be upgraded to a uniform one-block claim. \begin{thebibliography}{99} \bibitem{wagner2026} Tal Wagner. \newblock New bounds for kernel sums via fast spherical embeddings. \newblock In \emph{Proceedings of the 43rd International Conference on Machine Learning}, PMLR 306:124205--124223, 2026. \newblock \href{https://proceedings.mlr.press/v306/wagner26a.html}{Published version}. The open question is in Section~6; references to Section~7 use the preprint. \newblock \href{https://arxiv.org/abs/2605.01263}{arXiv:2605.01263v1 [cs.DS]}, 2 May 2026. \bibitem{backurs2024} Arturs Backurs, Zinan Lin, Sepideh Mahabadi, Sandeep Silwal, and Jakub Tarnawski. \newblock Efficiently computing similarities to private datasets. \newblock In \emph{The Twelfth International Conference on Learning Representations}, 2024. \newblock \href{https://openreview.net/forum?id=HMe5CJv9dQ} {OpenReview:HMe5CJv9dQ}. \bibitem{rahimirecht2007} Ali Rahimi and Benjamin Recht. \newblock Random features for large-scale kernel machines. \newblock In \emph{Advances in Neural Information Processing Systems}, volume 20, pages 1177--1184, 2007. \newblock \href{https://proceedings.neurips.cc/paper_files/paper/2007/hash/013a006f03dbc5392effeb8f18fda755-Abstract.html} {NeurIPS proceedings record}. \bibitem{greengard1991} L.~Greengard and J.~Strain. \newblock The fast {G}auss transform. \newblock \emph{SIAM J. Sci. Stat. Comput.}, 12(1):79--94, 1991. \newblock \url{https://doi.org/10.1137/0912004}. \bibitem{charikar2017} M.~Charikar and P.~Siminelakis. \newblock Hashing-based-estimators for kernel density in high dimensions. \newblock In \emph{Proc. 58th IEEE Symposium on Foundations of Computer Science (FOCS)}, 1032--1043, 2017. \newblock \url{https://doi.org/10.1109/FOCS.2017.99}. \bibitem{ckns2020} M.~Charikar, M.~Kapralov, N.~Nouri, and P.~Siminelakis. \newblock Kernel density estimation through density constrained near neighbor search. \newblock In \emph{Proc. 61st IEEE Symposium on Foundations of Computer Science (FOCS)}, 172--183, 2020. \newblock \url{https://doi.org/10.1109/FOCS46700.2020.00025}. \bibitem{ailon2009} N.~Ailon and B.~Chazelle. \newblock The fast {J}ohnson--{L}indenstrauss transform and approximate nearest neighbors. \newblock \emph{SIAM J. Comput.}, 39(1):302--322, 2009. \newblock \url{https://doi.org/10.1137/060673096}. \bibitem{lss2013} Quoc V. Le, Tam\'as Sarl\'os, and Alexander J. Smola. \newblock Fastfood---computing Hilbert space expansions in loglinear time. \newblock In \emph{Proceedings of the 30th International Conference on Machine Learning}, PMLR 28(3):244--252, 2013. \newblock \href{https://proceedings.mlr.press/v28/le13.html}{PMLR:v28/le13}. \bibitem{feng2015} Chang Feng, Qinghua Hu, and Shizhong Liao. \newblock Random feature mapping with signed circulant matrix projection. \newblock In \emph{Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence}, pp.~3490--3496, 2015. \newblock \href{https://www.ijcai.org/Abstract/15/491}{IJCAI proceedings record}. \bibitem{choromanski2016} Krzysztof Choromanski and Vikas Sindhwani. \newblock Recycling randomness with structure for sublinear time kernel expansions. \newblock In \emph{Proceedings of the 33rd International Conference on Machine Learning}, PMLR 48:2502--2510, 2016. \newblock \href{https://proceedings.mlr.press/v48/choromanski16.html} {PMLR:v48/choromanski16}. \bibitem{lss2014} Quoc Viet Le, Tam\'as Sarl\'os, and Alexander J. Smola. \newblock Fastfood: approximate kernel expansions in loglinear time. \newblock Expanded version, \href{https://arxiv.org/abs/1408.3060v1}{arXiv:1408.3060v1}, 2014. \bibitem{demnikadri2024} Nizar Demni and Hachem Kadri. \newblock Orthogonal random features: explicit forms and sharp inequalities. \newblock \emph{Transactions on Machine Learning Research}, September 2024. \newblock \href{https://openreview.net/forum?id=FMtRZ4xzSi}{OpenReview:FMtRZ4xzSi}. \bibitem{orf2016} Felix Xinnan Yu, Ananda Theertha Suresh, Krzysztof Choromanski, Daniel Holtmann-Rice, and Sanjiv Kumar. \newblock Orthogonal random features. \newblock In \emph{Advances in Neural Information Processing Systems}, volume 29, 2016. \newblock \href{https://proceedings.neurips.cc/paper/2016/hash/53adaf494dc89ef7196d73636eb2451b-Abstract.html}{NeurIPS proceedings record}. \bibitem{rom2017} Krzysztof Choromanski, Mark Rowland, and Adrian Weller. \newblock The unreasonable effectiveness of structured random orthogonal embeddings. \newblock In \emph{Advances in Neural Information Processing Systems}, volume 30, 2017. \newblock \href{https://papers.nips.cc/paper_files/paper/2017/hash/bf8229696f7a3bb4700cfddef19fa23f-Abstract.html}{NeurIPS proceedings record}. \bibitem{geometry2018} Krzysztof Choromanski, Mark Rowland, Tam\'as Sarl\'os, Vikas Sindhwani, Richard E. Turner, and Adrian Weller. \newblock The geometry of random features. \newblock In \emph{Proceedings of the 21st International Conference on Artificial Intelligence and Statistics}, PMLR 84:1--9, 2018. \newblock \href{https://proceedings.mlr.press/v84/choromanski18a.html}{PMLR:v84/choromanski18a}. \bibitem{phillipstai2018} Jeff M. Phillips and Wai Ming Tai. \newblock Improved coresets for kernel density estimates. \newblock In \emph{Proceedings of the 29th Annual ACM--SIAM Symposium on Discrete Algorithms}, pages 2718--2727, 2018. \newblock \href{https://doi.org/10.1137/1.9781611975031.173}{doi:10.1137/1.9781611975031.173}. \bibitem{tai2022} Wai Ming Tai. \newblock Optimal coreset for Gaussian kernel density estimation. \newblock In \emph{38th International Symposium on Computational Geometry}, LIPIcs 224, pages 63:1--63:15, 2022. \newblock \href{https://doi.org/10.4230/LIPIcs.SoCG.2022.63}{doi:10.4230/LIPIcs.SoCG.2022.63}. \bibitem{cohen2026} Ofek I. Cohen. \newblock Query-oblivious coresets for softmax attention: improved bounds and efficient constructions. \newblock \href{https://arxiv.org/abs/2609.06327v2}{arXiv:2609.06327v2}, 13 September 2026. \end{thebibliography} \end{document}