when $\sigma\leq\tfrac{1}{2}$. Thus, we have shown that for any $(i,j)\in S$,
we have

$\lvert X(i,j)-\bar{X}(i,j)\rvert\leq\sigma^{4}/\pi.$ (D.27)

Next, we argue that the cardinality $\lvert S\rvert$ is sufficiently large. We
will do this by bounding the size of $S^{\mathsf{c}}$. We have by inequalities
for $\ell^{p}$ norms and D.97 and D.98

$\frac{1}{\sqrt{2}}\left\lVert\begin{bmatrix}i\\\
j\end{bmatrix}\right\rVert_{2}\leq\left\lVert\bm{\tau}_{\nu
ij}\right\rVert_{\infty}\leq\left\lVert\begin{bmatrix}i\\\
j\end{bmatrix}\right\rVert_{2},$

so if we define

$\displaystyle S^{\prime}$ $\displaystyle=\left\\{(i,j)\in
G\nonscript\>\middle|\allowbreak\nonscript\>\mathopen{}\left\lvert\left\lVert\begin{bmatrix}i\\\
j\end{bmatrix}\right\rVert_{2}-\alpha\right\rvert\leq\sqrt{24\sigma^{2}\log(1/\sigma)}\right\\},$

we have $S^{\mathsf{c}}\subset S^{\prime}$. The square $[-1,1]$ is covered by
the union of balls of radius $\sqrt{2}/(n-1)$ centered at each point of the
grid $G$. Consider the subset

$U=\left\\{(u,v)\in[-1,1]\nonscript\>\middle|\allowbreak\nonscript\>\mathopen{}\left\lvert\sqrt{u^{2}+v^{2}}-\alpha\right\rvert\leq\frac{\sqrt{2}}{n-1}+\sqrt{24\sigma^{2}\log(1/\sigma)}\right\\}.$

Then by the triangle inequality and the above covering reasoning,
$S^{\prime}+\\{(u,v)\in\mathbb{R}^{2}\nonscript\>|\allowbreak\nonscript\>\mathopen{}\sqrt{u^{2}+v^{2}}\leq\sqrt{2}/(n-1)\\}\subset
U$, from which it follows by a volume bound

$\lvert
S^{\mathsf{c}}\rvert\pi\left(\frac{\sqrt{2}}{n-1}\right)^{2}\leq\operatorname{Vol}(U).$

Because $U$ is an annulus, we calculate readily

$\operatorname{Vol}(U)=4\alpha\left(\frac{\sqrt{2}}{n-1}+\sqrt{24\sigma^{2}\log(1/\sigma)}\right),$

whence

$\lvert
S^{\mathsf{c}}\rvert\leq\frac{2n}{\pi}+\frac{n^{2}\sqrt{48\sigma^{2}\log(1/\sigma)}}{\pi},$

where the last inequality worst-cases over our condition on $\alpha$.

Now, to conclude, we have by the above

$\displaystyle\left\lVert\bar{\bm{X}}-\bm{X}\right\rVert_{\mathrm{F}}^{2}$
$\displaystyle=\sum_{(i,j)\in
S}\left((\bar{\bm{X}})_{ij}-(\bm{X}\circ\bm{\tau}_{\nu})_{ij}\right)^{2}+\sum_{(i,j)\in
S^{\mathsf{c}}}\left((\bar{\bm{X}})_{ij}-(\bm{X}\circ\bm{\tau}_{\nu})_{ij}\right)^{2}$
$\displaystyle\leq\frac{n^{2}\sigma^{8}}{\pi^{2}}+\lvert
S^{\mathsf{c}}\rvert\sup_{(i,j)\in
G}\left((\bar{\bm{X}})_{ij}-(\bm{X}\circ\bm{\tau}_{\nu})_{ij}\right)^{2}$
$\displaystyle\leq\frac{n^{2}\sigma^{8}}{\pi^{2}}+\frac{2n}{\pi}+\frac{n^{2}\sqrt{48\sigma^{2}\log(1/\sigma)}}{\pi},$

because both matrices have entries in $[0,1]$.

∎

######  Lemma D.5.

For $\nu=\pi/4$, consider the “directly sampled” infinite-resolution template

$(\bar{\bm{X}})_{ij}={\mathds{1}}_{\lVert(\bm{\tau}_{\nu})_{ij}\rVert_{\infty}\leq\alpha},$
(D.28)

where we recall D.97 and D.98. Then one has

$\left\lVert\bar{\bm{X}}\right\rVert_{\mathrm{F}}\geq n^{2}\alpha^{2}-5n.$

###### Proof.

Consider the case $\nu=\pi/4$. By rotational symmetry of $\bar{\bm{X}}$ by
multiples of $\pi/2$, and discarding the sum over the central axes when $n$ is
odd, we have

$\displaystyle\left\lVert\bar{\bm{X}}\right\rVert_{\mathrm{F}}^{2}$
$\displaystyle=\sum_{(i,j)\in G}{\mathds{1}}_{\max\\{\lvert i+j\rvert,\lvert
i-j\rvert\\}\leq\sqrt{2}\alpha}$
$\displaystyle=\sum_{i=0}^{n-1}\sum_{j=0}^{n-1}{\mathds{1}}_{\max\\{\lvert
i-(n-1-j)\rvert,\lvert i-j\rvert\\}\leq(n-1)\alpha/\sqrt{2}}$
$\displaystyle\geq
4\sum_{i=0}^{\lfloor\tfrac{n-1}{2}\rfloor}\sum_{j=0}^{\lfloor\tfrac{n-1}{2}\rfloor}{\mathds{1}}_{\lvert
i-(n-1-j)\rvert\leq(n-1)\alpha/\sqrt{2}}.$

So, by the integral test estimate (because the summand is monotone increasing
as a function of both $i$ and $j$ when the other is fixed) and nonnegativity,

$\displaystyle\left\lVert\bar{\bm{X}}\right\rVert_{\mathrm{F}}^{2}$
$\displaystyle\geq
4\int_{0}^{\lfloor\tfrac{n-1}{2}\rfloor}\int_{0}^{\lfloor\tfrac{n-1}{2}\rfloor}{\mathds{1}}_{\lvert
i-(n-1-j)\rvert\leq(n-1)\alpha/\sqrt{2}}\mathop{}\\!\mathrm{d}i\mathop{}\\!\mathrm{d}j$
$\displaystyle=4(n-1)^{2}\int_{0}^{\tfrac{1}{n-1}\lfloor\tfrac{n-1}{2}\rfloor}\int_{0}^{\tfrac{1}{n-1}\lfloor\tfrac{n-1}{2}\rfloor}{\mathds{1}}_{\lvert
i-(1-j)\rvert\leq\alpha/\sqrt{2}}\mathop{}\\!\mathrm{d}i\mathop{}\\!\mathrm{d}j$
$\displaystyle\geq
4(n-1)^{2}\int_{0}^{\tfrac{1}{2}-\tfrac{1}{n-1}}\int_{0}^{\tfrac{1}{2}-\tfrac{1}{n-1}}{\mathds{1}}_{\lvert
i-(1-j)\rvert\leq\alpha/\sqrt{2}}\mathop{}\\!\mathrm{d}i\mathop{}\\!\mathrm{d}j$
$\displaystyle\geq
4(n-1)^{2}\left(\int_{0}^{\tfrac{1}{2}}\int_{0}^{\tfrac{1}{2}}{\mathds{1}}_{\lvert
i-(1-j)\rvert\leq\alpha/\sqrt{2}}\mathop{}\\!\mathrm{d}i\mathop{}\\!\mathrm{d}j-2\int_{0}^{\tfrac{1}{2}}\int_{\tfrac{1}{2}-\tfrac{1}{n-1}}^{\tfrac{1}{2}}{\mathds{1}}_{\lvert
i-(1-j)\rvert\leq\alpha/\sqrt{2}}\mathop{}\\!\mathrm{d}i\mathop{}\\!\mathrm{d}j\right),$

where in the final inequality we used permutation symmetry of the integral as
a function of $(i,j)$ to simplify the residual. Now, the region of integration
in the first term in the last line of the previous expression is equivalent to
$\\{(i,j)\nonscript\>|\allowbreak\nonscript\>\mathopen{}(\tfrac{1}{2}-i)+(\tfrac{1}{2}-j)\leq\alpha/\sqrt{2}\\}$,
which defines a right triangle with two side lengths equal to
$\alpha/\sqrt{2}$. Because $\alpha<1/\sqrt{2}$, the integral evaluates to
$\alpha^{2}/4$. Meanwhile, the integral in the second term is no larger than
$1/2(n-1)$, because the integrand is bounded by $1$. Thus

$\left\lVert\bar{\bm{X}}\right\rVert_{\mathrm{F}}^{2}\geq(n-1)^{2}\alpha^{2}-4(n-1).$

Distributing in this expression and worst-casing slightly gives the claim.

∎

###  D.2 Proofs for Theorem 2

##### Problem setup (and continuum idealization).

Let $k\in\mathbb{N}$, and consider an observation
$\bm{X}\in\mathbb{R}^{m\times n}$ drawn from the class D.3, with rotation
parameter $\nu_{\natural}$ (so that
$(\bm{X})_{ij}=X_{\natural}\circ\bm{\tau}_{-\nu_{\natural}}(i,j)$ if $(i,j)\in
G$, following D.6). For $\bm{U}\in\mathbb{R}^{m\times k}$,
$\bm{V}\in\mathbb{R}^{n\times k}$, we study the optimization objective

$\mathcal{L}_{\mathrm{discrete}}(\nu,\bm{U},\bm{V})=\frac{1}{2}\left\lVert\bm{X}-\left(\bm{U}\bm{V}^{\ast}\right)\circ\bm{\tau}_{-\nu}\right\rVert_{\mathrm{F}}^{2},$
(D.29)

where here in the context of discrete images, the transformations
$\bm{\tau}_{-\nu}$ must be implemented with resampling (we give a brief
overview of this idea in Section D.4). The resampling operation can be chosen
to be continuously differentiable, making it amenable to gradient-based
optimization on the objective $\mathcal{L}_{\mathrm{discrete}}$, but it
introduces a host of discretization-based artifacts to the optimization
process that are challenging to treat.222In particular, note that for any
$\nu$, $\bm{M}\mapsto\bm{M}\circ\bm{\tau}_{\nu}$, as defined in Section D.4,
is a linear operator. If we call this operator $\mathcal{A}_{\nu}$, it can be
seen from Section D.4 that $\mathcal{A}_{\nu}^{\ast}\mathcal{A}_{\nu}$ is a
banded matrix, but it is not incoherent—this means that the analysis of the
problem D.29 requires tools other those developed to analyze matrix sensing
under the RIP (c.f. [60, 41]). The situation is further complicated by the
fact that the objective D.29 simultaneously learns the sensing matrix (in
matrix sensing parlance) and the low-rank factorization, a setting that has
not been considered in prior work. We will simplify the situation by
considering a continuum limit of the objective D.29, and a corresponding
continuum gradient-like iteration for its solution.

Consider operators $\bm{U}:\mathbb{R}^{k}\to L^{2}(\mathbb{R})$,
$\bm{V}:\mathbb{R}^{k}\to L^{2}(\mathbb{R})$. These operators can be thought
of as ‘matrices’, whose columns are $L^{2}(\mathbb{R})$ functions—note that in
the continuum, following D.5 we have

$X_{\natural}(s,t)=\underbrace{{\mathds{1}}_{\lvert
s\rvert\leq\alpha}}_{u_{\natural}(s)}\underbrace{{\mathds{1}}_{\lvert
t\rvert\leq\alpha}}_{v_{\natural}(t)},$

i.e., as an operator, $X_{\natural}=u_{\natural}v_{\natural}^{\ast}$. The
corresponding continuum analogue of the observation $\bm{X}$ is the deformed
template $X=X_{\natural}\circ\bm{\tau}_{-\nu_{\natural}}$. To mirror the
smoothing effect of a continuous interpolation kernel imposed in D.96, we
introduce an extra gaussian smoothing filter
$\varphi_{\sigma^{2}}(s,t)=(2\pi\sigma^{2})^{-1}e^{-(s^{2}+t^{2})/2\sigma^{2}}$
to the objective function, yielding the objective

$\mathcal{L}^{\sigma}(\nu,\bm{U},\bm{V})=\frac{1}{2}\left\lVert\varphi_{\sigma^{2}}\ast\left(X-\left(\bm{U}\bm{V}^{\ast}\right)\circ\bm{\tau}_{-\nu}\right)\right\rVert_{L^{2}}^{2}.$
(D.30)

Notice that, by its definition D.2, the map $f\mapsto f\circ\bm{\tau}_{-\nu}$
is a unitary transformation (apply the change of variables formula in the
integral defining the $L^{2}$ inner product). Using in addition the Lie group
structure of the rotation matrices D.2, we have that for any $f\in
L^{2}(\mathbb{R}^{2})$, any $\nu$ and any $\sigma^{2}$,

$\displaystyle(\varphi_{\sigma^{2}}\ast(f\circ\bm{\tau}_{\nu}))(\bm{x})$
$\displaystyle=\int_{\mathbb{R}^{2}}\varphi_{\sigma^{2}}(\bm{x}^{\prime})f(\bm{R}_{\nu}(\bm{x}-\bm{x}^{\prime}))\mathop{}\\!\mathrm{d}\bm{x}^{\prime}$
$\displaystyle=\int_{\mathbb{R}^{2}}\varphi_{\sigma^{2}}(\bm{R}_{-\nu}(\bm{x}^{\prime}))f(\bm{R}_{\nu}(\bm{x})-\bm{x}^{\prime})\mathop{}\\!\mathrm{d}\bm{x}^{\prime}$
$\displaystyle=\int_{\mathbb{R}^{2}}\varphi_{\sigma^{2}}(\bm{x}^{\prime})f(\bm{R}_{\nu}(\bm{x})-\bm{x}^{\prime})\mathop{}\\!\mathrm{d}\bm{x}^{\prime}$
$\displaystyle=(\varphi_{\sigma^{2}}\ast f)\circ\bm{\tau}_{\nu}(\bm{x})$
(D.31)

by the change of variables formula and rotational invariance of the gaussian
function. In words, rigid motions commute with gaussian smoothing. Applying
this result together with the unitary transformation property, we can write
our objective as

$\displaystyle\mathcal{L}^{\sigma}(\nu,\bm{U},\bm{V})$
$\displaystyle=\frac{1}{2}\left\lVert\varphi_{\sigma^{2}}\ast
X-(\varphi_{\sigma^{2}}\ast(\bm{U}\bm{V}^{\ast}))\circ\bm{\tau}_{-\nu}\right\rVert_{L^{2}}^{2}$
$\displaystyle=\frac{1}{2}\left\lVert(\varphi_{\sigma^{2}}\ast
X)\circ\bm{\tau}_{\nu}-\varphi_{\sigma^{2}}\ast(\bm{U}\bm{V}^{\ast})\right\rVert_{L^{2}}^{2}$
$\displaystyle=\frac{1}{2}\left\lVert\varphi_{\sigma^{2}}\ast\left(X_{\natural}\circ\bm{\tau}_{\nu-\nu_{\natural}}-\bm{U}\bm{V}^{\ast}\right)\right\rVert_{L^{2}}^{2}.$
(D.32)

We emphasize that D.32 and D.30 are equal, but D.32 is more straightforward to
differentiate.

##### Simplifications to D.32.

Our analysis will apply to a simplified version of the general objective D.32.
We discuss the simplifications we make here.

  1. 1.

Single-channel factorization ($k=1$). We analyze a critically-parameterized
version of the problem D.32, where $k=1$. This leads to the objective

$\mathcal{L}^{\sigma}(\nu,u,v)=\frac{1}{2}\left\lVert\varphi_{\sigma^{2}}\ast\left(X_{\natural}\circ\bm{\tau}_{\nu-\nu_{\natural}}-uv^{\ast}\right)\right\rVert_{L^{2}}^{2},$
(D.33)

where $u,v\in L^{2}(\mathbb{R})$. When the transformation component of D.33 is
omitted, this simplification is analogous to consideration of the rank-one
matrix factorization problem [41, §3]; because the untransformed square
template $X_{\natural}$ has “rank one” (in a suitable, generalized sense),
perfect reconstruction is still possible in our setting. Although the rank-one
case is a vast simplification over the problem D.32 with general $k$, we begin
our analysis here because the introduction of the simultaneous transformation
optimization component to D.33 represents a nontrivial complication with
respect to existing analyses (c.f. [50, 32]). We anticipate that the emerging
understanding of overparameterized matrix sensing will be useful in
generalizing our results to the setting of general $k$ [60, 35, 101, 99].

  2. 2.

Symmetric factorization. Because the square template $X_{\natural}$ is self-
adjoint as a Fredholm operator (in other words, the template satisfies
$X_{\natural}(s,t)=X_{\natural}(t,s)$), it is reasonable to reduce the search
space in D.33 to factorizations where $u=v$. This gives the problem

$\mathcal{L}^{\sigma}(\nu,u)=\frac{1}{2}\left\lVert\varphi_{\sigma^{2}}\ast\left(X_{\natural}\circ\bm{\tau}_{\nu-\nu_{\natural}}-uu^{\ast}\right)\right\rVert_{L^{2}}^{2}.$
(D.34)

All of our experiments with TILTED make use of general, asymmetric grid
factors, so a theoretical understanding of the general asymmetric case (when
the target template $X_{\natural}$ is asymmetric) remains crucial for future
work. In this connection, we note that theoretical analyses of asymmetric
matrix factorization typically add an additional “balancing” regularizer to
the objective D.32 (c.f. [41, 32, 50, 28])—in our experiments, the $2,1$
regularizer described in Section A.3 plays this role.

##### Gradient-like iterations for alignment and factorization.

Obtaining a gradient iteration for the objective D.32 can be done
straightforwardly with respect to the finite-dimensional $\nu$ variable:
making essential use of the duality on $L^{2}(\mathbb{R})$ and the fact that
the convolution of two gaussian functions is another gaussian function, with
variance equal to the sum of the factors’ variances, we calculate in Lemma D.7

$\displaystyle\nabla_{\nu}\mathcal{L}^{\sigma}(\nu,u)$
$\displaystyle=-\left\langle\varphi_{\sigma^{2}}\ast\left(uu^{\ast}\circ\bm{\tau}_{\nu_{\natural}-\nu}\right),\left\langle\nabla_{\bm{x}}[\varphi_{\sigma^{2}}\ast
X_{\natural}],\begin{bmatrix}0&-1\\\
1&0\end{bmatrix}(\,\cdot\,)\right\rangle_{\ell^{2}}\right\rangle_{L^{2}(\mathbb{R}^{2})}.$
(D.35)

Differentiation with respect to the $u$ factor in D.34 requires a slightly
more technical notion of gradient. To limit technicality in the analysis, we
study instead an infinite-dimensional analogue of a projected gradient descent
method, where after each update to the $u$ variable we project it onto the
“unit sphere” in $L^{2}(\mathbb{R})$ as $u\mapsto u/\lVert
u\rVert_{L^{2}(\mathbb{R})}$. Moreover, when performing factorization, we
optimize only the unsmoothed loss $\mathcal{L}^{0}(\nu,\,\cdot\,)$. We recall
in Lemma D.19 that in this setting, whenever the factorization target
$X_{\natural}\circ\bm{\tau}_{\nu-\nu_{\natural}}$ is not negative (as an
operator), it is equivalent in this setting to seek the largest positive
eigenvalue of the (symmetrized) operator corresponding to the factorization
target. Moreover, as long as the factorization target has no negative
eigenvalues of significant magnitude,333This is typically the case; see Lemma
D.1. Our proofs show that this structure persists throughout iterations of our
algorithm, as well, in order to guarantee that our algorithm succeeds. this
process is achieved by the power method, which in our setting produces
iterates

$u_{k+1}=\frac{\left(\mathcal{T}_{X_{\natural}\circ\bm{\tau}_{\nu-\nu_{\natural}}}+\mathcal{T}_{X_{\natural}\circ\bm{\tau}_{\nu-\nu_{\natural}}}^{\ast}\right)u_{k}}{\left\lVert\left(\mathcal{T}_{X_{\natural}\circ\bm{\tau}_{\nu-\nu_{\natural}}}+\mathcal{T}_{X_{\natural}\circ\bm{\tau}_{\nu-\nu_{\natural}}}^{\ast}\right)u_{k}\right\rVert_{L^{2}(\mathbb{R})}},$
(D.36)

before outputting an approximate factor for the target, which we will write as
$\mathsf{P}(k,u_{0},\nu)\in L^{2}(\mathbb{R})$ (specifying the dependence on
the power method’s initialization $u_{0}$ and the rotation $\nu$ applied to
the template):

$\mathsf{P}(k,u_{0},\nu)=\sqrt{\tfrac{1}{2}u_{k}^{\ast}(\mathcal{T}_{X_{\natural}\circ\bm{\tau}_{\nu-\nu_{\natural}}}+\mathcal{T}_{X_{\natural}\circ\bm{\tau}_{\nu-\nu_{\natural}}}^{\ast})u_{k}}u_{k}.$
(D.37)

A priori, this may return a complex-valued function; we will take care in our
analysis to show that this never occurs when the iteration count is set
appropriately.

##### Our algorithm.

The key mathematical property underlying the success of TILTED in practical
experiments is the fact that incremental improvements to representation
(factorization) help promote incremental improvements to alignment, and vice
versa. The algorithm we study theoretically is a simplified version of TILTED,
but nonetheless captures this complex interplay and sheds light on why it
succeeds in practice. The major simplification we impose is that rather than
jointly updating the $\nu$ (alignment) iterates and the $u$ (factorization)
iterates, we will update them individually in consecutive blocks, as in an
alternating minimization procedure. Our algorithm separates into five distinct
stages, described below.

###### Stage one: rough representation.

From a “flat” initialization for the scene

$u_{0}={\mathds{1}}_{[-1,+1]},$ (D.38)

we perform $T_{\mathrm{rough}}$ iterations of power method D.37, to generate a
roughly-localized representation of the template $X_{\natural}$:

$u_{\mathrm{rough}}=\mathsf{P}(T_{{\mathrm{rough}}},u_{0},0).$ (D.39)

This procedure corresponds to the initial iterations of TILTED in practical
experiments, where the uninformative initialization $u_{0}$ does not produce
sufficient gradients (in texture or geometry) for alignment to occur. The
roughly-localized output $u_{\mathrm{rough}}$ usefully ends up with both
texture and a rough shape profile that promotes subsequent alignment.

###### Stage two: rough alignment.

Given a step size $\beta$, we perform $T_{\nu}$ iterations of gradient descent
on the alignment objective with smoothing level $\sigma$, initialized
randomly:

$\nu_{0}\sim\operatorname{Unif}([0,2\pi]),$ (D.40)

and with the factorization iterate at the output of the previous rough
representation step:

$\displaystyle\nu_{k+1}$
$\displaystyle=\nu_{k}-\beta\nabla_{\nu}\mathcal{L}^{\sigma}(\nu_{k},u_{\mathrm{rough}}),\qquad
k=0,1,\dots,T_{\nu}-1.$ (D.41)

We write $\hat{\nu}=\nu_{T_{\nu}}$. The alignment problem in D.34 has multiple
optimal solutions, due to the symmetries of the alignment target
$X_{\natural}$—this means the optimization landscape is not globally convex.
At these initial iterations of the alignment procedure, with a non-informative
initialization, we rely on the presence of strong gradient in the objective
landscape to bring our initial iterate close to one of the several equivalent
optimal solutions. At a technical level, this style of analysis mirrors those
used in other global analyses of nonconvex optimization landscapes [50].

###### Stage three: refined representation.

This final stage of the algorithm takes advantage of the roughly-localized
alignment output from the previous stage to improve the representation quality
further—the initial roughly-localized template $u_{\mathrm{rough}}$ from the
first stage is better localized, and its edges sharpened to match those of the
target $X_{\natural}$. Accordingly, we run $T_{u}$ iterations of power method
D.37, started with the outputs of the previous stages:

$\hat{u}=\mathsf{P}(T_{u},u_{\mathrm{rough}},\hat{\nu}).$ (D.42)

The algorithm’s output is the pair $(\hat{\nu},\hat{u})$.

##### Main result.

Our main result establishes convergence of our alternating minimization
version of TILTED to the true parameters $(\nu_{\natural},u_{\natural})$, up
to symmetry, in a “hard” instance of the problem: where $\nu_{\natural}=\pi/4$
(as we studied in Section D.1) and $\alpha=\tfrac{1}{\sqrt{2}}$ (corresponding
to an ‘in focus’ target).

######  Theorem D.2.

Consider the iterations encompassed by D.39, D.41 and D.42, with
initializations D.38 and D.40. Suppose $\alpha=\tfrac{1}{\sqrt{2}}$ and
$\nu_{\natural}=\pi/4$. There are absolute constants $c_{1}$, $C_{1}$,
$C_{2}>0$ such that for any parameters $\sigma$, $\beta$ satisfying

$\displaystyle\sigma{}^{2}$ $\displaystyle\leq\tfrac{1}{10^{4}},$
$\displaystyle\beta$ $\displaystyle\leq c_{1},$

for any $0<\varepsilon\leq\tfrac{1}{768}$, if the iteration counts satisfy

$\displaystyle T_{\mathrm{rough}}$ $\displaystyle\geq-
C_{1}\log(\sigma^{2}\varepsilon),$ $\displaystyle T_{\nu}$
$\displaystyle\geq-\frac{C_{2}\log(3\varepsilon)}{\beta},$ $\displaystyle
T_{u}$ $\displaystyle\geq 16,$

then with probability over the random initialization of $\nu_{0}$ at least
$4/7$, one has

$\displaystyle\min\left\\{\lvert\hat{\nu}-\nu_{\natural}\rvert\mod\frac{\pi}{2},\frac{\pi}{2}-\left(\lvert\hat{\nu}-\nu_{\natural}\rvert\mod\frac{\pi}{2}\right)\right\\}$
$\displaystyle\leq 3\varepsilon,$
$\displaystyle\lVert\hat{u}-u_{\natural}\rVert_{L^{2}(\mathbb{R})}$
$\displaystyle\leq 31\sqrt{\varepsilon}.$

In particular, the template parameters are recovered up to symmetry.

###### Proof.

Following the alternating structure of the algorithm we study, the proof
separates into a distinct stage for each phase of the algorithm. For
concision, we will not carefully track the value of absolute constants in some
parts of the proof; expressions such as $c,c_{1},\dots$ and $C,C_{1},\dots$
will denote small (respectively, large) absolute constants whose value may
change from line to line unless otherwise noted. We will also use the
expression $f\lesssim g$ to denote the statement “there exists an absolute
constant $C>0$ such that $f\leq Cg$” for functions $f$, $g$, and analogously
for $f\gtrsim g$.

##### Rough factorization stage.

We will apply Lemma D.6 to the final iterate D.39, obtained via the power
method D.37; to this end, we need to check properties of the operator

$\frac{1}{2}\left(\mathcal{T}_{X_{\natural}\circ\bm{\tau}_{\pi/4}}+\mathcal{T}_{X_{\natural}\circ\bm{\tau}_{\pi/4}}^{\ast}\right)=\mathcal{T}_{X_{\natural}\circ\bm{\tau}_{\pi/4}}$

(the simplification uses symmetry properties of the $\pi/4$-rotated template),
and of the initialization D.38. Notice that by Lemma D.1, we have

$\left\lVert\mathcal{T}_{X_{\natural}\circ\bm{\tau}_{\pi/4}}\right\rVert=\lambda_{\max}\left(\mathcal{T}_{X_{\natural}\circ\bm{\tau}_{\pi/4}}\right)=\frac{4}{\pi},$

which we will denote as $\lambda_{1}$ (in the notation of Lemma D.6), and its
corresponding unit eigenvector is $v_{1}(s)=\cos(\pi s/2){\mathds{1}}_{\lvert
s\rvert\leq 1}$. Moreover, Lemma D.1 shows that the sequence of eigenvalue
magnitudes of this operator are a decreasing function of index $k$, and
therefore

$\left\lvert\frac{\lambda_{k}}{\lambda_{1}}\right\rvert\leq\frac{4}{3\pi}\cdot\frac{\pi}{4}=1-\frac{2}{3}.$

In addition, we calculate

$\langle
u_{0},v_{1}\rangle_{L^{2}(\mathbb{R})}=\langle{\mathds{1}}_{[-1,1]},\cos(\pi
s/2)\rangle_{L^{2}(\mathbb{R})}=\frac{4}{\pi},$

and evidently $\lVert u_{0}\rVert_{L^{2}(\mathbb{R})}=\sqrt{2}$. Applying the
second conclusion of Lemma D.6, we thus get

$\left\lVert
u_{\mathrm{rough}}-\frac{2}{\sqrt{\pi}}\cos(\tfrac{\pi}{2}(\,\cdot\,)){\mathds{1}}_{[-1,1]}\right\rVert_{L^{2}(\mathbb{R})}\leq\frac{\sqrt{\pi}}{3^{T_{{\mathrm{rough}}}-1}}$
(D.43)

as long as $T_{{\mathrm{rough}}}\geq 2$.

##### Alignment stage.

To establish progress by the iteration D.41, we combine a standard
optimization analysis under a lower bound on the magnitude of the gradient
with Lemma D.9, which gives a lower bound on the ‘nominal’ value of the
gradient, and a basic perturbation analysis that uses the control we have
established in the previous step between $u_{\mathrm{rough}}$ and its nominal
value.

First, by the fact that $T_{{\mathrm{rough}}}\geq 2$ and
$\sigma\leq\tfrac{1}{100}$, we can apply Lemma D.10. We perform a landscape
analysis of the loss $\mathcal{L}^{\sigma}(\,\cdot\,,u_{\mathrm{rough}})$,
where we relate it to properties of the ‘nominal loss’
$\mathcal{L}^{\sigma}(\,\cdot\,,\bar{u}_{\mathrm{rough}})$, to guarantee
progress of the gradient iteration D.41. The initialization
$\nu_{0}\sim\operatorname{Unif}([0,2\pi])$, and by Lemma D.9, we see that the
objective $\nu\mapsto\mathcal{L}^{\sigma}(\nu,u)$ (for any $\sigma$ and any
$u$) is $\pi/2$-periodic and has reflection symmetry about $\nu_{\natural}$ on
the interval $[\nu_{\natural}-\pi/4,\nu_{\natural}+\pi/4]$. This implies that
the landscape (and hence the behavior of the gradient descent iterates) is
determined for all $\nu$ by its behavior on the domain
$[\nu_{\natural}-\pi/4,\nu_{\natural}+\pi/4]$, and we can therefore assume
that $\nu_{0}\in[\nu_{\natural}-\pi/4,\nu_{\natural}+\pi/4]$; it then follows
by the uniform initialization that with probability at least
$(\pi/7)/(\pi/4)=4/7$, we have

$\lvert\nu_{0}-\nu_{\natural}\rvert\leq\pi/7.$

This means we can invoke the lower bound in Lemma D.9 to obtain that

$\displaystyle\operatorname{sign}(\nu_{0}-\nu_{\natural})\cdot\nabla_{\nu}\mathcal{L}^{\sigma}(\nu_{0},\bar{u}_{\mathrm{rough}})$
$\displaystyle\gtrsim\sin(\lvert\nu_{0}-\nu_{\natural}\rvert)$
$\displaystyle\gtrsim\lvert\nu_{0}-\nu_{\natural}\rvert,$

where the last inequality uses that $\sin x\geq(2/\pi)x$ when $0\leq
x\leq\pi/2$. Meanwhile, by the first estimate of the second assertion in Lemma
D.10 and D.43, this implies

$\displaystyle\operatorname{sign}(\nu_{0}-\nu_{\natural})\cdot\nabla_{\nu}\mathcal{L}^{\sigma}(\nu_{0},{u}_{\mathrm{rough}})$
$\displaystyle\gtrsim\lvert\nu_{0}-\nu_{\natural}\rvert-\frac{3^{-T_{{\mathrm{rough}}}}}{\sigma^{2}}.$
(D.44)

Next, using the upper bound in Lemma D.9, we have that for any $\nu$,

$\left\lvert\nabla_{\nu}\mathcal{L}^{\sigma}(\nu,\bar{u}_{\mathrm{rough}})\right\rvert\lesssim\left\lvert\nu-\nu_{\natural}\right\rvert.$

Combining this with the first estimate of the second assertion in Lemma D.10
and D.43, as above, we obtain

$\left\lvert\nabla_{\nu}\mathcal{L}^{\sigma}(\nu,u_{\mathrm{rough}})\right\rvert\lesssim\left\lvert\nu-\nu_{\natural}\right\rvert+\frac{3^{-T_{{\mathrm{rough}}}}}{\sigma^{2}}.$

In particular, choosing $\beta\leq c$ for an absolute constant $c\leq 1$ and
$T_{{\mathrm{rough}}}\gtrsim-\log(\sigma^{2}\varepsilon)$ for any
$\varepsilon>0$, we have

$\beta\left\lvert\nabla_{\nu}\mathcal{L}^{\sigma}(\nu,u_{\mathrm{rough}})\right\rvert\leq\left\lvert\nu-\nu_{\natural}\right\rvert+\varepsilon.$
(D.45)

Now, for $\gamma>0$, define the domains

$S_{\gamma}=\\{\nu\in\mathbb{R}\nonscript\>|\allowbreak\nonscript\>\mathopen{}\lvert\nu-\nu_{\natural}\rvert\geq\gamma\\}.$

Fix $0<\varepsilon<\pi/14$. We are going to argue that after $T_{\nu}$
iterations of D.41, the last iterate $\hat{\nu}$ satisfies $\hat{\nu}\in
S_{3\varepsilon}^{\mathsf{c}}$. We start by proving two invariants of the
sequence of iterates D.41. First, note that

$\displaystyle\lvert\nu_{k+1}-\nu_{\natural}\rvert$
$\displaystyle=\lvert\nu_{k}-\beta\nabla_{\nu}\mathcal{L}^{\sigma}(\nu_{k},u_{\mathrm{rough}})-\nu_{\natural}\rvert$
$\displaystyle\leq 2\lvert\nu_{k}-\nu_{\natural}\rvert+\varepsilon,$ (D.46)

by the triangle inequality and D.45. Next, suppose that for some $k$, we have
$\nu_{k}\in S_{\varepsilon}\cap S_{\pi/7}^{\mathsf{c}}$. By D.44, if
$T_{{\mathrm{rough}}}\gtrsim-\log(\sigma^{2}\varepsilon)$, we have from D.44
(via Lemma D.9)

$\operatorname{sign}(\nu_{k}-\nu_{\natural})\cdot\nabla_{\nu}\mathcal{L}^{\sigma}(\nu_{k},{u}_{\mathrm{rough}})\gtrsim\lvert\nu_{k}-\nu_{\natural}\rvert.$
(D.47)

Suppose first that $\nu_{k}-\nu_{\natural}\geq 0$. Then D.47 becomes

$\nabla_{\nu}\mathcal{L}^{\sigma}(\nu_{k},{u}_{\mathrm{rough}})\gtrsim\nu_{k}-\nu_{\natural}.$

In particular, the gradient at $\nu_{k}$ is nonnegative. This implies

$\displaystyle\nu_{k+1}-\nu_{\natural}$
$\displaystyle=\nu_{k}-\beta\nabla_{\nu}\mathcal{L}^{\sigma}(\nu_{k},u_{\mathrm{rough}})-\nu_{\natural}$
$\displaystyle\leq\left(1-c_{0}\beta\right)\left(\nu_{k}-\nu_{\natural}\right)$
$\displaystyle<\nu_{k}-\nu_{\natural},$

since $\beta\leq 1$, where $c_{0}>0$ is an absolute constant that we may
assume is no larger than $\tfrac{1}{2}$. We also have, by D.45, that

$\nu_{k+1}-\nu_{\natural}=\nu_{k}-\beta\nabla_{\nu}\mathcal{L}^{\sigma}(\nu_{k},u_{\mathrm{rough}})-\nu_{\natural}\geq-\varepsilon.$

But $\nu_{k}\in S_{\varepsilon}$, so
$\varepsilon\leq\lvert\nu_{k}-\nu_{\natural}\rvert$. We conclude

$\left\lvert\nu_{k+1}-\nu_{\natural}\right\rvert\leq\max\left\\{\varepsilon,\left(1-c_{0}\beta\right)\left\lvert\nu_{k}-\nu_{\natural}\right\rvert\right\\}\leq\left\lvert\nu_{k}-\nu_{\natural}\right\rvert,$
(D.48)

and a completely analogous argument implies the same conclusion in the case
where $\nu_{k}-\nu_{\natural}\leq 0$. As a consequence, suppose now that for
some $k$, we have $\nu_{k}\in S_{3\varepsilon}^{\mathsf{c}}$. If in fact
$\nu_{k}\in S_{\varepsilon}^{\mathsf{c}}$, we know immediately from D.46 that
$\nu_{k+1}\in S_{3\varepsilon}^{\mathsf{c}}$. On the other hand, if instead
$\nu_{k}\in S_{\varepsilon}\cap S_{3\varepsilon}^{\mathsf{c}}$, we have
immediately from D.48 that $\nu_{k+1}\in S_{3\varepsilon}^{\mathsf{c}}$. We
conclude the full non-escape invariant:

$\nu_{k}\in S_{3\varepsilon}^{\mathsf{c}}\implies\nu_{k+1}\in
S_{3\varepsilon}^{\mathsf{c}}.$ (D.49)

We can now give an inductive argument to obtain the desired convergence,
namely that

$\hat{\nu}\in S_{3\varepsilon}^{\mathsf{c}}.$

First, if $\nu_{0}\in S_{3\varepsilon}^{\mathsf{c}}$, we are done immediately,
by D.49. If not, then by the preceding parameter choices and assumption on the
initialization we have $\nu_{0}\in S_{3\varepsilon}\cap
S_{\pi/7}^{\mathsf{c}}$ and therefore $\nu_{0}\in S_{\varepsilon}\cap
S_{\pi/7}^{\mathsf{c}}$, so that by D.48, we obtain

$\nu_{1}\in
S_{\max\\{\varepsilon,(1-c_{0}\beta)\lvert\nu_{0}-\nu_{\natural}\rvert\\}}^{\mathsf{c}}.$

At this point, notice that by assumption
$(1-c_{0}\beta)\lvert\nu_{0}-\nu_{\natural}\rvert\geq\tfrac{3}{2}\varepsilon$,
so in fact

$\nu_{1}\in
S_{(1-c_{0}\beta)\lvert\nu_{0}-\nu_{\natural}\rvert}^{\mathsf{c}}.$

Proceeding inductively in this way, it follows that at iteration
$k\in\mathbb{N}$ we either have $\nu_{k}\in S_{3\varepsilon}^{\mathsf{c}}$ or
that $\nu_{k-1}\in S_{3\varepsilon}\cap S^{\mathsf{c}}_{\pi/7}$ and

$\nu_{k}\in
S_{(1-c_{0}\beta)\lvert\nu_{k-1}-\nu_{\natural}\rvert}^{\mathsf{c}}.$

Unraveling this recurrence gives

$\nu_{k}\in
S_{(1-c_{0}\beta)^{k}\lvert\nu_{0}-\nu_{\natural}\rvert}^{\mathsf{c}}.$

Thus, as soon as

$T_{\nu}\gtrsim\frac{\log(3\varepsilon)}{\log(1-c_{0}\beta)},$

we have $\hat{\nu}\in S_{3\varepsilon}^{\mathsf{c}}$, i.e. that

$\lvert\hat{\nu}-\nu_{\natural}\rvert\leq 3\varepsilon.$ (D.50)

##### Refined factorization stage.

In this stage, we run power method to refine the factorization
$u_{\mathrm{rough}}$, using the fact that $\hat{\nu}\approx\nu_{\natural}$ to
argue that the relevant operator for the refinement power method D.42 (c.f.
D.36 and D.37) is sufficiently close to $\mathcal{T}_{X_{\natural}}$ (a self-
adjoint operator, hence equal to its Hermitian part) that we can guarantee the
progress of the power method D.42 by applying spectral properties of
$\mathcal{T}_{X_{\natural}}=u_{\natural}u_{\natural}^{\ast}$ in Lemma D.6.
More precisely, if we define the kernel

$\hat{X}=\frac{1}{2}\left(X_{\natural}\circ\bm{\tau}_{\hat{\nu}-\nu_{\natural}}+X_{\natural}\circ\bm{\tau}_{-(\hat{\nu}-\nu_{\natural})}\right),$

the refinement power method D.42 involves the operator
$\mathcal{T}_{\hat{X}}$, since for any $\nu\in\mathbb{R}$ and any $f,g\in
L^{2}(\mathbb{R})$

$\displaystyle\left\langle\mathcal{T}_{X_{\natural}\circ\bm{\tau}_{\nu}}[f],g\right\rangle_{L^{2}(\mathbb{R})}$
$\displaystyle=\iint_{\mathbb{R}^{2}}X_{\natural}\circ\bm{\tau}_{\nu}(s,t)g(s)f(t)\mathop{}\\!\mathrm{d}s\mathop{}\\!\mathrm{d}t,$

and by D.62 in the proof of Lemma D.8 and the fact that
$X_{\natural}(s,t)=X_{\natural}(t,s)$, we have that

$X_{\natural}\circ\bm{\tau}_{\nu}(s,t)=X_{\natural}\circ\bm{\tau}_{-\nu}(t,s),$

whence

$\displaystyle\left\langle\mathcal{T}_{X_{\natural}\circ\bm{\tau}_{\nu}}[f],g\right\rangle_{L^{2}(\mathbb{R})}$
$\displaystyle=\left\langle\mathcal{T}_{X_{\natural}\circ\bm{\tau}_{-\nu}}[g],f\right\rangle_{L^{2}(\mathbb{R})},$

so that

$\frac{1}{2}\left(\mathcal{T}_{X_{\natural}\circ\bm{\tau}_{\hat{\nu}-\nu_{\natural}}}+\mathcal{T}_{X_{\natural}\circ\bm{\tau}_{\hat{\nu}-\nu_{\natural}}}^{\ast}\right)=\mathcal{T}_{\hat{X}}.$

Thus, to accomplish our goal, we need to prove that the spectrum of
$\mathcal{T}_{\hat{X}}$ has a gap. In the sequel, we will repeatedly use the
fact that $\mathcal{T}_{\hat{X}}$ and $\mathcal{T}_{X}$ are self-adjoint
Fredholm operators, and that for any Fredholm operator with kernel $f\in
L^{2}(\mathbb{R}^{2})$, we have

$\lVert\mathcal{T}_{f}\rVert_{\mathrm{HS}}=\lVert
f\rVert_{L^{2}(\mathbb{R}^{2})}.$ (D.51)

Conversely, if $\mathcal{T}:L^{2}(\mathbb{R})\to L^{2}(\mathbb{R})$ is a self-
adjoint Hilbert-Schmidt operator, it is in particular a compact operator,
which can be written as
$\mathcal{T}=\sum_{i=1}^{\infty}\lambda_{i}v_{i}v_{i}^{\ast}$ for eigenvalues
$(\lambda_{i})_{i\in\mathbb{N}}\subset\mathbb{R}$ and an orthonormal basis of
eigenfunctions $(v_{i})_{i\in\mathbb{N}}$, with
$\lVert\mathcal{T}\rVert_{\mathrm{HS}}=\sum_{i\in\mathbb{N}}\lambda_{i}^{2}$
(c.f. [19, §B]); if we put
$f(s,t)=\sum_{i\in\mathbb{N}}\lambda_{i}v_{i}(s)v_{i}(t)$, then $f\in
L^{2}(\mathbb{R}^{2})$ and we have $\mathcal{T}=\mathcal{T}_{f}$. This
together with D.51 shows that $f\mapsto\mathcal{T}_{f}$ is an isometry of
Banach spaces, and we will exploit this in the sequel to simplify our
notation, writing (for example) $\lVert f\rVert_{\mathrm{HS}}$ to denote
$\lVert\mathcal{T}_{f}\rVert_{\mathrm{HS}}$ if $f\in L^{2}(\mathbb{R}^{2})$,
and so on.

First, we note that $\mathcal{T}_{\hat{X}}$ is Hilbert-Schmidt, by the
triangle inequality and the fact that it is a Fredholm operator (together with
the fact that $f\mapsto f\circ\bm{\tau}_{\nu}$ is a unitary transformation of
$L^{2}(\mathbb{R}^{2})$):

$\displaystyle\lVert\mathcal{T}_{\hat{X}}\rVert_{\mathrm{HS}}=\lVert\hat{X}\rVert_{L^{2}(\mathbb{R}^{2})}$
$\displaystyle\leq\frac{1}{2}\left(\left\lVert
X_{\natural}\circ\bm{\tau}_{\hat{\nu}-\nu_{\natural}}\right\rVert_{L^{2}(\mathbb{R}^{2})}+\lVert
X_{\natural}\circ\bm{\tau}_{-(\hat{\nu}-\nu_{\natural})}\rVert_{L^{2}(\mathbb{R}^{2})}\right)$
$\displaystyle=\left\lVert
X_{\natural}\right\rVert_{L^{2}(\mathbb{R}^{2})}=\left\lVert\mathcal{T}_{X_{\natural}}\right\rVert_{\mathrm{HS}}.$
(D.52)

This means that $\mathcal{T}_{\hat{X}}$ is a compact operator; it is also
self-adjoint, by construction. We have therefore
$\mathcal{T}_{\hat{X}}=\sum_{i=1}^{\infty}\lambda_{i}v_{i}v_{i}^{\ast}$ for
eigenvalues $(\lambda_{i})_{i\in\mathbb{N}}\subset\mathbb{R}$ and an
orthonormal basis of eigenfunctions $(v_{i})_{i\in\mathbb{N}}$ (c.f. [19,
§B]). Without loss of generality, we assume that the sequence is ordered such
that $\lvert\lambda_{1}\rvert=\lVert\hat{X}\rVert$. To show that the spectrum
has a gap in the way that is needed to apply Lemma D.6, we need to show that
$\lambda_{1}>0$ and that the rest of the spectrum is bounded in magnitude away
from $\lambda_{1}$. We will establish the latter first. Note that

$\displaystyle\sup_{i\geq
2}\,\lvert\lambda_{i}\rvert^{2}\leq\sum_{i=2}^{\infty}\lvert\lambda_{i}\rvert^{2}$
$\displaystyle=-\lvert\lambda_{1}\rvert^{2}+\sum_{i=1}^{\infty}\lvert\lambda_{i}\rvert^{2}$
$\displaystyle=\lVert\hat{X}\rVert_{\mathrm{HS}}^{2}-\lVert\hat{X}\rVert^{2}.$

By the triangle inequality and (as above) the fact that
$\lVert\>\cdot\>\rVert\leq\lVert\>\cdot\>\rVert_{\mathrm{HS}}$, we have

$\displaystyle\lVert\hat{X}\rVert$ $\displaystyle\geq\lVert
X_{\natural}\rVert-\lVert X_{\natural}-\hat{X}\rVert$ $\displaystyle\geq\lVert
X_{\natural}\rVert-\lVert X_{\natural}-\hat{X}\rVert_{\mathrm{HS}}$
$\displaystyle=\lVert X_{\natural}\rVert_{\mathrm{HS}}-\lVert
X_{\natural}-\hat{X}\rVert_{\mathrm{HS}}$

where we used the fact that $X_{\natural}=u_{\natural}u_{\natural}^{\ast}$, so
that $\lVert X_{\natural}\rVert_{\mathrm{HS}}=u_{\natural}^{\ast}u_{\natural}$
coincides with $\lVert X_{\natural}\rVert=\sup_{\lVert f\rVert_{L^{2}}\leq
1}\,\lvert\langle u_{\natural},f\rangle\rvert\lVert
u_{\natural}\rVert_{L^{2}}=\lVert u_{\natural}\rVert_{L^{2}}^{2}$ (apply the
Schwarz inequality). Thus, if $\lVert
X_{\natural}-\hat{X}\rVert_{\mathrm{HS}}\leq\lVert
X_{\natural}\rVert_{\mathrm{HS}}$, we have

$\displaystyle\sup_{i\geq 2}\,\lvert\lambda_{i}\rvert^{2}$
$\displaystyle\leq\lVert\hat{X}\rVert_{\mathrm{HS}}^{2}-\left(\lVert
X_{\natural}\rVert_{\mathrm{HS}}-\lVert
X_{\natural}-\hat{X}\rVert_{\mathrm{HS}}\right)^{2}$ $\displaystyle\leq
2\lVert X_{\natural}\rVert_{\mathrm{HS}}\lVert
X_{\natural}-\hat{X}\rVert_{\mathrm{HS}},$

where the second inequality applies D.52 and discards the (negative) second-
order term. Since $u_{\natural}={\mathds{1}}_{[-1/\sqrt{2},1/\sqrt{2}]}$, we
have $\lVert X_{\natural}\rVert_{\mathrm{HS}}=\sqrt{2}$, and to proceed using
the above it suffices to control $\lVert
X_{\natural}-\hat{X}\rVert_{\mathrm{HS}}$ and show that it is no larger than
$\sqrt{2}$. To this end, we have

$\displaystyle\left\lVert\hat{X}-X_{\natural}\right\rVert$
$\displaystyle\leq\left\lVert\hat{X}-X_{\natural}\right\rVert_{\mathrm{HS}}$
$\displaystyle\leq\frac{1}{2}\left\lVert
X_{\natural}\circ\bm{\tau}_{\hat{\nu}-\nu_{\natural}}-X_{\natural}\right\rVert_{\mathrm{HS}}+\frac{1}{2}\left\lVert
X_{\natural}\circ\bm{\tau}_{-(\hat{\nu}-\nu_{\natural})}-X_{\natural}\right\rVert_{\mathrm{HS}},$

where the second line uses the triangle inequality. Below, write
$\alpha=1/\sqrt{2}$. One has for any $\varepsilon\in\mathbb{R}$

$\displaystyle\left\lVert
X_{\natural}\circ\bm{\tau}_{\varepsilon}-X_{\natural}\right\rVert_{\mathrm{HS}}^{2}$
$\displaystyle=2\left\lVert
X_{\natural}\right\rVert_{L^{2}(\mathbb{R}^{2})}^{2}-2\langle
X_{\natural}\circ\bm{\tau}_{\varepsilon},X_{\natural}\rangle_{L^{2}(\mathbb{R}^{2})}$
$\displaystyle=8\alpha^{2}-2\langle
X_{\natural}\circ\bm{\tau}_{\varepsilon},X_{\natural}\rangle_{L^{2}(\mathbb{R}^{2})},$

because the operators are Fredholm operators and $\bm{\tau}_{\varepsilon}$ is
a unitary transformation. To estimate the cross term, we argue geometrically.
For $\lvert\varepsilon\rvert\leq 1$, we have the estimate
$\lvert\cos\varepsilon\rvert+\lvert\sin\varepsilon\rvert\leq
1+\lvert\varepsilon\rvert$. This implies that

$\displaystyle\lVert\bm{R}_{\varepsilon}\bm{x}\rVert_{\infty}$
$\displaystyle\leq\left\lVert\bm{R}_{\varepsilon}\right\rVert_{\infty\to\infty}\lVert\bm{x}\rVert_{\infty}$
$\displaystyle\leq\lVert\bm{x}\rVert_{\infty}\left(\lvert\cos\varepsilon\rvert+\lvert\sin\varepsilon\rvert\right)$
$\displaystyle\leq\lVert\bm{x}\rVert_{\infty}(1+\lvert\varepsilon\rvert).$

Points $\bm{x}\in\mathbb{R}^{2}$ where the inner product $\langle
X_{\natural}\circ\bm{\tau}_{\varepsilon},X_{\natural}\rangle_{L^{2}(\mathbb{R}^{2})}$
is positive (it is nonnegative, because both of the integrands are
nonnegative) are those where $\lVert\bm{x}\rVert_{\infty}\leq\alpha$ and
$\lVert\bm{R}_{\varepsilon}\bm{x}\rVert_{\infty}\leq\alpha$. By the previous
estimate, both conditions occur when
$\lVert\bm{x}\rVert_{\infty}\leq\alpha/(1+\lvert\varepsilon\rvert)$. Since
$1/(1+\lvert\varepsilon\rvert)^{2}\geq(1-\lvert\varepsilon\rvert)^{2}$ if
$\lvert\varepsilon\rvert\leq 1$, this implies

$\displaystyle\langle
X_{\natural}\circ\bm{\tau}_{\varepsilon},X_{\natural}\rangle_{L^{2}(\mathbb{R}^{2})}$
$\displaystyle\geq\int_{\lVert\bm{x}\rVert_{\infty}\leq\alpha/(1+\lvert\varepsilon\rvert)}\mathop{}\\!\mathrm{d}\bm{x}$
$\displaystyle=\frac{4\alpha^{2}}{(1+\lvert\varepsilon\rvert)^{2}}$
$\displaystyle\geq 4\alpha^{2}-8\alpha^{2}\lvert\varepsilon\rvert,$

so

$\left\lVert
X_{\natural}\circ\bm{\tau}_{\varepsilon}-X_{\natural}\right\rVert_{\mathrm{HS}}^{2}\leq
16\alpha^{2}\lvert\varepsilon\rvert,$

and thus, since $\lvert\nu_{\natural}-\hat{\nu}\rvert\leq 1$ by the reduction-
by-symmetry to the domain $[\nu_{\natural}-\pi/4,\nu_{\natural}+\pi/4]$ given
in the previous phase of the argument,

$\lVert\hat{X}-X_{\natural}\rVert\leq\lVert\hat{X}-X_{\natural}\rVert_{\mathrm{HS}}\leq
2\sqrt{2}\sqrt{\lvert\hat{\nu}-\nu_{\natural}\rvert}.$ (D.53)

In particular, if $\lvert\hat{\nu}-\nu_{\natural}\rvert\leq\tfrac{1}{4}$, we
have $\lVert\hat{X}-X_{\natural}\rVert_{\mathrm{HS}}\leq\lVert
X_{\natural}\rVert_{\mathrm{HS}}$, and by the above

$\sup_{i\geq 2}\,\lvert\lambda_{i}\rvert\leq
2\sqrt{2}\left\lvert\nu_{\natural}-\hat{\nu}\right\rvert^{1/4}.$

Meanwhile, under this condition the above estimates yield

$\displaystyle\lvert\lambda_{1}\rvert=\lVert\hat{X}\rVert$
$\displaystyle\leq\lVert X_{\natural}\rVert+\lVert X_{\natural}-\hat{X}\rVert$
$\displaystyle\leq\sqrt{2}+2\sqrt{2}\lvert\nu_{\natural}-\hat{\nu}\rvert^{1/2},$
(D.54)

and moreover, by the Schwarz inequality,

$\displaystyle\langle
u_{\natural},\hat{X}[u_{\natural}]\rangle_{L^{2}(\mathbb{R})}$
$\displaystyle\geq\langle
u_{\natural},X_{\natural}[u_{\natural}]\rangle-\lVert
u_{\natural}\rVert_{L^{2}(\mathbb{R})}^{2}\lVert\hat{X}-X_{\natural}\rVert$
$\displaystyle\geq\lVert
u_{\natural}\rVert_{L^{2}(\mathbb{R})}^{4}-2\sqrt{2}\lVert
u_{\natural}\rVert_{L^{2}(\mathbb{R})}^{2}\lvert\nu_{\natural}-\hat{\nu}\rvert^{1/2}$

Since $\lVert u_{\natural}\rVert_{L^{2}(\mathbb{R})}=2^{1/4}$, this means that
if $\lvert\hat{\nu}-\nu_{\natural}\rvert\leq\tfrac{1}{64}$, we have

$\left\langle\frac{u_{\natural}}{\lVert
u_{\natural}\rVert_{L^{2}}},\hat{X}\left[\frac{u_{\natural}}{\lVert
u_{\natural}\rVert_{L^{2}}}\right]\right\rangle_{L^{2}(\mathbb{R})}\geq\frac{3\sqrt{2}}{4},$

and since, under this condition, we have

$\sup_{i\geq 2}\,\lvert\lambda_{i}\rvert\leq 1,$

we conclude that

$\max_{i\in\mathbb{N}}\lambda_{i}=\max_{\lVert u\rVert_{L^{2}(\mathbb{R})}\leq
1}\,\langle
u,\hat{X}[u]\rangle_{L^{2}(\mathbb{R})}\geq\left\langle\frac{u_{\natural}}{\lVert
u_{\natural}\rVert_{L^{2}}},\hat{X}\left[\frac{u_{\natural}}{\lVert
u_{\natural}\rVert_{L^{2}}}\right]\right\rangle_{L^{2}(\mathbb{R})}>\sup_{i\geq
2}\,\lvert\lambda_{i}\rvert.$

(c.f. the proof of Lemma D.19). In particular, we have $\lambda_{1}>0$.
Following as well the above arguments, we have if
$\lvert\hat{\nu}-\nu_{\natural}\rvert\leq\tfrac{1}{64}$

$\lvert\lambda_{1}\rvert\geq\sqrt{2}-2\sqrt{2}\lvert\nu_{\natural}-\hat{\nu}\rvert^{1/2}\geq\frac{3\sqrt{2}}{4},$
(D.55)

which implies the gap condition

$\frac{\sup_{i\geq
2}\,\lvert\lambda_{i}\rvert}{\lambda_{1}}\leq\frac{2\lvert\nu_{\natural}-\hat{\nu}\rvert^{1/4}}{1-2\lvert\nu_{\natural}-\hat{\nu}\rvert^{1/2}}\leq\frac{8}{3}\lvert\nu_{\natural}-\hat{\nu}\rvert^{1/4}<1$
(D.56)

under the preceding assumptions. Using these characterizations of the spectral
gap, we can conveniently also apply [4, Proposition 6.1] to obtain

$\left\lVert\frac{u_{\natural}}{\lVert
u_{\natural}\rVert_{L^{2}}}\frac{u_{\natural}^{\ast}}{\lVert
u_{\natural}\rVert_{L^{2}}}-v_{1}v_{1}^{\ast}\right\rVert_{\mathrm{HS}}\leq\frac{2}{\sqrt{2}-1}\lVert
X_{\natural}-\hat{X}\rVert_{\mathrm{HS}}\leq
14\sqrt{\lvert\nu_{\natural}-\hat{\nu}\rvert}.$

Meanwhile, we have

$\left\lVert\frac{u_{\natural}}{\lVert
u_{\natural}\rVert_{L^{2}}}\frac{u_{\natural}^{\ast}}{\lVert
u_{\natural}\rVert_{L^{2}}}-v_{1}v_{1}^{\ast}\right\rVert_{\mathrm{HS}}^{2}=2\left(1-\left\langle\frac{u_{\natural}}{\lVert
u_{\natural}\rVert_{L^{2}}},v_{1}\right\rangle^{2}\right).$

Since $v_{1}$ is only defined up to sign, let us suppose without loss of
generality that $v_{1}$ is such that $\langle
v_{1},u_{\natural}\rangle_{L^{2}}\geq 0$. Proceeding, we then obtain

$\displaystyle\left\lVert\frac{u_{\natural}}{\lVert
u_{\natural}\rVert_{L^{2}}}\frac{u_{\natural}^{\ast}}{\lVert
u_{\natural}\rVert_{L^{2}}}-v_{1}v_{1}^{\ast}\right\rVert_{\mathrm{HS}}^{2}$
$\displaystyle=2\left(1-\left\langle\frac{u_{\natural}}{\lVert
u_{\natural}\rVert_{L^{2}}},v_{1}\right\rangle\right)\left(1+\left\langle\frac{u_{\natural}}{\lVert
u_{\natural}\rVert_{L^{2}}},v_{1}\right\rangle\right)$ $\displaystyle\geq
2\left(1-\left\langle\frac{u_{\natural}}{\lVert
u_{\natural}\rVert_{L^{2}}},v_{1}\right\rangle\right)$
$\displaystyle=\left\lVert\frac{u_{\natural}}{\lVert
u_{\natural}\rVert_{L^{2}}}-v_{1}\right\rVert_{L^{2}(\mathbb{R})}^{2}.$

Combining, this gives

$\left\lVert 2^{-1/4}u_{\natural}-v_{1}\right\rVert_{L^{2}(\mathbb{R})}\leq
14\sqrt{\lvert\nu_{\natural}-\hat{\nu}\rvert}.$ (D.57)

This allows us to lower bound the correlation between the power method
initialization $u_{\mathrm{rough}}$ and the target eigenvector: by the
triangle inequality and the Schwarz inequality,

$\displaystyle\langle v_{1},u_{\mathrm{rough}}\rangle$
$\displaystyle\geq\langle v_{1},\bar{u}_{\mathrm{rough}}\rangle-\lVert
u_{\mathrm{rough}}-\bar{u}_{\mathrm{rough}}\rVert_{L^{2}(\mathbb{R})}$
$\displaystyle\geq 2^{-1/4}\langle
u_{\natural},\bar{u}_{\mathrm{rough}}\rangle-\lVert
v_{1}-2^{-1/4}u_{\natural}\rVert_{L^{2}(\mathbb{R})}-\lVert
u_{\mathrm{rough}}-\bar{u}_{\mathrm{rough}}\rVert_{L^{2}(\mathbb{R})}.$

We calculate

$2^{-1/4}\langle
u_{\natural},\bar{u}_{\mathrm{rough}}\rangle=\frac{2}{2^{1/4}\sqrt{\pi}}\int_{-1}^{1}\cos(\pi
x/2)\mathop{}\\!\mathrm{d}x=\frac{8}{2^{1/4}\pi^{3/2}},$

so that, by D.43 and D.57, we have for $T_{\mathrm{rough}}\geq 4$ and
$\lvert\nu_{\natural}-\hat{\nu}\rvert\leq\tfrac{1}{256}$ that

$\langle v_{1},u_{\mathrm{rough}}\rangle\geq\frac{1}{4}.$ (D.58)

Moreover, it allows us to control the unnormalized distance between the power
method output and the target in terms of the normalized distance: the triangle
inequality gives

$\displaystyle\left\lVert
u_{\natural}-\sqrt{\lambda_{1}}v_{1}\right\rVert_{L^{2}(\mathbb{R})}$
$\displaystyle\leq\max\left\\{\lVert
u_{\natural}\rVert_{L^{2}(\mathbb{R})},\sqrt{\lambda_{1}}\right\\}\left\lVert\frac{u_{\natural}}{\lVert
u_{\natural}\rVert_{L^{2}}}-v_{1}\right\rVert_{L^{2}(\mathbb{R})}+\lvert\lVert
u_{\natural}\rVert_{L^{2}(\mathbb{R})}-\sqrt{\lambda_{1}}\rvert$
$\displaystyle\leq
14\left(2^{1/4}+2^{3/8}\lvert\nu_{\natural}-\hat{\nu}\rvert^{1/4}\right)\sqrt{\lvert\nu_{\natural}-\hat{\nu}\rvert}+\lvert\lVert
u_{\natural}\rVert_{L^{2}(\mathbb{R})}-\sqrt{\lambda_{1}}\rvert,$

where the second line applies D.54. Meanwhile, D.54 and D.55 imply

$2^{1/4}\left(\sqrt{1-2\lvert\nu_{\natural}-\hat{\nu}\rvert^{1/2}}-1\right)\leq\sqrt{\lambda_{1}}-2^{1/4}\leq
2^{1/4}\left(\sqrt{1+2\lvert\nu_{\natural}-\hat{\nu}\rvert^{1/2}}-1\right),$

and given that $2\lvert\nu_{\natural}-\hat{\nu}\rvert^{1/2}\leq\tfrac{1}{8}$
by our assumptions, the inequalities $\sqrt{1+x}\leq 1+x/2$ and
$\sqrt{1-x}\geq 1-x$ (the latter valid if $0\leq x\leq 1$) lead to the bounds

$-2^{5/4}\lvert\nu_{\natural}-\hat{\nu}\rvert^{1/2}\leq\sqrt{\lambda_{1}}-2^{1/4}\leq
2^{5/4}\lvert\nu_{\natural}-\hat{\nu}\rvert^{1/2},$

so, plugging into the previous estimate, we obtain

$\displaystyle\left\lVert
u_{\natural}-\sqrt{\lambda_{1}}v_{1}\right\rVert_{L^{2}(\mathbb{R})}\leq
30\sqrt{\lvert\nu_{\natural}-\hat{\nu}\rvert}$ (D.59)

after worst-casing constants. We can finally apply Lemma D.6 with the
properties D.56 and D.58 together with the triangle inequality and D.59 to
obtain that the iteration D.42 satisfies

$\lVert\hat{u}-u_{\natural}\rVert_{L^{2}(\mathbb{R})}\leq
30\sqrt{\lvert\nu_{\natural}-\hat{\nu}\rvert}+28\left(\frac{8}{3}\lvert\nu_{\natural}-\hat{\nu}\rvert^{1/4}\right)^{T_{u}}$

after worst-casing constants slightly.

##### Concluding the result.

Finally, we instantiate our results above with appropriate parameter choices
to obtain the desired conclusion. We have shown the following: there are
absolute constants $c_{1}$, $C_{1}$, $C_{2}>0$ such that for any parameters
$\sigma$, $\beta$ satisfying

$\displaystyle\sigma{}^{2}$ $\displaystyle\leq\tfrac{1}{10^{4}},$
$\displaystyle\beta$ $\displaystyle\leq c_{1},$

for any $0<\varepsilon\leq\tfrac{1}{768}$, if the iteration counts satisfy

$\displaystyle T_{\mathrm{rough}}$ $\displaystyle\geq-
C_{1}\log(\sigma^{2}\varepsilon),$ $\displaystyle T_{\nu}$
$\displaystyle\geq-\frac{C_{2}\log(3\varepsilon)}{\beta},$ $\displaystyle
T_{u}$ $\displaystyle\geq 16,$

then with probability over the random initialization of $\nu_{0}$ at least
$4/7$, one has

$\displaystyle\lvert\hat{\nu}-\nu_{\natural}\rvert$ $\displaystyle\leq
3\varepsilon,$
$\displaystyle\lVert\hat{u}-u_{\natural}\rVert_{L^{2}(\mathbb{R})}$
$\displaystyle\leq 31\sqrt{\varepsilon}.$

The condition on $T_{u}$ is quite mild because the rate of convergence
improves with the quality of the output of the alignment stage of the
algorithm, since the target $u_{\natural}u_{\natural}^{\ast}$ is rank one. The
condition on $T_{\nu}$ above takes advantage of the fact that when $0\leq
x\leq\tfrac{1}{2}$, we have by concavity $\log(1-x)\geq(-2\log 2)x$ to
simplify the stated bound in our previous work.

∎

######  Remark D.3.

Theorem D.2 establishes a linear rate of convergence of both the alignment
iterates $\nu_{k}$ and the representation iterations that generate
$u_{\mathrm{rough}}$ and $\hat{u}$ to the true parameters of the template, up
to symmetry. The dependence on the other problem parameters in these rates,
namely the smoothing $\sigma^{2}$ and the step size $\beta$, is about as mild
as one would hope for: the smoothing level $\sigma^{2}$ only enters the rates
logarithmically, and the step size is only required to be smaller than an
absolute constant, which is reflected as a linear dependence in the rate of
convergence of the alignment step of the algorithm. The issue of smoothing
represents an interesting conceptual takeaway from our analysis, with regards
to modern 3D representation approaches like TILTED which do not explicitly
incorporate a classical coarse-to-fine smoothing schedule, as in, for example,
image registration [13]. Our proofs demonstrate that the reason smoothing is
not necessary for precise local convergence is that computational constraints
on the representation capacity of the method (here, a rank-one matrix) and the
$L^{2}$ loss create texture gradients (i.e., blurry images) when optimizing
the representation, and these texture gradients cause the subsequent alignment
landscape to be smoother than one might otherwise expect. For example, when
$\sigma^{2}$ is small, the smoothed template
$\varphi_{\sigma^{2}}\mathbin{\ast}X_{\natural}$ has a Lipschitz constant on
the order of $1/\sigma$, due to sharp edges in $X_{\natural}$; nevertheless,
this sharpness does not reflect in our rates as a consequence of the blessings
of capacity-constrained inexact representation.

Theorem D.2 contains a hypothesis on the probability of success, which is
asserted to be at least $\tfrac{4}{7}$; since this value is larger than
$\tfrac{1}{2}$, it is theoretically possible to boost the success probability
to an arbitrarily-high level by running multiple independent trials of the
algorithm and aggregating the outputs appropriately. In practice, of course,
the algorithm succeeds with probability one on the template $X_{\natural}$:
the discrepancy is due to the technical need to prove that the nonconvex
alignment landscape $\nu\mapsto\mathcal{L}^{\sigma}(\nu,u_{\mathrm{rough}})$
has suitable negative curvature in neighborhoods of the maximizers
$(\nu_{\natural}+\tfrac{\pi}{4})+\tfrac{\pi}{2}\mathbb{Z}$. This “benign
global geometry”, in the sense of [50], has been studied in other contexts
[41, 42, 60], although the mixture of discrete and continuous symmetries in
the $(\nu,u)$ landscape of D.34 is somewhat distinguished. In general, we have
endeavored to keep the optimization analysis in Theorem D.2 as elementary as
possible, and we have not made attempts to optimize absolute constants. Simple
and standard modifications to the proofs can be made to yield slightly better
constants and rates, at the cost of additional technicality [16, 41, 50].

######  Remark D.4.

We discuss three directions of extension for Theorem D.2 below.

  1. 1.

Joint factorization and alignment. The algorithm we study, in its use of the
power method as a standin for matrix factorization as in D.34 as well as its
use of “block” alternating minimization iterations rather than alternating
gradient steps on $\nu$ and $u$, differs from our implementation of TILTED in
ways that present important directions for further technical improvement. It
seems to us that extending our analysis to the case of alternating gradient
steps would require some additional conceptual insight (e.g., the
identification of a conserved quantity): various technical components of the
current alignment argument are delicate and break when the factorization
target is not constant. A similar issue is associated with the extension of
the result to $\nu_{\natural}\neq\pi/4$, although this case seems “easier”;
e.g., perturbative analogues of Lemma D.1 for other values of $\nu_{\natural}$
would suffice here. In the alternating $(\nu,u)$ setting, there is also a
challenge associated with the fact that texture gradients induced by inexact
factorization become smaller as the alignment becomes more accurate, making
the landscape nonsmooth. Rather than introducing auxiliary smoothing in this
setting, it may be most relevant to practice to study the nonsmooth landscape
directly, à la [38]; the analysis can be less technical in our setting since
there is no statistical component to the problem. Extending the loss D.34 to
the setting of overparameterized matrix factorization is also interesting;
developing this extension in the context of observations $X_{\natural}$ with
background clutter, as discussed below, may be the most natural setting.

  2. 2.

Extensions to multi-object scenes and three dimensions. Establishing a direct
3D analogue of Theorem D.2 seems to be mostly technical. Extending the result
to apply to scenes $X_{\natural}$ with other objects and background clutter
present seems more challenging: the proof of Theorem D.2 presents a
perturbative framework for analyzing TILTED that should not be hard to extend
to ‘perturbed’ observations $X_{\natural}$ when the magnitude of the
perturbation is small, but getting insights into how the algorithm can be
changed to cope with the kinds of structured perturbations that arise in real-
world scenes (e.g., a scene with objects with shape content that cannot be
axis-aligned as well as the square, like people, but that nonetheless contains
enough ‘prominent’ axis-alignable components, such as buildings and roads in a
built environment, for success to be possible) seems to require novel ideas.
One path forward here could be to introduce additional appearance components
to the square $X_{\natural}$, such as a texture, and study conditions under
which these are sufficiently decorrelated with the shape components of the
template for success to remain possible. Another possibility is to study the
overparameterized case and separate distinct factorization components into
“groups”, as in our implementation of TILTED, which have their own
transformations and can thus represent distinct parts of the scene; the
necessary symmetry-breaking aspects of such a result feel reminiscent of
analyses of dictionary learning [50], but feel significantly more challenging
due to the need to localize different objects via factorization in the setting
of TILTED.

  3. 3.

Computing with a MLP. An extremely important avenue for extension of Theorem
D.2 is to go beyond the linear representation studied there and introduce a
neural network for representing the scene. This presents an additional
challenge with respect to disentangling appearance and shape versus our
current analysis: there, the rank-one capacity constraint on the factorization
leads to inexact intermediate factorizations that create texture gradients to
help alignment, and alignment improvements help to further improve the
representation. With a MLP, there seems to be some natural capacity to
represent coordinate rotations (c.f. Section D.4)—understanding how
initialization and implicit bias of gradient descent training preserves the
disentangled learning of appearance and alignment that we prove occurs in the
linear model is a fascinating direction for future work.

####  D.2.1 Supporting Results

######  Lemma D.6.

Let $\mathcal{T}:L^{2}(\mathbb{R})\to L^{2}(\mathbb{R})$ be a nonzero self-
adjoint Hilbert-Schmidt operator with corresponding eigenvalues
$(\lambda_{k})_{k\in\mathbb{N}}$ and orthonormal basis
$(v_{k})_{k\in\mathbb{N}}\subset L^{2}(\mathbb{R})$. Without loss of
generality, suppose that $\lVert\mathcal{T}\rVert=\lvert\lambda_{1}\rvert>0$.
Suppose moreover that $\lambda_{1}>0$,444If $\lambda_{1}<0$, it is necessary
to take absolute values in order to obtain the result asserted here: consider
for example the case where $\mathcal{T}=-\operatorname{\mathrm{Id}}$, so that
$u_{k}=(-1)^{k}u_{0}$ if $\lVert u_{0}\rVert_{L^{2}(\mathbb{R})}=1$. and that
the spectrum has a gap, i.e., that for some $0<\gamma\leq 1$ we have
$\lambda_{1}-\lvert\lambda_{k}\rvert\geq\gamma\lambda_{1}$ for all $k>1$.
Consider power method on $\mathcal{T}$, starting from initialization $u_{0}\in
L^{2}(\mathbb{R})$:

$u_{k+1}=\frac{\mathcal{T}u_{k}}{\lVert\mathcal{T}u_{k}\rVert_{L^{2}(\mathbb{R})}}.$

Then if $\lvert\langle
v_{1},u_{0}\rangle_{L^{2}(\mathbb{R})}\rvert\geq\eta>0$, it holds

$\left\lVert u_{k}-\operatorname{sign}(\langle
v_{1},u_{0}\rangle_{L^{2}(\mathbb{R})})v_{1}\right\rVert_{L^{2}(\mathbb{R})}^{2}\leq
2(1-\gamma)^{2k}\frac{\lVert u_{0}\rVert_{L^{2}(\mathbb{R})}^{2}}{\eta^{2}}.$

In addition, if the iteration count satisfies

$k\geq\frac{\log(\eta/4\lVert
u_{0}\rVert_{L^{2}(\mathbb{R})})}{\log(1-\gamma)},$

then the ‘rank-one approximating factor’ error satisfies

$\left\lVert\sqrt{u_{k}^{\ast}\mathcal{T}u_{k}}u_{k}-\sqrt{\lambda_{1}}\operatorname{sign}(\langle
v_{1},u_{0}\rangle_{L^{2}(\mathbb{R})})v_{1}\right\rVert_{L^{2}(\mathbb{R})}^{2}\leq
18{\lambda_{1}}(1-\gamma)^{2k}\frac{\lVert
u_{0}\rVert_{L^{2}(\mathbb{R})}^{2}}{\eta^{2}}.$

###### Proof.

We apply the standard argument; under the assumption of a Hilbert-Schmidt
operator with a gapped spectrum, as we have made here, the standard argument’s
convergence is actually dimension-free, in contrast to the general case (c.f.
[9]). We use basic notions from the analysis of self-adjoint Hilbert-Schmidt
operators in the proof (see [18, §B]).

The main observation to make is that the update equation for $u_{k+1}$ in the
definition of the power method is a $0$-absolutely-homogeneous function of
$u_{k}$. This implies

$u_{k}=\frac{\mathcal{T}^{k}u_{0}}{\left\lVert\mathcal{T}^{k}u_{0}\right\rVert_{L^{2}(\mathbb{R})}}.$

It is clear that this iteration is well-defined, i.e., that for every $k$ one
has $\mathcal{T}^{k}u_{0}\neq 0$, by the assumption that $\lvert\langle
v_{1},u_{0}\rangle\rvert>0$ (and the fact that $\lvert\lambda_{1}\rvert>0$),
since, as we will use below,

$\displaystyle\mathcal{T}^{k}u_{0}$
$\displaystyle=\sum_{l=1}^{\infty}\lambda_{l}^{k}\langle
v_{l},u_{0}\rangle_{L^{2}(\mathbb{R})}v_{l},$
$\displaystyle\left\lVert\mathcal{T}^{k}u_{0}\right\rVert_{L^{2}(\mathbb{R})}^{2}$
$\displaystyle=\sum_{l=1}^{\infty}\lambda_{l}^{2k}\lvert\langle
v_{l},u_{0}\rangle_{L^{2}(\mathbb{R})}\rvert^{2},$

since the sequence $(v_{l})$ is an orthonormal basis. Moreover, notice that if
we initialize the power method with $-u_{0}$ instead of $u_{0}$, we end up
only changing the sign of the output $u_{k}$; hence we can assume below
without loss of generality that $\langle v_{1},u_{0}\rangle>0$. Now, expanding
the square shows that

$\displaystyle\left\lVert u_{k}-v_{1}\right\rVert_{L^{2}}^{2}$
$\displaystyle=\left\lVert\frac{\mathcal{T}^{k}u_{0}}{\left\lVert\mathcal{T}^{k}u_{0}\right\rVert_{L^{2}(\mathbb{R})}}-v_{1}\right\rVert_{L^{2}}^{2}$
$\displaystyle=2\left(1-\frac{\lambda_{1}^{k}\langle
v_{1},u_{0}\rangle_{L^{2}(\mathbb{R})}}{\lVert\mathcal{T}^{k}u_{0}\rVert_{L^{2}(\mathbb{R})}}\right).$

Since $\lambda_{1}>0$, we have

$\displaystyle\frac{\lVert\mathcal{T}^{k}u_{0}\rVert_{L^{2}(\mathbb{R})}}{\lambda_{1}^{k}\langle
v_{1},u_{0}\rangle_{L^{2}(\mathbb{R})}}$
$\displaystyle=\left(\frac{1}{\lambda_{1}^{2k}\langle
v_{1},u_{0}\rangle_{L^{2}(\mathbb{R})}^{2}}\sum_{l=1}^{\infty}\lambda_{l}^{2k}\lvert\langle
v_{l},u_{0}\rangle_{L^{2}(\mathbb{R})}\rvert^{2}\right)^{1/2}$
$\displaystyle=\left(1+\sum_{l=2}^{\infty}\left(\frac{\lvert\lambda_{l}\rvert}{\lvert\lambda_{1}\rvert}\right)^{2k}\frac{\langle
v_{l},u_{0}\rangle_{L^{2}(\mathbb{R})}^{2}}{\langle
v_{1},u_{0}\rangle_{L^{2}(\mathbb{R})}^{2}}\right)^{1/2}.$

The gapped assumption implies that

$\frac{\lvert\lambda_{l}\rvert}{\lvert\lambda_{1}\rvert}\leq 1-\gamma,$

and the lower bound $\langle
v_{1},u_{0}\rangle_{L^{2}(\mathbb{R})}^{2}\geq\eta^{2}$ then implies

$\frac{\lVert\mathcal{T}^{k}u_{0}\rVert_{L^{2}(\mathbb{R})}}{\lambda_{1}^{k}\langle
v_{1},u_{0}\rangle_{L^{2}(\mathbb{R})}}\leq\left(1+(1-\gamma)^{2k}\frac{\lVert
u_{0}\rVert_{L^{2}(\mathbb{R})}^{2}}{\eta^{2}}\right)^{1/2}.$

For $x\geq 0$, the function $x\mapsto 1-(1+x)^{-1/2}$ is increasing and
concave, and therefore satisfies $1-(1+x)^{-1/2}\leq\tfrac{1}{2}x$. As a
result, we have

$\left\lVert u_{k}-v_{1}\right\rVert_{L^{2}}^{2}\leq
2(1-\gamma)^{2k}\frac{\lVert u_{0}\rVert_{L^{2}(\mathbb{R})}^{2}}{\eta^{2}},$

as claimed.

To obtain the claimed estimate for the rank-one approximating factor error, we
use the triangle inequality and a bound for the square root when its argument
is sufficiently far from $0$. Notice that
$\sqrt{\lambda_{1}}=\sqrt{v_{1}^{\ast}\mathcal{T}v_{1}}$, and by the triangle
inequality

$\displaystyle\left\lvert
u_{k}^{\ast}\mathcal{T}u_{k}-\lambda_{1}\right\rvert$
$\displaystyle\leq\left\lvert
u_{k}^{\ast}\mathcal{T}u_{k}-u_{k}^{\ast}\mathcal{T}v_{1}\right\rvert+\left\lvert
u_{k}^{\ast}\mathcal{T}v_{1}-v_{1}^{\ast}\mathcal{T}v_{1}\right\rvert$
$\displaystyle\leq 2\lVert\mathcal{T}\rVert\left\lVert
u_{k}-v_{1}\right\rVert_{L^{2}(\mathbb{R})}$
$\displaystyle=2\lambda_{1}\left\lVert
u_{k}-v_{1}\right\rVert_{L^{2}(\mathbb{R})}.$ (D.60)

by the Schwarz inequality and the fact that $u_{k}$ and $v_{1}$ are unit norm.
This implies

$u_{k}^{\ast}\mathcal{T}u_{k}\geq\lambda_{1}\left(1-2\lVert
u_{k}-v_{1}\rVert_{L^{2}(\mathbb{R})}\right).$

As a result, if

$k\geq\frac{\log(\eta/4\lVert
u_{0}\rVert_{L^{2}(\mathbb{R})})}{\log(1-\gamma)},$

we have $u_{k}^{\ast}\mathcal{T}u_{k}>0$, and square roots can be taken
without worry. We have by the triangle inequality

$\displaystyle\left\lVert\sqrt{u_{k}^{\ast}\mathcal{T}u_{k}}u_{k}-\sqrt{\lambda_{1}}v_{1}\right\rVert_{L^{2}(\mathbb{R})}$
$\displaystyle\leq\left\lVert\sqrt{u_{k}^{\ast}\mathcal{T}u_{k}}u_{k}-\sqrt{v_{1}^{\ast}\mathcal{T}v_{1}}u_{k}\right\rVert_{L^{2}(\mathbb{R})}+\left\lVert\sqrt{v_{1}^{\ast}\mathcal{T}v_{1}}u_{k}-\sqrt{v_{1}^{\ast}\mathcal{T}v_{1}}v_{1}\right\rVert_{L^{2}(\mathbb{R})}$
$\displaystyle\leq\left\lvert\sqrt{u_{k}^{\ast}\mathcal{T}u_{k}}-\sqrt{v_{1}^{\ast}\mathcal{T}v_{1}}\right\rvert+\sqrt{\lambda_{1}}\left\lVert
u_{k}-v_{1}\right\rVert_{L^{2}(\mathbb{R})},$

since $u_{k}$ and $v_{1}$ are unit norm. Now, by the fundamental theorem of
calculus, we have for any $x,y\geq 0$

$\left\lvert\sqrt{x}-\sqrt{y}\right\rvert=\frac{1}{2}\left\lvert\int_{y}^{x}z^{-1/2}\mathop{}\\!\mathrm{d}z\right\rvert\leq\frac{\lvert
x-y\rvert}{2\sqrt{\min\\{x,y\\}}},$

and in our setting, we have shown above

$u_{k}^{\ast}\mathcal{T}u_{k}\geq\left(1-\frac{1}{\sqrt{2}}\right)\lambda_{1}$

by our choice of $k$. Since $2(1-1/\sqrt{2})^{1/2}\geq 1$, it follows

$\displaystyle\left\lvert\sqrt{u_{k}^{\ast}\mathcal{T}u_{k}}-\sqrt{v_{1}^{\ast}\mathcal{T}v_{1}}\right\rvert$
$\displaystyle\leq\frac{1}{\sqrt{\lambda_{1}}}\left\lvert
u_{k}^{\ast}\mathcal{T}u_{k}-v_{1}^{\ast}\mathcal{T}v_{1}\right\rvert$
$\displaystyle\leq 2\sqrt{\lambda_{1}}\left\lVert
u_{k}-v_{1}\right\rVert_{L^{2}(\mathbb{R})}.$

where we used D.60 in the final line. Consequently, we have shown

$\left\lVert\sqrt{u_{k}^{\ast}\mathcal{T}u_{k}}u_{k}-\sqrt{\lambda_{1}}v_{1}\right\rVert_{L^{2}(\mathbb{R})}\leq
3\sqrt{\lambda_{1}}\left\lVert u_{k}-v_{1}\right\rVert_{L^{2}(\mathbb{R})},$

as claimed.

∎

######  Lemma D.7.

For the objective $\mathcal{L}^{\sigma}$ defined in D.32, one has

$\displaystyle\nabla_{\nu}\mathcal{L}^{\sigma}(\nu,\bm{U},\bm{V})$
$\displaystyle=-\left\langle\varphi_{\sigma^{2}}\ast\left(\bm{U}\bm{V}^{\ast}\circ\bm{\tau}_{\nu_{\natural}-\nu}\right),\left\langle\nabla_{\bm{x}}[\varphi_{\sigma^{2}}\ast
X_{\natural}],\begin{bmatrix}0&-1\\\
1&0\end{bmatrix}(\,\cdot\,)\right\rangle_{\ell^{2}}\right\rangle_{L^{2}(\mathbb{R}^{2})},$
$\displaystyle\nabla_{\bm{U}}\mathcal{L}^{\sigma}(\nu,\bm{U},\bm{V})$
$\displaystyle=-\left[\varphi_{2\sigma^{2}}\ast\left(X_{\natural}\circ\bm{\tau}_{\nu-\nu_{\natural}}-\bm{U}\bm{V}^{\ast}\right)\right]\bm{V}$
$\displaystyle\nabla_{\bm{V}}\mathcal{L}^{\sigma}(\nu,\bm{U},\bm{V})$
$\displaystyle=-\left[\varphi_{2\sigma^{2}}\ast\left(X_{\natural}\circ\bm{\tau}_{\nu_{\natural}-\nu}-\bm{V}\bm{U}^{\ast}\right)\right]\bm{U}.$

###### Proof.

For the gradients of $\mathcal{L}^{\sigma}$ with respect to $(\bm{U},\bm{V})$,
direct calculation using the chain rule for the Fréchet derivative and the
duality of $L^{2}(\mathbb{R})$ gives

$\displaystyle\nabla_{\bm{U}}\mathcal{L}^{\sigma}(\nu,\bm{U},\bm{V})$
$\displaystyle=-\left[\varphi_{2\sigma^{2}}\ast\left(X_{\natural}\circ\bm{\tau}_{\nu-\nu_{\natural}}-\bm{U}\bm{V}^{\ast}\right)\right]\bm{V}$
$\displaystyle\nabla_{\bm{V}}\mathcal{L}^{\sigma}(\nu,\bm{U},\bm{V})$
$\displaystyle=-\left[\varphi_{2\sigma^{2}}\ast\left(X_{\natural}\circ\bm{\tau}_{\nu-\nu_{\natural}}-\bm{U}\bm{V}^{\ast}\right)\right]^{\ast}\bm{U}.$

It is convenient to simplify the adjoint operation in the second expression.
First, note that
$f\mapsto[\varphi_{2\sigma^{2}}\ast(X_{\natural}\circ\bm{\tau}_{\nu-\nu_{\natural}}-\bm{U}\bm{V}^{\ast})][f]$
is a bounded operator on $L^{2}(\mathbb{R})$, because its $L^{2}\to L^{2}$
operator norm is bounded by its Hilbert-Schmidt norm, which is finite:

$\left\lVert\varphi_{2\sigma^{2}}\ast(X_{\natural}\circ\bm{\tau}_{\nu-\nu_{\natural}}-\bm{U}\bm{V}^{\ast})\right\rVert_{\mathrm{HS}}^{2}=\int_{\mathbb{R}^{2}}[\varphi_{2\sigma^{2}}\ast(X_{\natural}\circ\bm{\tau}_{\nu-\nu_{\natural}}-\bm{U}\bm{V}^{\ast})](s,t)^{2}\mathop{}\\!\mathrm{d}s\mathop{}\\!\mathrm{d}t<+\infty,$

by Young’s inequality for convolutions. This allows us to use Fubini’s theorem
freely in the sequel. For any $f,g\in L^{2}(\mathbb{R})$, we have

$\displaystyle\left\langle\left[\varphi_{2\sigma^{2}}\ast\left(X_{\natural}\circ\bm{\tau}_{\nu-\nu_{\natural}}-\bm{U}\bm{V}^{\ast}\right)\right][f],g\right\rangle_{L^{2}(\mathbb{R})}$
$\displaystyle\qquad=\int_{\mathbb{R}}g(s)\left(\int_{\mathbb{R}}\left[\varphi_{2\sigma^{2}}\ast(X_{\natural}\circ\bm{\tau}_{\nu-\nu_{\natural}}-\bm{U}\bm{V}^{\ast})\right](s,t)f(t)\mathop{}\\!\mathrm{d}t\right)\mathop{}\\!\mathrm{d}s$
$\displaystyle\qquad=\int_{\mathbb{R}}\int_{\mathbb{R}}\int_{\mathbb{R}^{2}}f(t)g(s)\varphi_{2\sigma^{2}}((s,t)-\bm{x})(X_{\natural}\circ\bm{\tau}_{\nu-\nu_{\natural}}-\bm{U}\bm{V}^{\ast})(\bm{x})\mathop{}\\!\mathrm{d}\bm{x}\mathop{}\\!\mathrm{d}t\mathop{}\\!\mathrm{d}s$
$\displaystyle\qquad=\int_{\mathbb{R}}\int_{\mathbb{R}}\int_{\mathbb{R}^{2}}\iiint
f(t)g(s)\varphi_{2\sigma^{2}}((t,s)-\bm{x})(X_{\natural}\circ\bm{\tau}_{\nu-\nu_{\natural}}-\bm{U}\bm{V}^{\ast})\left(\begin{bmatrix}1&0\\\
0&1\end{bmatrix}\bm{x}\right)\mathop{}\\!\mathrm{d}\bm{x}\mathop{}\\!\mathrm{d}t\mathop{}\\!\mathrm{d}s,$
(D.61)

where the third equality uses a unitary change of variables
$\bm{x}\mapsto\begin{bmatrix}0&1\\\ 1&0\end{bmatrix}\bm{x}$ in the convolution
integral. Notice that

$\displaystyle(X_{\natural}\circ\bm{\tau}_{\nu-\nu_{\natural}}-\bm{U}\bm{V}^{\ast})(s,t)$
$\displaystyle=X_{\natural}\circ\bm{\tau}_{\nu-\nu_{\natural}}(s,t)-\sum_{i=1}^{k}u_{i}(s)v_{i}(t)$
$\displaystyle=X_{\natural}\left(\bm{R}_{\nu-\nu_{\natural}}\begin{bmatrix}0&1\\\
1&0\end{bmatrix}(t,s)\right)-\sum_{i=1}^{k}v_{i}(t)u_{i}(s).$

Moreover, if $\bm{Q}$ is any orthogonal matrix with determinant $-1$, then for
any $\nu$ one has $\det(\bm{R}_{\nu}\bm{Q})=-1$; because the orthogonal
matrices form a Lie group and every $2\times 2$ orthogonal matrix with
determinant $-1$ is symmetric, it follows

$\bm{R}_{\nu}\bm{Q}=\bm{Q}\bm{R}_{\nu}^{\ast}.$ (D.62)

In particular,

$\displaystyle\bm{R}_{\nu-\nu_{\natural}}\begin{bmatrix}0&1\\\
1&0\end{bmatrix}$ $\displaystyle=\begin{bmatrix}0&1\\\
1&0\end{bmatrix}\bm{R}_{\nu-\nu_{\natural}}^{\ast},$

which, together with the fact that $X_{\natural}(s,t)=X_{\natural}(t,s)$,
implies that

$(X_{\natural}\circ\bm{\tau}_{\nu-\nu_{\natural}}-\bm{U}\bm{V}^{\ast})(s,t)=(X_{\natural}\circ\bm{\tau}_{\nu_{\natural}-\nu}-\bm{V}\bm{U}^{\ast})(t,s).$

Applying this to D.61 and unwinding the preceding steps implies immediately

$\left\langle\left[\varphi_{2\sigma^{2}}\ast\left(X_{\natural}\circ\bm{\tau}_{\nu-\nu_{\natural}}-\bm{U}\bm{V}^{\ast}\right)\right][f],g\right\rangle_{L^{2}(\mathbb{R})}=\left\langle\left[\varphi_{2\sigma^{2}}\ast\left(X_{\natural}\circ\bm{\tau}_{\nu_{\natural}-\nu}-\bm{V}\bm{U}^{\ast}\right)\right][g],f\right\rangle_{L^{2}(\mathbb{R})},$

which implies the claimed expression for the gradients with respect to
$\bm{V}$. The gradient with respect to $\nu$ is a similar calculation with the
chain rule, but involves some simplifications so we reproduce it here. From
the chain rule, for any $\Delta\nu\in\mathbb{R}$ we have for the differential

$\displaystyle\mathop{}\\!\mathrm{d}_{\nu}[\mathcal{L}^{\sigma}(\,\cdot\,,\bm{U},\bm{V})](\Delta\nu)$
$\displaystyle=\left\langle\varphi_{\sigma^{2}}\ast\left(X_{\natural}\circ\bm{\tau}_{\nu-\nu_{\natural}}-\bm{U}\bm{V}^{\ast}\right),{\left.\kern-1.2pt\frac{\partial}{\partial
t}\vphantom{\big{|}}\right|_{t=0}}[X_{\natural}\circ\bm{\tau}_{\nu+t\Delta\nu-\nu_{\natural}}]\right\rangle_{L^{2}(\mathbb{R}^{2})}$
$\displaystyle=\left\langle\varphi_{\sigma^{2}}\ast\left(X_{\natural}\circ\bm{\tau}_{\nu-\nu_{\natural}}-\bm{U}\bm{V}^{\ast}\right),\left\langle\nabla_{\bm{x}}[\varphi_{\sigma^{2}}\ast
X_{\natural}]\circ\bm{\tau}_{\nu-\nu_{\natural}},\dot{\bm{R}}_{\nu-\nu_{\natural}}(\,\cdot\,)\right\rangle_{\ell^{2}}\right\rangle_{L^{2}(\mathbb{R}^{2})}\Delta\nu,$
(D.63)

where $\dot{\bm{R}}_{\nu}$ is the elementwise derivative of the expression in
D.2 for $\bm{R}_{\nu}$, which evaluates as

$\displaystyle\dot{\bm{R}}_{\nu}$
$\displaystyle=\begin{bmatrix}-\sin\nu&-\cos\nu\\\
\cos\nu&-\sin\nu\end{bmatrix}$
$\displaystyle=\begin{bmatrix}\cos\nu&-\sin\nu\\\
\sin\nu&\cos\nu\end{bmatrix}\begin{bmatrix}0&-1\\\ 1&0\end{bmatrix}$
$\displaystyle=\bm{R}_{\nu}\begin{bmatrix}0&-1\\\ 1&0\end{bmatrix}.$

Note that the expression in the $\ell^{2}$ inner product in D.63 is a function
of $\bm{x}\in\mathbb{R}^{2}$. In particular, the function

$\bm{x}\mapsto\left\langle\bm{R}_{\nu-\nu_{\natural}}^{\ast}\nabla_{\bm{x}}[\varphi_{\sigma^{2}}\ast
X_{\natural}]\circ\bm{\tau}_{\nu-\nu_{\natural}}(\bm{x}),\begin{bmatrix}0&-1\\\
1&0\end{bmatrix}\bm{x}\right\rangle_{\ell^{2}}$

gives the rotational component (tangential to the co-incident circle centered
at the origin) of the rotated gradient vector field of
$\varphi_{\sigma^{2}}\ast X_{\natural}$ at the point $\bm{x}$. This gives the
expression

$\nabla_{\nu}\mathcal{L}^{\sigma}(\nu,\bm{U},\bm{V})=\left\langle\varphi_{\sigma^{2}}\ast\left(X_{\natural}\circ\bm{\tau}_{\nu-\nu_{\natural}}-\bm{U}\bm{V}^{\ast}\right),\left\langle\bm{R}_{\nu-\nu_{\natural}}^{\ast}\nabla_{\bm{x}}[\varphi_{\sigma^{2}}\ast
X_{\natural}]\circ\bm{\tau}_{\nu-\nu_{\natural}},\begin{bmatrix}0&-1\\\
1&0\end{bmatrix}(\,\cdot\,)\right\rangle_{\ell^{2}}\right\rangle_{L^{2}(\mathbb{R}^{2})}.$

Using the commutation relationship D.31 and a unitary change of variables
$\bm{x}\mapsto\bm{\tau}_{\nu_{\natural}-\nu}(\bm{x})$, the previous expression
implies

$\nabla_{\nu}\mathcal{L}^{\sigma}(\nu,\bm{U},\bm{V})=\left\langle\varphi_{\sigma^{2}}\ast\left(X_{\natural}-\bm{U}\bm{V}^{\ast}\circ\bm{\tau}_{\nu_{\natural}-\nu}\right),\left\langle\nabla_{\bm{x}}[\varphi_{\sigma^{2}}\ast
X_{\natural}],\begin{bmatrix}0&-1\\\
1&0\end{bmatrix}(\,\cdot\,)\right\rangle_{\ell^{2}}\right\rangle_{L^{2}(\mathbb{R}^{2})}.$

As in Lemma D.8, let $\mathcal{C}(\bm{x})$ denote the function of $\bm{x}$
encompassed by the $\ell^{2}$ inner product. By Lemma D.8, we have that
$\mathcal{C}(s,t)=-\mathcal{C}(t,s)$, whereas by D.31 we have that
$(\varphi_{\sigma^{2}}\ast X_{\natural})(s,t)=(\varphi_{\sigma^{2}}\ast
X_{\natural})(t,s)$. It follows that these two functions are orthogonal over
$L^{2}(\mathbb{R}^{2})$, so that in particular

$\nabla_{\nu}\mathcal{L}^{\sigma}(\nu,\bm{U},\bm{V})=-\left\langle\varphi_{\sigma^{2}}\ast\left(\bm{U}\bm{V}^{\ast}\circ\bm{\tau}_{\nu_{\natural}-\nu}\right),\left\langle\nabla_{\bm{x}}[\varphi_{\sigma^{2}}\ast
X_{\natural}],\begin{bmatrix}0&-1\\\
1&0\end{bmatrix}(\,\cdot\,)\right\rangle_{\ell^{2}}\right\rangle_{L^{2}(\mathbb{R}^{2})},$

as claimed. ∎

######  Lemma D.8.

Let

$\mathcal{C}(\bm{x})=\left\langle\nabla_{\bm{x}}[\varphi_{\sigma^{2}}\ast
X_{\natural}](\bm{x}),\begin{bmatrix}0&-1\\\
1&0\end{bmatrix}\bm{x}\right\rangle_{\ell^{2}}$

denote the rotational component of the gradient vector field of the smoothed
template. Let $\bm{Q}\in\mathrm{O}(2)$ satisfy $\det(\bm{Q})=-1$, and suppose
that $\bm{Q}$ is a symmetry of the square template $X_{\natural}$: in
particular

$\bm{Q}\in\left\\{\begin{bmatrix}1&0\\\
0&-1\end{bmatrix},\begin{bmatrix}-1&0\\\
0&1\end{bmatrix},\begin{bmatrix}0&1\\\ 1&0\end{bmatrix},\begin{bmatrix}0&-1\\\
-1&0\end{bmatrix}\right\\}$ (D.64)

(this is the subgroup of $\mathsf{D}_{4}$ consisting of symmetries of
determinant $-1$). Then one has

$\mathcal{C}(\bm{Q}\bm{x})=-\mathcal{C}(\bm{x}).$

###### Proof.

With D.2, we can write

$\mathcal{C}(\bm{x})=\left\langle\nabla_{\bm{x}}[\varphi_{\sigma^{2}}\ast
X_{\natural}](\bm{x}),\bm{R}_{\pi/2}\bm{x}\right\rangle_{\ell^{2}}.$

For $\bm{Q}$ as in D.64 and using D.62, we have

$\displaystyle\mathcal{C}(\bm{Q}\bm{x})$
$\displaystyle=\left\langle\nabla_{\bm{x}}[\varphi_{\sigma^{2}}\ast
X_{\natural}](\bm{Q}\bm{x}),\bm{Q}\bm{R}_{-\pi/2}\bm{x}\right\rangle_{\ell^{2}}$
$\displaystyle=-\left\langle\nabla_{\bm{x}}[\varphi_{\sigma^{2}}\ast
X_{\natural}](\bm{Q}\bm{x}),\bm{Q}\bm{R}_{\pi/2}\bm{x}\right\rangle_{\ell^{2}}$
$\displaystyle=-\left\langle\bm{Q}\nabla_{\bm{x}}[\varphi_{\sigma^{2}}\ast
X_{\natural}](\bm{Q}\bm{x}),\bm{R}_{\pi/2}\bm{x}\right\rangle_{\ell^{2}}.$
(D.65)

The second line uses D.2, and the third uses that every member of D.64 is
symmetric. By Young’s inequality, we have

$\nabla_{\bm{x}}[\varphi_{\sigma^{2}}\ast
X_{\natural}]=\nabla_{\bm{x}}[\varphi_{\sigma^{2}}]\ast X_{\natural},$

and because $\varphi_{\sigma^{2}}$ is invariant to all orthogonal matrices,
its gradient is equivariant with respect to $\mathrm{O}(2)$, so in particular

$\displaystyle(\bm{Q}\nabla_{\bm{x}}[\varphi_{\sigma^{2}}]\ast
X_{\natural})(\bm{Q}\bm{x})$
$\displaystyle=\int_{\mathbb{R}^{2}}X_{\natural}(\bm{x}^{\prime})\bm{Q}\nabla_{\bm{x}}[\varphi_{\sigma^{2}}](\bm{Q}\bm{x}-\bm{x}^{\prime})\mathop{}\\!\mathrm{d}\bm{x}^{\prime}$
$\displaystyle=\int_{\mathbb{R}^{2}}X_{\natural}(\bm{x}^{\prime})\nabla_{\bm{x}}[\varphi_{\sigma^{2}}](\bm{x}-\bm{Q}\bm{x}^{\prime})\mathop{}\\!\mathrm{d}\bm{x}^{\prime}$
$\displaystyle=\int_{\mathbb{R}^{2}}X_{\natural}(\bm{Q}\bm{x}^{\prime})\nabla_{\bm{x}}[\varphi_{\sigma^{2}}](\bm{x}-\bm{x}^{\prime})\mathop{}\\!\mathrm{d}\bm{x}^{\prime}$
$\displaystyle=\int_{\mathbb{R}^{2}}X_{\natural}(\bm{x}^{\prime})\nabla_{\bm{x}}[\varphi_{\sigma^{2}}](\bm{x}-\bm{x}^{\prime})\mathop{}\\!\mathrm{d}\bm{x}^{\prime}$
$\displaystyle=(\nabla_{\bm{x}}[\varphi_{\sigma^{2}}]\ast
X_{\natural})(\bm{x}).$

Above, the third line uses an orthogonal change of variables in the
convolution integral, and the fourth uses that $\bm{Q}$ is a symmetry of
$X_{\natural}$. By D.65, we have that
$\mathcal{C}(\bm{Q}\bm{x})=-\mathcal{C}(\bm{x})$.

∎

######  Lemma D.9.

The following symmetry properties hold:

  1. 1.

For any $u\in L^{2}(\mathbb{R})$, $\sigma>0$, the objective
$\nu\mapsto\mathcal{L}^{\sigma}(\nu,u)$ is $\pi/2$-periodic;

  2. 2.

For any $u\in L^{2}(\mathbb{R})$, $\sigma>0$, and
$-\pi/4\leq\nu-\nu_{\natural}\leq\pi/4$, one has
$\mathcal{L}^{\sigma}(\nu-\nu_{\natural},u)=\mathcal{L}^{\sigma}(\nu_{\natural}-\nu,u)$.

Moreover, consider the alignment gradient at the nominal rough initial
representation:

$\nu\mapsto\nabla_{\nu}\mathcal{L}^{\sigma}(\nu,\bar{u}_{\mathrm{rough}}).$

where the nominal rough initial representation is defined as

$\bar{u}_{\mathrm{rough}}(s)=\frac{2}{\sqrt{\pi}}{\mathds{1}}_{\lvert
s\rvert\leq 1}\cos(\pi s/2).$

Suppose that $\alpha=\tfrac{1}{\sqrt{2}}$. Then for any $\nu$,

$\left\lvert\nabla_{\nu}\mathcal{L}^{\sigma}(\nu,\bar{u}_{\mathrm{rough}})\right\rvert\leq
256\lvert\sin(\nu-\nu_{\natural})\rvert.$

If, in addition, $\sigma\leq 10^{-3}$, then if $\nu$ is sufficiently far from
maximizers, i.e., if

$\left\lvert\left(\nu-\nu_{\natural}+\frac{\pi}{4}\mod\frac{\pi}{2}\right)-\frac{\pi}{4}\right\rvert\leq\frac{\pi}{7},$
(D.66)

one has

$\operatorname{sign}\left(\left(\nu-\nu_{\natural}+\frac{\pi}{4}\mod\frac{\pi}{2}\right)-\frac{\pi}{4}\right)\cdot\nabla_{\nu}\mathcal{L}^{\sigma}(\nu,\bar{u}_{\mathrm{rough}})\geq
c_{0}\sin\left(\left\lvert\left(\nu-\nu_{\natural}+\frac{\pi}{4}\mod\frac{\pi}{2}\right)-\frac{\pi}{4}\right\rvert\right)$

for an absolute constant $c_{0}>0$. In particular, the gradient is nonnegative
when $\nu-\nu_{\natural}\mod\pi/2\leq\pi/7$, and nonpositive when
$\nu-\nu_{\natural}\mod\pi/2\geq\pi/2-\pi/7$.

###### Proof.

The proof exploits heavily the $\mathsf{D}_{4}$ symmetries of the square
template $X_{\natural}$ (c.f. Lemma D.8) and of the initialization
$\bar{u}_{\mathrm{rough}}\bar{u}_{\mathrm{rough}}^{\ast}$. Before proceeding
with the analysis of the gradient, we go through some simplifying reductions
based on symmetry. First, by the definition of the loss in D.34, it suffices
to analyze the case where $\nu_{\natural}=0$, and perform the substitution
$\nu\mapsto\nu-\nu_{\natural}$ in all results obtained. Next, notice that
because $\bm{R}_{\nu+\pi/2}=\bm{R}_{\pi/2}\bm{R}_{\nu}$ for any $\nu$
(following the notation of D.2), one has
$X_{\natural}(\bm{R}_{\nu+\pi/2}\bm{x})=X_{\natural}(\bm{R}_{\nu}\bm{x})$ for
any $\bm{x}$ by symmetry, which implies (c.f. D.34) that
$\mathcal{L}^{\sigma}(\nu+\pi/2,u)=\mathcal{L}^{\sigma}(\nu,u)$ for any
$\nu,u$. Moreover, by D.62, one has $\bm{R}_{-\nu}=\bm{Q}\bm{R}_{\nu}\bm{Q}$,
where

$\bm{Q}=\begin{bmatrix}0&1\\\ 1&0\end{bmatrix}.$

We have that $\bm{Q}$ is an orthogonal matrix with determinant $-1$; writing
$\bm{\tau}_{\bm{Q}}:\mathbb{R}^{2}\to\mathbb{R}^{2}$ for its induced
transformation, we have again by symmetry that
$X_{\natural}\circ\bm{\tau}_{\pi/2-\nu}(\bm{x})=X_{\natural}\circ\bm{\tau}_{\nu}\circ\bm{\tau}_{\bm{Q}}$.
Applying then D.31 (notice that the calculation does not use the fact that
$\det(\bm{R}_{\nu})=1$, and in fact any orthogonal matrix yields the same
conclusion) together with a unitary change of coordinates, we obtain that

$\mathcal{L}^{\sigma}(\pi/2-\nu,\bar{u}_{\mathrm{rough}})=\frac{1}{2}\left\lVert\varphi_{\sigma^{2}}\ast\left(X_{\natural}\circ\bm{\tau}_{\nu}-\bar{u}_{\mathrm{rough}}\bar{u}_{\mathrm{rough}}^{\ast}\circ\bm{\tau}_{\bm{Q}}\right)\right\rVert_{L^{2}}^{2},$

since $\bm{Q}^{\ast}=\bm{Q}$. But since $\bm{\tau}_{\bm{Q}}(s,t)=(t,s)$, it
follows from symmetry that
$\mathcal{L}^{\sigma}(\pi/2-\nu,\bar{u}_{\mathrm{rough}})=\mathcal{L}^{\sigma}(\nu,\bar{u}_{\mathrm{rough}})$.
We have thus shown that
$\nu\mapsto\mathcal{L}^{\sigma}(\nu,\bar{u}_{\mathrm{rough}})$ is

  1. 1.

$\pi/2$-periodic;

  2. 2.

on $[0,\pi/2]$, symmetric about $\pi/4$.

It therefore suffices to assume that $0\leq\nu\leq\pi/4$ in the sequel, since
conclusions on this interval can be translated to all $\nu\in\mathbb{R}$ as
stated in the statement of the result by these symmetry properties.

We proceed to estimate the gradient

$\nabla_{\nu}\mathcal{L}^{\sigma}(\nu,\bar{u}_{\mathrm{rough}})=-\left\langle\underbrace{\varphi_{\sigma^{2}}\mathbin{\ast}\left(\bar{u}_{\mathrm{rough}}\bar{u}_{\mathrm{rough}}^{\ast}\circ\bm{\tau}_{-\nu}\right)}_{\mathcal{R}},\mathcal{C}\right\rangle_{L^{2}(\mathbb{R}^{2})}$

under the preceding assumptions, where $\mathcal{C}$ is defined as in Lemma
D.8. First, we reduce the $L^{2}$ integral in the expression for a gradient
into a difference of integrals over a ‘fundamental domain’ depending on the
$\mathcal{D}_{4}$ symmetries of $X_{\natural}$ and the initialization; this
expression will be useful for upper and lower bounds. Then, we will establish
the lower bound, which is more technical, before concluding with the upper
bound. For $(\bm{\kappa},\pi)\in\\{-1,1\\}^{2}\times\mathrm{P}(2)$, where
$\mathrm{P}(2)$ is the set of permutations on $2$ elements, we consider the
“wedge” domains

$C_{\bm{\kappa},\pi}=\left\\{\bm{x}=(s,t)\in\mathbb{R}^{2}\nonscript\>\middle|\allowbreak\nonscript\>\mathopen{}\kappa_{1}s\geq
0,\kappa_{2}t\geq
0,\pi_{1}(s,\kappa_{1}\kappa_{2}t)\geq\pi_{2}(s,\kappa_{1}\kappa_{2}t)\right\\}.$

Intuitively, in the third constraint, $\pi$ governs the “direction” of the
inequality, and $\kappa_{1}\kappa_{2}$ selects the proper subspace to reflect
about. One notes that
$\cup_{(\bm{\kappa},\pi)\in\\{-1,1\\}^{2}\times\mathrm{P}(2)}C_{\bm{\kappa},\pi}=\mathbb{R}^{2}$,
and if $(\bm{\kappa},\pi)\neq(\bm{\kappa}^{\prime},\pi^{\prime})$ then
$C_{\bm{\kappa},\pi}\cap C_{\bm{\kappa}^{\prime},\pi^{\prime}}$ has zero
Lebesgue measure. Because $\mathcal{C}$ and $\mathcal{R}$ are smooth
functions, it follows

$\displaystyle\nabla_{\nu}\mathcal{L}^{\sigma}(\nu,\bar{u}_{\mathrm{rough}})$
$\displaystyle=-\left\langle\mathcal{R}\left(\sum_{(\bm{\kappa},\pi)\in\\{-1,1\\}^{2}\times\mathrm{P}(2)}{\mathds{1}}_{C_{\bm{\kappa},\pi}}\right),\mathcal{C}\right\rangle_{L^{2}}$
$\displaystyle=\sum_{(\bm{\kappa},\pi)\in\\{-1,1\\}^{2}\times\mathrm{P}(2)}-\left\langle\mathcal{R}{\mathds{1}}_{C_{\bm{\kappa},\pi}},\mathcal{C}\right\rangle_{L^{2}}.$

Recall, following D.31, that we can freely interchange the order of gaussian
smoothing and rotation in the expression for
$\mathcal{L}^{\sigma}(\nu,\bar{u}_{\mathrm{rough}})$. Since
$\bar{u}_{\mathrm{rough}}(s)=\bar{u}_{\mathrm{rough}}(-s)$ for any
$s\in\mathbb{R}$, by the argument above applied to $X_{\natural}$ we have that
for any $\nu$

$\displaystyle\mathcal{R}\circ\bm{\tau}_{\pm\pi/2}$
$\displaystyle=\left(\varphi_{\sigma^{2}}\mathbin{\ast}\left(\bar{u}_{\mathrm{rough}}\bar{u}_{\mathrm{rough}}^{\ast}\circ\bm{\tau}_{-\nu}\right)\right)\circ\bm{\tau}_{\pm\pi/2}$
$\displaystyle=\varphi_{\sigma^{2}}\mathbin{\ast}\left(\bar{u}_{\mathrm{rough}}\bar{u}_{\mathrm{rough}}^{\ast}\circ\bm{\tau}_{\pm\pi/2}\circ\bm{\tau}_{-\nu}\right)$
$\displaystyle=\varphi_{\sigma^{2}}\mathbin{\ast}\left(\bar{u}_{\mathrm{rough}}\bar{u}_{\mathrm{rough}}^{\ast}\circ\bm{\tau}_{-\nu}\right)$
$\displaystyle=\mathcal{R}.$

Meanwhile, we note that

$\bm{R}_{\pi/2}=\begin{bmatrix}0&-1\\\ 1&0\end{bmatrix}=\begin{bmatrix}0&1\\\
1&0\end{bmatrix}\begin{bmatrix}1&0\\\
0&-1\end{bmatrix};\quad\bm{R}_{-\pi/2}=\begin{bmatrix}0&1\\\
-1&0\end{bmatrix}=\begin{bmatrix}0&1\\\ 1&0\end{bmatrix}\begin{bmatrix}-1&0\\\
0&1\end{bmatrix},$

so by Lemma D.8, $\mathcal{C}\circ\bm{\tau}_{\pm\pi/2}=\mathcal{C}$. Thus,
changing coordinates in the $L^{2}$ integral, we get

$\nabla_{\nu}\mathcal{L}^{\sigma}(\nu,\bar{u}_{\mathrm{rough}})=-4\left\langle\mathcal{R}\left({\mathds{1}}_{C_{\\{1,-1\\},\operatorname{\mathrm{Id}}}}+{\mathds{1}}_{C_{\\{1,1\\},\operatorname{\mathrm{Id}}}}\right),\mathcal{C}\right\rangle_{L^{2}},$

where we recall

$C_{\\{1,-1\\},\operatorname{\mathrm{Id}}}=\left\\{\bm{x}=(s,t)\in\mathbb{R}^{2}\nonscript\>\middle|\allowbreak\nonscript\>\mathopen{}s\geq
0,t\leq 0,s\geq-t\right\\},\quad
C_{\\{1,1\\},\operatorname{\mathrm{Id}}}=\left\\{\bm{x}=(s,t)\in\mathbb{R}^{2}\nonscript\>\middle|\allowbreak\nonscript\>\mathopen{}s\geq
0,t\geq 0,s\geq t\right\\}.$ (D.67)

By another change of coordinates and Lemma D.8, we then have in addition

$\nabla_{\nu}\mathcal{L}^{\sigma}(\nu,\bar{u}_{\mathrm{rough}})\geq-4\int_{\\{0\leq
t\leq
s\\}}\left(\mathcal{R}(s,t)-\mathcal{R}(s,-t)\right)\mathcal{C}(s,t)\mathop{}\\!\mathrm{d}s\mathop{}\\!\mathrm{d}t$
(D.68)

Next, we control $\mathcal{R}(s,t)-\mathcal{R}(s,-t)$ using the geometry of
the rough factorization
$\bar{u}_{\mathrm{rough}}\bar{u}_{\mathrm{rough}}^{\ast}$; we will then
conclude the bound from D.68. First, by linearity and D.31, we have

$\displaystyle\mathcal{R}(s,t)-\mathcal{R}(s,-t)$
$\displaystyle=\varphi_{\sigma^{2}}\mathbin{\ast}\left(\bar{u}_{\mathrm{rough}}\bar{u}_{\mathrm{rough}}^{\ast}\circ\bm{\tau}_{-\nu}\right)(s,t)-\varphi_{\sigma^{2}}\mathbin{\ast}\left(\bar{u}_{\mathrm{rough}}\bar{u}_{\mathrm{rough}}^{\ast}\circ\bm{\tau}_{-\nu}\right)(s,-t)$
$\displaystyle=\varphi_{\sigma^{2}}\mathbin{\ast}\left(\bar{u}_{\mathrm{rough}}\bar{u}_{\mathrm{rough}}^{\ast}\circ\bm{\tau}_{-\nu}-\bar{u}_{\mathrm{rough}}\bar{u}_{\mathrm{rough}}^{\ast}\circ\bm{\tau}_{-\nu}\circ\bm{\tau}_{\bm{Q}}\right)(s,t),$
(D.69)

where $\bm{Q}$ is the matrix representation of the orthogonal transformation
$(s,t)\mapsto(s,-t)$. Gaussian smoothing is nonnegativity-preserving, so
developing a lower bound on the difference
$\mathcal{R}(s,t)-\mathcal{R}(s,-t)$ can be done by developing a lower bound
on the parenthesized term above. By D.62 and symmetry, we have

$\bar{u}_{\mathrm{rough}}\bar{u}_{\mathrm{rough}}^{\ast}\circ\bm{\tau}_{-\nu}\circ\bm{\tau}_{\bm{Q}}=\bar{u}_{\mathrm{rough}}\bar{u}_{\mathrm{rough}}^{\ast}\circ\bm{\tau}_{\nu}.$
(D.70)

Applying the first conclusion in Lemma D.12 together with Lemma D.11, it
follows that

$-(\mathcal{R}(s,t)-\mathcal{R}(s,-t))\mathcal{C}(s,t)\geq 0$

for every $0\leq t\leq s$.This means that we can obtain a lower bound for the
RHS of D.68 by integrating over a subset of the domain $\\{0\leq t\leq s\\}$.
When $\sigma$ is small, the field $\mathcal{C}$ concentrates around the
boundary of the square template $X_{\natural}$; we will therefore obtain a
lower bound for the gradient by integrating in a small strip around this
region. To this end, the second conclusion in Lemma D.12 gives the following
quantitative bound, valid for $0\leq t\leq s\leq 1$ and all
$0\leq\nu\leq\pi/7$:

$\bar{u}_{\mathrm{rough}}\bar{u}_{\mathrm{rough}}^{\ast}\circ\bm{\tau}_{\nu}(\bm{x})-\bar{u}_{\mathrm{rough}}\bar{u}_{\mathrm{rough}}^{\ast}\circ\bm{\tau}_{-\nu}(\bm{x})\geq\frac{7\sin\nu}{1000}{\mathds{1}}_{-0.137\leq
t-\tfrac{1}{\sqrt{2}}\leq-0.127}{\mathds{1}}_{-0.001\leq
s-\tfrac{1}{\sqrt{2}}\leq 0.001}.$

Since we are considering a regime with $\sigma$ small, it is now reasonable to
simplify this estimate further by worst-casing the smoothing that connects it
to $\mathcal{R}$. Because this indicator is a box in the $(s,t)$ plane, its
smoothed version is a product of smoothed indicators for compact connected
intervals in $\mathbb{R}$. If $I=[-a,a]$ is such an interval (because
convolution commutes with translations, it will be sufficient to consider such
a centered interval), we have (see the derivative calculations at the start of
the proof of Lemma D.13) that
$\varphi_{\sigma^{2}}\mathbin{\ast}{\mathds{1}}_{I}(x)$ is decreasing (resp.
increasing) for $x\geq 0$ (resp. $x\leq 0$). Hence the minimum value taken by
$\varphi_{\sigma^{2}}\mathbin{\ast}{\mathds{1}}_{I}$ among those $x\in I$ is
attained at $x\in\\{\pm a\\}$, where

$\displaystyle{\mathds{1}}_{I}\mathbin{\ast}\varphi_{\sigma^{2}}(a)=\int_{-a}^{a}\varphi_{\sigma^{2}}(x-a)\mathop{}\\!\mathrm{d}x$
$\displaystyle=\int_{0}^{2a}\varphi_{\sigma^{2}}(x)\mathop{}\\!\mathrm{d}x$
$\displaystyle=\frac{1}{2}-\int_{2a}^{\infty}\varphi_{\sigma^{2}}(x)\mathop{}\\!\mathrm{d}x$
$\displaystyle\geq\frac{1}{2}-\frac{\sigma}{2a\sqrt{2\pi}}e^{-2a^{2}/\sigma^{2}},$

by the standard estimate for the gaussian tail integral. Thus, as soon as
$\sigma\leq 2a$, one has

${\mathds{1}}_{I}\mathbin{\ast}\varphi_{\sigma^{2}}(a)\geq\frac{1}{4},$ (D.71)

which shows that
${\mathds{1}}_{I}\mathbin{\ast}\varphi_{\sigma^{2}}\geq\tfrac{1}{4}{\mathds{1}}_{I}$
if $\sigma\leq 2a$. Applying this to our lower bound, it follows that if
$\sigma\leq\tfrac{1}{500}$, we have

$-\left(\mathcal{R}(s,t)-\mathcal{R}(s,-t)\right)\geq\frac{7\sin\nu}{16000}{\mathds{1}}_{-0.137\leq
t-\tfrac{1}{\sqrt{2}}\leq-0.127}{\mathds{1}}_{-0.001\leq
s-\tfrac{1}{\sqrt{2}}\leq 0.001}.$

Plugging this bound into D.68 gives

$\nabla_{\nu}\mathcal{L}^{\sigma}(\nu,\bar{u}_{\mathrm{rough}})\geq\frac{7\sin\nu}{4000}\iint_{\begin{subarray}{c}-0.001\leq
s-1/\sqrt{2}\leq 0.001,\\\ -0.137\leq
t-1/\sqrt{2}\leq-0.127\end{subarray}}\mathcal{C}(s,t)\mathop{}\\!\mathrm{d}s\mathop{}\\!\mathrm{d}t.$
(D.72)

The remainder of the proof is a relatively tedious calculation over this
domain of integration. We make use of the expressions for $\mathcal{C}$
derived in Lemma D.11:

$\displaystyle\mathcal{C}(s,t)$
$\displaystyle=sf(s)f^{\prime}(t)-tf(t)f^{\prime}(s),\quad\text{where}$
$\displaystyle f(x)$
$\displaystyle=\frac{1}{\sqrt{2\pi\sigma^{2}}}\int_{-1/\sqrt{2}}^{1/\sqrt{2}}e^{-\tfrac{(x-x^{\prime})^{2}}{2\sigma^{2}}}\mathop{}\\!\mathrm{d}x^{\prime},\quad
x\in\mathbb{R};$ $\displaystyle f^{\prime}(x)$
$\displaystyle=\varphi_{\sigma^{2}}(x+\alpha)-\varphi_{\sigma^{2}}(x-\alpha).$

Moreover, we recall that $f^{\prime}(x)\geq 0$ if $x\geq 0$ and
$f^{\prime}(x)\leq 0$ if $x\leq 0$, as shown in the proof of Lemma D.11. We
have $\lvert sf(s)\rvert\leq 1$ when $s\leq 1$ by Young’s convolution
inequality, and

$\displaystyle f^{\prime}(t)$
$\displaystyle\geq-\varphi_{\sigma^{2}}(t-1/\sqrt{2})$
$\displaystyle\geq-\varphi_{\sigma^{2}}(-0.127)$
$\displaystyle\geq-\frac{1}{\sigma\sqrt{2\pi}}e^{-\tfrac{1}{128\sigma^{2}}}$

for $t$ in the region of integration. Similarly, for $t$ in the region of
integration

$\displaystyle tf(t)$
$\displaystyle\geq\left(\frac{1}{\sqrt{2}}-0.137\right)f(1/\sqrt{2}-0.127)$
$\displaystyle\geq\frac{1}{4}\left(\frac{1}{\sqrt{2}}-0.137\right),$

where the last line uses D.71. Finally, we have for $s$ in the domain of
integration

$\displaystyle f^{\prime}(s)$
$\displaystyle=\varphi_{\sigma^{2}}(s-1/\sqrt{2})-\varphi_{\sigma^{2}}(s+1/\sqrt{2})$
$\displaystyle\geq\varphi_{\sigma^{2}}(s-1/\sqrt{2})-\varphi_{\sigma^{2}}(\sqrt{2}-0.001)$
$\displaystyle\geq\varphi_{\sigma^{2}}(s-1/\sqrt{2})-\frac{1}{\sigma\sqrt{2\pi}}e^{-\tfrac{1}{2\sigma^{2}}}.$

Combining these, we have the lower bound (valid on the domain of integration
of our gradient lower bound)

$\displaystyle\mathcal{C}(s,t)$
$\displaystyle\geq\frac{1}{4}\left(\frac{1}{\sqrt{2}}-0.137\right)\left(\varphi_{\sigma^{2}}(s-1/\sqrt{2})-\frac{1}{\sigma\sqrt{2\pi}}e^{-\tfrac{1}{2\sigma^{2}}}\right)-\frac{1}{\sigma\sqrt{2\pi}}e^{-\tfrac{1}{128\sigma^{2}}}$
$\displaystyle\geq\frac{1}{8}\varphi_{\sigma^{2}}(s-1/\sqrt{2})-\frac{1}{\sigma\sqrt{\pi}}e^{-\tfrac{1}{128\sigma^{2}}}.$

Integrating the first term in this lower bound over the $s$ region gives, by a
change of coordinates,

$\displaystyle\int_{-0.001+1/\sqrt{2}}^{0.001+1/\sqrt{2}}\varphi_{\sigma^{2}}(s-1/\sqrt{2})\mathop{}\\!\mathrm{d}s$
$\displaystyle=\int_{-0.001}^{0.001}\varphi_{\sigma^{2}}(s)\mathop{}\\!\mathrm{d}s$
$\displaystyle=1-2\int_{0}^{0.001}\varphi_{\sigma^{2}}(s)\mathop{}\\!\mathrm{d}s$
$\displaystyle\geq
1-2\frac{\sigma}{10^{-3}\sqrt{2\pi}}e^{-10^{-6}/2\sigma^{2}},$

using also the gaussian tail estimate we applied above. Thus, as soon as
$\sigma\leq 10^{-3}$, we have

$\int_{-0.001+1/\sqrt{2}}^{0.001+1/\sqrt{2}}\varphi_{\sigma^{2}}(s-1/\sqrt{2})\mathop{}\\!\mathrm{d}s\geq\frac{1}{2},$

and under this constraint on $\sigma$, we have moreover from our previous
lower bound

$\int_{-0.001+1/\sqrt{2}}^{0.001+1/\sqrt{2}}\mathcal{C}(s,t)\mathop{}\\!\mathrm{d}s\geq\frac{1}{20}.$

Integrating over the region of $t$ adds only an additional constant multiple,
since this expression does not depend on $t$. Consequently, these calculations
together with D.72 imply the claimed lower bound.

We can obtain the claimed upper bound in a similar way. Since the lower bound
we have just established characterizes the sign of the gradient at all points
where $0\leq\nu\leq\pi/7$ (and similarly for negative $\nu$, by symmetry of
the objective), it suffices to simply control the magnitude of the gradient.
By D.68, D.69 and D.70, and $L^{1}$-$L^{\infty}$ control, we have

$\displaystyle\left\lvert\nabla_{\nu}\mathcal{L}^{\sigma}(\nu,\bar{u}_{\mathrm{rough}})\right\rvert$
$\displaystyle\leq 4\left(\sup_{0\leq t\leq
s}\,\left\lvert\varphi_{\sigma^{2}}\mathbin{\ast}\left(\bar{u}_{\mathrm{rough}}\bar{u}_{\mathrm{rough}}^{\ast}\circ\bm{\tau}_{-\nu}-\bar{u}_{\mathrm{rough}}\bar{u}_{\mathrm{rough}}^{\ast}\circ\bm{\tau}_{\nu}\right)(s,t)\right\rvert\right)\int_{\\{s\geq
0,t\geq 0,s\geq
t\\}}\left\lvert\mathcal{C}(s,t)\right\rvert\mathop{}\\!\mathrm{d}s\mathop{}\\!\mathrm{d}t$
$\displaystyle\leq 4\left(\sup_{0\leq t\leq
s}\,\left\lvert\bar{u}_{\mathrm{rough}}\bar{u}_{\mathrm{rough}}^{\ast}\circ\bm{\tau}_{-\nu}-\bar{u}_{\mathrm{rough}}\bar{u}_{\mathrm{rough}}^{\ast}\circ\bm{\tau}_{\nu}\right\rvert(s,t)\right)\int_{\\{0\leq
t\leq
s\\}}\left\lvert\mathcal{C}(s,t)\right\rvert\mathop{}\\!\mathrm{d}s\mathop{}\\!\mathrm{d}t,$

where we use Young’s convolution inequality in the second line. By the
expressions given above and the triangle inequality, we have

$\displaystyle\int_{\\{0\leq t\leq
s\\}}\left\lvert\mathcal{C}(s,t)\right\rvert\mathop{}\\!\mathrm{d}s\mathop{}\\!\mathrm{d}t$
$\displaystyle\leq\int_{\\{0\leq t\leq s\\}}\left(\left\lvert
sf(s)f^{\prime}(t)\right\rvert+\left\lvert
tf(t)f^{\prime}(s)\right\rvert\right)\mathop{}\\!\mathrm{d}s\mathop{}\\!\mathrm{d}t$
$\displaystyle\leq 2\int_{\mathbb{R}^{2}}\left(\left\lvert
sf(s)f^{\prime}(t)\right\rvert\right)\mathop{}\\!\mathrm{d}s\mathop{}\\!\mathrm{d}t$
$\displaystyle=2\left(\int_{\mathbb{R}}\left\lvert
sf(s)\right\rvert\mathop{}\\!\mathrm{d}s\right)\left(\int_{\mathbb{R}}\lvert
f^{\prime}(t)\rvert\mathop{}\\!\mathrm{d}t\right),$

where the third line uses Fubini’s theorem. Because $f^{\prime}$ is a
difference of two gaussians, the integral of its magnitude is no larger than
$2$. Meanwhile, we have by Fubini’s theorem

$\displaystyle\int_{\mathbb{R}}\lvert sf(s)\rvert\mathop{}\\!\mathrm{d}s$
$\displaystyle=\int_{-1/\sqrt{2}}^{1/\sqrt{2}}\int_{\mathbb{R}}\lvert
s\rvert\varphi_{\sigma^{2}}(s-x)\mathop{}\\!\mathrm{d}s\mathop{}\\!\mathrm{d}x$
$\displaystyle=\int_{-1/\sqrt{2}}^{1/\sqrt{2}}\int_{\mathbb{R}}\lvert
s+x\rvert\varphi_{\sigma^{2}}(s)\mathop{}\\!\mathrm{d}s\mathop{}\\!\mathrm{d}x$
$\displaystyle\leq\int_{-1/\sqrt{2}}^{1/\sqrt{2}}(\lvert
x\rvert+\sqrt{2/\pi})\mathop{}\\!\mathrm{d}x$
$\displaystyle=\frac{1}{2}+\frac{2}{\sqrt{\pi}}.$

Thus

$\int_{\\{0\leq t\leq
s\\}}\left\lvert\mathcal{C}(s,t)\right\rvert\mathop{}\\!\mathrm{d}s\mathop{}\\!\mathrm{d}t\leq
8.$

Meanwhile, by definition (see Lemma D.9), $\bar{u}_{\mathrm{rough}}$ is a
$\sqrt{\pi}$-Lipschitz function of its argument, and is bounded by
$2/\sqrt{\pi}$; this means that
$\bar{u}_{\mathrm{rough}}\bar{u}_{\mathrm{rough}}^{\ast}:\mathbb{R}^{2}\to\mathbb{R}$
is a $2\sqrt{2}$-Lipschitz function of its argument with respect to the
$\ell^{2}$ metric on $\mathbb{R}^{2}$. Recalling moreover that
$\bar{u}_{\mathrm{rough}}$ is compactly supported on $[-1,1]$, it follows that
for any $\bm{x}=(s,t)$ at which
$\bar{u}_{\mathrm{rough}}\bar{u}_{\mathrm{rough}}^{\ast}\circ\bm{\tau}_{\pm\nu}$
is nonzero, we have

$\displaystyle\left\lvert\bar{u}_{\mathrm{rough}}\bar{u}_{\mathrm{rough}}^{\ast}\circ\bm{\tau}_{-\nu}(\bm{x})-\bar{u}_{\mathrm{rough}}\bar{u}_{\mathrm{rough}}^{\ast}\circ\bm{\tau}_{\nu}(\bm{x})\right\rvert$
$\displaystyle\leq
2\sqrt{2}\left\lVert\bm{\tau}_{-\nu}(\bm{x})-\bm{\tau}_{\nu}(\bm{x})\right\rVert_{2}$
$\displaystyle\leq
2\sqrt{2}\left\lVert\bm{R}_{-\nu}-\bm{R}_{\nu}\right\rVert\left\lVert\bm{x}\right\rVert_{2}$
$\displaystyle\leq 4\left\lVert\bm{R}_{-\nu}-\bm{R}_{\nu}\right\rVert.$

In the last two lines, we simply pass to the operator norm of the difference
of rotation matrices and then use that $\lVert\bm{x}\rVert_{\infty}\leq 1$. In
dimension two, we have the representation

$\bm{R}_{\nu}=(\cos\nu)\bm{I}+(\sin\nu)\begin{bmatrix}0&-1\\\
1&0\end{bmatrix},$

and each of these matrices (without the prefactors) is orthogonal, hence has
unit operator norm. Thus, the triangle inequality gives

$\left\lVert\bm{R}_{-\nu}-\bm{R}_{\nu}\right\rVert\leq
2\left\lvert\sin\nu\right\rvert.$

since $\sin$ and $\cos$ are both $1$-Lipschitz. Combining, this shows

$\left\lvert\nabla_{\nu}\mathcal{L}^{\sigma}(\nu,\bar{u}_{\mathrm{rough}})\right\rvert\leq
256\sin\nu.$

∎

######  Lemma D.10.

Consider the roughly-localized alignment iteration D.41. Suppose

$\left\lVert
u_{\mathrm{rough}}-\bar{u}_{\mathrm{rough}}\right\rVert_{L^{2}(\mathbb{R})}\leq\frac{2}{\sqrt{\pi}},$

where the nominal rough initial representation $\bar{u}_{\mathrm{rough}}$ is
defined as in Lemma D.9. For any $\sigma\leq\tfrac{1}{100}$ and
$\alpha=\tfrac{1}{\sqrt{2}}$, the following holds:

  1. 1.

The functions $\nabla_{\nu}\mathcal{L}^{\sigma}(\,\cdot\,,u_{\mathrm{rough}})$
and $\nabla_{\nu}\mathcal{L}^{\sigma}(\,\cdot\,,\bar{u}_{\mathrm{rough}})$
satisfy

$\displaystyle\left\lVert\nabla_{\nu}\mathcal{L}^{\sigma}(\,\cdot\,,\bar{u}_{\mathrm{rough}})\right\rVert_{\mathrm{Lip}}$
$\displaystyle\leq\frac{4}{\pi\sigma^{2}},$
$\displaystyle\left\lVert\nabla_{\nu}\mathcal{L}^{\sigma}(\,\cdot\,,u_{\mathrm{rough}})\right\rVert_{\mathrm{Lip}}$
$\displaystyle\leq\frac{4}{\sigma^{2}}\left(\frac{1}{\pi}+\frac{2\left\lVert
u_{\mathrm{rough}}-\bar{u}_{\mathrm{rough}}\right\rVert_{L^{2}(\mathbb{R})}}{\sqrt{\pi}}\right),$

where $\lVert\>\cdot\>\rVert_{\mathrm{Lip}}$ denotes the Lipschitz seminorm;

  2. 2.

We have the gradient estimate

$\left\lvert\nabla_{\nu}\mathcal{L}^{\sigma}(\,\cdot\,,u_{\mathrm{rough}})-\nabla_{\nu}\mathcal{L}^{\sigma}(\,\cdot\,,\bar{u}_{\mathrm{rough}})\right\rvert\leq\frac{8}{\sqrt{\pi}\sigma^{2}}\left\lVert\bar{u}_{\mathrm{rough}}-u_{\mathrm{rough}}\right\rVert_{L^{2}(\mathbb{R})},$

as well as the squared-gradient estimate

$\left\lvert\left(\nabla_{\nu}\mathcal{L}^{\sigma}(\,\cdot\,,u_{\mathrm{rough}})\right)^{2}-\left(\nabla_{\nu}\mathcal{L}^{\sigma}(\,\cdot\,,\bar{u}_{\mathrm{rough}})\right)^{2}\right\rvert\leq\frac{512}{\pi^{3/2}\sigma^{4}}\left\lVert\bar{u}_{\mathrm{rough}}-u_{\mathrm{rough}}\right\rVert_{L^{2}(\mathbb{R})}.$

###### Proof.

We will prove the first assertion first. We recall from Lemma D.7 that for any
$\nu\in\mathbb{R}$, $u\in L^{2}(\mathbb{R})$,

$\nabla_{\nu}\mathcal{L}^{\sigma}(\nu,u)=-\left\langle\varphi_{\sigma^{2}}\mathbin{\ast}\left(uu^{\ast}\circ\bm{\tau}_{\nu_{\natural}-\nu}\right),\left\langle\nabla_{\bm{x}}[\varphi_{\sigma^{2}}\mathbin{\ast}X_{\natural}],\bm{\tau}_{\pi/2}\right\rangle_{\ell^{2}}\right\rangle_{L^{2}(\mathbb{R}^{2})},$

and using D.31 and the fact that $f\mapsto f\circ\bm{\tau}_{\nu}$ is a unitary
transformation of $L^{2}(\mathbb{R}^{2})$, we thus have

$\nabla_{\nu}\mathcal{L}^{\sigma}(\nu,u)=-\left\langle\varphi_{\sigma^{2}}\mathbin{\ast}uu^{\ast},\mathcal{C}^{u_{\natural}}\circ\bm{\tau}_{\nu-\nu_{\natural}}\right\rangle_{L^{2}(\mathbb{R}^{2})},$

using notation from Lemmas D.8 and D.13 as

$\mathcal{C}^{u}(\bm{x})=\left\langle\nabla_{\bm{x}}[\varphi_{\sigma^{2}}\ast
uu^{\ast}](\bm{x}),\begin{bmatrix}0&-1\\\
1&0\end{bmatrix}\bm{x}\right\rangle_{\ell^{2}}.$

It then follows that

$\displaystyle\nabla_{\nu}^{2}\mathcal{L}^{\sigma}(\nu,u)$
$\displaystyle=-\left\langle\varphi_{\sigma^{2}}\mathbin{\ast}uu^{\ast},\left\langle\bm{R}_{\nu-\nu_{\natural}}^{\ast}\nabla_{\bm{x}}\mathcal{C}^{u_{\natural}}\circ\bm{\tau}_{\nu-\nu_{\natural}},\bm{\tau}_{\pi/2}\right\rangle_{\ell^{2}}\right\rangle_{L^{2}(\mathbb{R}^{2})}$
$\displaystyle=-\left\langle\varphi_{\sigma^{2}}\mathbin{\ast}\left(uu^{\ast}\circ\bm{\tau}_{\nu_{\natural}-\nu}\right),\left\langle\nabla_{\bm{x}}\mathcal{C}^{u_{\natural}},\bm{\tau}_{\pi/2}\right\rangle_{\ell^{2}}\right\rangle_{L^{2}(\mathbb{R}^{2})},$

calculating as in the proof of Lemma D.7 for the first derivative. We can
estimate the RHS with the Schwarz inequality; by Young’s convolution
inequality and the fact that $f\mapsto f\circ\bm{\tau}_{-\nu}$ is a unitary
transformation of $L^{2}(\mathbb{R}^{2})$, we obtain

$\displaystyle\left\lVert\varphi_{\sigma^{2}}\mathbin{\ast}\left(uu^{\ast}\circ\bm{\tau}_{\nu_{\natural}-\nu}\right)\right\rVert_{L^{2}(\mathbb{R}^{2})}$
$\displaystyle\leq\left\lVert\varphi_{\sigma^{2}}\right\rVert_{L^{1}(\mathbb{R}^{2})}\left\lVert
uu^{\ast}\circ\bm{\tau}_{\nu_{\natural}-\nu}\right\rVert_{L^{2}(\mathbb{R}^{2})}$
$\displaystyle\leq\left\lVert uu^{\ast}\right\rVert_{L^{2}(\mathbb{R}^{2})}$
$\displaystyle=\lVert u\rVert_{L^{2}(\mathbb{R})}^{2}.$

Meanwhile, by the second estimate in Lemma D.14, we have

$\left\lVert\left\langle\nabla_{\bm{x}}\mathcal{C}^{u_{\natural}},\bm{\tau}_{\pi/2}\right\rangle_{\ell^{2}}\right\rVert_{L^{2}(\mathbb{R}^{2})}\leq\left(\frac{3}{\pi}+\frac{55}{\pi\sigma^{2}}+\frac{4}{5\pi\sigma^{4}}\right)^{1/2}\leq\frac{1}{\sigma^{2}},$

where the worst-casing uses that $\sigma^{2}\leq\tfrac{1}{100}$. Thus, we have

$\left\lvert\nabla_{\nu}^{2}\mathcal{L}^{\sigma}(\nu,u)\right\rvert\leq\frac{\lVert
u\rVert_{L^{2}(\mathbb{R})}^{2}}{\sigma^{2}}.$

For real numbers $x,y$, we have

$\lvert x^{2}-y^{2}\rvert\leq 2\max\\{\lvert x\rvert,\lvert y\rvert\\}\lvert
x-y\rvert,$

so by the triangle inequality,

$\displaystyle\left\lvert\left\lVert
u_{\mathrm{rough}}\right\rVert_{L^{2}(\mathbb{R})}^{2}-\left\lVert\bar{u}_{\mathrm{rough}}\right\rVert_{L^{2}(\mathbb{R})}^{2}\right\rvert$
$\displaystyle\leq 2\max\left\\{\left\lVert
u_{\mathrm{rough}}\right\rVert_{L^{2}(\mathbb{R})},\left\lVert\bar{u}_{\mathrm{rough}}\right\rVert_{L^{2}(\mathbb{R})}\right\\}\left\lVert
u_{\mathrm{rough}}-\bar{u}_{\mathrm{rough}}\right\rVert_{L^{2}(\mathbb{R})}$
$\displaystyle\leq
2\left(\left\lVert\bar{u}_{\mathrm{rough}}\right\rVert_{L^{2}(\mathbb{R})}+\left\lVert
u_{\mathrm{rough}}-\bar{u}_{\mathrm{rough}}\right\rVert_{L^{2}(\mathbb{R})}\right)\left\lVert
u_{\mathrm{rough}}-\bar{u}_{\mathrm{rough}}\right\rVert_{L^{2}(\mathbb{R})}$
$\displaystyle\leq
4\left\lVert\bar{u}_{\mathrm{rough}}\right\rVert_{L^{2}(\mathbb{R})}\left\lVert
u_{\mathrm{rough}}-\bar{u}_{\mathrm{rough}}\right\rVert_{L^{2}(\mathbb{R})},$

where the last line requires that $\lVert
u_{\mathrm{rough}}-\bar{u}_{\mathrm{rough}}\rVert_{L^{2}(\mathbb{R})}\leq\lVert\bar{u}_{\mathrm{rough}}\rVert_{L^{2}(\mathbb{R})}$.
Since $\lVert\bar{u}_{\mathrm{rough}}\rVert_{L^{2}(\mathbb{R})}=2/\sqrt{\pi}$
by Lemma D.1, this, combined with our previously-derived bound, is equivalent
to the assertion.

For the second assertion, we have by the above inequality

$\displaystyle\left\lvert\left(\nabla_{\nu}\mathcal{L}^{\sigma}(\,\cdot\,,u_{\mathrm{rough}})\right)^{2}-\left(\nabla_{\nu}\mathcal{L}^{\sigma}(\,\cdot\,,\bar{u}_{\mathrm{rough}})\right)^{2}\right\rvert\leq$
$\displaystyle
2\max\left\\{\left\lvert\nabla_{\nu}\mathcal{L}^{\sigma}(\,\cdot\,,u_{\mathrm{rough}})\right\rvert,\left\lvert\nabla_{\nu}\mathcal{L}^{\sigma}(\,\cdot\,,\bar{u}_{\mathrm{rough}})\right\rvert,\right\\}$
$\displaystyle\quad\times\left\lvert\nabla_{\nu}\mathcal{L}^{\sigma}(\,\cdot\,,u_{\mathrm{rough}})-\nabla_{\nu}\mathcal{L}^{\sigma}(\,\cdot\,,\bar{u}_{\mathrm{rough}})\right\rvert,$

so we can bound the sizes of the two factors as well as their absolute
difference. Using the expression given in the proof of the previous assertion
for the gradient, we note that for any $\nu\in\mathbb{R}$

$\nabla_{\nu}\mathcal{L}^{\sigma}(\nu,0)=0,$

so bounding the sizes of the two factors is accomplished by a bound on their
difference. Now, by linearity and the Schwarz inequality, we have for any any
$u,v\in L^{2}(\mathbb{R})$ and any $\nu\in\mathbb{R}$

$\displaystyle\left\lvert\nabla_{\nu}\mathcal{L}^{\sigma}(\nu,u)-\nabla_{\nu}\mathcal{L}^{\sigma}(\nu,v)\right\rvert$
$\displaystyle=\left\lvert\left\langle\varphi_{\sigma^{2}}\mathbin{\ast}\left(\left(uu^{\ast}-vv^{\ast}\right)\circ\bm{\tau}_{\nu_{\natural}-\nu}\right),\left\langle\nabla_{\bm{x}}[\varphi_{\sigma^{2}}\mathbin{\ast}X_{\natural}],\bm{\tau}_{\pi/2}\right\rangle_{\ell^{2}}\right\rangle_{L^{2}(\mathbb{R}^{2})}\right\rvert$
$\displaystyle\leq\left\lVert\varphi_{\sigma^{2}}\mathbin{\ast}\left(\left(uu^{\ast}-vv^{\ast}\right)\circ\bm{\tau}_{\nu_{\natural}-\nu}\right)\right\rVert_{L^{2}(\mathbb{R}^{2})}\left\lVert\left\langle\nabla_{\bm{x}}[\varphi_{\sigma^{2}}\mathbin{\ast}X_{\natural}],\bm{\tau}_{\pi/2}\right\rangle_{\ell^{2}}\right\rVert_{L^{2}(\mathbb{R}^{2})}.$

The second factor can be controlled with the second conclusion of Lemma D.13:
this gives

$\left\lVert\left\langle\nabla_{\bm{x}}[\varphi_{\sigma^{2}}\mathbin{\ast}X_{\natural}],\bm{\tau}_{\pi/2}\right\rangle_{\ell^{2}}\right\rVert_{L^{2}(\mathbb{R}^{2})}\leq\frac{1}{2\sigma^{2}}\left(1+\sigma^{2}\right)^{1/2}\leq\frac{1}{\sigma^{2}},$

where the last bound worst-cases with our assumption on $\sigma$. For the
first factor, we use Young’s convolution inequality and the fact that
$f\mapsto f\circ\bm{\tau}_{\nu_{\natural}-\nu}$ is a unitary transformation of
$L^{2}(\mathbb{R}^{2})$ to obtain

$\displaystyle\left\lVert\varphi_{\sigma^{2}}\mathbin{\ast}\left(\left(uu^{\ast}-vv^{\ast}\right)\circ\bm{\tau}_{-\nu}\right)\right\rVert_{L^{2}(\mathbb{R}^{2})}$
$\displaystyle\leq\left\lVert\varphi_{\sigma^{2}}\right\rVert_{L^{1}(\mathbb{R}^{2})}\left\lVert\left(uu^{\ast}-vv^{\ast}\right)\circ\bm{\tau}_{\nu_{\natural}-\nu}\right\rVert_{L^{2}(\mathbb{R}^{2})}$
$\displaystyle\leq\left\lVert
uu^{\ast}-vv^{\ast}\right\rVert_{L^{2}(\mathbb{R}^{2})}.$

We have

$\displaystyle\left\lVert
uu^{\ast}-vv^{\ast}\right\rVert_{L^{2}(\mathbb{R}^{2})}$
$\displaystyle=\left\lvert\left\lVert
u\right\rVert_{L^{2}(\mathbb{R})}^{2}-\left\lVert
v\right\rVert_{L^{2}(\mathbb{R})}^{2}\right\rvert$ $\displaystyle\leq
2\max\left\\{\left\lVert u\right\rVert_{L^{2}(\mathbb{R})},\left\lVert
v\right\rVert_{L^{2}(\mathbb{R})}\right\\}\left\lvert\left\lVert
u\right\rVert_{L^{2}(\mathbb{R})}-\left\lVert
v\right\rVert_{L^{2}(\mathbb{R})}\right\rvert$ $\displaystyle\leq
2\max\left\\{\left\lVert u\right\rVert_{L^{2}(\mathbb{R})},\left\lVert
v\right\rVert_{L^{2}(\mathbb{R})}\right\\}\left\lVert
u-v\right\rVert_{L^{2}(\mathbb{R})},$

where the two inequalities are both applications of the triangle inequality.
Combining these estimates, we have shown

$\displaystyle\left\lvert\nabla_{\nu}\mathcal{L}^{\sigma}(\nu,u)-\nabla_{\nu}\mathcal{L}^{\sigma}(\nu,v)\right\rvert\leq\frac{2}{\sigma^{2}}\max\left\\{\left\lVert
u_{\mathrm{rough}}\right\rVert_{L^{2}(\mathbb{R})},\left\lVert\bar{u}_{\mathrm{rough}}\right\rVert_{L^{2}(\mathbb{R})}\right\\}\left\lVert\bar{u}_{\mathrm{rough}}-u_{\mathrm{rough}}\right\rVert_{L^{2}(\mathbb{R})},$

and applying this in the context of our gradient bounds, we obtain

$\displaystyle\left\lvert\left(\nabla_{\nu}\mathcal{L}^{\sigma}(\,\cdot\,,u_{\mathrm{rough}})\right)^{2}-\left(\nabla_{\nu}\mathcal{L}^{\sigma}(\,\cdot\,,\bar{u}_{\mathrm{rough}})\right)^{2}\right\rvert$
$\displaystyle\leq\frac{8}{\sigma^{4}}\max\left\\{\left\lVert
u_{\mathrm{rough}}\right\rVert_{L^{2}(\mathbb{R})}^{3},\left\lVert\bar{u}_{\mathrm{rough}}\right\rVert_{L^{2}(\mathbb{R})}^{3}\right\\}\left\lVert\bar{u}_{\mathrm{rough}}-u_{\mathrm{rough}}\right\rVert_{L^{2}(\mathbb{R})}$
$\displaystyle\leq\frac{64}{\sigma^{4}}\left\lVert\bar{u}_{\mathrm{rough}}\right\rVert_{L^{2}(\mathbb{R})}^{3}\left\lVert\bar{u}_{\mathrm{rough}}-u_{\mathrm{rough}}\right\rVert_{L^{2}(\mathbb{R})},$

where the final inequality simplifies using the triangle inequality and the
assumption $\lVert
u_{\mathrm{rough}}-\bar{u}_{\mathrm{rough}}\rVert_{L^{2}(\mathbb{R})}\leq\lVert\bar{u}_{\mathrm{rough}}\rVert_{L^{2}(\mathbb{R})}$,
as we used before. This is precisely the second assertion.

∎

####  D.2.2 Technical Lemmas

######  Lemma D.11.

Let $u={\mathds{1}}_{[-\alpha,\alpha]}$ for some $\alpha>0$, and for some
smoothing level $\sigma>0$ consider the associated curl field

$\mathcal{C}(\bm{x})=\left\langle\nabla_{\bm{x}}[\varphi_{\sigma^{2}}\ast
uu^{\ast}](\bm{x}),\begin{bmatrix}0&-1\\\
1&0\end{bmatrix}\bm{x}\right\rangle_{\ell^{2}}.$

If $\sigma^{2}\leq\tfrac{\alpha^{2}}{24}$, then for any $\bm{x}=(s,t)$ with
$0\leq t\leq s$, one has

$\mathcal{C}(s,t)\geq 0.$

###### Proof.

The proof uses expressions obtained in the proof of Lemma D.13. Following
D.80, if we define

$f(x)=\frac{1}{\sqrt{2\pi\sigma^{2}}}\int_{-\alpha}^{\alpha}e^{-\tfrac{(x-x^{\prime})^{2}}{2\sigma^{2}}}\mathop{}\\!\mathrm{d}x^{\prime},\quad
x\in\mathbb{R},$

then we have

$\mathcal{C}(s,t)=sf(s)f^{\prime}(t)-tf(t)f^{\prime}(s).$

Moreover, note that $f>0$, and by D.81 one has $f^{\prime}(x)=0$ only if
$x=0$. To show the claim, it therefore suffices to show that

$\frac{f^{\prime}(t)}{tf(t)}\geq\frac{f^{\prime}(s)}{sf(s)},\quad s\geq t>0.$

Differentiating, this monotonicity condition becomes

$s(f^{\prime}(s))^{2}+f(s)f^{\prime}(s)-sf^{\prime\prime}(s)f(s)\geq 0,\quad
s>0.$ (D.73)

After a change of coordinates, we have

$f(s)=\frac{1}{\sqrt{\pi}}\int_{-\alpha/\sqrt{2}\sigma}^{\alpha/\sqrt{2}\sigma}e^{-(s-\sqrt{2}\sigma
x)^{2}/2\sigma^{2}}\mathop{}\\!\mathrm{d}x.$

Write $A=\alpha/\sqrt{2}\sigma$, and define

$g(s)=\int_{-A}^{A}e^{-(s-x)^{2}}\mathop{}\\!\mathrm{d}x.$

Noting that $\pi^{-1/2}g(s/\sqrt{2}\sigma)=f(s)$ and inspecting D.73, we see
that it suffices to show that $g$ satisfies the differential inequality in
D.73. Using the fundamental theorem of calculus, we have

$\displaystyle g^{\prime}(s)$ $\displaystyle=e^{-(s+A)^{2}}-e^{-(s-A)^{2}}$
$\displaystyle=-2e^{-s^{2}-A^{2}}\sinh(2sA),$ (D.74)

and by an additional straightforward differentiation

$g^{\prime\prime}(s)=4e^{-s^{2}-A^{2}}(s\sinh(2sA)-A\cosh(2sA)).$

After substituting into D.73 and cancelling some positive factors, the
inequality to show becomes

$2sA\sinh(2sA)\left(\frac{A^{-1}e^{-A^{2}}}{e^{s^{2}}g(s)}\right)+2sA\coth(2sA)-(1+2s^{2})\geq
0.$ (D.75)

We will prove this bound in two regimes: first, for $0<s\leq A$, then for
$s>A$.

###### Small $s$.

To start, we will develop a simple estimate for $g$. Notice that

$\displaystyle e^{s^{2}}g(s)$
$\displaystyle=\int_{-A}^{A}e^{-x^{2}}e^{2sx}\mathop{}\\!\mathrm{d}x$
$\displaystyle\leq\int_{-A}^{A}e^{2sx}\mathop{}\\!\mathrm{d}x$
$\displaystyle=\frac{1}{s}\sinh(2As),$

so it suffices to show

$2s^{2}e^{-A^{2}}+2sA\coth(2sA)-(1+2s^{2})\geq 0.$

For large $A$, the first term is sub-leading, and it suffices to simply show

$2sA\coth(2sA)-(1+2s^{2})\geq 0.$

We will show this bound on the requisite interval in two steps, since
$s\mapsto s\coth s$ does not have a globally-convergent power series
representation at zero. First, we have from the power series representation
the bound $2sA\coth 2sA\geq 1+\tfrac{(2sA)^{2}}{3}-\tfrac{(2sA)^{4}}{45}$ for
all $s$; this bound is initially valid for $\lvert 2sA\rvert<\pi$, then
extended to all $s$ by noticing that it is decreasing for $2sA\geq\pi$,
whereas $2sA\coth 2sA$ is increasing for $s\geq 0$. With this bound, it
suffices to show

$\frac{2s^{2}}{3}\left(2A^{2}-3-\frac{8A^{4}s^{2}}{15}\right)\geq 0,$

which, when $A^{2}\geq 6$, holds for all $0\leq s\leq A^{-1}\sqrt{45/16}$.
Next, notice that D.75 can be written equivalently as

$s\left(e^{-(s-A)^{2}}-e^{-(s+A)^{2}}\right)+g(s)\left(2sA\coth(2sA)-(1+2s^{2})\right)\geq
0,$ (D.76)

where the first term is nonnegative. Since $\tanh(x)\leq 1$ if $x\geq 0$, it
then suffices to show

$g(s)\left(2sA-(1+2s^{2})\right)\geq 0.$

The concave quadratic function $2sA-(1+2s^{2})$ has its two roots at
$\tfrac{A}{2}\pm\tfrac{\sqrt{A^{2}-1}}{2}$; using the inequality
$\sqrt{1-x}\geq 1-x$ for $0\leq x\leq 1$, it follows that these two roots are
outside of the interval $[\tfrac{1}{2A},A-\tfrac{1}{2A}]$, and hence
$2sA-(1+2s^{2})$ is nonnegative on this interval. Since
$\sqrt{45/16}\geq\tfrac{1}{2}$, this establishes the inequality on $0<s\leq
A-\tfrac{1}{2A}$.

Finally, to demonstrate the inequality on $A-\tfrac{1}{2A}\leq s\leq A$, we
return to the sufficient expression of D.75 given above, as

$s\left(e^{-(s-A)^{2}}-e^{-(s+A)^{2}}\right)+g(s)\left(2sA-(1+2s^{2})\right)\geq
0,$

and note again that the concave quadratic function $2sA-(1+2s^{2})$ is
maximized at $s=A/2$, hence is a decreasing function of $s$ on this interval;
so it suffices to show

$s\left(e^{-(s-A)^{2}}-e^{-(s+A)^{2}}\right)-g(s)\geq 0,$

From D.74, it is clear that $g$ is a decreasing function of $s$, so we can
show

$s\left(e^{-(s-A)^{2}}-e^{-(s+A)^{2}}\right)-g(A-\tfrac{1}{2A})\geq 0.$

Now, exploiting the fact that the parameter $s$ in the definition of $g(s)$ is
similar to a “mean” parameter for the gaussian integrand, we calculate

$\displaystyle g(A-\tfrac{1}{2A})$
$\displaystyle=\int_{-A}^{A}e^{-\left(x-(A-\tfrac{1}{2A})\right)^{2}}\mathop{}\\!\mathrm{d}x$
$\displaystyle=\int_{-A}^{A-\tfrac{1}{2A}}e^{-\left(x-(A-\tfrac{1}{2A})\right)^{2}}\mathop{}\\!\mathrm{d}x+\int_{A-\tfrac{1}{2A}}^{A}e^{-\left(x-(A-\tfrac{1}{2A})\right)^{2}}\mathop{}\\!\mathrm{d}x$
$\displaystyle\leq\frac{\sqrt{\pi}}{2}+\frac{1}{2A}.$

The last line above worst-cases the value of the first integral (as it is no
larger than half of the integral over $\mathbb{R}$, by symmetry), and uses a
$L^{1}$-$L^{\infty}$ bound to control the second. Meanwhile, using elementary
inequalities and $A^{2}\geq 12$ assumed previously, we have

$\displaystyle s\left(e^{-(s-A)^{2}}-e^{-(s+A)^{2}}\right)$
$\displaystyle\geq\left(A-\frac{1}{2A}\right)\left(1-(s-A)^{2}-e^{-\left(2A-\tfrac{1}{2A}\right)^{2}}\right)$
$\displaystyle\geq\left(A-\frac{1}{2A}\right)\left(1-\frac{1}{4A^{2}}-e^{-3A^{2}}\right),$

so it suffices to show

$A\left(1-\frac{1}{2A^{2}}\right)\left(1-\frac{1}{4A^{2}}-e^{-3A^{2}}\right)-\left(\frac{\sqrt{\pi}}{2}+\frac{1}{2A}\right)\geq
0,$

which is evidently true for all $A^{2}\geq 12$. This establishes the
inequality on $0<s\leq A$.

###### Large $s$.

For this regime, we will again proceed in steps; first for $A\leq s\leq
A+\tfrac{1}{3}$, then for $A+\tfrac{1}{3}\leq s\leq 2A$, then for $s\geq 2A$.

First, we will develop the bound for $A\leq s\leq A+c$, where $c>0$ is a small
absolute constant. Proceeding as above, but using now that when $s\geq A$ we
have $2sA-(1+2s^{2})=-(1+2s(s-A)\leq 0$ so that we can leverage the bound
$g(s)=\int_{s-A}^{s+A}e^{-x^{2}}\mathop{}\\!\mathrm{d}x\leq\int_{0}^{s+A}e^{-x^{2}}\mathop{}\\!\mathrm{d}x\leq\sqrt{\pi}/2$,
we have that it suffices to show

$A\left(e^{-c^{2}}-e^{-4A^{2}}\right)-\frac{\sqrt{\pi}}{2}\left(1+2c(A+c)\right)\geq
0,$

which, after rearranging, is simply

$A\left(e^{-c^{2}}-\sqrt{\pi}c\right)-Ae^{-4A^{2}}-\sqrt{\pi}\left(\tfrac{1}{2}+c^{2}\right)\geq
0.$

We verify numerically that this holds for $c=\tfrac{1}{3}$ when $A^{2}\geq
12$, as we have assumed.

Now we proceed for $s\geq A+\tfrac{1}{3}$. We will develop a sequence of
refined upper bounds on $g(s)$. We have from a change of coordinates

$\displaystyle g(s)$
$\displaystyle=e^{-(s-A)^{2}}\int_{0}^{2A}e^{-x^{2}-2x(s-A)}\mathop{}\\!\mathrm{d}x.$
(D.77)

Our previous estimate amounts to controlling the integral via $e^{-x^{2}}\leq
1$. We will improve over this estimate slightly by instead developing a
piecewise linear upper bound for the concave function
$x\mapsto-x^{2}-2x(s-A)$. Below, we will write $t=s-A$ for concision; by
assumption $t\geq\tfrac{1}{3}$. For any $\varepsilon\geq 0$, by concavity, we
have for all $x\in\mathbb{R}$

$-x^{2}-2x(s-A)\leq-2(t+\varepsilon)x+\varepsilon^{2}.$

Elementary algebra shows that the “null” upper bound for $\varepsilon=0$, that
is $x\mapsto-2tx$, intersects with
$x\mapsto-2(t+\varepsilon)x+\varepsilon^{2}$ at $x=\varepsilon/2$. Hence, if
$0\leq\varepsilon\leq 4A$, we can estimate the integral as

$\displaystyle\int_{0}^{2A}e^{-x^{2}-2x(s-A)}\mathop{}\\!\mathrm{d}x$
$\displaystyle\leq\int_{0}^{\varepsilon/2}e^{-2tx}\mathop{}\\!\mathrm{d}x+e^{\varepsilon^{2}}\int_{\varepsilon/2}^{2A}e^{-2(t+\varepsilon)x}\mathop{}\\!\mathrm{d}x$
$\displaystyle=\frac{1}{2t}\left(1-e^{-t\varepsilon}\right)+\frac{1}{2(t+\varepsilon)}\left(e^{-\varepsilon
t}-e^{\varepsilon^{2}}e^{-4(t+\varepsilon)A}\right)$
$\displaystyle\leq\frac{1}{2t}\left(1-\frac{\varepsilon e^{-\varepsilon
t}}{\varepsilon+t}\right).$

Choosing $\varepsilon=1/t$, this bound implies

$g(s)\leq\frac{1}{2t}e^{-(s-A)^{2}}\left(1-\frac{e^{-1}}{1+t^{2}}\right),$

and so it suffices to show

$e^{-(s-A)^{2}}\left(s-\frac{1}{2(s-A)}\left(1-\frac{e^{-1}}{1+(s-A)^{2}}\right)\left(1+2s(s-A)\right)\right)-se^{-(s+A)^{2}}\geq
0.$

After some cancellation, this reads equivalently

$\frac{1}{2(s-A)}\left(\frac{1+2s(s-A)}{e(1+(s-A)^{2})}-1\right)-se^{-4sA}\geq
0.$

We will estimate the term in parenthesis. We have

$\displaystyle\frac{1+2s(s-A)}{e(1+(s-A)^{2})}-1$
$\displaystyle=\left(\frac{-(1-\tfrac{1}{e})-(s-A)\left(s(1-\tfrac{2}{e})-A\right)}{1+(s-A)^{2}}\right).$

The numerator is a concave quadratic, which is maximized at
$s=A\tfrac{e-1}{e-2}$; the constant is between $2$ and $3$. We check that when
$s=A+\tfrac{1}{3}$ and $A^{2}\geq 12$, the numerator is positive. Using
$A+\tfrac{1}{3}\leq s\leq 2A$, we thus have that it suffices to show

$\left(\frac{11+6A-10e}{9e(1+A^{2})}\right)-\frac{4A}{3}e^{-4A^{2}}\geq 0.$

We numerically verify that this inequality holds for all $A^{2}\geq 12$.

Finally, we improve D.77 once more and then use $s\geq 2A$ to conclude
quickly. An improved estimate comes from [51, Theorem 1]: we apply this to
D.77 to obtain

$\displaystyle g(s)$ $\displaystyle\leq
e^{-(s-A)^{2}}\int_{0}^{\infty}e^{-x^{2}-2x(s-A)}\mathop{}\\!\mathrm{d}x$
$\displaystyle=\frac{\sqrt{\pi}}{2}\mathrm{erfc}(s-A)$
$\displaystyle\leq\frac{e^{-(s-A)^{2}}}{2(s-A)}\left[1-\frac{2-3e^{-(1+2(s-A))}-2(s-A)e^{-(1+2(s-A))}}{(1+2(s-A))^{2}}\right],$

where the estimate is applied in the third line, and the second line is a
standard integral. Following then D.76 and using again that
$\lvert\tanh\rvert\leq 1$, it suffices to show

$1-\frac{2-3e^{-(1+2(s-A))}-2(s-A)e^{-(1+2(s-A))}}{(1+2(s-A))^{2}}\leq\frac{2s(s-A)\left(1-e^{-4sA}\right)}{1+2s(s-A)}.$

After rearranging with some algebra, it suffices to show

$e^{-(1+2(s-A))}\frac{3+2(s-A)}{(1+2(s-A))^{2}}+e^{-4sA}\frac{2s(s-A)}{1+2s(s-A)}\leq\frac{2}{(1+2(s-A))^{2}}-\frac{1}{1+2s(s-A)}.$

By algebra,

$\frac{2}{(1+2(s-A))^{2}}-\frac{1}{1+2s(s-A)}=\frac{1+4sA-4(s-A)-4A^{2}}{(1+2s(s-A))(1+2(s-A))^{2}},$

which is easily seen to be nonnegative when $s\geq A$. Clearing denominators,
it then suffices to show

$(3+2(s-A))(1+2s(s-A))e^{-(1+2(s-A))}+2s(s-A)(1+2(s-A))^{2}e^{-4sA}\leq
1+4sA-4(s-A)-4A^{2}.$

We can show this holds easily by worst-casing for convenience, since the LHS
has exponential prefactors. Since $s\geq 2A$, we have $2(s-A)\geq s$. We
always have $s-A\leq s$, and since $A\geq 1$ we have $s\geq 2$, so it suffices
to show

$9s^{3}e^{-s}+18s^{4}e^{-4sA}\leq 1+4sA-4(s-A)-4A^{2}.$

Elementary calculus implies that the first term on the LHS is decreasing as
soon as $s\geq 3$, and the second term is decreasing as soon as $s\geq 1/A$,
both of which are implied by $s\geq 2A$ and our assumptions on $A$. Since the
RHS is increasing, it suffices to check

$9A^{3}e^{-A}+18A^{4}e^{-4A^{2}}\leq 1+4A(A-1).$

A numerical evaluation and the preceding calculus argument shows that this is
true as soon as $A\geq 3$.

∎

######  Lemma D.12.

Consider the residual field arising in the study of the alignment gradient:
for any $\nu\in\mathbb{R}$, we consider

$\bar{u}_{\mathrm{rough}}\bar{u}_{\mathrm{rough}}^{\ast}\circ\bm{\tau}_{\nu}-\bar{u}_{\mathrm{rough}}\bar{u}_{\mathrm{rough}}^{\ast}\circ\bm{\tau}_{-\nu},$

where the (unscaled, for convenience) nominal rough initial representation is
defined as

$\bar{u}_{\mathrm{rough}}(s)={\mathds{1}}_{\lvert s\rvert\leq 1}\cos(\pi
s/2).$

Then for any $\bm{x}=(s,t)$ with $0\leq t\leq s\leq 1$, the difference is
nonnegative:

$\bar{u}_{\mathrm{rough}}\bar{u}_{\mathrm{rough}}^{\ast}\circ\bm{\tau}_{\nu}(\bm{x})-\bar{u}_{\mathrm{rough}}\bar{u}_{\mathrm{rough}}^{\ast}\circ\bm{\tau}_{-\nu}(\bm{x})\geq
0,$

and moreover for any $\bm{x}=(s,t)$ with $0\leq t\leq s\leq 1$ and any
$0\leq\nu\leq\pi/7$, it satisfies the estimate

$\bar{u}_{\mathrm{rough}}\bar{u}_{\mathrm{rough}}^{\ast}\circ\bm{\tau}_{\nu}(\bm{x})-\bar{u}_{\mathrm{rough}}\bar{u}_{\mathrm{rough}}^{\ast}\circ\bm{\tau}_{-\nu}(\bm{x})\geq\frac{7\sin\nu}{1000}{\mathds{1}}_{-0.137\leq
t-\tfrac{1}{\sqrt{2}}\leq-0.127}{\mathds{1}}_{-0.001\leq
s-\tfrac{1}{\sqrt{2}}\leq 0.001}.$

###### Proof.

We have to show

$\bar{u}_{\mathrm{rough}}\bar{u}_{\mathrm{rough}}^{\ast}\circ\bm{\tau}_{-\nu}-\bar{u}_{\mathrm{rough}}\bar{u}_{\mathrm{rough}}^{\ast}\circ\bm{\tau}_{\nu}\leq
0.$

Using two trigonometric identities, we can write for any $\bm{x}=(s,t)$ with
$0\leq t\leq s\leq 1$

$\displaystyle\bar{u}_{\mathrm{rough}}\bar{u}_{\mathrm{rough}}^{\ast}\circ\bm{\tau}_{-\nu}(\bm{x})-\bar{u}_{\mathrm{rough}}\bar{u}_{\mathrm{rough}}^{\ast}\circ\bm{\tau}_{\nu}(\bm{x})$
$\displaystyle\qquad=\sin(\tfrac{\pi}{2}(s+t)\cos\nu)\sin(\tfrac{\pi}{2}(s-t)\sin\nu)-\sin(\tfrac{\pi}{2}(s-t)\cos\nu)\sin(\tfrac{\pi}{2}(s+t)\sin\nu).$

It is clear that this expression is identically zero when $\nu=0$ or $s=t$, so
assume otherwise below. To show the expression is nonpositive, it is
equivalent to show

$\frac{\sin(\tfrac{\pi}{2}(s+t)\cos\nu)}{\sin(\tfrac{\pi}{2}(s+t)\sin\nu)}\leq\frac{\sin(\tfrac{\pi}{2}(s-t)\cos\nu)}{\sin(\tfrac{\pi}{2}(s-t)\sin\nu)}$

for each $0\leq t\leq s\leq 1$ and all $0\leq\nu\leq\pi/4$. Given that under
these constraints $s+t\leq 2$, it therefore suffices to show that

$x\mapsto\frac{\sin(\tfrac{\pi}{2}x\cos\nu)}{\sin(\tfrac{\pi}{2}x\sin\nu)}$

is a decreasing function of $x$ on $[0,2]$. Rescaling coordinates, this is
equivalent to showing that

$x\mapsto\frac{\sin(x\cot\nu)}{\sin x}$

is decreasing on $[0,\pi\sin\nu]$, and because $1/\cot\nu\geq\sin\nu$ when
$0\leq\nu\leq\pi/4$ it suffices instead to show decreasingness on
$[0,\pi/\cot\nu]$. This is a standard calculation that arises in the study of
the Dirichlet kernel in Fourier analysis; to obtain it, write $A=\cot\nu$ and
differentiate to obtain the sufficient condition

$Ax\cot Ax\leq x\cot x,\quad 0<x<\pi/A.$

This can be seen, for instance, from the power series expression for $x\cot
x$, convergent for $\lvert x\rvert<\pi$:

$Ax\cot Ax=1-2\sum_{k=1}^{\infty}\frac{\zeta(2k)}{\pi^{2k}}A^{2k}x^{2k}\leq
1-2\sum_{k=1}^{\infty}\frac{\zeta(2k)}{\pi^{2k}}x^{2k}=x\cot x,$

since $A\geq 1$ and all terms in the sum are nonpositive, where $\zeta$
denotes the Riemann zeta function. Thus we have shown

$\bar{u}_{\mathrm{rough}}\bar{u}_{\mathrm{rough}}^{\ast}\circ\bm{\tau}_{-\nu}-\bar{u}_{\mathrm{rough}}\bar{u}_{\mathrm{rough}}^{\ast}\circ\bm{\tau}_{\nu}\leq
0.$

Next, we show the quantitative bound. By our earlier work, we can write at any
$\bm{x}=(s,t)$ with $0\leq t<s\leq 1$

$\displaystyle\frac{\sqrt{\pi}}{2}\left(\bar{u}_{\mathrm{rough}}\bar{u}_{\mathrm{rough}}^{\ast}\circ\bm{\tau}_{\nu}(\bm{x})-\bar{u}_{\mathrm{rough}}\bar{u}_{\mathrm{rough}}^{\ast}\circ\bm{\tau}_{-\nu}(\bm{x})\right)$
$\displaystyle\qquad=\sin(\tfrac{\pi}{2}(s+t)\sin\nu)\sin(\tfrac{\pi}{2}(s-t)\cos\nu)-\sin(\tfrac{\pi}{2}(s+t)\cos\nu)\sin(\tfrac{\pi}{2}(s-t)\sin\nu).$
(D.78)

We will obtain a lower bound for this expression by combining term-by-term
bounds, optimized for $t\approx s$. The difference terms are easiest: we can
use the standard estimates

$\displaystyle\sin\left(\tfrac{\pi}{2}(s-t)\cos\nu\right)$
$\displaystyle\geq\tfrac{\pi}{2}(s-t)\cos\nu-\left(\tfrac{\pi}{2}(s-t)\cos\nu\right)^{3}/6,$
$\displaystyle\sin\left(\tfrac{\pi}{2}(s-t)\sin\nu\right)$
$\displaystyle\leq\tfrac{\pi}{2}(s-t)\sin\nu,$

which follow by concavity. Similarly, concavity gives the estimates

$\displaystyle\sin\left(\tfrac{\pi}{2}(s+t)\sin\nu\right)$
$\displaystyle\geq\sin\left(\pi
s\sin\nu\right)+\tfrac{\pi}{2}\sin\nu\cos\left(\pi
s\sin\nu\right)(t-s)-\frac{\pi^{2}\sin^{2}\nu}{8}(t-s)^{2},$
$\displaystyle\sin\left(\tfrac{\pi}{2}(s+t)\cos\nu\right)$
$\displaystyle\leq\sin\left(\pi
s\cos\nu\right)+\tfrac{\pi}{2}\cos\nu\cos\left(\pi s\cos\nu\right)(t-s).$

These estimates yield a polynomial lower bound for the difference term when
substituted into D.78. Since we know this difference is nonnegative, we can
improve the bound by taking the maximum of it and zero, and then further
simplify the bound based on its local behavior near $t\approx s$ to a
quadratic lower bound. To this end, we have the unwieldy lower bound

$\displaystyle\bar{u}_{\mathrm{rough}}\bar{u}_{\mathrm{rough}}^{\ast}\circ\bm{\tau}_{\nu}(\bm{x})-\bar{u}_{\mathrm{rough}}\bar{u}_{\mathrm{rough}}^{\ast}\circ\bm{\tau}_{-\nu}(\bm{x})$
$\displaystyle\geq\frac{\pi(s-t)}{2}\left(\cos(\nu)\sin(\pi
s\sin\nu)-\sin(\nu)\sin(\pi s\cos\nu)\right)$
$\displaystyle\quad-\frac{\pi^{2}(s-t)^{2}\cos\nu\sin\nu}{4}\left(\cos(\pi
s\sin\nu)-\cos(\pi s\cos\nu)\right)$
$\displaystyle\quad-\frac{\pi^{3}(s-t)^{3}\cos\nu}{16}\left(\sin^{2}\nu+\frac{1}{3}\cos^{2}\nu\sin(\pi
s\sin\nu)\right)$
$\displaystyle\quad+\frac{\pi^{4}(s-t)^{4}\cos^{3}(\nu)\cos(\pi
s\sin\nu)\sin\nu}{96}+\frac{\pi^{5}(s-t)^{5}\cos^{3}(\nu)\sin^{2}(\nu)}{384}.$

The degree four and five terms in this bound are both nonnegative, hence can
be worst-cased out. To verify that the degree-two term dominates the degree-
three term, we have to show for some $0<\varepsilon<1$

$\displaystyle(1-\varepsilon)\sin\nu\left(\cos(\pi s\sin\nu)-\cos(\pi
s\cos\nu)\right)$
$\displaystyle-\frac{\pi(s-t)}{4}\left(\sin^{2}\nu+\frac{1}{3}\cos^{2}\nu\sin(\pi
s\sin\nu)\right)\geq 0.$

We have $0\leq s-t\leq 1$, and the LHS of the previous bound is a decreasing
function of $s-t$. Moreover, we have $\sin(\pi s\sin\nu)/\sin\nu\leq\pi s$.
Hence, to show this bound holds for all $0\leq\nu\leq\pi/7$ and all $0\leq
s-t\leq 1/2$, it suffices to show for some $\varepsilon$

$\displaystyle(1-\varepsilon)\left(\cos(\pi s\sin\nu)-\cos(\pi
s\cos\nu)\right)$ $\displaystyle-\frac{\pi}{8}\left(\sin\pi/7+\frac{\pi
s}{3}\right)\geq 0.$

We will show this by lower bounding the first term with calculus. We have for
the second derivative of the first summand

$\partial_{\nu}^{2}[\cos(\pi s\sin\nu)](\nu)=\sin(\pi s\sin\nu)(\pi
s\sin\nu)-(\pi s\cos\nu)^{2}\cos(\pi s\sin\nu).$

We notice that this is an increasing function of $\nu$, because it is a
difference of two terms which are (respectively) a product of two nonnegative
increasing functions and a product of two nonnegative decreasing functions.
Hence it attains its minimum value at $\nu=0$. Similarly, we have

$\partial_{\nu}^{2}[-\cos(\pi s\cos\nu)](\nu)=(\pi s\sin\nu)^{2}\cos(\pi
s-(\pi s\cos\nu)\sin(\pi s\cos\nu)\cos\nu),$

which is once again a difference of a product of two nonnegative increasing
functions and a product of two nonnegative decreasing functions, hence attains
its minimum value at $\nu=0$. It follows that the same is true of the sum, and
Taylor’s theorem then implies the lower bound

$\cos(\pi s\sin\nu)-\cos(\pi s\cos\nu)\geq(1-\cos\pi s)-\frac{(\pi s)^{2}+\pi
s\sin\pi s}{2}\nu^{2}.$

When $s\geq\tfrac{1}{2}$, we have $-\cos\pi s\geq 2s-1$. Worst-casing
$\nu\leq\pi/7$ and choosing $\varepsilon=1/8$, it then suffices to show under
these conditions

$\left(2s-\frac{(\pi s)^{2}+\pi s\sin\pi
s}{2}(\pi/7)^{2}\right)-\frac{\pi}{7}\left(\sin\pi/7+\frac{\pi
s}{3}\right)\geq 0.$

A numerical evaluation shows that this holds for all $\tfrac{1}{2}\leq s\leq
1$. Hence, we have the lower bound, valid for $\tfrac{1}{2}\leq s\leq 1$, all
$s-\tfrac{1}{2}\leq t\leq s$, and all $0\leq\nu\leq\pi/7$:

$\displaystyle\bar{u}_{\mathrm{rough}}\bar{u}_{\mathrm{rough}}^{\ast}\circ\bm{\tau}_{\nu}(\bm{x})-\bar{u}_{\mathrm{rough}}\bar{u}_{\mathrm{rough}}^{\ast}\circ\bm{\tau}_{-\nu}(\bm{x})$
$\displaystyle\geq\frac{\pi(s-t)}{2}\left(\cos(\nu)\sin(\pi
s\sin\nu)-\sin(\nu)\sin(\pi s\cos\nu)\right)$
$\displaystyle\quad-\frac{15\pi^{2}(s-t)^{2}\cos\nu\sin\nu}{32}\left(\cos(\pi
s\sin\nu)-\cos(\pi s\cos\nu)\right).$

Letting

$\displaystyle A$ $\displaystyle=\frac{\pi}{2}\left(\cos(\nu)\sin(\pi
s\sin\nu)-\sin(\nu)\sin(\pi s\cos\nu)\right),$ $\displaystyle B$
$\displaystyle=\frac{15\pi^{2}\cos\nu\sin\nu}{32}\left(\cos(\pi
s\sin\nu)-\cos(\pi s\cos\nu)\right),$

we have $B\geq 0$ since $\cos$ is decreasing and $\sin\leq\cos$ on our
interval of interest, and

$\bar{u}_{\mathrm{rough}}\bar{u}_{\mathrm{rough}}^{\ast}\circ\bm{\tau}_{\nu}(\bm{x})-\bar{u}_{\mathrm{rough}}\bar{u}_{\mathrm{rough}}^{\ast}\circ\bm{\tau}_{-\nu}(\bm{x})\geq
Ar-
Br^{2}=B\left(\left(\frac{A}{2B}\right)^{2}-\left(r-\frac{A}{2B}\right)^{2}\right),$

where the RHS is a concave quadratic function of $r=s-t$. For such a concave