Exact three-dimensional spline assignment aliases and FFT normalization

Define $V_1={\mathbf{1}}_{[0,1]}$ and recursively $V_P(u)={\int }_0^1{V}_{P-1}(u-s)ds$, so $V_P=V_{P-1}\ast {\mathbf{1}}_{[0,1]}$ by the convolution definition [F1]. For $P=2$, the integral is the length of $[0,1]\cap [u-1,u]$, giving $u$ on $[0,1]$, $2-u$ on $[1,2]$, and zero outside; this is the truncated-power formula. For $P\ge 3$, integrate the formula for $V_{P-1}$ term by term; reindexing the second sum and applying Pascal's identity gives the stated formula for $W_P$. Thus $V_P=W_P$ for all $P\ge 2$. The recursion gives nonnegativity and support in $[0,P]$. The formula gives $W_P(0)=0$, and its value at $P$ is the $P$th finite difference of the degree-$(P-1)$ polynomial $u^{P-1}$, hence is zero; therefore the zero extension is continuous at both support endpoints. Differentiating the formula on each polynomial interval and applying Pascal's identity gives $W_P^{\mathrm{\prime }}(u)=W_{P-1}(u)-W_{P-1}(u-1)$; for $P=2$ this identity holds on open intervals, with the one-sided values at integers.

From the transform factor, for $n_r\mathrm{\ne }0$ and $u_r=k_r\mathrm{/}{M}_r$, $\mathrm{\mid }{D}_r(k_r+n_r{M}_r)\mathrm{/}{D}_r(k_r)\mathrm{\mid }=\mathrm{\mid }{u}_r\mathrm{/}(u_r+n_r){\mathrm{\mid }}^P$. The phase factors have modulus one; if $u_r=0$, every shifted sinc numerator vanishes. Since $\mathrm{\mid }{u}_r\mathrm{\mid }<1\mathrm{/}2$, $\mathrm{\mid }{u}_r+n\mathrm{\mid }\ge (1-\mathrm{\mid }{u}_r\mathrm{\mid })\mathrm{\mid }n\mathrm{\mid }$. Summing over positive and negative $n$ and applying [F3] gives the total bound for $a_r$. For real $J\ge 1$ put $L=\lfloor J\rfloor \ge 1$. Since $x^{-P}$ decreases, $n^{-P}\le {\int }_{n-1}^n{x}^{-P}dx$ for each integer $n>L$. Summing and taking the limit gives ${\sum }_{n>J}{n}^{-P}\le {\int }_L^{\mathrm{\infty }}{x}^{-P}dx=L^{1-P}\mathrm{/}(P-1)$, proving the stated finite remainder, including noninteger thresholds. The tensor product has total nonzero alias mass $A_k={\prod }_r(1+a_r)-1$.

From step 1.1, $W_P$ is the convolution of $P$ copies of ${\mathbf{1}}_{[0,1]}$. Fubini [F7] factors its Fourier integral as ${\widehat{W}}_P(\omega )=({\int }_0^1{e}^{-i\omega s}ds{)}^P$. For $\omega \mathrm{\ne }0$, the sine and cosine primitives from [F6] give ${\int }_0^1{e}^{-i\omega s}ds=e^{-i\omega \mathrm{/}2}\mathrm{sinc}(\omega \mathrm{/}2)$; at $\omega =0$ the integral is $1$. Therefore ${\widehat{W}}_P(\omega )=e^{-iP\omega \mathrm{/}2}\mathrm{sinc}(\omega \mathrm{/}2{)}^P$ and $\int W_P=1$. The same primitive gives ${\int }_0^1{e}^{2\pi imv}dv=1$ for $m=0$ and $0$ for nonzero integers $m$.

For $P=2$, write $W_2(a-\mathrm{\ell })={\int }_0^1{W}_1(a-\mathrm{\ell }-s)ds$ and interchange the nonnegative sum and integral by [F4]. Except at finitely many $s$ for which $a-s$ is an integer, exactly one integer $\mathrm{\ell }$ has $a-\mathrm{\ell }-s\in [0,1]$; the exceptional set has integral zero, so ${\sum }_{\mathrm{\ell }\in \mathbb{Z}}{W}_2(a-\mathrm{\ell })=1$. For $P>2$, use $W_P(x)={\int }_0^1{W}_{P-1}(x-s)ds$ and Tonelli [F4]; the inductive identity for $P-1$ makes the sum inside the integral equal to $1$. Thus ${\sum }_{\mathrm{\ell }\in \mathbb{Z}}{W}_P(a-\mathrm{\ell })=1$ for every $P\ge 2$.

For one coordinate, set $\theta =2\pi k\mathrm{/}M$ and $H(a)=e^{i\theta a}{\sum }_{\mathrm{\ell }\in \mathbb{Z}}{W}_P(a-\mathrm{\ell })e^{-i\theta \mathrm{\ell }}$. The sum is locally finite and continuous, and reindexing shows $H(a+1)=H(a)$. Only finitely many $\mathrm{\ell }$ contribute on $[0,1]$. Substitution $s=a-\mathrm{\ell }$ and partition of $\mathbb{R}$ into $[-\mathrm{\ell },1-\mathrm{\ell }]$ give its $m$th Fourier coefficient as ${\int }_{\mathbb{R}}{W}_P(s)e^{-i(2\pi m-\theta )s}ds={\widehat{W}}_P(2\pi m-\theta )$, using step 2.1. For $\mathrm{\mid }k\mathrm{\mid }<M\mathrm{/}2$, these coefficients are $O((1+\mathrm{\mid }m\mathrm{\mid }{)}^{-P})$, hence absolutely summable by [F3]. Their Fourier series converges uniformly by [F5] to a continuous function with the same coefficients as $H$.

In one coordinate, summing the periodic residue weights over $\mathrm{\ell }=0,\dots ,M_r-1$ is the same as summing $W_P(M_r{t}_r-L)$ over all integers $L=\mathrm{\ell }+j{M}_r$; by step 2.2 this sum is $1$. Taking the product over the three coordinates gives ${\sum }_{\mathrm{\ell }\in \mathcal{G}}{w}_{\mathrm{\ell }}(t)=1$. Therefore ${\sum }_{\mathrm{\ell }}{g}_{\mathrm{\ell }}={\sum }_i{q}_i{\sum }_{\mathrm{\ell }}{w}_{\mathrm{\ell }}(t_i)={\sum }_i{q}_i=0$ for neutral data.

Let $h$ be the difference between $H$ and the uniform Fourier sum in step 3.1. Every Fourier coefficient of $h$ is zero. For $J\ge 1$, define $K_J(v)=J^{-1}\mathrm{\mid }{\sum }_{r=0}^{J-1}{e}^{2\pi irv}{\mathrm{\mid }}^2$. It is a finite nonnegative trigonometric polynomial with integral $1$ by step 2.1; the vanishing coefficients of $h$ therefore give $K_J\ast h=0$. Given $\epsilon >0$, uniform continuity of $h$ gives $\delta \in (0,1\mathrm{/}2)$ such that $\mathrm{\mid }h(a-v)-h(a)\mathrm{\mid }<\epsilon$ when $v$ is within $\delta$ of an integer. Away from those points, the geometric-sum formula gives $K_J(v)\le [J{\sin }^2(\pi \delta ){]}^{-1}$. Hence $\mathrm{\parallel }{K}_J\ast h-h{\mathrm{\parallel }}_{\mathrm{\infty }}\le \epsilon +2\mathrm{\parallel }h{\mathrm{\parallel }}_{\mathrm{\infty }}\mathrm{/}(J{\sin }^2(\pi \delta ))$. Letting $J\to \mathrm{\infty }$ and then $\epsilon \downarrow 0$ yields $h=0$. Thus the series in step 3.1 equals $H$.

Multiply the identity $H(a)={\sum }_m{\widehat{W}}_P(2\pi m-\theta )e^{2\pi ima}$ established by steps 3.1 and 4.1 by $e^{-i\theta a}$, put $a=Mt$, and reindex $n=-m$. Since $W_P$ is real, ${\widehat{W}}_P(-\omega )=\overline{{\widehat{W}}_P(\omega )}$; step 2.1 then gives ${\sum }_{\mathrm{\ell }\in \mathbb{Z}}{W}_P(Mt-\mathrm{\ell })e^{-2\pi ik\mathrm{\ell }\mathrm{/}M}={\sum }_{n\in \mathbb{Z}}\overline{D_r(k+nM)}{e}^{-2\pi i(k+nM)t}$. In the finite-grid periodic sum, each index $\mathrm{\ell }+jM$ has the same phase as residue $\mathrm{\ell }$, since $e^{-2\pi ikj}=1$. Thus the identity holds for the periodized assignment weights.

Apply step 5.1 in each of the three coordinates and multiply the absolutely convergent series. Dividing by $\overline{D(k)}={\prod }_r\overline{D_r(k_r)}$ yields $b_k(t)={\sum }_{n\in {\mathbb{Z}}^3}{r}_{k,n}{e}^{-2\pi i(k+n\odot M)\cdot t}$. By [F2], $\sqrt{N_g}{\widehat{g}}_M(k)={\sum }_i{q}_i{\sum }_{\mathrm{\ell }}{w}_{\mathrm{\ell }}(t_i)e^{-2\pi ik\cdot \mathrm{\ell }\mathrm{/}M}$. Substitute the single-particle identity, divide by $\overline{D(k)}$, and interchange the absolutely convergent alias series with the finite particle sum. This gives $z_k={\sum }_n{r}_{k,n}{\rho }_{k+n\odot M}$ with exactly the stated $\sqrt{N_g}$ factor and no cell-volume factor.

Since $\mathrm{\mid }{a}_k(t)\mathrm{\mid }=1$, the identity for $b_k$ gives $\mathrm{\mid }{b}_k-a_k\mathrm{\mid }\le A_k$ and $\mathrm{\mid }{b}_k\mathrm{\mid }\le 1+A_k$. Also $\mathrm{\mid }{\rho }_j\mathrm{\mid }\le {\sum }_i\mathrm{\mid }{q}_i\mathrm{\mid }=Q$ for every $j$, so the exact identity for $z_k$ gives $\mathrm{\mid }{z}_k-{\rho }_k\mathrm{\mid }\le Q{A}_k$. These are the asserted source-assignment alias bounds.