Nonuniform fast fourier transforms

For $E=\mathrm{\varnothing }$ all three values are stipulated as zero. If $E$ is nonempty finite, enumerate its elements and induct on the number of entries. A one-entry list of real moduli has a maximum; given a maximum for the first $n$ entries, compare it with the $(n+1)$st modulus using [F2] and [F4] and keep the larger. Induction [F5] constructs the maximum of the finite modulus list. The finite sum formulas in [F1] are well-defined.

Every term $\mathrm{\mid }{z}_e{\mathrm{\mid }}^2$ is nonnegative by [F2], so the finite sum in the Euclidean norm is nonnegative; [F3] supplies its unique nonnegative square root. Thus all three displayed values are defined, including the separately stipulated empty-array case.

First prove Cauchy–Schwarz for these arrays. If $y=0$, its inner product with $x$ is zero. If $y\mathrm{\ne }0$, choose $e_0$ with $y_{e_0}\mathrm{\ne }0$; [F2]–[F3] give $\mathrm{\parallel }y{\mathrm{\parallel }}_2^2={\sum }_e\mathrm{\mid }{y}_e{\mathrm{\mid }}^2>0$. Put $a=⟨x,y{⟩}_E$ and $c=a\mathrm{/}\mathrm{\parallel }y{\mathrm{\parallel }}_2^2$. Expanding the finite sum using [F1] and conjugation laws gives $0\le \mathrm{\parallel }x-cy{\mathrm{\parallel }}_2^2=\mathrm{\parallel }x{\mathrm{\parallel }}_2^2-\frac{\mathrm{\mid }a{\mathrm{\mid }}^2}{\mathrm{\parallel }y{\mathrm{\parallel }}_2^2}\mathrm{.}$ Multiplying by the positive denominator yields $\mathrm{\mid }⟨x,y{⟩}_E{\mathrm{\mid }}^2\le \mathrm{\parallel }x{\mathrm{\parallel }}_2^2\mathrm{\parallel }y{\mathrm{\parallel }}_2^2$; all quantities are nonnegative, so [F4] gives $\mathrm{\mid }⟨x,y{⟩}_E\mathrm{\mid }\le \mathrm{\parallel }x{\mathrm{\parallel }}_2\mathrm{\parallel }y{\mathrm{\parallel }}_2$.

Expand the squared norm: $\mathrm{\parallel }x+y{\mathrm{\parallel }}_2^2=\mathrm{\parallel }x{\mathrm{\parallel }}_2^2+2\mathrm{Re}⟨x,y{⟩}_E+\mathrm{\parallel }y{\mathrm{\parallel }}_2^2\le (\mathrm{\parallel }x{\mathrm{\parallel }}_2+\mathrm{\parallel }y{\mathrm{\parallel }}_2{)}^2,$ where the inequality follows from step 1.1 and $\mathrm{Re}z\le \mathrm{\mid }z\mathrm{\mid }$, itself immediate from $\mathrm{\mid }a+ib{\mathrm{\mid }}^2=a^2+b^2\ge a^2$ and [F4]. Both sides before squaring are nonnegative, so [F4] gives the stated triangle inequality.

Fix $j<N$ and $k\in \mathcal{K}$, and put $t=2\pi k\cdot x_j\in \mathbb{R}$. By [F1]–[F2], $e^{-it}=\cos (-t)+i\sin (-t)=\cos t-i\sin t$. Applying [F3] gives $\overline{e^{-it}}=\cos t+i\sin t=e^{it}$. Thus $(A^{\ast }{)}_{jk}=\overline{A_{kj}}=e^{+2\pi ik\cdot x_j}$.

For any $c\in {\mathbb{C}}^N$ and $f\in {\mathbb{C}}^{\mathcal{K}}$, expand the finite sums: $⟨Ac,f{⟩}_{\mathcal{K}}={\sum }_{k\in \mathcal{K}}{\sum }_{j<N}{c}_j{e}^{-2\pi ik\cdot x_j}\overline{f_k}={\sum }_{j<N}{c}_j\overline{{\sum }_{k\in \mathcal{K}}{f}_k{e}^{+2\pi ik\cdot x_j}}=⟨c,A^{\ast }f{⟩}_{\{j<N\}}\mathrm{.}$ The first equality uses finite distributivity/reordering from [F4]; the second uses step 1.1 and the stated inner-product convention. Thus the type-2 sum is exactly the conjugate-transpose action under matching finite inner products.

Put $\alpha =\pi \mathrm{/}\tau >0$ using [F5] and $\tau >0$, and set $q=\exp (-\alpha )\in (0,1)$ by [F4]. Fix $R>0$ and choose an integer $n_0>R+1$ by [F2]. For $\mathrm{\mid }x\mathrm{\mid }\le R$ and $\mathrm{\mid }n\mathrm{\mid }\ge n_0$, one has $\mathrm{\mid }x+n\mathrm{\mid }\ge \mathrm{\mid }n\mathrm{\mid }-R>1$, hence $(x+n{)}^2\ge (\mathrm{\mid }n\mathrm{\mid }-R{)}^2\ge \mathrm{\mid }n\mathrm{\mid }-R$. Since $\exp$ is increasing, the $n$th nonnegative summand is at most $\exp (-\alpha (\mathrm{\mid }n\mathrm{\mid }-R))=\exp (\alpha R)q^{\mathrm{\mid }n\mathrm{\mid }}$ by [F6]. The two-sided geometric tail is finite and tends to zero uniformly in $x\in [-R,R]$ as its starting index tends to infinity, by [F3]. This proves absolute and uniform convergence on every compact interval.

Each finite partial sum is continuous by [F1] and [F4]. Fix $x_0\in \mathbb{R}$ and $\epsilon >0$, choose $R>\mathrm{\mid }{x}_0\mathrm{\mid }+1$, and choose a partial-sum index for which the uniform tail on $[-R,R]$ is below $\epsilon \mathrm{/}3$ by step 1.1. Continuity of that finite partial sum at $x_0$ gives a neighborhood where its change is below $\epsilon \mathrm{/}3$; the two tail values contribute less than $2\epsilon \mathrm{/}3$. Thus the full sum is continuous at $x_0$. Absolute convergence permits the reindexing $m=n+1$ in ${\varphi }_{\tau }(x+1)={\sum }_n\exp (-\alpha (x+1+n{)}^2)$, giving ${\varphi }_{\tau }(x+1)={\varphi }_{\tau }(x)$. Since $x_0$ was arbitrary, the sum is continuous and one-periodic.

Let $q=\exp (-\pi L\mathrm{/}\tau )\in (0,1)$ by [F2]–[F3]. For positive omitted indices write $n=L+h$ with $h\ge 1$. Since $0\le x\le 1$, $(x+n{)}^2\ge n^2=(L+h{)}^2\ge L^2+Lh$, so their sum is at most $\exp (-\pi L^2\mathrm{/}\tau ){\sum }_{h\ge 1}{q}^h$. By [F4] this is at most $\exp (-\pi L^2\mathrm{/}\tau )\mathrm{/}(1-q)$.

For negative omitted indices write $n=-(L+1+h)$ with $h\ge 0$. Then $\mathrm{\mid }x+n\mathrm{\mid }=L+1+h-x\ge L+h$, and $(L+h{)}^2\ge L^2+Lh$. Their sum is at most $\exp (-\pi L^2\mathrm{/}\tau ){\sum }_{h\ge 0}{q}^h=\exp (-\pi L^2\mathrm{/}\tau )\mathrm{/}(1-q)$ by [F4].

The two omitted tails are nonnegative and exhaust the indices outside $[-L,L]$. Adding steps 1.1 and 1.2 gives the claimed remainder $R_{\tau ,L}$; [F3] also proves its denominator is positive.

Let $h_{\tau }(u)=\exp (-\pi u^2\mathrm{/}\tau )$. By [F4], induction on derivative order gives $h_{\tau }^{(q)}(u)=P_q(u)\exp (-\pi u^2\mathrm{/}\tau )$ for a polynomial $P_q$. For every $m,q$, the quantity $\mathrm{\mid }u{\mathrm{\mid }}^m\mathrm{\mid }{P}_q(u)\mathrm{\mid }\exp (-\pi u^2\mathrm{/}\tau )$ tends to zero as $\mathrm{\mid }u\mathrm{\mid }\to \mathrm{\infty }$: bound the polynomial by a finite sum of powers, set $z=u^2$, and apply [F5] with $a=\pi \mathrm{/}\tau >0$ by [F7]. On a compact interval it is bounded by continuity. Thus every seminorm in [F3] is finite and $h_{\tau }\in \mathcal{S}(\mathbb{R})$.

Apply [F1] to $h_{\tau }$ from step 1.1. By [F2] with $t=1\mathrm{/}\tau$, its Fourier transform at integer $r$ is $\sqrt{\tau }\exp (-\pi \tau r^2)$. The left periodization is ${\varphi }_{\tau }$ by [F6], so [F1] gives the displayed Fourier series, its coefficient formula, and both convergence assertions.

Fix one coordinate, write $M=M_r$, $\tau ={\tau }_r$, $w=w_r$, $a=\pi \mathrm{/}(\tau M^2)>0$ by [F6], and $y=M{x}_r$. Reindexing the finite grid index and period index by $m=\mathrm{\ell }+nM$ gives ${\sum }_{\mathrm{\ell }=0}^{M-1}{\varphi }_{\tau }(\mathrm{\ell }\mathrm{/}M-x_r)={\sum }_{m\in \mathbb{Z}}\exp (-a(m-y{)}^2)\mathrm{.}$ For every integer $s\ge 0$, at most two integers satisfy $s\le \mathrm{\mid }m-y\mathrm{\mid }<s+1$. Their terms are at most $\exp (-a{s}^2)$; for $s\ge 1$, $s^2\ge s$. Thus the sum is at most $2{\sum }_{s=0}^{\mathrm{\infty }}\exp (-as)=2\mathrm{/}(1-\exp (-a))=S_r$ by [F2].

If $\mathrm{\ell }\mathrm{\notin }{W}_r(x_r)$, then every $m=\mathrm{\ell }+nM$ satisfies $\mathrm{\mid }m-y\mathrm{\mid }>w$. On either side of $y$, the lattice distances form a unit-spaced sequence $d+n$ with $d>w$. The first term is at most $\exp (-a{w}^2)$. For each later term, monotonicity of $f_a$ gives $f_a(d+n)\le {\int }_{d+n-1}^{d+n}{f}_a(t)dt$. For $R>w$, [F3]–[F4] give ${\int }_w^R{f}_a(t)dt\le \frac{1}{w}{\int }_w^{R}t{f}_a(t)dt=\frac{\exp (-a{w}^2)-\exp (-a{R}^2)}{2aw}\le \frac{\exp (-a{w}^2)}{2aw}\mathrm{.}$ By [F5], the last subtracted term tends to zero as $R\to \mathrm{\infty }$. Taking limits of the finite tail sums, which converge by [F1], bounds each side by $\exp (-a{w}^2)(1+1\mathrm{/}(2aw))$. Both sides together yield ${\sum }_{\mathrm{\ell }\mathrm{\notin }{W}_r(x_r)}{\varphi }_{\tau }(\mathrm{\ell }\mathrm{/}M-x_r)\le T_r$.

The complement of the product set $W(x)$ is the union of the $d$ sets where at least one coordinate index is outside its $W_r(x_r)$. Since all kernel terms are nonnegative, the total omitted product mass is at most the sum of the $d$ coordinate-tail product sums. Each such finite product factors into the one-coordinate tail in step 1.2 and the full-coordinate masses in step 1.1; hence it is at most $T_r{\prod }_{s\mathrm{\ne }r}{S}_s$. Summing over $r$ gives $T_d$.

Substitute [F1] into each factor of ${\mathrm{\Phi }}_{\tau }$ and then into ${\tilde{g}}_k$. Absolute uniform convergence in [F1] permits interchanging the finite grid/source sums with the absolutely convergent Fourier series. For an integer $m_r$, the coordinate root sum is $\frac{1}{M_r}{\sum }_{{\mathrm{\ell }}_r=0}^{M_r-1}{e}^{2\pi i(m_r-k_r){\mathrm{\ell }}_r\mathrm{/}{M}_r}=\{\begin{array}{ll}1,& m_r-k_r\in M_r\mathbb{Z},\\ 0,& m_r-k_r\mathrm{\notin }{M}_r\mathbb{Z}\mathrm{.}\end{array}$ Indeed, in the first case every term is $1$; in the second, $z=e^{2\pi i(m_r-k_r)\mathrm{/}{M}_r}\mathrm{\ne }1$ by [F3] while $z^{M_r}=1$, so the finite geometric sum is $(1-z^{M_r})\mathrm{/}(1-z)=0$. Thus only $m_r=k_r+q_r{M}_r$ remain in each coordinate, giving the displayed exact alias identity.

The $q=0$ term of that identity is $\widehat{\mathrm{\Phi }}(k)F_k$ by [F1]–[F2]. Each factor $\sqrt{{\tau }_r}\exp (-\pi {\tau }_r{k}_r^2)$ is positive by [F6], so division by $\widehat{\mathrm{\Phi }}(k)$ is valid. For each $q$, its coefficient ratio is $\frac{\widehat{\mathrm{\Phi }}(k+q\odot M)}{\widehat{\mathrm{\Phi }}(k)}={\prod }_r\exp \text{\hspace{0.17em}⁣}(-\pi {\tau }_r((k_r+q_r{M}_r{)}^2-k_r^2))\mathrm{.}$ Separating $q=0$ proves the deconvolution identity.

Since $M_r>2K_r$, ${\tau }_r>0$ and $\pi >0$ by [F6], the exponent parameter ${\lambda }_r=\pi {\tau }_r{M}_r(M_r-2K_r)$ is positive. Positivity and strict monotonicity of $\exp$ in [F6] imply $0<s_r=e^{-{\lambda }_r}<1$. Fix one coordinate $r$. If $q_r=\pm h$ with integer $h\ge 1$ and $\mathrm{\mid }{k}_r\mathrm{\mid }\le K_r$, then $(k_r+q_r{M}_r{)}^2-k_r^2=q_r^2{M}_r^2+2q_r{M}_r{k}_r\ge h^2{M}_r^2-2h{M}_r{K}_r\ge h{M}_r(M_r-2K_r)>0.$ Hence the absolute alias multiplier for that coordinate is at most $s_r^h$. By [F5] its sum over nonzero $q_r$ is at most $2s_r\mathrm{/}(1-s_r)$, so the sum over all coordinate multi-indices other than zero is at most the product of the coordinate sums including their unit terms, minus the all-zero term, namely $A$. The unit-modulus fact [F4], multiplicativity, and the triangle inequality in [F7] bound each source phase sum by ${\sum }_j\mathrm{\mid }{c}_j\mathrm{\mid }$. This gives the asserted alias bound.