claimroutine

Exact resampling identity with permutations retained

Exact factorization

P_sF_s=2^{2\alpha^2}B_0P_tF_tA

with contractions

concrete maps whose approximations are built next

Claim·§8.1 The one-dimensional interface·inside lemOne-dimensional resampling without sorting

Statement (paper)

With

A=\mathsf S'=\mathsf S/2

and

B_0=\mathsf D'\mathsf J'C

, where

\mathsf D'=2^{-(2\alpha^2-2)}\mathsf D

and

\mathsf J'=N^{-1}/2

, the maps

A:\mathbb C^s\to\mathbb C^t

and

B_0:\mathbb C^t\to\mathbb C^s

are linear contractions satisfying

B_0P_tF_tA=2^{-2\alpha^2}P_sF_s

, that is,

P_sF_s=2^{2\alpha^2}B_0P_tF_tA

In plain English

Taking

A=\mathsf S/2

and

B_0=\mathsf D'\mathsf J'C

with

\mathsf D'=2^{-(2\alpha^2-2)}\mathsf D

and

\mathsf J'=N^{-1}/2

gives linear contractions

A:\mathbb C^s\to\mathbb C^t

and

B_0:\mathbb C^t\to\mathbb C^s

with

B_0P_tF_tA=2^{-2\alpha^2}P_sF_s

, equivalently

P_sF_s=2^{2\alpha^2}B_0P_tF_tA

Why it's here

This fixes the concrete factorization of the permuted length-

s

transform through the permuted length-

t

transform that the lemma asserts. The rescalings by

1/2

and

2^{-(2\alpha^2-2)}

make both maps contractions while leaving only the clean factor

2^{-2\alpha^2}

. The later claims then only need to build ordered numerical approximations of these specific maps and bound their errors.}

Classified routine:

A rescaling of the Gaussian resampling identity of Harvey–van der Hoeven ('Integer multiplication in time O(n log n)', 2021), in which the length-s DFT factors through the length-t DFT via the resampling map S, deconvolution D and permutation-related maps. Here the identity is only conjugated by permutations and normalized so that both factors are contractions.

Uses

Nothing else in the paper

Used by

claimOrdered approximations with error and time bounds

Sources

PaperOpen

Section: §8.1 The one-dimensional interface
Page: —
Label: —
Line: sections/07-resampling.tex:82

Leannot aligned

Phase 2 aligns this node to a Lean declaration.