# Canonical Factors for Hybrid Neural Fields

Brent Yi1 Weijia Zeng1 Sam Buchanan2 Yi Ma1

1UC Berkeley 2TTI-Chicago

###### Abstract

Factored feature volumes offer a simple way to build more compact, efficient,
and intepretable neural fields, but also introduce biases that are not
necessarily beneficial for real-world data. In this work, we (1) characterize
the undesirable biases that these architectures have for axis-aligned
signals—they can lead to radiance field reconstruction differences of as high
as $2$ PSNR—and (2) explore how learning a set of canonicalizing
transformations can improve representations by removing these biases. We prove
in a two-dimensional model problem that simultaneously learning these
transformations together with scene appearance succeeds with drastically
improved efficiency. We validate the resulting architectures, which we call
TILTED, using image, signed distance, and radiance field reconstruction tasks,
where we observe improvements across quality, robustness, compactness, and
runtime. Results demonstrate that TILTED can enable capabilities comparable to
baselines that are 2x larger, while highlighting weaknesses of neural field
evaluation procedures.

Figure 1:  Learned transforms for factored feature volumes. Latent
decompositions with fixed, axis-aligned projections (left) introduce biases
for axis-aligned signals. A more robust, transform-invariant latent
decomposition (TILTED) is obtained by treating projections to feature grids as
learnable functions, here parameterized by $\bm{\tau}_{t}$.

##  1 Introduction

Our physical world layers complexity on top of regularity. Tucked below the
details that imbue our surroundings with character—the intricate fibers of a
fine-grained veneer, the light-catching specularities of everyday metal,
plastic, and glass—one finds the simple geometric primitives and symmetries
associated with built and natural structures. The challenge of representations
for the world, such as those used for 3D reconstruction, anchors itself in the
interaction between the two ends of this dichotomy: point clouds and voxel
grids offer versatility, but their inability to capture structure results in
resource usage that can grow too intractably for complex details in expansive
scenes; meshes harness the uniformity of surfaces for compactness, but still
fail on entities with structure that steps outside of an acceptable
regime—consider fog or deviations on curves.

In this work, we build on the idea that scalably capturing the details of a
complex signal is only possible when a representation enables capture of its
structure. We use this theme to study and improve state-of-the-art hybrid
neural fields, which typically pair neural decoders with factored feature
volumes [67, 68, 85, 82, 88, 86]. Aided by an ability to exploit sparse and
low-rank structure, factorization is simple to implement and offers a host of
advantages, such as compactness, efficiency, and interpretability. However,
these advantages hinge on an implicit frame of representation, which is not
guaranteed to be aligned with the structure of scenes or signals one aims to
represent. Drawing on insights from both low-rank texture extraction [23] and
implicit regularization in optimization methods for factorization [35, 60], we
theoretically characterize the importance of this alignment and then show how
it can enable practical improvements to neural field architectures with
factored feature volumes. Our contributions are as follows:

(1) We analyze the fragility of factored grids in a two-dimensional model
problem, where resource efficiency on simple-to-capture structures can be
undermined even by small planar rotations (Section 3). We prove that this
fragility can be overcome by jointly optimizing over the parameters of a set
of canonical factors and a transformation of domain, when the underlying
structure is well-aligned in some frame of representation.

(2) We study how this same weakness affects practical neural field
architectures, where it can lead to radiance field accuracy differences of as
high as 2 PSNR (Section 5). We propose optimization of more robust, transform-
invariant latent decompositions (TILTED) via the same idea of canonical
factors (Section 4). TILTED models are optimized to jointly recover factors of
a decomposed feature volume with a set of canonicalizing transformations,
which are simple to incorporate into existing factorization techniques.

(3) We evaluate the TILTED models on three tasks: 2D image, signed distance
field, and neural radiance field reconstruction (Section 5). Our experiments
highlight biases in existing neural field architecture and evaluation
procedures, while demonstrating TILTED’s advantages across quality,
robustness, compactness, and runtime. For real-world scenes, TILTED can
simultaneously improve reconstruction detail, halve memory consumption, and
accelerate training times by 25%.

##  2 Related Work

###  2.1 Neural Fields

In its standard form, a neural field is implemented using an MLP that takes
coordinates as input and returns a vector of interest. For example, a basic
neural radiance field [48] with network parameters $\bm{\theta}{}$ maps
spatial positions $\bm{p}=(p_{x},p_{y},p_{z})\in\mathbb{R}^{3}$ to RGB colors
$\bm{c}\in[0,1]^{3}$ and densities $\sigma\in\mathbb{R}_{\geq 0}$:

$\bm{p}\xrightarrow[]{\texttt{MLP}_{\bm{\theta}}}(\bm{c},\sigma).$ (2.1)

This framework is highly versatile. Instead of only position, inputs can
include additional conditioning information such as specularity-enabling view
directions [48], per-camera appearance embeddings [56], or time [85]. Instead
of radiance, possible outputs also include representations of binary occupancy
[40, 43], signed distance functions [44, 45], joint representations of
surfaces and radiance [62, 61, 57], actions [69, 100], and semantics [80, 71,
74, 91]. The core ideas behind TILTED are not tied to specific input or output
modalities.

(a) CP

(b) Tri-plane

(c) Vector-matrix

Figure 2:  Tensor decompositions for 3D features volumes studied by prior work
[68, 67, 68, 85]. Note that all assume a fixed, axis-aligned structure; TILTED
instead proposes to learn transformations of this structure.

###  2.2 Hybrid Neural Fields

When a single MLP is used as a data structure, as in 2.1, all stored
information needs to be encoded and entangled in the network weights
$\bm{\theta}{}$. The result is expensive for both training and inference. To
address this, several works have proposed forms of hybrid neural fields, which
have two components: an explicit geometric data structure from which latent
vectors are interpolated and a neural decoder [79, 73]. In the case of 3D
coordinate inputs and radiance outputs, as in 2.1, these architectures can be
instantiated as

$\bm{p}\xrightarrow[]{\texttt{VoxelTrilerp}_{\bm{\phi}{}}}\bm{Z}\xrightarrow[]{\texttt{MLP}_{\bm{\theta}}}(\bm{c},\sigma),$
(2.2)

where $\texttt{VoxelTrilerp}_{\bm{\phi}{}}$ interpolates the ‘latent grid’
parameters $\bm{\phi}{}$ to produce a latent feature
$\bm{Z}\in\mathbb{R}^{d}$, which is then decoded to standard radiance field
outputs by an MLP with parameters $\bm{\theta}{}$.

Instead of implementing the latent feature volume $\bm{\phi}{}$ as a dense
voxel grid, a common pattern is to decompose this tensor into lower-
dimensional factors $\bm{\phi}{}=\\{\bm{F}_{1}\dots\bm{F}_{F}\\}$. In this
way, hybrid neural field approaches that rely on factored feature volumes [67,
68, 82, 85, 83, 77] generalize 2.2 by (i) projecting input coordinates onto
each of $F$ lower-dimensional coordinate spaces, (ii) interpolating $F$
feature vectors from the corresponding factors, and (iii) reducing—for
example, by concatenation, multiplication, or addition—the set of latent
features into the final latent $\bm{Z}$:

$\begin{split}\bm{Z}&=\texttt{Reduce}\bigl{(}\bigl{[}\texttt{Interp}_{\bm{F}_{1}}(\texttt{Proj}_{1}(\bm{p}))\bigr{]},\dots,\\\
&\hphantom{=\texttt{Reduce}\bigl{(}\,\,}\bigl{[}\texttt{Interp}_{\bm{F}_{F}}(\texttt{Proj}_{F}(\bm{p}))\bigr{]}\bigr{)}.\end{split}$
(2.3)

Interpolating only on lower-dimensional feature grids
$\bm{F}_{1},\dots,\bm{F}_{F}$, which may be 1D or 2D when $\bm{p}$ is 3D or
higher, provides efficiency advantages. We use 2.3 to formalize existing
factorization techniques in Appendix B.

Hybrid neural fields offer a unique set of advantages. In contrast to
techniques based on caching and distillation, which require a pretrained
neural network [53, 54, 63, 59, 75, 52], hybrid neural field architectures
accelerate both training and evaluation. They also offer unique opportunities
in generation [67, 84, 96], real-time rendering [102, 94] upsampling [68],
incremental growth [81, 103, 89, 92], interpretable regularization [85], anti-
aliasing [88], exploiting sparsity [86], and dynamic scene reconstruction [82,
93, 95].

Existing latent grid factorization methods constrain the Proj operations to
axis-aligned projections (Figure 2). Similar to what has been observed in
axis-aligned positional encodings [49] (and pointed out by concurrent work
[86]), this results in a bias for axis-aligned signals. TILTED proposes to
learn a set of transforms that removes this bias.

###  2.3 Learning With Transformations of Domain

TILTED improves reconstruction performance via optimization over
transformations of domain, a mathematical idea dating back to the earliest
days of computer vision. A concrete example is the image registration problem
[8, 11, 15, 17], where we seek a transformation $\bm{\tau}$ that deforms an
observed image $\bm{Y}$ to match a target $\bm{X}$ via gradient descent.
TILTED takes inspiration from many tried-and-tested techniques for robustly
solving problems of this type, including coarse-to-fine fitting and other
regularization schemes (e.g., [13, 14, 26]). Although this type of
‘supervised’ registration is studied in the context of neural fields [87], it
is less relevant to learning neural implicit models like 2.2 and 2.3, where
ground-truth is rarely available. Instead, we build TILTED around an insight
of [23]: for scenes consisting of natural or built environments, the
transformation that ‘aligns’ the scene with its intrinsic coordinate frame
yields the most compact representation. In the case of 2D images, [23]
instantiate this principle as a search for a transformation that minimizes the
sum of the singular values of the image, a relaxation of the rank:

$\min_{\bm{\tau}}\,\left\lVert\bm{Y}\circ\bm{\tau}\right\rVert_{*}.$ (2.4)

TILTED combines this insight with the emerging understanding of implicit
regularization in overparameterized matrix factorization problems [35, 60,
101], which implies that an implicit bias toward low-rank structures in
factored grid representations learned with gradient descent obviates the
explicit rank regularization of 2.4.

A parallel line of work seeks to imbue a broader family of neural network
architectures with invariance or ‘equivariance’ to transformations or
symmetries that the network should respect. These include parallel channel
networks [20, 27, 30, 72], approaches based on pooling over transformations
[22, 24, 34], and approaches with learnable deformation offsets [31, 29, 33,
64]. Other approaches aim to construct networks that are transformation-
invariant by design [21, 37, 66]. With TILTED, we demonstrate how to combine
the benefits of transformation invariance with a variety of hybrid neural
field architectures—as we discuss in Section 3, naive factorizations are
limited in the diversity of structures that they can capture.

Figure 3: Limitations of low-rank feature grids. (a): The square template
$\bm{X}_{\natural}$ is axis-aligned, and has a maximally-compact (rank one)
representation. (b): After a rotation by $\pi/4$ radians, the square template
(in red) only changes its orientation, but its approximability by a low-rank
grid deteriorates dramatically. We draw the scaled eigenvectors and
approximation for $F=3$. (c): By optimizing over transformations, a rank-one
grid can be used to represent all rotations of $\bm{X}_{\natural}$. (d): We
plot the number of components needed to achieve varying PSNR levels as a
function of image resolution for $\nu=\pi/4$. The number of components is
always significantly larger than is necessary when transform optimization is
used.

##  3 Low-Rank Grids Are Delicate Creatures

In this section, we demonstrate that under ideal conditions, it is
computationally feasible to recover a minimal set of canonical factors
associated with a transformed scene using gradient-based optimization over
appearance and pose. We omit the MLP decoder in 2.2 and focus only on the
bottleneck imposed by the factored feature grid of 2.3. Note that the capacity
of the decoder is tightly constrained by performance considerations; TensoRF
[68] and K-Planes [85], for example, use only a single nonlinearity to decode
density and proposal fields respectively.

Concretely, let $\bm{X}_{\natural}\in\mathbb{R}^{n\times n}$ denote the
grayscale image corresponding to the axis-aligned square pattern in Figure
3(a). We can decompose $\bm{X}_{\natural}$ as
$\bm{X}_{\natural}=\bm{u}_{\natural}\bm{v}_{\natural}^{\ast}$, where
$\bm{u}_{\natural}$ and $\bm{v}_{\natural}$ are one-dimensional square pulses
aligned with the support of $\bm{X}_{\natural}$; $\bm{X}_{\natural}$ has rank
one, and can be perfectly reconstructed by a maximally-compact low-rank
feature grid. In contrast, consider exactly the same scene, but with an
additional rotation by an angle of $\nu\in[0,\pi/4]$ applied to yield a
transformed scene $\bm{X}_{\nu}=\bm{X}_{\natural}\circ\bm{\tau}_{\nu}$ (Figure
3(b)). As $\nu$ approaches its maximum value, the rank of the transformed
scene grows to a constant multiple of the resolution $n$, implying that
perfect representation of $\bm{X}_{\nu}$ by a low-rank feature grid demands
essentially as many components as a generic $n\times n$ matrix. Moreover, even
approximate representation of the transformed scene by a pure low-rank grid is
inefficient, as we prove for the instance visualized in Figure 3:

######  Theorem 1 (informal version of Theorem D.1).

There exist absolute constants $c_{0},c_{1}>0$ such that for any target
channel count $F\leq c_{0}n^{1/9.5}$, every rank-$F$ approximation
$\hat{\bm{X}}$ to $\bm{X}_{\pi/4}$ satisfies

$\frac{1}{n^{2}}\left\lVert\hat{\bm{X}}-\bm{X}_{\pi/4}\right\rVert_{\mathrm{F}}^{2}\geq\frac{c_{1}}{1+F}.$

Theorem 1 asserts that a broad class of sublinear-rank approximations to
$\bm{X}_{\nu}$ have mean squared error at least as large as the reciprocal
number of components. Our proofs suggest this lower bound is tight up to
logarithmic factors—in particular, as we illustrate numerically in Figure
3(d), target PSNR levels that are more stringent require larger grid ranks $F$
as the image resolution grows. This situation stands in stark contrast to what
can be achieved by capturing the structure of $\bm{X}_{\natural}$: regardless
of the image resolution, there exists a single canonical factor
$\bm{u}_{\natural}$ which can represent any observation $\bm{X}_{\nu}$ via
composition with a rotation $\bm{\tau}_{\nu}$ (Figure 3(c)). We prove that the
$F=1$ instantiation of this problem successfully represents $\bm{X}_{\nu}$ in
the hard instance visualized in Figure 3 by jointly optimizing over grid
factors and transformations:

######  Theorem 2 (informal version of Theorem D.2).

The infinite-resolution limit of the optimization procedure

$\min_{\phi,\bm{u}}\,\left\lVert\bm{X}_{\pi/4}-\left(\bm{u}\bm{u}^{\ast}\right)\circ\bm{\tau}_{\phi}\right\rVert_{\mathrm{F}}^{2}$
(3.1)

solved with randomly-initialized constant-stepping gradient descent converges
to the true parameters $(\pi/4,\bm{u}_{\natural})$, up to symmetry, at a
linear rate.

Theorem 2 provides theoretical grounding for TILTED’s transformation
optimization approach in an idealized setting. Importantly, there exist
conditions under which the joint learning of the visual representation and
pose parameters provably succeeds. The proof reveals a key principle
underlying the success of this disentangled representation learning: there is
a symbiotic relationship between the model’s representation accuracy and its
alignment accuracy, due to its constrained capacity (i.e., $F=1$ feature
channels). More precisely, incremental improvements to representation quality
under inaccurate alignment help the model localize the scene content and
create texture gradients that promote improvements to alignment; meanwhile,
improvements to alignment allow the model to leverage its constrained capacity
to more accurately represent the scene.

##  4 TILTED

To instantiate the optimization procedure 3.1 in practice, we study a family
of architectures that we call TILTED, implemented based on two goals: (1)
Robustness. TILTED aims to be able to capture a broader set of structures than
methods based on existing factorization techniques. Reconstruction ability
should be invariant to simple transformations like rotations; as discussed
theoretically in Section 3 and later empirically in Section 5, this does not
hold for naively decomposed feature volumes. (2) Generality. TILTED does not
attempt to re-invent the wheel; instead, it is designed to be compatible with
and build directly upon existing approaches [68, 85] for factoring feature
volumes.

Rather than assuming that the projection functions $\texttt{Proj}_{i}$ in 2.3
are static and axis-aligned, TILTED aims at recovery of canonical factors by
replacing the fixed and axis-aligned $\texttt{Proj}_{i}$ with learnable
functions $\texttt{Proj}_{i,\bm{\tau}}$, where $\bm{\tau}$ is a set of
learnable transformation parameters. By substituting into 2.3, the feature
volume interpolation function then becomes:

$\begin{split}\bm{Z}&=\texttt{Reduce}\bigl{(}\bigl{[}\texttt{Interp}_{\bm{F}_{1}}(\texttt{Proj}_{1,\bm{\tau}}(\bm{p}))\bigr{]},\dots,\\\
&\hphantom{=\texttt{Reduce}\bigl{(}\,\,}\bigl{[}\texttt{Interp}_{\bm{F}_{F}}(\texttt{Proj}_{F,\bm{\tau}}(\bm{p}))\bigr{]}\bigr{)}.\end{split}$
(4.1)

The transformations $\bm{\tau}$ enable mapping from arbitrary scene
coordinates to canonicalized domains for each factor $\bm{F}_{i}$. As
illustrated in Figure 1, this can be interpreted as a reconfiguration of
factors to best align with and capture the structure of target signals.

###  4.1 Applying Transformations

The design space for the parameterization of $\bm{\tau}$ and how it is applied
to input coordinates $\bm{p}$ is large. We develop TILTED for the case where
$\bm{\tau}$ is a set of $T$ randomly initialized rotations
$\bm{\tau}=\\{\bm{\tau}_{1}\dots\bm{\tau}_{T}\\}$, parameterized by the unit
circle $\mathbb{S}^{1}$ in 2D and $\mathbb{S}^{3}$ (the universal cover of the
set of rotation matrices $\mathrm{SO}(3)$; i.e., unit quaternions) in 3D. We
suffix variants with the value of $T$; TILTED-4, for example, refers to TILTED
with $4$ learned rotations.

All experiments build atop feature volumes studied in prior work: for 3D, the
CP [3], vector-matrix [68], and K-Planes [85] decompositions, which are each
detailed in Appendix B. K-Planes in 3D is equivalent to a tri-plane [67], but
uses a multiplicative reduction. We characterize each decomposition
architecture using the channel dimension $d$ of its reduced latent vector
$\bm{Z}\in\mathbb{R}^{d}$. We constrain $T$ such that it evenly divides $d$,
and apply rotations to the input coordinates such that each rotation
$\bm{\tau}_{t}$ is used to compute $d/T$ of the final output channels. This
can be interpreted as a vectorized alternative to instantiating $T$ instances
of a given decomposition, each with channel count $d/T$, applying a different
learned rotation to the input of each decomposition, and concatenating
outputs. The resulting formulation has several desirable qualities:

Robustness. When $\bm{\tau}$ is defined by a family of transforms and
optimized from a random initialization, we see two related advantages. First,
as established in Section 3, the latent feature volume becomes able to
represent signals that are not axis-aligned with vastly improved parameter
efficiency. Second, reconstruction quality becomes invariant to the
transformation group encompassed by $\bm{\tau}$. When $\bm{\tau}$ is
constrained to rotations, a rotation applied to the scene becomes equivalent
to a rotation applied to the random initialization of $\bm{\tau}$.

Convergence. Transformation optimization problems like camera registration are
typically challenging and prone to local minima, but optimization in TILTED is
better positioned to succeed. We initialize many transforms: for any given
structure in a scene, only one of these many transforms needs to fall into the
basin of attraction for success. Optimization of individual transforms is also
highly symmetric. Consider rotation optimization over a 2D grid: each
increment of 90 degrees results in a representation with equivalent structure.
Our theoretical analysis, namely Theorem D.2, verifies that these properties
are sufficient for optimization to succeed under idealized conditions.

Overhead. Finally, notice that rotations in this form are inexpensive both to
store and apply. Standard hybrid neural fields can have on the order of
millions of parameters; a library of geometric transformations requires only
dozens. Because coordinate transformations reduce to simple matrix
multiplications, the exerted runtime penalty is also small.

###  4.2 Coarse-to-Fine Optimization

When optimizing over transformations, high frequency signals produce
undesirable local minima. We improve convergence via two coarse-to-fine
optimization strategies.

Figure 4:  Two-phase optimization.  Two TILTED neural fields are trained: the
first using a rank-constrained bottleneck representation (left); all
parameters are discarded except for the projection parameters
$\bm{\tau}_{\text{bneck}}$, which are used for initialization of the final
representation (right).

Dynamic low-pass filtering. Similar to prior work [98, 68], we encode features
interpolated in TILTED’s RGB and SDF experiments with a Fourier embedding
[49]. When these features are used, we adopt the coarse-to-fine strategy
proposed for learning deformation in Nerfies [58] and for camera registration
in BARF [55]. Given $J$ frequencies, we weight the $j$-th frequency band via:

$w^{j}_{k}(\eta_{k})=\frac{1-\cos(\pi\text{clamp}(\eta_{k}-j,0,1))}{2}$

where $k$ is the training step count and $\eta_{k}$ is interpolated from a
linear schedule $\in[0,J]$.

Two-phase optimization. Effective recovery of $\bm{\tau}$ is coupled with the
rank of latent decompositions. As rank is increased, high-frequency signals
become easier to express and overfit to; as a target signal becomes more
explainable without a well-aligned latent structure, optimizers have less
incentive to push $\bm{\tau}$ toward improved solutions.

To help disentangle the $\bm{\tau}$ recovery from the capacity of latent
feature volumes in radiance field experiments, we apply a two-phase strategy
inspired by structure from motion, where procedures like the 8-point algorithm
can be used to initialize Newton-based bundle adjustment. In the first phase,
we train a hybrid field using a channel-limited CP decomposition, which has
limited representational capacity. This produces “bottlenecked” MLP decoder
parameters $\bm{\theta}_{\text{bneck}}$, feature grid parameters
$\bm{\phi}_{\text{bneck}}$, and projection parameters
$\bm{\tau}_{\text{bneck}}$. We discard all parameters but
$\bm{\tau}_{\text{bneck}}$, and then simply set:

$\bm{\tau}_{\text{init}}=\bm{\tau}_{\text{bneck}}$

to initialize the final, more expressive neural field. Example reconstructions
after each phase are displayed in Figure 4.

##  5 Experiments

###  5.1 2D Image Reconstruction

To build intuition in a simple setting, we begin by studying TILTED for 2D
image reconstruction with low-rank feature grids, analogous to our theoretical
studies in Section 3. To evaluate sensitivity to image orientation, we
evaluate two model variants—with an axis-aligned decomposition and with a
TILTED decomposition—on four images rotated by angles sampled uniformly
between 0 and 180, at 10 degree intervals. The setup of models can be
interpreted as the 2D version of a CP decomposition-based neural field [68,
86]. In the axis-aligned case, latent grids are decomposed into $d=64$ vector
pairs, where each vector $\in\mathbb{R}^{128}$. The full latent grid can be
computed by concatenating the outer products of each pair. In the TILTED
variant, we introduce a set of $T=8$ 2D rotations, each of which are applied
to $d/T$ vector pairs. We run experiments that evoke the partially-observable
nature of most reconstruction tasks: we fit a hybrid field with a 2-layer,
32-unit decoder to a randomly subsampled half of the pixels in an image for
training, and use the other half for evaluation. Results over 5 seeds are
reported in Figure 5; differences are mild compared to more complex tasks, but
we nonetheless observe:

(1) TILTED improves robustness. When an axis-aligned decomposition is used,
recovered PSNRs are more volatile, with a difference of as high as 1 PSNR for
the Bricks test image. With the introduction of learned transforms,
reconstruction quality becomes stable to input rotations.

(2) TILTED improves detail recovery. We qualitatively evaluate results by
zooming into reconstructed images in Figure 6. TILTED improves reconstruction
particularly in fine features like the whiskers, which are jagged and
bottlenecked by the factorization in the axis-aligned case, but rendered with
fewer artifacts when we apply TILTED.

Figure 5:  Evaluation images and results for 2D image reconstruction. We apply
rotations to each input image, and plot holdout PSNR for a model trained at
each angle. Axis-aligned feature decompositions are sensitive to
transformations of the input, while TILTED retains a constant PSNR across
angles.  Figure 6:  Fine details without (left) and with (right) TILTED. The
TILTED reconstruction of the whiskers mitigates artifacts from axis-aligned
factors.

###  5.2 Signed Distance Field Reconstruction

IoU $\uparrow$ | 30 | 60 | 90
---|---|---|---
K-Planes |  0.949$\pm$0.015 |  0.952$\pm$0.015 |  0.952$\pm$0.016
w/ TILTED | 0.989$\pm$0.002 | 0.990$\pm$0.002 | 0.991$\pm$0.002
IoU $\uparrow$ | 45 | 90 | 135
Vector-Matrix |  0.970$\pm$0.007 |  0.979$\pm$0.005 |  0.982$\pm$0.003
w/ TILTED | 0.982$\pm$0.003 | 0.989$\pm$0.002 | 0.988$\pm$0.003
Table 1:  Aggregated metrics across models used for SDF experiments. Three
channel count variations are used for each latent decomposition structure.
TILTED improves reconstructions consistently.

Next, we study the impact of TILTED on reconstruction of signed distance
fields. We follow the mesh sampling strategy used for studying signed distance
fields in prior work [76, 83] to produce a set of 8M training points and 16M
evaluation points, and then train hybrid fields based on both VM and K-Plane
decompositions. Evaluation metrics are reported using intersection-over-union
(IoU).

We sweep reconstructions based on both K-Planes and VM, with three channel
counts for each architecture, on 8 different object meshes. Each
representation uses 3 resolutions—32, 128, and 256. For K-Planes, we use
channel counts of 30, 60, and 90; for VM, we use channel counts of 45, 90,
135. All experiments use a 3-layer, 64-unit decoder and 5 transforms. We
observe:

(1) Improved reconstructions across architectures and models. We report the
average IoU for eight objects in Table 1. TILTED improves results for all
decomposition and channel count variants. When we disaggregate results by
object (Appendix C.1), TILTED outperforms its axis-aligned counterpart in all
but one (of 48) examples.

(2) Implicit 3D regularization. To better understand how TILTED impacts SDF
reconstruction, we apply marching cubes [7] to learned fields after training.
Qualitative examples are shown in Figure 7. Renders reveal that the hybrid
field architectures we use, which were proposed for and have not been
extensively studied beyond the context of radiance fields, are prone to
floating artifacts in recovered meshes. The typical solution for artifacts
like these is to adjust the model size or regularization, for example to
increase channel count or encourage spatial smoothness with total variation.
We find that the canonical factors of TILTED achieves a similar effect without
expanding the factorization size or changing the optimized cost function.

Figure 7:  Signed-distance field reconstruction before (above) and after
(below) TILTED. TILTED reduces floating artifacts without expressiveness-
limiting regularization.

###  5.3 Neural Radiance Fields

Our final set of experiments evaluate TILTED in the context of neural radiance
fields for both synthetic and real data.

####  5.3.1 Synthetic Study

We begin with a quantitative study using the NeRF-Synthetic [48] dataset.
While this dataset is commonly used for evaluation of neural field
architectures [48, 68, 70, 85, 83, 79], it is unrealistic because objects are
rendered in Blender and perfectly axis-aligned. The bricks of the Lego scene,
for example, are exactly lined up with the coordinate system that camera poses
are defined in. To better understand the robustness of representations, we
compare NeRF-Synthetic against the randomly rotated variant used by [49]. We
refer to this dataset as NeRF-SyntheticSO(3). In NeRF-SyntheticSO(3), an
experiment for any given random seed begins training by applying a uniformly
sampled $\text{SO}(3)$ rotation to all camera poses. Robustness against this
basic operation is critical for real-world data, where axis-alignment is
rarely well-defined, let alone provided.

For each of the NeRF-Synthetic and NeRF-SyntheticSO(3) datasets, we train
every combination of: (1) two decompositions: VM and K-Planes, each 32
channels per factor, (2) three parameterizations of $\bm{\tau}$: axis-aligned
(baseline), 4 transforms, and 8 transforms, (3) eight scenes: chair, drums,
ficus, hotdog, lego, materials, mic, and ship, and (4) three random seeds: we
use 0, 1, and 2. To eliminate the possibility of bounding box clipping
artifacts interfering with results, we use enlarged scene bounding boxes of
$[-1.6,1.6]$; this exerts a noticeable but uniform penalty on PSNR metrics
relative to results with smaller standard bounding boxes. We additionally
incorporate the proposal fields, histogram loss, and distortion loss proposed
by MipNeRF-360 [65]. Our core conclusions are:

(1) Naive hybrid representations have strong axis-alignment biases. Results
from the axis-aligned factorizations mirror our theoretical results in Section
3. When an axis-aligned decomposition is used, the quality of reconstructions
becomes highly sensitive to the orientation of the target input. In Table 2,
we observe as high as a 2 PSNR drop from scene rotation on the Lego dataset.
In contrast, TILTED is designed with invariance in mind, and is thus robust to
these transformations.

(2) TILTED improves reconstructions. On the NeRF-SyntheticSO(3) dataset, we
observe performance increases from learned transforms, increasing the number
of optimized transformations, and adopting two-phase optimization. Table 3
highlights how TILTED improves PSNRs for the NeRF-SyntheticSO(3) dataset,
while Table 4 demonstrates how components of our method (multiple transforms
and two-phase optimization) improve results.

| K-Planes | VM
---|---|---
Lego |  35.31$\pm$0.02 $\to$ 33.29$\pm$0.11 |  34.24$\pm$0.04 $\to$ 32.63$\pm$0.01
Avg. |  32.12$\pm$0.02 $\to$ 31.62$\pm$0.04 |  31.30$\pm$0.03 $\to$ 30.76$\pm$0.03

Table 2:  PSNR decrease of prior methods, before and after random scene
rotation. Metrics are reported from NeRF-Synthetic (standard, axis-aligned)
$\to\ $ NeRF-SyntheticSO(3)(randomly rotated). Without TILTED, a simple
rotation of the scene coordinate frame can lead to as high as a 2 PSNR drop in
performance.

| K-Planes | w/ TILTED | VM | w/ TILTED
---|---|---|---|---
Lego | 33.29$\pm$0.11 | 34.35$\pm$0.07 | 32.63$\pm$0.01 | 33.90$\pm$0.06
Avg. | 31.62$\pm$0.04 | 31.91$\pm$0.04 | 30.76$\pm$0.03 | 31.08$\pm$0.02

Table 3:  PSNR improvement after incorporating TILTED, on the NeRF-SyntheticSO(3) dataset. TILTED offers transform-invariant reconstruction quality and moderate PSNR improvements.  | 8 transforms | 4 transforms
---|---|---
Two-Phase | 34.35$\pm$0.07 | 34.19$\pm$0.22
Without | 33.95$\pm$0.15 | 33.83$\pm$0.08
Table 4:  Ablations on the Lego synthetic dataset. Two-phase optimization and
an increased number of transforms synergistically improve reconstruction
quality. Similar but weaker trends can be found in less structured scenes.
Reported metrics use the K-Planes model.

####  5.3.2 Real-World Study

(a) Kitchen

(b) Giannini

(c) Stump

(d) Storefront

Figure 8:  Real-world radiance field comparisons, before (left) and after
(right) TILTED. For each scene, we arrange in three rows the outputs of (i)
rendering RGB images, (ii) visualizing the structure-revealing $\ell^{2}$-norm
of interpolated features, and (iii) mapping the top three principal components
of interpolated features to RGB. TILTED feature volumes result in better
reconstruction quality, with more structured, interpretable, and expressive
features. Results in this figure are from K-Planes.

In our final set of experiments, we apply TILTED to 18 real-world scenes made
available via Nerfstudio [97]. We modify architectures with (a) an
$\ell^{\infty}$ norm-based scene contraction (Equation A.1) to handle the
unbounded nature of real-world data, (b) camera pose optimization to account
for noisy camera poses, and (c) NeRF-W-style appearance embeddings [56]. Once
camera pose optimization and per-camera appearance embeddings are enabled, we
lose the ability to reliably compute evaluation metrics [97]. Instead, we
examine how incorporating TILTED impacts training PSNRs and qualitative
results.

(1) On real-world data, TILTED can simultaneously halve the memory footprint
of a model, accelerate training by 25%, and improve reconstructions. In Table
5, we compare standard factored neural field representations with two
techniques for improving reconstructions: doubling the feature volume channel
count and TILTED. Compared to an axis-aligned model of the same size, TILTED
improves reconstruction performance on all scenes. It also outperforms axis-
aligned models with 2x higher channel counts in most cases (72% of the time
for VM, 56% for K-Planes), thus cutting parameter count by almost half while
training 25% faster (11:04 vs 14:46 for 30k steps).

(2) Recovered transforms align factors to underlying scene geometry. In Figure
8, we visualize both renders and underlying latent features. We display a
norm-based latent visualization, which involves volume rendering a map of
feature norms using standard NeRF densities, and a PCA-based approach, which
maps latent vectors to RGB. Evoking the model problem result of Theorem 2,
TILTED factors interpretably align themself to the geometry of scenes while
enabling more detailed and expressive feature volumes.

(3) Standard evaluations incentivize axis-alignment biases. Despite
significantly outperforming axis-aligned baselines on both real-world data and
NeRF-Synthetic, we note that TILTED underperforms against baselines on the
axis-aligned NeRF-Synthetic dataset. This hints at room for further
performance optimizations of our method, while highlighting flaws in the way
that radiance fields architectures are often evaluated. Aiming to improve
standard evaluation metrics (like PSNR on the NeRF-Synthetic dataset) can end
up undermining real-world capabilities.

Dataset | K-Plane / 2x / TILTED | VM / 2x / TILTED
---|---|---
Kitchen | 25.95 / 26.91 / 27.12 | 25.63 / 26.54 / 26.90
Floating | 24.58 / 25.17 / 25.06 | 24.03 / 24.70 / 25.04
Poster | 33.14 / 33.71 / 33.79 | 32.84 / 33.49 / 33.61
Redwoods | 23.55 / 24.08 / 24.12 | 23.22 / 23.81 / 23.85
Stump | 26.82 / 27.29 / 27.28 | 26.33 / 26.83 / 26.97
Vegetation | 21.62 / 22.10 / 22.10 | 21.11 / 21.55 / 21.73
BWW | 24.64 / 25.06 / 24.95 | 24.22 / 24.75 / 24.80
Library | 25.24 / 25.68 / 25.78 | 25.50 / 25.78 / 25.84
Storefront | 29.71 / 30.12 / 29.87 | 29.15 / 29.77 / 29.87
Dozer | 22.37 / 22.88 / 22.69 | 21.91 / 22.46 / 22.40
Egypt | 20.69 / 21.10 / 21.12 | 20.84 / 21.17 / 21.09
Person | 24.83 / 24.93 / 25.36 | 25.28 / 25.38 / 25.39
Giannini | 20.51 / 20.90 / 20.82 | 20.27 / 20.64 / 20.60
Sculpture | 23.20 / 23.40 / 23.40 | 22.86 / 23.07 / 23.28
Plane | 22.75 / 23.00 / 23.01 | 22.53 / 22.84 / 22.74
Aspen | 15.99 / 16.20 / 16.21 | 15.98 / 16.15 / 16.20
Desolation | 22.14 / 22.40 / 22.25 | 21.88 / 22.11 / 22.12
Campanile | 24.27 / 24.64 / 24.37 | 23.97 / 24.35 / 24.19

Table 5:  For real-world data, TILTED improves PSNRs on all evaluated scenes,
typically outperforming even much larger axis-aligned models. We compare:
standard hybrid neural fields (K-Plane, VM), axis-aligned fields with channel
counts doubled (2x), and the fields with the original channel count but
addition of TILTED (TILTED).

##  6 Conclusion

We demonstrate the importance of alignment for factored feature volumes via
TILTED, an extension to existing hybrid neural field architectures based on
the idea of canonical factors. By aligning to and thus capturing the structure
of a scene, TILTED enables improvements across reconstruction detail,
compactness, and runtime. We also developed the theoretical foundations for
this methodology; our analysis can be viewed as providing the first provable
guarantee for explicit disentangled representation learning with visual data
beyond spatial deconvolution (e.g., [47]), here disentangling appearance and
pose.

Many directions exist for extending our work, both practically and
theoretically. On the practical side, these include further explorations of
convergence characteristics, more diverse families of transformations, and
“scaling laws” — how methods like TILTED interact with larger representations
or scenes. On the theoretical side, possible future work includes extending
our results to overparameterized models, MLPs, and scenes with visual clutter.
We also note that our work compares TILTED neural fields only to their axis-
aligned equivalents: while an abundance of prior work has shown the unique
advantages of these representations over alternatives, many applications will
still benefit from alternative techniques [76, 90].

Acknowledgements. This material is based upon work supported by the National
Science Foundation Graduate Research Fellowship Program under Grant DGE
2146752. YM acknowledges partial support from the ONR grant N00014-22-1-2102,
the joint Simons Foundation-NSF DMS grant 2031899, and a research grant from
TBSI. The authors thank Justin Kerr, Chung Min Kim, Sara Fridovich-Keil, Druv
Pai, and members of the Nerfstudio team for implementation references,
technical discussions, and suggestions.

## References

  * [1] Carl Eckart and Gale Young “The approximation of one matrix by another of lower rank” In _Psychometrika_ 1.3, 1936, pp. 211–218 DOI: 10.1007/BF02288367
  * [2] L Mirsky “SYMMETRIC GAUGE FUNCTIONS AND UNITARILY INVARIANT NORMS” In _The Quarterly Journal of Mathematics_ 11.1 Oxford Academic, 1960, pp. 50–59 DOI: 10.1093/qmath/11.1.50
  * [3] J Douglas Carroll and Jih-Jie Chang “Analysis of individual differences in multidimensional scaling via an N-way generalization of “Eckart-Young” decomposition” In _Psychometrika_ 35.3 Springer, 1970, pp. 283–319
  * [4] Chandler Davis and W M Kahan “The Rotation of Eigenvectors by a Perturbation. III” In _SIAM Journal on Numerical Analysis_ 7.1 Society for IndustrialApplied Mathematics, 1970, pp. 1–46 DOI: 10.1137/0707001
  * [5] Elias M Stein and Guido Weiss “Introduction to Fourier Analysis on Euclidean Spaces” Princeton University Press, 1971 URL: https://market.android.com/details?id=book-YUCV678MNAIC
  * [6] R Keys “Cubic convolution interpolation for digital image processing” In _IEEE transactions on Acoustics, Speech, and Signal Processing_ 29.6, 1981, pp. 1153–1160 DOI: 10.1109/TASSP.1981.1163711
  * [7] William E Lorensen and Harvey E Cline “Marching cubes: A high resolution 3D surface construction algorithm” In _ACM SIGGRAPH Computer Graphics_ 21.4 ACM New York, NY, USA, 1987, pp. 163–169
  * [8] Lisa Gottesfeld Brown “A survey of image registration techniques” In _ACM Comput. Surv._ 24.4 New York, NY, USA: Association for Computing Machinery, 1992, pp. 325–376 DOI: 10.1145/146370.146374
  * [9] J Kuczyński and H Woźniakowski “Estimating the Largest Eigenvalue by the Power and Lanczos Algorithms with a Random Start” In _SIAM Journal on Matrix Analysis and Applications_ 13.4 Society for IndustrialApplied Mathematics, 1992, pp. 1094–1122 DOI: 10.1137/0613066
  * [10] Rajendra Bhatia “Matrix Analysis” Springer, New York, NY, 1997 DOI: 10.1007/978-1-4612-0653-8
  * [11] J B Antoine Maintz and Max A Viergever “A survey of medical image registration” In _Med. Image Anal._ 2.1, 1998, pp. 1–36 DOI: 10.1016/S1361-8415(01)80026-8
  * [12] Jor-Ting Chan, Chi-Kwong Li and Charlies Tu “A class of unitarily invariant norms on B(H)” In _Proceedings of the American Mathematical Society_ 129.4 American Mathematical Society (AMS), 2000, pp. 1065–1076 DOI: 10.1090/s0002-9939-00-05692-6
  * [13] Martin Lefébure and Laurent D Cohen “Image Registration, Optical Flow and Local Rigidity” In _Journal of Mathematical Imaging and Vision_ 14.2, 2001, pp. 131–147 DOI: 10.1023/A:1011259231755
  * [14] M I Miller and L Younes “Group Actions, Homeomorphisms, and Matching: A General Framework” In _International Journal of Computer Vision_ 41.1, 2001, pp. 61–84 DOI: 10.1023/A:1011161132514
  * [15] Simon Baker and Iain Matthews “Lucas-Kanade 20 Years On: A Unifying Framework” In _Int. J. Comput. Vis._ 56.3, 2004, pp. 221–255 DOI: 10.1023/B:VISI.0000011205.11775.fd
  * [16] Yurii Nesterov “Introductory Lectures on Convex Optimization: A Basic Course”, Applied Optimization Springer US, 2004 DOI: 10.1007/978-1-4419-8853-9
  * [17] Richard Szeliski “Image Alignment and Stitching: A Tutorial” In _Foundations and Trends® in Computer Graphics and Vision_ 2.1 Now Publishers, 2007, pp. 1–104 DOI: 10.1561/0600000009
  * [18] Haim Brezis “Functional Analysis, Sobolev Spaces and Partial Differential Equations” Springer, New York, NY, 2011 DOI: 10.1007/978-0-387-70914-7
  * [19] Christopher Heil “A Basis Theory Primer: Expanded Edition” Birkhäuser Boston, 2011 DOI: 10.1007/978-0-8176-4687-5
  * [20] Dan Cireşan, Ueli Meier and Juergen Schmidhuber “Multi-column deep neural networks for image classification” In _2012 IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ Los Alamitos, CA, USA: IEEE Computer Society, 2012, pp. 3642–3649 DOI: 10.1109/CVPR.2012.6248110
  * [21] Stéphane Mallat “Group Invariant Scattering” In _Commun. Pure Appl. Math._ 65.10, 2012, pp. 1331–1398 DOI: 10.1002/cpa.21413
  * [22] Kihyuk Sohn and Honglak Lee “Learning invariant representations with local transformations” In _Proceedings of the 29th International Coference on International Conference on Machine Learning_ , 2012, pp. 1339–1346 URL: https://dl.acm.org/citation.cfm?id=3042573.3042745
  * [23] Zhengdong Zhang, Arvind Ganesh, Xiao Liang and Yi Ma “TILT: Transform Invariant Low-Rank Textures” In _International Journal of Computer Vision_ 99.1 Springer, 2012, pp. 1–24 DOI: 10.1007/s11263-012-0515-x
  * [24] Angjoo Kanazawa, Abhishek Sharma and David Jacobs “Locally Scale-Invariant Convolutional Neural Networks”, 2014 arXiv: http://arxiv.org/abs/1412.5104
  * [25] Diederik P Kingma and Jimmy Ba “Adam: A method for stochastic optimization” In _arXiv preprint arXiv:1412.6980_ , 2014
  * [26] Elif Vural and Pascal Frossard “Analysis of Image Registration with Tangent Distance” In _SIAM Journal on Imaging Sciences_ 7.4 Society for IndustrialApplied Mathematics, 2014, pp. 2860–2915 DOI: 10.1137/140974559
  * [27] Sander Dieleman, Kyle W. Willett and Joni Dambre “Rotation-invariant convolutional neural networks for galaxy morphology prediction” In _Monthly Notices of the Royal Astronomical Society_ 450.2, 2015, pp. 1441–1459 DOI: 10.1093/mnras/stv632
  * [28] Benjamin D Haeffele and Rene Vidal “Global Optimality in Tensor Factorization, Deep Learning, and Beyond”, 2015 arXiv: http://arxiv.org/abs/1506.07540
  * [29] Max Jaderberg, Karen Simonyan, Andrew Zisserman and Koray Kavukcuoglu “Spatial Transformer Networks” In _Proceedings of the 28th International Conference on Neural Information Processing Systems_ , 2015, pp. 2017–2025
  * [30] Dmitry Laptev, Nikolay Savinov, Joachim M. Buhmann and Marc Pollefeys “TI-Pooling: Transformation-Invariant Pooling for Feature Learning in Convolutional Neural Networks” In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2016
  * [31] Jifeng Dai, Haozhi Qi, Yuwen Xiong, Yi Li, Guodong Zhang, Han Hu and Yichen Wei “Deformable convolutional networks” In _Proceedings of the IEEE International Conference on Computer Vision_ , 2017, pp. 764–773 URL: http://openaccess.thecvf.com/content_iccv_2017/html/Dai_Deformable_Convolutional_Networks_ICCV_2017_paper.html
  * [32] Rong Ge, Chi Jin and Yi Zheng “No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis” In _Proceedings of the 34th International Conference on Machine Learning_ 70, 2017, pp. 1233–1242 URL: https://proceedings.mlr.press/v70/ge17a.html
  * [33] Chen-Hsuan Lin and Simon Lucey “Inverse Compositional Spatial Transformer Networks” In _2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2017 DOI: 10.1109/cvpr.2017.242
  * [34] Daniel E. Worrall, Stephan J. Garbin, Daniyar Turmukhambetov and Gabriel J. Brostow “Harmonic Networks: Deep Translation and Rotation Equivariance” In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2017
  * [35] Yuanzhi Li, Tengyu Ma and Hongyang Zhang “Algorithmic Regularization in Over-parameterized Matrix Sensing and Neural Networks with Quadratic Activations” In _Proceedings of the 31st Conference On Learning Theory_ 75 PMLR, 2018, pp. 2–47 URL: https://proceedings.mlr.press/v75/li18a.html
  * [36] Roman Vershynin “High-Dimensional Probability: An Introduction with Applications in Data Science” Cambridge University Press, 2018 DOI: 10.1017/9781108231596
  * [37] Thomas Wiatowski and Helmut Bölcskei “A Mathematical Theory of Deep Convolutional Neural Networks for Feature Extraction” In _IEEE Trans. Inf. Theory_ 64.3, 2018, pp. 1845–1866 DOI: 10.1109/TIT.2017.2776228
  * [38] Yu Bai, Qijia Jiang and Ju Sun “Subgradient Descent Learns Orthogonal Dictionaries” In _International Conference on Learning Representations_ , 2019 URL: https://openreview.net/forum?id=HklSf3CqKm
  * [39] Gary Becigneul and Octavian-Eugen Ganea “Riemannian Adaptive Optimization Methods” In _International Conference on Learning Representations_ , 2019 URL: https://openreview.net/forum?id=r1eiqi09K7
  * [40] Zhiqin Chen and Hao Zhang “Learning implicit fields for generative shape modeling” In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2019, pp. 5939–5948
  * [41] Yuejie Chi, Yue M Lu and Yuxin Chen “Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview” In _IEEE Transactions on Signal Processing_ 67.20, 2019, pp. 5239–5269 DOI: 10.1109/TSP.2019.2937282
  * [42] Dar Gilboa, Sam Buchanan and John Wright “Efficient Dictionary Learning with Gradient Descent” In _Proceedings of the 36th International Conference on Machine Learning_ 97 PMLR, 2019, pp. 2252–2259 URL: http://proceedings.mlr.press/v97/gilboa19a.html
  * [43] Lars Mescheder, Michael Oechsle, Michael Niemeyer, Sebastian Nowozin and Andreas Geiger “Occupancy networks: Learning 3d reconstruction in function space” In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2019, pp. 4460–4470
  * [44] Jeong Joon Park, Peter Florence, Julian Straub, Richard Newcombe and Steven Lovegrove “Deepsdf: Learning continuous signed distance functions for shape representation” In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2019, pp. 165–174
  * [45] Shunsuke Saito, Zeng Huang, Ryota Natsume, Shigeo Morishima, Angjoo Kanazawa and Hao Li “Pifu: Pixel-aligned implicit function for high-resolution clothed human digitization” In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , 2019, pp. 2304–2314
  * [46] Tero Karras, Samuli Laine, Miika Aittala, Janne Hellsten, Jaakko Lehtinen and Timo Aila “Analyzing and improving the image quality of stylegan” In _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ , 2020, pp. 8110–8119
  * [47] Han-Wen Kuo, Yuqian Zhang, Yenson Lau and John Wright “Geometry and Symmetry in Short-and-Sparse Deconvolution” In _SIAM Journal on Mathematics of Data Science_ 2.1 Society for IndustrialApplied Mathematics, 2020, pp. 216–245 DOI: 10.1137/19M1237569
  * [48] Ben Mildenhall, Pratul P. Srinivasan, Matthew Tancik, Jonathan T. Barron, Ravi Ramamoorthi and Ren Ng “NeRF: Representing Scenes as Neural Radiance Fields for View Synthesis” In _ECCV_ , 2020
  * [49] Matthew Tancik, Pratul P. Srinivasan, Ben Mildenhall, Sara Fridovich-Keil, Nithin Raghavan, Utkarsh Singhal, Ravi Ramamoorthi, Jonathan T. Barron and Ren Ng “Fourier Features Let Networks Learn High Frequency Functions in Low Dimensional Domains” In _NeurIPS_ , 2020
  * [50] Yuqian Zhang, Qing Qu and John Wright “From Symmetry to Geometry: Tractable Nonconvex Problems”, 2020 arXiv: http://arxiv.org/abs/2007.06753
  * [51] Zhimin Zhang, Jinpan Fang, Jaduo Lin, Shancheng Zhao, Fengjun Xiao and Jinming Wen “Improved upper bound on the complementary error function” In _Electronics Letters_ 56.13 Institution of EngineeringTechnology (IET), 2020, pp. 663–665 DOI: 10.1049/el.2020.0979
  * [52] Forrester Cole, Kyle Genova, Avneesh Sud, Daniel Vlasic and Zhoutong Zhang “Differentiable surface rendering via non-differentiable sampling” In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , 2021, pp. 6088–6097
  * [53] Stephan J Garbin, Marek Kowalski, Matthew Johnson, Jamie Shotton and Julien Valentin “Fastnerf: High-fidelity neural rendering at 200fps” In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , 2021, pp. 14346–14355
  * [54] Peter Hedman, Pratul P Srinivasan, Ben Mildenhall, Jonathan T Barron and Paul Debevec “Baking neural radiance fields for real-time view synthesis” In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , 2021, pp. 5875–5884
  * [55] Chen-Hsuan Lin, Wei-Chiu Ma, Antonio Torralba and Simon Lucey “BARF: Bundle-Adjusting Neural Radiance Fields” In _IEEE International Conference on Computer Vision (ICCV)_ , 2021
  * [56] Ricardo Martin-Brualla, Noha Radwan, Mehdi SM Sajjadi, Jonathan T Barron, Alexey Dosovitskiy and Daniel Duckworth “Nerf in the wild: Neural radiance fields for unconstrained photo collections” In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2021, pp. 7210–7219
  * [57] Michael Oechsle, Songyou Peng and Andreas Geiger “Unisurf: Unifying neural implicit surfaces and radiance fields for multi-view reconstruction” In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , 2021, pp. 5589–5599
  * [58] Keunhong Park, Utkarsh Sinha, Jonathan T Barron, Sofien Bouaziz, Dan B Goldman, Steven M Seitz and Ricardo Martin-Brualla “Nerfies: Deformable neural radiance fields” In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , 2021, pp. 5865–5874
  * [59] Christian Reiser, Songyou Peng, Yiyi Liao and Andreas Geiger “Kilonerf: Speeding up neural radiance fields with thousands of tiny mlps” In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , 2021, pp. 14335–14345
  * [60] Dominik Stöger and Mahdi Soltanolkotabi “Small random initialization is akin to spectral learning: Optimization and generalization guarantees for overparameterized low-rank matrix reconstruction” In _Advances in Neural Information Processing Systems_ 34, 2021, pp. 23831–23843 URL: https://proceedings.neurips.cc/paper_files/paper/2021/file/c82836ed448c41094025b4a872c5341e-Paper.pdf
  * [61] Peng Wang, Lingjie Liu, Yuan Liu, Christian Theobalt, Taku Komura and Wenping Wang “NeuS: Learning Neural Implicit Surfaces by Volume Rendering for Multi-view Reconstruction” In _Advances in Neural Information Processing Systems_ , 2021, pp. 27171–27183 URL: https://proceedings.neurips.cc/paper_files/paper/2021/file/e41e164f7485ec4a28741a2d0ea41c74-Paper.pdf
  * [62] Lior Yariv, Jiatao Gu, Yoni Kasten and Yaron Lipman “Volume rendering of neural implicit surfaces” In _Advances in Neural Information Processing Systems_ 34, 2021, pp. 4805–4815
  * [63] Alex Yu, Ruilong Li, Matthew Tancik, Hao Li, Ren Ng and Angjoo Kanazawa “Plenoctrees for real-time rendering of neural radiance fields” In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , 2021, pp. 5752–5761
  * [64] Xizhou Zhu, Weijie Su, Lewei Lu, Bin Li, Xiaogang Wang and Jifeng Dai “Deformable DETR: Deformable Transformers for End-to-End Object Detection” In _International Conference on Learning Representations_ , 2021 URL: https://openreview.net/forum?id=gZ9hCDWe6ke
  * [65] Jonathan T Barron, Ben Mildenhall, Dor Verbin, Pratul P Srinivasan and Peter Hedman “Mip-NeRF 360: Unbounded anti-aliased neural radiance fields” In _2022 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ IEEE, 2022 DOI: 10.1109/cvpr52688.2022.00539
  * [66] Sam Buchanan, Jingkai Yan, Ellie Haber and John Wright “Resource-Efficient Invariant Networks: Exponential Gains by Unrolled Optimization”, 2022 arXiv: http://arxiv.org/abs/2203.05006
  * [67] Eric R Chan, Connor Z Lin, Matthew A Chan, Koki Nagano, Boxiao Pan, Shalini De Mello, Orazio Gallo, Leonidas J Guibas, Jonathan Tremblay, Sameh Khamis, Tero Karras and Gordon Wetzstein “Efficient geometry-aware 3D generative adversarial networks” In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2022, pp. 16123–16133
  * [68] Anpei Chen, Zexiang Xu, Andreas Geiger, Jingyi Yu and Hao Su “TensoRF: Tensorial Radiance Fields” In _European Conference on Computer Vision (ECCV)_ , 2022
  * [69] Pete Florence, Corey Lynch, Andy Zeng, Oscar A Ramirez, Ayzaan Wahid, Laura Downs, Adrian Wong, Johnny Lee, Igor Mordatch and Jonathan Tompson “Implicit behavioral cloning” In _Conference on Robot Learning_ , 2022, pp. 158–168 PMLR
  * [70] Sara Fridovich-Keil, Alex Yu, Matthew Tancik, Qinhong Chen, Benjamin Recht and Angjoo Kanazawa “Plenoxels: Radiance Fields Without Neural Networks” In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2022, pp. 5501–5510
  * [71] Xiao Fu, Shangzhan Zhang, Tianrun Chen, Yichong Lu, Lanyun Zhu, Xiaowei Zhou, Andreas Geiger and Yiyi Liao “Panoptic NeRF: 3D-to-2D label transfer for panoptic urban scene segmentation” In _2022 International Conference on 3D Vision (3DV)_ , 2022 DOI: 10.1109/3dv57658.2022.00042
  * [72] Ylva Jansson and Tony Lindeberg “Scale-Invariant Scale-Channel Networks: Deep Networks That Generalise to Previously Unseen Scales” In _Journal of Mathematical Imaging and Vision_ 64.5, 2022, pp. 506–536 DOI: 10.1007/s10851-022-01082-2
  * [73] Animesh Karnewar, Tobias Ritschel, Oliver Wang and Niloy Mitra “ReLU Fields: The Little Non-Linearity That Could” In _ACM SIGGRAPH 2022 Conference Proceedings_ New York, NY, USA: Association for Computing Machinery, 2022 DOI: 10.1145/3528233.3530707
  * [74] Abhijit Kundu, Kyle Genova, Xiaoqi Yin, Alireza Fathi, Caroline Pantofaru, Leonidas Guibas, Andrea Tagliasacchi, Frank Dellaert and Thomas Funkhouser “Panoptic Neural Fields: A Semantic Object-Aware Neural Scene Representation” In _CVPR_ , 2022
  * [75] Zhi-Hao Lin, Wei-Chiu Ma, Hao-Yu Hsu, Yu-Chiang Frank Wang and Shenlong Wang “NeurMiPs: Neural Mixture of Planar Experts for View Synthesis” In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2022, pp. 15702–15712
  * [76] Thomas Müller, Alex Evans, Christoph Schied and Alexander Keller “Instant neural graphics primitives with a multiresolution hash encoding” In _ACM Transactions on Graphics_ 41.4 New York, NY, USA: Association for Computing Machinery, 2022, pp. 1–15 DOI: 10.1145/3528223.3530127
  * [77] Anton Obukhov, Mikhail Usvyatsov, Christos Sakaridis, Konrad Schindler and Luc Van Gool “TT-NF: Tensor Train Neural Fields”, 2022 arXiv: http://arxiv.org/abs/2209.15529
  * [78] Robin Rombach, Andreas Blattmann, Dominik Lorenz, Patrick Esser and Bjorn Ommer “High-resolution image synthesis with latent diffusion models” In _2022 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2022 DOI: 10.1109/cvpr52688.2022.01042
  * [79] Cheng Sun, Min Sun and Hwann-Tzong Chen “Direct Voxel Grid Optimization: Super-Fast Convergence for Radiance Fields Reconstruction” In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2022, pp. 5459–5469
  * [80] Suhani Vora, Noha Radwan, Klaus Greff, Henning Meyer, Kyle Genova, Mehdi S.. Sajjadi, Etienne Pot, Andrea Tagliasacchi and Daniel Duckworth “NeSF: Neural Semantic Fields for Generalizable Semantic Segmentation of 3D Scenes” In _Transactions on Machine Learning Research_ , 2022 URL: https://openreview.net/forum?id=ggPhsYCsm9
  * [81] Zihan Zhu, Songyou Peng, Viktor Larsson, Weiwei Xu, Hujun Bao, Zhaopeng Cui, Martin R. Oswald and Marc Pollefeys “NICE-SLAM: Neural Implicit Scalable Encoding for SLAM” In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2022, pp. 12786–12796
  * [82] Ang Cao and Justin Johnson “HexPlane: A Fast Representation for Dynamic Scenes” In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2023, pp. 130–141
  * [83] Anpei Chen, Zexiang Xu, Xinyue Wei, Siyu Tang, Hao Su and Andreas Geiger “Factor Fields: A Unified Framework for Neural Fields and Beyond”, 2023 arXiv: http://arxiv.org/abs/2302.01226
  * [84] Hansheng Chen, Jiatao Gu, Anpei Chen, Wei Tian, Zhuowen Tu, Lingjie Liu and Hao Su “Single-Stage Diffusion NeRF: A Unified Approach to 3D Generation and Reconstruction”, 2023 arXiv:2304.06714 [cs.CV]
  * [85] Sara Fridovich-Keil, Giacomo Meanti, Frederik Rahbæk Warburg, Benjamin Recht and Angjoo Kanazawa “K-Planes: Explicit Radiance Fields in Space, Time, and Appearance” In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2023, pp. 12479–12488
  * [86] Quankai Gao, Qiangeng Xu, Hao Su, Ulrich Neumann and Zexiang Xu “Strivec: Sparse Tri-Vector Radiance Fields”, 2023 arXiv: http://arxiv.org/abs/2307.13226
  * [87] Lily Goli, Daniel Rebain, Sara Sabour, Animesh Garg and Andrea Tagliasacchi “nerf2nerf: Pairwise Registration of Neural Radiance Fields” In _2023 IEEE International Conference on Robotics and Automation (ICRA)_ , 2023, pp. 9354–9361 DOI: 10.1109/ICRA48891.2023.10160794
  * [88] Wenbo Hu, Yuling Wang, Lin Ma, Bangbang Yang, Lin Gao, Xiao Liu and Yuewen Ma “Tri-MipRF: Tri-Mip Representation for Efficient Anti-Aliasing Neural Radiance Fields”, 2023 arXiv: http://arxiv.org/abs/2307.11335
  * [89] Mohammad Mahdi Johari, Camilla Carta and François Fleuret “ESLAM: Efficient Dense SLAM System Based on Hybrid Representation of Signed Distance Fields” In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2023, pp. 17408–17419
  * [90] Bernhard Kerbl, Georgios Kopanas, Thomas Leimkuehler and George Drettakis “3D Gaussian Splatting for Real-Time Radiance Field Rendering” In _ACM Transactions on Graphics (TOG)_ 42.4 ACM New York, NY, USA, 2023, pp. 1–14
  * [91] Justin Kerr, Chung Min Kim, Ken Goldberg, Angjoo Kanazawa and Matthew Tancik “LERF: Language Embedded Radiance Fields”, 2023 arXiv: http://arxiv.org/abs/2303.09553
  * [92] Andréas Meuleman, Yu-Lun Liu, Chen Gao, Jia-Bin Huang, Changil Kim, Min H. Kim and Johannes Kopf “Progressively Optimized Local Radiance Fields for Robust View Synthesis” In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2023, pp. 16539–16548
  * [93] Sungheon Park, Minjung Son, Seokhwan Jang, Young Chun Ahn, Ji-Yeon Kim and Nahyup Kang “Temporal Interpolation Is All You Need for Dynamic Neural Radiance Fields” In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2023, pp. 4212–4221
  * [94] Christian Reiser, Rick Szeliski, Dor Verbin, Pratul Srinivasan, Ben Mildenhall, Andreas Geiger, Jon Barron and Peter Hedman “MERF: Memory-Efficient Radiance Fields for Real-time View Synthesis in Unbounded Scenes” In _ACM Transactions on Graphics_ 42.4 Association for Computing Machinery, 2023, pp. 1–12 URL: https://doi.org/10.1145/3592426
  * [95] Ruizhi Shao, Zerong Zheng, Hanzhang Tu, Boning Liu, Hongwen Zhang and Yebin Liu “Tensor4D: Efficient Neural 4D Decomposition for High-Fidelity Dynamic Reconstruction and Rendering” In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2023, pp. 16632–16642
  * [96] J Ryan Shue, Eric Ryan Chan, Ryan Po, Zachary Ankner, Jiajun Wu and Gordon Wetzstein “3d neural field generation using triplane diffusion” In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2023, pp. 20875–20886
  * [97] Matthew Tancik, Ethan Weber, Evonne Ng, Ruilong Li, Brent Yi, Terrance Wang, Alexander Kristoffersen, Jake Austin, Kamyar Salahi, Abhik Ahuja, David Mcallister, Justin Kerr and Angjoo Kanazawa “Nerfstudio: A Modular Framework for Neural Radiance Field Development” In _ACM SIGGRAPH 2023 Conference Proceedings_ Association for Computing Machinery, 2023, pp. 1–12 URL: https://doi.org/10.1145/3588432.3591516
  * [98] Tengfei Wang, Bo Zhang, Ting Zhang, Shuyang Gu, Jianmin Bao, Tadas Baltrusaitis, Jingjing Shen, Dong Chen, Fang Wen, Qifeng Chen and Baining Guo “RODIN: A Generative Model for Sculpting 3D Digital Avatars Using Diffusion” In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2023, pp. 4563–4573
  * [99] Rachel Ward and Tamara G Kolda “Convergence of Alternating Gradient Descent for Matrix Factorization”, 2023 arXiv: http://arxiv.org/abs/2305.06927
  * [100] Thomas Weng, David Held, Franziska Meier and Mustafa Mukadam “Neural Grasp Distance Fields for Robot Manipulation” In _2023 IEEE International Conference on Robotics and Automation (ICRA)_ , 2023, pp. 1814–1821 DOI: 10.1109/ICRA48891.2023.10160217
  * [101] Xingyu Xu, Yandi Shen, Yuejie Chi and Cong Ma “The Power of Preconditioning in Overparameterized Low-Rank Matrix Sensing” In _Proceedings of the 40th International Conference on Machine Learning_ 202 PMLR, 2023, pp. 38611–38654 URL: https://proceedings.mlr.press/v202/xu23o.html
  * [102] Lior Yariv, Peter Hedman, Christian Reiser, Dor Verbin, Pratul P Srinivasan, Richard Szeliski, Jonathan T Barron and Ben Mildenhall “BakedSDF: Meshing Neural SDFs for Real-Time View Synthesis” In _ACM SIGGRAPH 2023 Conference Proceedings_ Association for Computing Machinery, 2023, pp. 1–9 URL: https://doi.org/10.1145/3588432.3591536
  * [103] Zihan Zhu, Songyou Peng, Viktor Larsson, Zhaopeng Cui, Martin R. Oswald, Andreas Geiger and Marc Pollefeys “NICER-SLAM: Neural Implicit Scene Encoding for RGB SLAM”, 2023 arXiv:2302.03594 [cs.CV]

##  Appendix A Implementation Details

###  A.1 Tangent-space optimization

Due to manifold constraints, rotations cannot be naively optimized using
standard first-order optimizers. In TILTED, we address this via a Riemannian
ADAM [39] approach. Each $\bm{\tau}_{t}$ is stored as a unit-complex vector
($\in\mathbb{S}^{1}$) for 2D experiments and as a unit quaternion
($\in\mathbb{S}^{3}$) for 3D experiments, but gradients are computed with
respect to tangent spaces corresponding to the standard $\mathfrak{so}(2)$ and
$\mathfrak{so}(3)$ Lie algebras. ADAM [25] is applied to scale tangent-space
gradients $\xi_{t}^{k}$ at each training step $k$, and an exponential map is
used in place of addition to apply updates:

$\bm{\tau}_{t,k+1}=\bm{\tau}{}_{t,k}\text{Exp}(\alpha_{k}\xi_{t,k})$

where $\alpha_{k}$ is the learning rate for $\bm{\tau}{}$ at step $k$. For
experiments with real world data, we refine camera poses using this same
mechanism.

###  A.2 Handling boundaries

One benefit of axis-aligned latent decompositions is that they make bounding
boxes intuitive: all coordinates used for interpolation can be constrained to
lie within a well-defined input domain. When we apply geometric
transformations to the domain of factors, however, the regions of the input
space that each factor covers stop fully overlapping. To resolve this for
bounded scenes, we apply simple coordinate clipping. Toroidal boundary
conditions, similar to what is used in Factor Fields [83], can also be used.
For unbounded scenes, we adopt an $\ell^{\infty}$ norm-based scene contraction
function [65, 97]:

$\begin{split}\text{contract}(\bm{p})&=\begin{cases}\
\bm{p}&\|\bm{p}\|_{\infty}\leq 1\\\
(2-\frac{1}{\|\bm{p}\|_{\infty}})(\frac{\bm{p}}{\|\bm{p}\|_{\infty}})&\|\bm{p}\|_{\infty}>1\end{cases}\end{split}$
(A.1)

When applied after $\bm{\tau}$, note that scene contraction places all points
in the range $[-2,2]$, which mitigates boundary concerns entirely.

###  A.3 Regularization

We implement two standard regularization terms: spatial total variation (TV)
on feature grids and the distortion loss proposed by MipNeRF 360 [65]. NeRF
experiments additionaly rely on a pair of proposal fields, which require an
additional interlevel loss [65]. We also found benefit in including a
sparsity-encouraging regularization term based on the $\ell_{2,1}$ matrix
norm. This can be interpreted as forming a matrix ${A}$ with columns
$({a}_{1},\dots,{a}_{F*T})$, where each column vector ${a}_{i}$ contains
parameters that correspond to a unique transformation and factor pair
$\bm{\tau}_{t}$, $\bm{F}_{f}$. The final regularization term is computed by
summing the $\ell_{2}$ norms of each column vector.

All coefficients and additional implementation details can be found in our
code release.

##  Appendix B Concretizing Factored Feature Volumes

In this section, we concretize how feature volume decompositions used by prior
work can be instantiated using the common notation that we present:

$\begin{split}\bm{Z}&=\texttt{Reduce}\bigl{(}\bigl{[}\texttt{Interp}_{\bm{F}_{1}}(\texttt{Proj}_{1}(\bm{p}))\bigr{]},\dots,\\\
&\hphantom{=\texttt{Reduce}\bigl{(}\,\,}\bigl{[}\texttt{Interp}_{\bm{F}_{F}}(\texttt{Proj}_{F}(\bm{p}))\bigr{]}\bigr{)},\end{split}$
(B.1)

where, as earlier, $\bm{p}$ is an input coordinate and $\bm{Z}$ is an output
that can be used to regress quantities like radiance or signed distance. This
unified formulation, which closely mirrors the structure of our
implementation, enables integration of the latent registration mechanism
proposed by TILTED in a general-purpose way.

###  B.1 Vector outer products

Among the best-known approaches for factoring tensors is the classic
CANDECOMP/PARAFAC (CP) decomposition, which has been studied as a baseline for
factoring latent grids in prior work [68]. In 3D, the CP decomposition is
equivalent to a single vector-matrix decomposition when the matrix rank is
constrained to rank-$1$ and can thus be represented with a vector outer
product.

To build CP-decomposed latent structures, a channel dimension is included to
instantiate three paired 1D feature grids and projection functions:

$\begin{split}\bm{F}_{1}&\in\mathbb{R}^{w\times c}\\\
\bm{F}_{2}&\in\mathbb{R}^{h\times c}\\\ \bm{F}_{3}&\in\mathbb{R}^{d\times
c}\quad\end{split}\begin{split}\vphantom{\mathbb{R}^{W}}\texttt{Proj}_{1}(\bm{p})&=p_{x}\in\mathbb{R}\\\
\vphantom{\mathbb{R}^{W}}\texttt{Proj}_{2}(\bm{p})&=p_{y}\in\mathbb{R}\\\
\vphantom{\mathbb{R}^{W}}\texttt{Proj}_{3}(\bm{p})&=p_{z}\in\mathbb{R}\end{split}$

Where $w$, $h$, and $d$ are the spatial dimensions of the voxel grid we aim to
represent, and $c$ is a channel count. After interpolation, an element-wise
(Hadamard) product $\odot$ is used to reduce interpolated latents
$\bm{Z}_{1}$, $\bm{Z}_{2}$, and $\bm{Z}_{3}$ into the final latent $\bm{Z}$:

$\texttt{Reduce}(\bm{Z}_{1},\bm{Z}_{2},\bm{Z}_{3})=\bm{Z}_{1}\odot\bm{Z}_{2}\odot\bm{Z}_{3}$
(B.2)

###  B.2 Tri-plane architectures

Beginning in generative 3D [67, 98], several works have evaluated tri-plane
architectures for decomposing latent 3D grids. The key idea of a tri-plane is
to build feature grids along the XY, YZ, and XZ planes (Figure 2(b)), which
are dramatically more compact than a full 3D tensor and conducive to
generative architectures developed for 2D image synthesis. Using the notation
described above, this can be concretized by setting $F=3$ and defining three
axis-aligned factors and projection functions:

$\begin{split}\bm{F}_{1}&\in\mathbb{R}^{w\times h\times c}\\\
\bm{F}_{2}&\in\mathbb{R}^{h\times d\times c}\\\
\bm{F}_{3}&\in\mathbb{R}^{w\times d\times
c}\quad\end{split}\begin{split}\vphantom{\mathbb{R}^{W}}\texttt{Proj}_{1}(\bm{p})&=(p_{x},p_{y})\in\mathbb{R}^{2}\\\
\vphantom{\mathbb{R}^{W}}\texttt{Proj}_{2}(\bm{p})&=(p_{y},p_{z})\in\mathbb{R}^{2}\\\
\vphantom{\mathbb{R}^{W}}\texttt{Proj}_{3}(\bm{p})&=(p_{x},p_{z})\in\mathbb{R}^{2}\end{split}$

As described in the general case above, projected coordinates are used to
interpolate per-projection latent vectors $\bm{Z}_{1}$, $\bm{Z}_{2}$, and
$\bm{Z}_{3}$ from the corresponding set of feature grids $\bm{F}_{1}$,
$\bm{F}_{2}$, and $\bm{F}_{3}$, which are passed through a Reduce operation to
produce the final latent vector $\bm{Z}$.

Several choices exist for Reduce. EG3D [67], which adapts a StyleGAN2 [46]
architecture for 3D generation of faces and cats, uses element-wise summation:

$\texttt{Reduce}(\bm{Z}_{1},\bm{Z}_{2},\bm{Z}_{3})=\bm{Z}_{1}+\bm{Z}_{2}+\bm{Z}_{3}$

Rodin [98], which adapts latent diffusion [78] for 3D generation of avatars,
adopts concatenation:

$\texttt{Reduce}(\bm{Z}_{1},\bm{Z}_{2},\bm{Z}_{3})=\bm{Z}_{1}\oplus\bm{Z}_{2}\oplus\bm{Z}_{3}$

Outside of generative models, K-Planes [85] demonstrates that a Hadamard
product for reduction is advantageous when applied with both linear and MLP
decoders. In TILTED, we adopt the K-Planes naming for tri-plane architectures
due to the use of product-based reduction.

###  B.3 Vector-matrix pairs

Rather than building a representation using only matrix components, TensoRF
[68] proposes a factorization of voxel grids using three vector-matrix (VM)
pairs (Figure 2(c)). The corresponding factors and projection functions can be
formalized as:

$\begin{split}\bm{F}_{1}&\in\mathbb{R}^{w\times c}\\\
\bm{F}_{2}&\in\mathbb{R}^{h\times d\times c}\\\
\bm{F}_{3}&\in\mathbb{R}^{h\times c}\\\ \bm{F}_{4}&\in\mathbb{R}^{w\times
d\times c}\\\ \bm{F}_{5}&\in\mathbb{R}^{h\times c}\\\
\bm{F}_{6}&\in\mathbb{R}^{w\times h\times
c}\quad\end{split}\begin{split}\vphantom{\mathbb{R}^{W}}\texttt{Proj}_{1}(\bm{p})&=p_{x}\\\
\vphantom{\mathbb{R}^{W}}\texttt{Proj}_{2}(\bm{p})&=(p_{y},p_{z})\\\
\vphantom{\mathbb{R}^{W}}\texttt{Proj}_{3}(\bm{p})&=p_{y}\\\
\vphantom{\mathbb{R}^{W}}\texttt{Proj}_{4}(\bm{p})&=(p_{x},p_{z})\\\
\vphantom{\mathbb{R}^{W}}\texttt{Proj}_{5}(\bm{p})&=p_{z}\\\
\vphantom{\mathbb{R}^{W}}\texttt{Proj}_{6}(\bm{p})&=(p_{x},p_{y})\end{split}$

The result is 6 interpolated latent vectors $\bm{Z}_{1\dots 6}$. Components
from each vector-matrix pair are multiplied to produce 3 vectors, which are
then concatenated:

$\texttt{Reduce}(\bm{Z}_{1\dots
6})=\bigoplus_{i=1,3,5}\bigl{[}\bm{Z}_{i}\odot\bm{Z}_{i+1}\bigr{]}$

After reduction, the latent $\bm{Z}$ is passed to an MLP decoder to regress
quantities like radiance or signed distance.

###  B.4 Multi-resolution factors

The decomposition architectures presented in Sections B.1, B.2, and B.3 all
assume that decompositions exist at only one resolution per scene. In
practice, it can be advantageous to aggregate features at varying spatial
resolutions [76, 85].

Adapting the notation above to the multi-resolution setting is
straightforward. K-Planes, for example, runs all experiments at four
resolutions: $64\times 64$, $128\times 128$, $256\times 256$, and $512\times
512$. Generalizing to $R$ resolutions and per-resolution scale factor $s_{r}$,
the process for interpolating multi-resolution K-Planes features can be
written with our abstractions as:

$\begin{split}\bm{F}_{r,1}&\in\mathbb{R}^{w_{r}\times h_{r}\times c}\\\
\bm{F}_{r,2}&\in\mathbb{R}^{h_{r}\times d_{r}\times c}\\\
\bm{F}_{r,3}&\in\mathbb{R}^{w_{r}\times d_{r}\times
c}\quad\end{split}\begin{split}\vphantom{\mathbb{R}^{W}}\texttt{Proj}_{r,1}(\bm{p})&=(s_{r}p_{x},s_{r}p_{y})\\\
\vphantom{\mathbb{R}^{W}}\texttt{Proj}_{r,2}(\bm{p})&=(s_{r}p_{y},s_{r}p_{z})\\\
\vphantom{\mathbb{R}^{W}}\texttt{Proj}_{r,3}(\bm{p})&=(s_{r}p_{x},s_{r}p_{z})\end{split}$

for $r={1\dots R}$. For the Reduce operator, the Hadamard product is applied
within each resolution, and concatenation is applied across resolutions:

$\begin{split}\texttt{Reduce}(\\{\bm{Z}_{r,i}\\}_{r,i})\quad=\bigoplus_{r=1\dots
R}\bigl{[}\bm{Z}_{r,1}\odot\bm{Z}_{r,2}\odot\bm{Z}_{r,3}\bigr{]}\end{split}$

TILTED applies this pattern to all 3D experiments.

##  Appendix C Additional Results

###  C.1 Disaggregated SDF results

####  C.1.1 SDF results, with random scene rotation

In this section, we report disaggregated results from our SDF reconstruction
experiments, with and without TILTED. We apply a random global rotation to
each mesh in these results.

Methods | Avg | Bunny | Lucy | Chair | Armadillo | Dragon | Cheburashka | Beast | Happy
---|---|---|---|---|---|---|---|---|---
K-Planes-30 | 0.949 | 0.969 | 0.933 | 0.937 | 0.952 | 0.935 | 0.980 | 0.922 | 0.967
w/ TILTED | 0.989 | 0.996 | 0.987 | 0.987 | 0.993 | 0.977 | 0.995 | 0.988 | 0.990
K-Planes-60 | 0.949 | 0.982 | 0.939 | 0.922 | 0.955 | 0.922 | 0.979 | 0.918 | 0.978
w/ TILTED | 0.990 | 0.996 | 0.982 | 0.993 | 0.989 | 0.983 | 0.997 | 0.984 | 0.993
K-Planes-90 | 0.946 | 0.967 | 0.951 | 0.898 | 0.946 | 0.929 | 0.989 | 0.913 | 0.974
w/ TILTED | 0.991 | 0.996 | 0.981 | 0.991 | 0.994 | 0.986 | 0.995 | 0.990 | 0.992
Table 6: K-Plane results for SDF reconstruction with random scene rotation. We report IoUs with 30, 60, and 90 channels. Methods | Avg | Bunny | Lucy | Chair | Armadillo | Dragon | Cheburashka | Beast | Happy
---|---|---|---|---|---|---|---|---|---
VM-45 | 0.866 | 0.974 | 0.802 | 0.950 | 0.913 | 0.821 | 0.969 | 0.977 | 0.519
w/ TILTED | 0.974 | 0.994 | 0.973 | 0.936 | 0.988 | 0.952 | 0.979 | 0.981 | 0.991
VM-90 | 0.946 | 0.982 | 0.956 | 0.948 | 0.984 | 0.762 | 0.981 | 0.972 | 0.985
w/ TILTED | 0.977 | 0.995 | 0.984 | 0.897 | 0.994 | 0.978 | 0.995 | 0.987 | 0.989
VM-135 | 0.982 | 0.988 | 0.969 | 0.974 | 0.987 | 0.971 | 0.986 | 0.988 | 0.991
w/ TILTED | 0.988 | 0.996 | 0.982 | 0.976 | 0.992 | 0.981 | 0.994 | 0.987 | 0.994
Table 7: Vector-matrix results for SDF reconstruction with random scene
rotation. We report IoUs with 45, 90, and 135 channels.

####  C.1.2 SDF results, without random scene rotation

In this section, we report SDF reconstruction metrics when we turn off random
scene rotation. Metrics here are similar to those when we include random scene
rotation. In the main paper body, we report metrics with random rotation
included.

Methods | Avg | Bunny | Lucy | Chair | Armadillo | Dragon | Cheburashka | Beast | Happy
---|---|---|---|---|---|---|---|---|---
K-Planes-30 | 0.949 | 0.970 | 0.945 | 0.965 | 0.945 | 0.843 | 0.989 | 0.970 | 0.966
w/ TILTED | 0.989 | 0.996 | 0.983 | 0.988 | 0.992 | 0.979 | 0.995 | 0.988 | 0.990
K-Planes-60 | 0.952 | 0.972 | 0.954 | 0.964 | 0.951 | 0.842 | 0.993 | 0.972 | 0.969
w/ TILTED | 0.990 | 0.997 | 0.982 | 0.991 | 0.991 | 0.981 | 0.996 | 0.989 | 0.993
K-Planes-90 | 0.952 | 0.977 | 0.945 | 0.959 | 0.961 | 0.838 | 0.994 | 0.971 | 0.971
w/ TILTED | 0.991 | 0.996 | 0.985 | 0.990 | 0.996 | 0.979 | 0.994 | 0.995 | 0.992
Table 8: K-Plane results for SDF reconstruction without random scene rotation. We report IoUs with 30, 60, and 90 channels. Methods | Avg | Bunny | Lucy | Chair | Armadillo | Dragon | Cheburashka | Beast | Happy
---|---|---|---|---|---|---|---|---|---
VM-45 | 0.970 | 0.990 | 0.927 | 0.975 | 0.970 | 0.952 | 0.988 | 0.981 | 0.980
w/ TILTED | 0.982 | 0.995 | 0.980 | 0.980 | 0.970 | 0.975 | 0.988 | 0.982 | 0.989
VM-90 | 0.979 | 0.993 | 0.971 | 0.991 | 0.955 | 0.960 | 0.992 | 0.983 | 0.988
w/ TILTED | 0.989 | 0.995 | 0.985 | 0.989 | 0.993 | 0.976 | 0.993 | 0.987 | 0.991
VM-135 | 0.982 | 0.993 | 0.973 | 0.987 | 0.991 | 0.964 | 0.977 | 0.981 | 0.989
w/ TILTED | 0.988 | 0.996 | 0.985 | 0.989 | 0.994 | 0.983 | 0.997 | 0.966 | 0.993
Table 9: Vector-matrix results for SDF reconstruction without random scene
rotation. We report IoUs with 45, 90, and 135 channels.

####  C.1.3 Ablations on coarse-to-fine optimization

We report an ablation for the low pass-based coarse-to-fine optimization in
Table 10.

Methods | Lucy | Dragon
---|---|---
K-Planes-90 TILTED | 0.985 | 0.979
K-Planes-90 TILTED w/o coarse-to-fine | 0.974 | 0.977
VM-135 TILTED | 0.985 | 0.983
VM-135 TILTED, w/o coarse-to-fine | 0.975 | 0.976
Table 10:  Ablation for coarse-to-fine optimization inspired by Nerfies [58]
and BARF [55]. Coarse-to-fine optimization improves IoUs for TILTED SDF
reconstructions.

###  C.2 2D Results

####  C.2.1 Experiments on various latent grid resolutions

In this section, we vary latent grid resolution for the 2D image
reconstruction task. TILTED improves results across resolutions.

Grid Resolution | 32 | 64 | 128 | 256 | 512 | 1024
---|---|---|---|---|---|---
Fox (axis-aligned) | 21.26 | 21.98 | 22.31 | 21.63 | 17.23 | 10.34
Fox (TILTED) | 21.33 | 22.19 | 22.52 | 22.23 | 19.21 | 17.00
Bridge (axis-aligned) | 20.95 | 21.96 | 22.99 | 23.63 | 23.46 | 20.90
Bridge (TILTED) | 21.43 | 22.28 | 23.34 | 24.16 | 24.08 | 22.23
Painting (axis-aligned) | 25.59 | 26.16 | 26.51 | 26.76 | 26.40 | 18.22
Painting (TILTED) | 25.83 | 26.5 | 26.81 | 26.94 | 26.81 | 22.15
Table 11:  Varying latent grid resolutions for 2D image reconstruction.

##  Appendix D Proofs for Section 3

We assume throughout these appendices that $n\geq 2$.

##### Notation.

We write $\mathbb{R}$ for the reals, $\mathbb{Z}$ for the integers, and
$\mathbb{N}$ for the positive integers. For positive integers $m$ and $n$, we
let $\mathbb{R}^{m}$ and $\mathbb{R}^{m\times n}$ denote the spaces of real-
valued $m$-dimensional vectors and $m$-by-$n$ matrices (resp.). We write
$\bm{e}_{i}$, $\bm{e}_{ij}$, etc. to denote the elements of the canonical
basis of these spaces, and ${1}_{m}$ and ${0}_{m,n}$ (etc.) to denote their
all-ones and all-zeros elements (resp.). We write
$\langle\>\cdot\>,\>\cdot\>\rangle$ and $\lVert\>\cdot\>\rVert_{F}$ to denote
the euclidean inner product and associated norm of these spaces. We will write
the $\ell^{p}$ norms $\lVert\bm{x}\rVert_{p}=(\sum_{i}\lvert
x_{i}\rvert^{p})^{1/p}$, with $\lVert\bm{x}\rVert_{\infty}=\max_{i}\,\lvert
x_{i}\rvert$, of these spaces as either $\lVert\>\cdot\>\rVert_{p}$ or
$\lVert\>\cdot\>\rVert_{\ell^{p}}$ depending on context. We will use the
notation $\lVert\>\cdot\>\rVert$ to denote the operator norm (the largest
singular value) on $m\times n$ matrices. If $\bm{A}\in\mathbb{R}^{m\times n}$,
we write $\bm{A}^{\ast}\in\mathbb{R}^{n\times m}$ for its (conjugate)
transpose. For matrices $\bm{A}$ and $\bm{B}$, we write $\bm{A}\otimes\bm{B}$
to denote their tensor product—if indices $(i,j)$ index $\bm{A}$ and $(k,l)$
index $\bm{B}$, we have
$(\bm{A}\otimes\bm{B})_{ijkl}=(\bm{A})_{ij}(\bm{B})_{kl}$.

As a technical tool (in Section D.1), and as a mathematical abstraction (in
Section D.2), we will frequently work with “continuum” images defined on the
square $[-1,1]^{2}\subset\mathbb{R}^{2}$. By default, we will use “image
coordinates” for $\bm{x}\in\mathbb{R}^{2}$ (in order to match the usual
matrix-type indexing of discrete images), which corresponds in the canonical
basis to the positively-oriented frame $[-\bm{e}_{2},\bm{e}_{1}]$. We will
formally write these coordinates as $\bm{x}=(s,t)$. For an image
$X:\mathbb{R}^{2}\to[0,1]$ we will write $\lVert
X\rVert_{L^{p}}=(\int_{\mathbb{R}^{2}}\lvert
X(\bm{x})\rvert^{p}\mathop{}\\!\mathrm{d}\bm{x})^{1/p}$ for the $L^{p}$ norms,
and $\lVert X\rVert_{L^{\infty}}=\sup_{\bm{x}\in\mathbb{R}^{2}}\,\lvert
X(\bm{x})\rvert$ when $X$ is bounded. The space $L^{2}(\mathbb{R}^{d})$ is a
Hilbert space; as for finite-dimensional vector spaces, we will write
$\langle\>\cdot\>,\>\cdot\>\rangle_{L^{2}}$ for its associated inner product
(which we take to be linear in its second argument), and if
$\mathcal{T}:L^{2}\to L^{2}$ is a bounded operator we will write
$\lVert\mathcal{T}\rVert$ for its (operator) norm and $\mathcal{T}^{\ast}$ for
its adjoint. Similarly, we will use notation defined above for matrix
operations for its analogous application to $L^{2}$ functions (e.g., tensor
products). If $\bm{\tau}:\mathbb{R}^{2}\to\mathbb{R}^{2}$ is a continuous
function (e.g., a rotation of the domain) and $X:\mathbb{R}^{2}\to\mathbb{R}$
is an image, we write $X\circ\bm{\tau}$ for their composition (the “deformed
image”). For sufficiently regular functions $f,g:\mathbb{R}^{2}\to\mathbb{R}$,
we define their convolution $(f\ast
g)(\bm{x})=\int_{\mathbb{R}^{2}}f(\bm{x}^{\prime})g(\bm{x}-\bm{x}^{\prime})\mathop{}\\!\mathrm{d}\bm{x}^{\prime}$;
this operation is symmetric and defines an element of $L^{p}$ when (say) $f$
is in $L^{1}$ and $g$ is in $L^{p}$. We will use ${\mathds{1}}_{A}$ to denote
the indicator function associated to an event $A$ in a probability space;
typically $A$ will be a subset of $\mathbb{R}^{2}$ (e.g., describing a
continuous image) or a discrete set (e.g., describing the Kronecker delta
${\mathds{1}}_{i=j}$ in summations).

Just as with discrete images, which can either be thought of as a function on
the discrete grid $\\{0,\dots,m-1\\}\times\\{0,\dots,n-1\\}$, representing
sampled intensity values, or a matrix (i.e., a finite-dimensional operator)
that aggregates those values, “continuum images” can also be thought of as
either functions or operators; if $f\in L^{2}(\mathbb{R}^{2})$, we will write
$\mathcal{T}_{f}:L^{2}(\mathbb{R})\to L^{2}(\mathbb{R})$ for the “Fredholm
operator” associated to an $L^{2}$ function $f$, defined by
$\mathcal{T}_{f}[g]=\int_{\mathbb{R}}f(\,\cdot\,,x)g(x)\mathop{}\\!\mathrm{d}x$.
If $\mathcal{T}:L^{2}(\mathbb{R})\to L^{2}(\mathbb{R})$ is bounded, we denote
its Hilbert-Schmidt norm by
$\lVert\mathcal{T}\rVert_{\mathrm{HS}}=(\sum_{n\in\mathbb{N}}\lVert\mathcal{T}u_{n}\rVert_{L^{2}(\mathbb{R})}^{2})^{1/2}$,
where $(u_{n})_{n\in\mathbb{N}}$ is any orthonormal basis of
$L^{2}(\mathbb{R})$; when $\mathcal{T}_{f}$ is a Fredholm operator, we have
$\lVert\mathcal{T}_{f}\rVert_{\mathrm{HS}}=\lVert
f\rVert_{L^{2}(\mathbb{R}^{2})}$, analogous to the Frobenius norm of a matrix.
We will exploit this correspondence in the sequel, often without mentioning
it, to identify a function $f\in L^{2}(\mathbb{R}^{2})$ with its Fredholm
operator $\mathcal{T}_{f}$ when convenient (c.f. [19, §B]); for example, for
$f\in L^{2}(\mathbb{R})$ we will write $ff^{\ast}:L^{2}(\mathbb{R})\to
L^{2}(\mathbb{R})$ to denote its induced Fredholm operator, which satisfies
$ff^{\ast}[g]=f\langle f,g\rangle_{L^{2}(\mathbb{R})}$, and we will identify
it with its $L^{2}(\mathbb{R}^{2})$ representative satisfying
$ff^{\ast}(s,t)=f(s)f(t)$. Consult the first few paragraphs in Section D.1 for
specialized notation used in low-rank approximation proofs, and the proof of
Lemma D.17 for notation used in proofs that require harmonic analysis.

##### Problem setup.

We analyze a simple model problem that captures the improved efficiency of
TILTED compared to competing approaches for compactly representing non-axis-
aligned scenes. Consider the following class of two-dimensional greyscale
images: let $m,n\in\mathbb{N}$ denote the image height and width, write
$\bm{c}=[\tfrac{m-1}{2},\tfrac{n-1}{2}]^{\ast}$ for the image center (we use
zero-indexing), and define a centered square template by

$(\bm{X}_{\natural})_{ij}=\begin{cases}1&\left\lVert[i,j]^{\ast}-\bm{c}\right\rVert_{\infty}\leq\alpha\min\\{c_{0},c_{1}\\}\\\
0&\mathrm{otherwise},\end{cases}$ (D.1)

where $0<\alpha<1$ controls the size of the square; we are interested in
$\alpha<1/\sqrt{2}$, for a square that takes up a constant fraction of the
image pixels. We consider a rotational motion model for the square template
$\bm{X}_{\natural}$: for a parameter $\nu\in[0,2\pi)$ corresponding to the
rotation about the image center $\bm{c}$, let
$\bm{\tau}_{\nu}:\mathbb{R}^{2}\to\mathbb{R}^{2}$ denote the (continuum)
transformation corresponding to

$\begin{bmatrix}s\\\ t\end{bmatrix}\mapsto\begin{bmatrix}\cos\nu&-\sin\nu\\\
\sin\nu&\cos\nu\end{bmatrix}\left(\begin{bmatrix}s\\\
t\end{bmatrix}-\bm{c}\right)+\bm{c},$ (D.2)

and consider the class of observations

$\mathfrak{S}=\left\\{\bm{X}\in\mathbb{R}^{m\times
n}\nonscript\>\middle|\allowbreak\nonscript\>\mathopen{}X_{ij}=\begin{cases}1&\left\lVert\bm{\tau}_{-\nu}(i,j)-\bm{c}\right\rVert_{\infty}\leq\alpha\min\\{c_{0},c_{1}\\}\\\
0&\mathrm{otherwise}\end{cases}\right\\}.$ (D.3)

In our lower bounds on low-rank compression in Section D.1, we will work with
a “directly-sampled” observation following the model D.3. In Section D.2, we
will work in a continuum idealization where it is more convenient to describe
the observations in a shifted coordinate system, which we now describe.

In our proofs, we will work in a shifted coordinate system so that the center
of the square D.1 lies at the origin of the coordinate system. In particular,
in these appendices we consider the image grid
$\\{0,1,\dots,m-1\\}\times\\{0,1,\dots,n-1\\}-\bm{c}$, corresponding to the
grid

$G_{\bm{c}}=\left\\{(i,j)\nonscript\>\middle|\allowbreak\nonscript\>\mathopen{}i\in\\{-(m-1)/2,\dots,(m-1)/2\\},j\in\\{-(n-1)/2,\dots,(n-1)/2\\}\\}.WewilloftenindexvectorsandmatricesbytheircoordinatesinG_{\bm{c}}anditsderivedgrids,ratherthaninthestandardimagegrid,duetothestraightforwardone-
to-onecorrespondencebetweengrids.Withoutlossofgenerality,wewillassumethatm\leq
n.LetusthennotethatinG_{\bm{c}}coordinates,\lx@cref{creftypecap~refnum}{eq:square_definition}admitstheequivalentrank-
oneexpression\begin{equation}\bm{X}_{\natural}=\bm{u}_{\natural}\bm{v}_{\natural}^{\ast},\quad(\bm{u}_{\natural})_{i}=\begin{cases}1&\left\lvert
i\right\rvert\leq\frac{\alpha}{2}(m-1)\\\
0&\mathrm{otherwise},\end{cases},\enspace(\bm{v}_{\natural})_{j}=\begin{cases}1&\left\lvert
j\right\rvert\leq\frac{\alpha}{2}(m-1)\\\
0&\mathrm{otherwise},\end{cases}.\end{equation}Wewillrequire,roughly,that0<\alpha<\tfrac{1}{\sqrt{2}},sothattherearenoboundaryissueswithrotatedversionsofthetemplate\lx@cref{creftypecap~refnum}{eq:odd_size_lr_square}.\par
Thetemplatedefinition\lx@cref{creftypecap~refnum}{eq:odd_size_lr_square}impliesthatastheimagesizem,nbecomelarge,\bm{X}_{\natural}samplesthesamefixedcontinuumtemplateX_{\natural}:[-1,1]\to\\{0,1\\}definedby\begin{equation}X_{\natural}(s,t)={\mathds{1}}_{\lvert
s\rvert\leq\alpha,\lvert
t\rvert\leq\alpha}.\end{equation}Tomakethiscorrespondence,itisnecessarytoscalethegridG_{\bm{c}}bythefactor2/(m-1):thiscorrespondstothegrid\begin{equation}G=\left\\{(i,j)\nonscript\>\middle|\allowbreak\nonscript\>\mathopen{}i\in\left\\{-1,-1+\frac{2}{m-1},\dots,1-\frac{2}{m-1},1\right\\},j\in\left\\{-\frac{n-1}{m-1},\dots,\frac{n-1}{m-1}\right\\}\right\\}.\end{equation}Itisthenevidentthatif(i,j)\in
G,onehas(\bm{X}_{\natural})_{(m-1)i/2,(m-1)j/2}=X_{\natural}(i,j).\par
Thepossiblecomplicationthatonemayhaverectangularimageswithn>misactuallynotessential
---
toseethis,notethatwealwayshavetheblockstructure\begin{equation*}\bm{X}_{\natural}=\begin{bmatrix}{0}&\bar{\bm{X}}_{\natural}&{0}^{\prime},\end{bmatrix}\end{equation*}where\bar{\bm{X}}_{\natural}followsthedefinition\lx@cref{creftypecap~refnum}{eq:odd_size_lr_square},butwithm=n,and{0}and{0}^{\prime}arezeromatricesofappropriatesizes.Thisshowsthat\bm{X}_{\natural}and\bar{\bm{X}}_{\natural}havethesamenonzerosingularvalues,thesameleftsingularvectors,andrightsingularvectorsthatareinone-
to-
onecorrespondence(simplyprependandappendtheappropriatenumberofzerostothesingularvectorsof\bar{\bm{X}}_{\natural}).ThisimpliesthatinourproofsfortheSVDapproachin\lx@cref{creftypecap~refnum}{sec:svd_proofs},wemayassumethatm=nwithoutanylossofgenerality.\par\par\par$

###  D.1 Proofs for Theorem 1

As mentioned previously, without loss of generality we assume $m=n$ in this
section. We will therefore write $\bm{X}\in\mathbb{R}^{n\times n}$ for the
observation, and use $m$ as a free parameter.

##### Problem setting.

We study the special case of $\nu_{\natural}=\pi/4$, so that the observation

$(\bm{X})_{ij}={\mathds{1}}_{\lVert(\bm{\tau}_{\pi/4})_{ij}\rVert_{\infty}\leq\alpha}$

corresponds to a “diamond”. This case makes the rank of the transformed image
as large as possible.

##### Continuum surrogate.

Our analysis will proceed by relating the singular value decomposition of
$\bm{X}$ to the spectrum of an ‘infinite resolution’ surrogate $X$, defined as

$X(s,t)=X_{\natural}(s\cos\nu_{\natural}+t\sin\nu_{\natural},-s\sin\nu_{\natural}+t\cos\nu_{\natural}).$

Whereas $\operatorname{supp}X_{\natural}=[-\alpha,\alpha]^{2}$, we have
$\operatorname{supp}X=[-\sqrt{2}\alpha,\sqrt{2}\alpha]^{2}$. The ‘infinite
resolution’ analogue of taking the singular value decomposition of an image is
the Schmidt decomposition (c.f. [12]) of the image’s associated Fredholm
operator: define $\mathcal{T}_{X}:L^{2}([-1,+1])\to L^{2}([-1,+1])$ by

$\mathcal{T}_{X}[f](s)=\int_{[-1,+1]}X(s,t)f(t)\mathop{}\\!\mathrm{d}t,$

and note by the geometry of the diamond $X$ that

$\mathcal{T}_{X}[f](s)=\int_{-(\sqrt{2}\alpha-\lvert
s\rvert)}^{\sqrt{2}\alpha-\lvert s\rvert}f(t)\mathop{}\\!\mathrm{d}t,$ (D.7)

so that in particular $\mathcal{T}_{X}$ is self-adjoint and Hilbert-Schmidt
(hence compact). The spectral theorem for compact operators on a Hilbert space
[19] then implies that $\mathcal{T}_{X}$ diagonalizes in an orthonormal basis
of eigenfunctions $(e_{k})_{k\in\mathbb{N}}\subset L^{2}([-1,+1])$ with
corresponding eigenvalues $(\lambda_{k})_{k\in\mathbb{N}}\subset\mathbb{R}$:

$\mathcal{T}_{X}=\sum_{k\in\mathbb{N}}\lambda_{k}e_{k}e_{k}^{\ast},$ (D.8)

where the equality must be interpreted in the sense of $L^{2}\to L^{2}$. We
will derive a closed-form expression for D.8 for the diamond (Lemma D.1), and
use a truncation and discretization of it as an approximate diagonalization of
the discrete diamond $\bm{X}$.

##### Approximation guarantees with the SVD.

The use of an infinite-dimensional surrogate to analyze $\bm{X}$ requires the
instantiation of some approximation machinery. We quantify reconstruction
performance in terms of squared error. For any matrix
$\bm{M}\in\mathbb{R}^{n\times n}$, we write
$\sigma_{1}(\bm{M})\geq\sigma_{2}(\bm{M})\geq\dots\geq\sigma_{n}(\bm{M})\geq
0$ for its singular values. The singular value decomposition asserts that for
any $\bm{M}$, there exist orthogonal matrices $\bm{U}(\bm{M})$ and
$\bm{V}(\bm{M})$ such that

$\bm{M}=\bm{U}\underbrace{\begin{bmatrix}\sigma_{1}(\bm{M})&&\\\ &\ddots&\\\
&&\sigma_{n}(\bm{M})\end{bmatrix}}_{\bm{\Sigma}}\bm{V}^{\ast}.$

We recall that
$\lVert\bm{M}\rVert_{\mathrm{F}}^{2}=\sum_{i=1}^{n}\sigma_{i}^{2}(\bm{M})$.
The “rank-$k$” SVD approximation to $\bm{M}$ is defined as111The “scare
quotes” are to draw attention to the fact that if $\bm{M}$ has rank strictly
less than $k$, this approximation is not actually rank $k$—its rank is no
larger than $\operatorname{rank}(\bm{M})$.

$\mathrm{SVD}_{k}(\bm{M})=\bm{U}\begin{bmatrix}\sigma_{1}(\bm{M})&&&\\\
&\ddots&&\\\ &&\sigma_{k}(\bm{M})&\\\
&&&{0}_{n-k,n-k}\end{bmatrix}\bm{V}^{\ast}.$

Following [10], for $p\geq 1$ we write
$\lVert\bm{M}\rVert_{(k)}^{(p)}=\bigl{(}\sum_{i=1}^{k}\sigma_{i}^{p}(\bm{M})\bigr{)}^{1/p}$
for the Ky Fan $p$-norms of a matrix $\bm{M}$. These are indeed norms in the
mathematical sense (e.g., [10, §IV.2, eqn. IV.47]). From the celebrated
Eckart-Young-Mirsky theorem [1, 2], we have

$\inf_{\operatorname{rank}(\bm{M})\leq
k}\,\left\lVert\bm{M}-\bm{X}\right\rVert_{\mathrm{F}}^{2}=\sum_{i=k+1}^{n}\sigma_{i}^{2}(\bm{X})=\lVert\bm{X}\rVert_{\mathrm{F}}^{2}-\left(\lVert\bm{X}\rVert_{(k)}^{(2)}\right)^{2},$

and it is evident that $\bm{M}=\mathrm{SVD}_{k}(\bm{X})$ achieves the infimum
in this formula: that is,

$\left\lVert\mathrm{SVD}_{k}(\bm{X})-\bm{X}\right\rVert_{\mathrm{F}}^{2}=\lVert\bm{X}\rVert_{\mathrm{F}}^{2}-\left(\left\lVert\bm{X}\right\rVert_{(k)}^{(2)}\right)^{2}.$

It follows that we can obtain lower bounds on the approximation error of SVD-
based compression of $\bm{X}$ via upper bounds on the Ky Fan $2$-norms of
$\bm{X}$.

For any $\bm{\Xi}\in\mathbb{R}^{n\times n}$, we have from the triangle
inequality

$\displaystyle\left\lVert\bm{X}\right\rVert_{(k)}^{(2)}$
$\displaystyle\leq\lVert\bm{\Xi}\rVert_{(k)}^{(2)}+\left\lVert\bm{\Xi}-\bm{X}\right\rVert_{(k)}^{(2)}$
$\displaystyle\leq\lVert\bm{\Xi}\rVert_{(k)}^{(2)}+\left\lVert\bm{\Xi}-\bm{X}\right\rVert_{\mathrm{F}},$
(D.9)

where the second inequality simply worst-cases over all $n$ singular values of
the residual. D.9 is the basis of our approximation argument: we will choose
$\bm{\Xi}$ as a matrix whose spectral decay is known, and which gives a good
approximation to the actual diamond matrix $\bm{X}$. In particular, we will
consider a family of approximations $\bm{\Xi}_{m}$, with $m\in\mathbb{N}$,
defined as

$(\bm{\Xi}_{m})_{ij}=\sum_{l=1}^{m}\lambda_{l}g_{l}(i)g_{l}(j),$ (D.10)

with coordinates $(i,j)\in G$ and with notation as defined in Lemma D.1. We
discuss the sources of error in these approximations momentarily; let us first
introduce additional notation to write these matrices more compactly. Define
$\bm{U}_{m}\in\mathbb{R}^{n\times m}$ by

$(\bm{U}_{m})_{ij}=g_{j}(i);\quad
i\in\\{k\nonscript\>|\allowbreak\nonscript\>\mathopen{}\exists l:(k,l)\in
G\\},\enspace j\in[n]$

(the slightly abstruse indexing notation simply defines the projection of $G$
onto either of its coordinate factors), and let
$\bm{\Lambda}_{m}\in\mathbb{R}^{m\times m}$ be a diagonal matrix with
$\lambda_{l}$ on its $l$-th diagonal entry. Then

$\bm{\Xi}_{m}=\bm{U}_{m}\bm{\Lambda}_{m}\bm{U}_{m}^{\ast}.$ (D.11)

For technical reasons, we will need to consider a further level of
approximation induced by smoothing the nonsmooth square pattern
$X_{\natural}$. For $\sigma^{2}>0$, we write
$\varphi_{\sigma^{2}}(t)=1/\sqrt{2\pi\sigma^{2}}\exp(-\tfrac{1}{2\sigma^{2}}t^{2})$
for the one-dimensional standard gaussian, and
$m_{\sigma^{2}}=\varphi_{\sigma^{2}}\varphi_{\sigma^{2}}^{\ast}$ for its two-
dimensional analogue. Let $f\mathbin{\ast}g$ denote the convolution of
$L^{2}(\mathbb{R}^{d})$ signals $f$ and $g$. Then define a smoothed family of
approximations

$(\tilde{\bm{\Xi}}_{m})_{ij}=\sum_{l=1}^{m}\lambda_{l}(\varphi_{\sigma^{2}}\mathbin{\ast}g_{l})(i)(\varphi_{\sigma^{2}}\mathbin{\ast}g_{l})(j).$
(D.12)

As above, let $\tilde{\bm{\Xi}}_{m}$ denote the matrix representation of this
construction:

$\tilde{\bm{\Xi}}_{m}=\tilde{\bm{U}}_{m}\bm{\Lambda}_{m}\tilde{\bm{U}}_{m}^{\ast}.$
(D.13)

Relative to the continuum diamond $X$, there are three main sources of error
in the approximations D.12. The parameter $m$ controls a truncation of the
infinite series of eigenfunctions that defines $\mathcal{T}_{X}$, and the grid
resolution (proportional to $n$) controls a discretization error relative to
the continuum image $X$. In addition, the smoothing scale $\sigma^{2}$
controls a further error, since the smoothed eigenfunctions do not coincide
with eigenfunctions of the ‘smoothed operator’. These three parameters are in
tension—choosing $m$ larger recovers more terms in the series defining
$\mathcal{T}_{X}$, but when the grid resolution is fixed at $2/(n-1)$, the
fact that the eigenfunctions $g_{l}$ become more and more oscillatory at
larger values of $l$ suggests a larger and larger discretization error, and a
need for a smaller and smaller smoothing scale $\sigma^{2}$ to avoid
destroying the spectral structure of the eigenfunctions $g_{l}$. We will
choose these parameters in tandem with the SVD rank $k$ in D.9 in order to
guarantee as strong of a lower bound on the approximation error as possible.

##### Main result.

Our main result is an inapproximability result for sublinear low-rank
approximations to $\bm{X}$, up to a threshold.

######  Theorem D.1.

There are absolute constants $c,C,C^{\prime}>0$ such that the following holds.
Let $\nu_{\natural}=\pi/4$ and $\alpha=1/\sqrt{2}$, and consider the
observation

$(\bm{X})_{ij}={\mathds{1}}_{\lVert(\bm{\tau}_{\nu_{\natural}})_{ij}\rVert_{\infty}\leq\alpha}.$

For every $n\geq\max\\{C,C^{\prime}k^{1/9.5}\\}$, one has for every
$\hat{\bm{X}}\in\mathbb{R}^{n\times n}$ with rank no larger than $k$

$\frac{1}{n^{2}}\left\lVert\hat{\bm{X}}-\bm{X}\right\rVert_{\mathrm{F}}^{2}\geq\frac{c}{1+k}.$

###### Proof.

We instantiate the argument discussed in the previous paragraph, culminating
in D.9. Below, we will occasionally not calculate precise constants for
simplicity, and similarly we will fix $\alpha=1/\sqrt{2}$, allowing us to
treat it as an absolute constant. Put

$\bar{X}=\varphi_{\sigma^{2}}^{\otimes 2}\mathbin{\ast}X$

for the smoothed observation (recall that $(\bm{X})_{ij}=X(i,j)$ for $(i,j)\in
G$), let $\bar{G}=(-1,-1)+\tfrac{2}{n-1}\mathbb{Z}^{2}$ denote the infinitely-
extended grid $G$ defined in D.6, and let $(\bar{\bm{X}})_{ij}=\bar{X}(i,j)$
for $(i,j)\in\bar{G}$. The inclusion $G\subset\bar{G}$ means that we can
naturally think of $\bar{\bm{X}}$ as a matrix indexed by $G$ as well (via
restriction), and we will write
$\lVert\>\cdot\>\rVert_{\ell^{2}(G)}=\lVert\>\cdot\>\rVert_{\mathrm{F}}$ and
$\lVert\>\cdot\>\rVert_{\ell^{2}(\bar{G})}$ to denote the respective norms.
Observe that, by linearity of the convolution operation and Lemma D.1, we have
for $(i,j)\in\bar{G}$

$\displaystyle(\bar{\bm{X}})_{ij}$
$\displaystyle=(\varphi_{\sigma^{2}}^{\otimes 2}\mathbin{\ast}X)(i,j)$
$\displaystyle=\sum_{l=1}^{\infty}\lambda_{l}(\varphi_{\sigma^{2}}\mathbin{\ast}g_{l})(i)(\varphi_{\sigma^{2}}\mathbin{\ast}g_{l})(j)$
$\displaystyle=(\tilde{\bm{\Xi}}_{m})_{ij}+\left(\underbrace{\sum_{l=m+1}^{\infty}\lambda_{l}(\varphi_{\sigma^{2}}\mathbin{\ast}g_{l})(\varphi_{\sigma^{2}}\mathbin{\ast}g_{l})^{\ast}}_{\Delta_{\mathrm{tail}}}\right)(i,j).$
(D.14)

Let $\hat{\bm{X}}$ be any approximation to $\bm{X}$ with rank at most $k$. For
technical convenience, we want to compare $\ell^{2}(G)$ norms to
$\ell^{2}(\bar{G})$ norms—note that these are distinct when we consider our
smoothed approximation $\bar{\bm{X}}$, because convolution with the mollifier
enlarges the support to be outside of $[-1,1]^{2}$. We extend $\hat{\bm{X}}$
and $\bm{X}$ to all of $\bar{G}$ by zero-padding, and note that

$\left\lVert\hat{\bm{X}}-\bm{X}\right\rVert_{\mathrm{F}}=\left\lVert\hat{\bm{X}}-\bm{X}\right\rVert_{\ell^{2}(G)}=\left\lVert\hat{\bm{X}}-\bm{X}\right\rVert_{\ell^{2}(\bar{G})}.$

By the triangle inequality, we have

$\left\lVert\hat{\bm{X}}-\bm{X}\right\rVert_{\ell^{2}({G})}\geq\left\lVert\hat{\bm{X}}-\bar{\bm{X}}\right\rVert_{\ell^{2}({G})}-\left\lVert\bar{\bm{X}}-\bm{X}\right\rVert_{\ell^{2}({G})},$

We can apply the EYM theorem to obtain

$\left\lVert\hat{\bm{X}}-\bar{\bm{X}}\right\rVert_{\ell^{2}({G})}\geq\sqrt{\left\lVert\bar{\bm{X}}\right\rVert_{\ell^{2}({G})}^{2}-\left(\left\lVert\bar{\bm{X}}\right\rVert_{(k)}^{(2)}\right)^{2}}.$
(D.15)

Notice that, by D.14 and the fact that the Ky Fan $2$-norms are mathematically
norms, we have

$\displaystyle\left(\left\lVert\bar{\bm{X}}\right\rVert_{(k)}^{(2)}\right)^{2}$
$\displaystyle\leq\left(\left\lVert\tilde{\bm{\Xi}}_{m}\right\rVert_{(k)}^{(2)}+\left\lVert\bm{\Delta}_{\mathrm{tail}}\right\rVert_{(k)}^{(2)}\right)^{2}$
$\displaystyle=\left(\left\lVert\tilde{\bm{\Xi}}_{m}\right\rVert_{(k)}^{(2)}\right)^{2}+\left(\left\lVert\bm{\Delta}_{\mathrm{tail}}\right\rVert_{(k)}^{(2)}\right)^{2}+2\left\lVert\tilde{\bm{\Xi}}_{m}\right\rVert_{(k)}^{(2)}\left\lVert\bm{\Delta}_{\mathrm{tail}}\right\rVert_{(k)}^{(2)}$
$\displaystyle\leq\left(\left\lVert\tilde{\bm{\Xi}}_{m}\right\rVert_{(k)}^{(2)}\right)^{2}+\left\lVert\bm{\Delta}_{\mathrm{tail}}\right\rVert_{\ell^{2}(G)}^{2}+2\left\lVert\tilde{\bm{\Xi}}_{m}\right\rVert_{(k)}^{(2)}\left\lVert\bm{\Delta}_{\mathrm{tail}}\right\rVert_{\ell^{2}(G)}$
$\displaystyle\leq\left(\left\lVert\tilde{\bm{\Xi}}_{m}\right\rVert_{(k)}^{(2)}\right)^{2}+\left\lVert\bm{\Delta}_{\mathrm{tail}}\right\rVert_{\ell^{2}(\bar{G})}^{2}+2\left\lVert\tilde{\bm{\Xi}}_{m}\right\rVert_{(k)}^{(2)}\left\lVert\bm{\Delta}_{\mathrm{tail}}\right\rVert_{\ell^{2}(\bar{G})}.$

Moreover, by Lemmas D.2 and D.3, we have

$\displaystyle\left(\left\lVert\tilde{\bm{\Xi}}_{m}\right\rVert_{(k)}^{(2)}\right)^{2}\leq\frac{n^{2}}{4}\left(4\alpha^{2}-\frac{16\alpha^{2}}{\pi^{2}}\frac{1}{2\min\\{m,k\\}+1}\right)$
$\displaystyle+Cn(m(1+\log m)^{1/2}+n\sigma^{2}m^{2})$
$\displaystyle\quad+C^{\prime}(m^{2}(1+\log m)+n^{2}\sigma^{4}m^{4}).$

Meanwhile, by D.14, we have that $\Delta_{\mathrm{tail}}$ is in
$L^{1}(\mathbb{R}^{2})$, and its $L^{1}$ norm is no larger than that of
$\bar{X}$. Applying Lemma D.17 thus implies

$\displaystyle\left\lVert\bm{\Delta}_{\mathrm{tail}}\right\rVert_{\ell^{2}(\bar{G})}^{2}$
$\displaystyle\leq\frac{n^{2}}{4}\lVert\Delta_{\mathrm{tail}}\rVert_{L^{2}}^{2}+\frac{C}{\sigma^{4}}(1+n\sigma).$

By Young’s inequality, we have that
$\lVert\Delta_{\mathrm{tail}}\rVert_{L^{2}}$ is less than the corresponding
tail sum without smoothing. Now notice that, by orthogonality,

$\displaystyle\left\lVert\sum_{l=m+1}^{\infty}\lambda_{l}g_{l}g_{l}^{\ast}\right\rVert_{L^{2}}^{2}$
$\displaystyle=\sum_{l=m+1}^{\infty}\lambda_{l}^{2}$
$\displaystyle\leq\frac{32\alpha^{2}}{\pi^{2}}\frac{1}{2m+1},$

following the arguments in the proof of Lemma D.3 (the last estimate assumes
$m\geq 1$). Thus

$\displaystyle\left\lVert\bm{\Delta}_{\mathrm{tail}}\right\rVert_{\ell^{2}(\bar{G})}^{2}$
$\displaystyle\leq\frac{32\alpha^{2}n^{2}}{4\pi^{2}}\frac{1}{2m+1}+\frac{1}{\sigma^{4}}(1+n\sigma).$

Combining these estimates, we have

$\displaystyle\left(\left\lVert\bar{\bm{X}}\right\rVert_{(k)}^{(2)}\right)^{2}$
$\displaystyle\leq
n^{2}\alpha^{2}+\frac{4n^{2}}{\pi^{2}}\frac{1}{2m+1}-\frac{2n^{2}/\pi^{2}}{2\min\\{m,k\\}+1}$
$\displaystyle\quad+Cn(m(1+\log
m)^{1/2}+n\sigma^{2}m^{2})+C^{\prime}m^{2}(1+\log
m)C^{\prime}n^{2}\sigma^{4}m^{4}+C^{\prime\prime}(1+n\sigma)/\sigma^{4}$
$\displaystyle\quad+C^{\prime\prime\prime}\left(n+\sqrt{nm\log^{1/2}m}+n\sigma
m+m\sqrt{\log
m}+n\sigma^{2}m^{2}\right)\left(\frac{n}{\sqrt{m}}+\sqrt{\frac{1+n\sigma}{\sigma^{4}}}\right).$

Inspecting these residuals with some foresight, it is clear that the
smoothing-induced terms will typically dominate: these require that
$m\sigma\lesssim 1$, but for the best lower bound we want $m$ to be large,
whereas the residuals of size $n/\sigma^{3}$ penalize us for choosing $\sigma$
to be too small. We will make the choices $m=n^{4/19}$ and $\sigma=m^{-5/4}$.
Evaluating the residual in the previous expression shows that for $n$
sufficiently large, there is an absolute constant $C>0$ such that

$\left(\left\lVert\bar{\bm{X}}\right\rVert_{(k)}^{(2)}\right)^{2}\leq
n^{2}\alpha^{2}+\frac{4n^{2}}{\pi^{2}}\frac{1}{2m+1}-\frac{2n^{2}/\pi^{2}}{2\min\\{m,k\\}+1}+Cn^{36/19}.$

Similarly, when $m\geq Ck$ for a sufficiently large constant $C$, this bound
is upper bounded by

$\left(\left\lVert\bar{\bm{X}}\right\rVert_{(k)}^{(2)}\right)^{2}\leq
n^{2}\alpha^{2}-\frac{cn^{2}}{k+1}+C^{\prime}n^{36/19}.$

Now, plugging this estimate into D.15 after requiring that $k\leq
c\sqrt{m}=cn^{2/19}$ for an absolute constant $c>0$, we have

$\left\lVert\hat{\bm{X}}-\bm{X}_{\nu_{\natural}}\right\rVert_{\ell^{2}({G})}\geq\sqrt{\left\lVert\bar{\bm{X}}\right\rVert_{\ell^{2}({G})}^{2}-n^{2}\alpha^{2}+\frac{cn^{2}}{1+k}-C^{\prime}n^{36/19}}-\left\lVert\bar{\bm{X}}-\bm{X}_{\nu_{\natural}}\right\rVert_{\ell^{2}({G})}.$

We just need to estimate the remaining error terms. By Lemma D.4, we have for
$m\geq 2^{2/3}$

$\left\lVert\bar{\bm{X}}-\bm{X}\right\rVert_{\ell^{2}(G)}^{2}\leq\frac{n^{2}\sigma^{8}}{\pi^{2}}+\frac{2n}{\pi}+\frac{n^{2}\sqrt{48\sigma^{2}\log(1/\sigma)}}{\pi}.$

We have chosen $\sigma=n^{-5/19}\leq n^{-1/4}$, which makes the residuals in
this expression of order smaller than $n^{3/2}$: for sufficiently large $n$,

$\left\lVert\bar{\bm{X}}-\bm{X}\right\rVert_{\ell^{2}(G)}^{2}\leq Cn^{3/2}$

for an absolute constant $C>0$. Similarly, by this last bound and Lemma D.5
together with the triangle inequality, we have for $n$ sufficiently large

$\displaystyle\left\lVert\bar{\bm{X}}\right\rVert_{\ell^{2}({G})}^{2}$
$\displaystyle\geq\left(\left\lVert{\bm{X}}_{\nu_{\natural}}\right\rVert_{\ell^{2}({G})}-\left\lVert\bar{\bm{X}}-\bm{X}\right\rVert_{\ell^{2}(G)}\right)^{2}$
$\displaystyle=\left\lVert{\bm{X}}\right\rVert_{\ell^{2}({G})}^{2}-2\left\lVert{\bm{X}}\right\rVert_{\ell^{2}({G})}\left\lVert\bar{\bm{X}}-\bm{X}\right\rVert_{\ell^{2}(G)}$
$\displaystyle\geq n^{2}\alpha^{2}-5n-Cn^{7/4}$

where we use the trivial upper bound $\lVert\bm{X}\rVert_{\ell^{2}(G)}\leq n$.
Plugging into our previous EYM estimate and noticing that the previous
residual dominates, we have for $n$ sufficiently large

$\displaystyle\left\lVert\hat{\bm{X}}-\bm{X}\right\rVert_{\ell^{2}({G})}$
$\displaystyle\geq\sqrt{\frac{cn^{2}}{1+k}-Cn^{36/19}}-C^{\prime}n^{3/4}.$

For the RMSE, given that $k\leq c\sqrt{m}=cn^{2/19}$ for an absolute constant
$c>0$, we can use the inequality $\sqrt{1-x}\geq 1-x$ for $0\leq x\leq 1$
(following from concavity) to get

$\frac{1}{n}\left\lVert\hat{\bm{X}}-\bm{X}\right\rVert_{\ell^{2}({G})}\geq\frac{c}{\sqrt{1+k}}-Cn^{-1/4}.$

This residual is redundant when $k\lesssim n^{2/19}$, and we can therefore
conclude

$\frac{1}{n^{2}}\left\lVert\hat{\bm{X}}-\bm{X}\right\rVert_{\ell^{2}({G})}^{2}\geq\frac{c}{1+k}$

for a sufficiently small absolute constant $c$.

∎

######  Remark D.1.

Theorem D.1 asserts lower bounds up to a threshold $k\lesssim n^{2/19}$. Based
on empirical evidence and certain key residuals in the proof of Lemma D.2, we
believe it should be possible to assert the same lower bound up to scalings
$k\lesssim n/\log^{c}(n)$, for some $c>0$, although our arguments are
insufficient to this task. The main technical issue we contend with in the
proof of Theorem D.1 is the nonsmoothness of the underlying image
$X_{\natural}$, which in our case necessitates the use of somewhat technical
smoothing arguments. Some lemmas that we develop to this end, especially
Lemmas D.17 and D.18, are suboptimal, and improvements would improve the
rates. At the same time, the perturbation framework we have developed in the
proof of Theorem D.1 relies as little as possible on specific analytical
properties of the spectral decomposition of the infinite-dimensional surrogate
$X=X_{\natural}\circ\bm{\tau}_{\nu_{\natural}}$ for the observation $\bm{X}$,
encapsulated in Lemma D.1; instead, we use only relatively coarse properties
of the spectral decomposition of $X$, including bounds on norms of the
eigenfunctions and their derivatives, the rate of decay of the eigenvalues,
and regularity of the boundary of the support of $X_{\natural}$. It is likely
that more precise estimates tailored at the specific properties of $X$ would
lead to straightforward improvements of the rates, but the resulting loss of
generality would be undesirable for modeling templates and scenes beyond the
model $X_{\natural}$. Accordingly, we believe the crux of our argument should
be applicable to templates $X_{\natural}$ that have better regularity without
having to go through smoothing arguments, which should yield improved rates in
a more general setting.

######  Remark D.2.

The fact that the observation $\bm{X}$ corresponds to the “directly sampled”
observation
$(i,j)\mapsto{\mathds{1}}_{\lVert\bm{\tau}_{\nu_{\natural}}(i,j)\rVert_{\infty}\leq\alpha}$
is not essential to our arguments in Theorem D.1—indeed, the same perturbation
framework would work with minor adaptations for any nonuniformly-sampled grid
that is sufficiently close to the uniform sampling grid $G$. For example,
defining $\bm{X}$ in terms of a resampled version of the square template
$\bm{X}_{\natural}$ using any compactly-supported interpolation kernel, such
as the bilinear interpolation kernel (c.f. Section D.4), would require only
minor adaptations, analogous to our treatment of the smoothing error in Lemma
D.4. Although nonrealistic as a model for image acquisition, it is an
interesting mathematical problem to extend our framework to the case of
nonuniform grids that are far from the uniform grid $G$, such as grids induced
by random sampling locations. Such an extension would require novel ideas,
particularly in the core perturbation result, Lemma D.17.

####  D.1.1 Supporting Results

######  Lemma D.1.

Define a sequence

$\lambda_{k}=(-1)^{k-1}\frac{4\sqrt{2}\alpha}{\pi(2k-1)},\quad k=1,2,\dots,$
(D.16)

and functions $g_{k}:[-1,1]\to\mathbb{R}$ by

$g_{k}(s)=\begin{cases}\frac{1}{\sqrt{\alpha\sqrt{2}}}\cos\left(\frac{\pi}{2\sqrt{2}{\alpha}}(2k-1)s\right)&\lvert
s\rvert\leq\sqrt{2}\alpha\\\ 0&\mathrm{otherwise},\end{cases}\quad
k=1,2,\dots$ (D.17)

Then the functions $g_{k}$ form an orthonormal basis for the range of the
(compact, self-adjoint) operator $\mathcal{T}_{X}$, and we have the
decomposition

$\mathcal{T}_{X}=\sum_{k\in\mathbb{N}}\lambda_{k}g_{k}g_{k}^{\ast}.$

###### Proof.

We take the formula D.7 as our starting point. Because of the spectral theorem
for self-adjoint compact operators on a Hilbert space, we have the
decomposition D.8 for $\mathcal{T}_{X}$. Our approach will be to study the
eigenvalue equation

$\mathcal{T}_{X}[g]=\lambda g,\enspace\lambda\neq 0,g\neq 0,$ (D.18)

and to produce a large enough family of solutions $(\lambda,g)$ to this
equation that we can assert that we have produced the eigenvalues and
eigenfunctions asserted by the spectral theorem in D.8. To begin, we make
several preliminary observations about solutions to the eigenvalue equation
D.18. First, we note from D.7 and the change of variables formula that

$\mathcal{T}_{X}[f](\sqrt{2}\alpha s)=\sqrt{2}{\alpha}\int_{-(1-\lvert
s\rvert)}^{1-\lvert s\rvert}f(\sqrt{2}\alpha t)\mathop{}\\!\mathrm{d}t,$

so that, if for $\varepsilon>0$ we write
$\mathcal{S}_{\varepsilon}[g](u)=g(\varepsilon u)$ as the dilation operator
(which satisfies
$\mathcal{S}_{\varepsilon}^{-1}=\mathcal{S}_{\varepsilon^{-1}}$), we have

$\mathcal{T}_{X}=\mathcal{S}_{\sqrt{2}\alpha}\bar{\mathcal{T}}_{X}\mathcal{S}_{\sqrt{2}\alpha}^{-1},$
(D.19)

where $\bar{\mathcal{T}}_{X}:L^{2}([-1,1])\to L^{2}([-1,1])$ is defined as

$\bar{\mathcal{T}}_{X}[f](s)=\sqrt{2}\alpha\int_{-(1-\lvert
s\rvert)}^{1-\lvert s\rvert}f(t)\mathop{}\\!\mathrm{d}t.$

In particular, $\mathcal{T}_{X}$ is similar to the operator
$\bar{\mathcal{T}}_{X}$. We therefore focus our analysis on
$\bar{\mathcal{T}}_{X}$ below. Next, note that by the Schwarz inequality, we
have

$\displaystyle\left\lvert\bar{\mathcal{T}}_{X}[f](s)\right\rvert$
$\displaystyle\leq\sqrt{2}\alpha\lVert
f\rVert_{L^{2}}\lVert{\mathds{1}}_{[-(1-\lvert s\rvert),1-\lvert
s\rvert]}\rVert_{L^{2}}$ $\displaystyle=4\alpha\lVert
f\rVert_{L^{2}}\sqrt{1-\lvert s\rvert}.$

In particular, we have $\bar{\mathcal{T}}_{X}[f](\pm 1)=0$ for any $f\in
L^{2}$. Thus, if $f$ is moreover a solution to D.18, it is necessary that
$f(\pm 1)=0$, giving us boundary conditions for the eigenvalue equation.
Similarly, the formula D.7 shows that
$\bar{\mathcal{T}}_{X}[f](s)=\bar{\mathcal{T}}_{X}[f](-s)$ for any $f\in
L^{2}$, so any $f$ solving D.18 also satisfies even symmetry.

We proceed with a standard bootstrapping argument—we start by seeking only
solutions to D.18 that are infinitely differentiable. For any $\lvert
s\rvert>0$, differentiating D.7 gives the equivalent boundary value problem

$\lambda g^{\prime}(s)=-\sqrt{2}\alpha\operatorname{sign}(s)\left(g(1-\lvert
s\rvert)-g(-(1-\lvert s\rvert))\right),\quad g(\pm 1)=0$

for the eigenvalue equation D.18. By even symmetry of $g$, this is equivalent
to the problem

$\lambda g^{\prime}(s)=-2\sqrt{2}\alpha\,g(1-s),\quad g(1)=0,\enspace
g^{\prime}(0)=0$

with $g\in C^{\infty}([0,1])$. Differentiating once more to eliminate the
‘space reversal’ on the RHS, we obtain the (necessary) system

$g^{\prime\prime}+\frac{8\alpha^{2}}{\lambda^{2}}g=0,\quad g(1)=0,\enspace
g^{\prime}(0)=0.$

This is a second-order linear ODE. It has as its solutions

$g(s)=A\cos\left(\frac{2\sqrt{2}\alpha}{\lvert\lambda\rvert}s\right)+B\sin\left(\frac{2\sqrt{2}\alpha}{\lvert\lambda\rvert}s\right)$

for constants $A,B$ to be determined with the boundary conditions. The
condition $g^{\prime}(0)=0$ implies that $B=0$. The condition
$g^{\prime}(1)=0$ implies either that $A=0$ or that

$\frac{2\sqrt{2}\alpha}{\lvert\lambda\rvert}\in\frac{\pi}{2}\left(2\mathbb{Z}+1\right),$

i.e., that the frequency is an odd multiple of $\pi/2$. This implies

$\lvert\lambda_{k}\rvert=\frac{4\sqrt{2}\alpha}{\pi(2k+1)},\quad k=0,1,\dots,$

and in particular

$g_{k}(s)=A_{k}\cos\left(\frac{\pi}{2}(2k+1)s\right),\quad k=0,1,\dots,$

where the constants $A_{k}$ can be determined such that $g$ has unit $L^{2}$
norm. We have

$\displaystyle\int_{-1}^{1}g_{k}(s)g_{k^{\prime}}(s)\mathop{}\\!\mathrm{d}s$
$\displaystyle=\frac{1}{2}\int_{-1}^{1}\left(\cos(\pi(k-k^{\prime})s)+\cos(\pi(k+k^{\prime}+1)s)\right)\mathop{}\\!\mathrm{d}s$
$\displaystyle=\left({\mathds{1}}_{k=k^{\prime}}+{\mathds{1}}_{k+k^{\prime}+1=0}\right)$
$\displaystyle={\mathds{1}}_{k=k^{\prime}}.$

In particular, $A_{k}=1$. It remains to determine the signs of the eigenvalues
$\lambda_{k}$. We calculate

$\displaystyle\bar{\mathcal{T}}_{X}[g_{k}](s)$
$\displaystyle=2\sqrt{2}\alpha\int_{0}^{1-\lvert
s\rvert}\cos\left(\frac{\pi}{2}(2k+1)s\right)$
$\displaystyle=\lvert\lambda_{k}\rvert\sin\left(\frac{\pi}{2}(2k+1)(1-\lvert
s\rvert)\right)$
$\displaystyle=\lvert\lambda_{k}\rvert\sin\left(\frac{\pi}{2}(2k+1)\right)\cos\left(\frac{\pi}{2}(2k+1)s\right)$
$\displaystyle=(-1)^{k}\lvert\lambda_{k}\rvert g_{k}(s).$

In particular, the functions $g_{k}$ form a mutually orthogonal set of
eigenfunctions of $\bar{\mathcal{T}}_{X}$ with corresponding eigenvalues

$\lambda_{k}=(-1)^{k}\frac{4\sqrt{2}\alpha}{\pi(2k+1)},\quad k=0,1,\dots$

To conclude, we note that from D.19 that the functions
$f_{k}:[-1,+1]\to\mathbb{R}$ defined by

$f_{k}(s)=\begin{cases}\frac{1}{\sqrt{\alpha\sqrt{2}}}\cos\left(\frac{\pi}{2\sqrt{2}{\alpha}}(2k+1)s\right)&\lvert
s\rvert\leq\sqrt{2}\alpha\\\ 0&\mathrm{otherwise},\end{cases}\quad
k=0,1,\dots$

form an orthonormal basis for the image of $\mathcal{T}_{X}$, and together
with the eigenvalues $\lambda_{k}$ defined above provide a Schmidt
decomposition of the operator $\mathcal{T}_{X}$:

$\mathcal{T}_{X}=\sum_{k\in\mathbb{N}_{0}}\lambda_{k}f_{k}f_{k}^{\ast}.$

This completes the proof. ∎

######  Lemma D.2.

For all $m\in\mathbb{N}$, any $k\in[n]$, and any $\sigma^{2}>0$, one has for
the operator defined in D.11

$\left\lVert\tilde{\bm{\Xi}}_{m}\right\rVert_{(k)}^{(2)}\leq\frac{n}{2}\left\lVert\bm{\Lambda}_{m}\right\rVert_{(k)}^{(2)}+\frac{4m(1+\log
m)^{1/2}}{\alpha}+\frac{\pi n\sigma^{2}m^{2}}{32\sqrt{2}\alpha}.$

###### Proof.

We build from the matrix representation D.11 of $\tilde{\bm{\Xi}}_{m}$. The
idea of the proof is straightforward: if $\tilde{\bm{U}}_{m}$ had orthonormal
columns, we would have immediately

$\left\lVert\tilde{\bm{\Xi}}_{m}\right\rVert_{(k)}^{(2)}=\left\lVert\bm{\Lambda}_{m}\right\rVert_{(k)}^{(2)},$
(D.20)

by unitary invariance. Because of discretization and smoothing errors,
$\tilde{\bm{U}}_{m}$ is not an orthonormal $m$-frame, so D.20 does not hold.
However, when $n$ is large and $m$ is not too large relative to $n$, we can
guarantee that $\tilde{\bm{U}}_{m}$ is close to orthonormal, which we will
combine with a perturbation result (Lemma D.16) to obtain the claim.

By Lemma D.16 and the triangle inequality, we have

$\displaystyle\left\lVert\tilde{\bm{\Xi}}_{m}\right\rVert_{(k)}^{(2)}$
$\displaystyle\leq\left\lVert\lvert\bm{\Lambda}_{m}\rvert^{1/2}\tilde{\bm{U}}_{m}^{\ast}\tilde{\bm{U}}_{m}\lvert\bm{\Lambda}_{m}\rvert^{1/2}\right\rVert_{(k)}^{(2)}$
$\displaystyle\leq\tfrac{n}{2}\left\lVert\bm{\Lambda}_{m}\right\rVert_{(k)}^{(2)}+\left\lVert\lvert\bm{\Lambda}_{m}\rvert^{1/2}\left(\tilde{\bm{U}}_{m}^{\ast}\tilde{\bm{U}}_{m}-\tfrac{n}{2}\bm{I}\right)\lvert\bm{\Lambda}_{m}\rvert^{1/2}\right\rVert_{(k)}^{(2)}$
$\displaystyle\leq\tfrac{n}{2}\left\lVert\bm{\Lambda}_{m}\right\rVert_{(k)}^{(2)}+\left\lVert\lvert\bm{\Lambda}_{m}\rvert^{1/2}\left(\tilde{\bm{U}}_{m}^{\ast}\tilde{\bm{U}}_{m}-\tfrac{n}{2}\bm{I}\right)\lvert\bm{\Lambda}_{m}\rvert^{1/2}\right\rVert_{\mathrm{F}},$
(D.21)

where in the final inequality we worst-case the residual by summing over all
singular values. We will bound the residual term in D.21 by bounding the
magnitude of each of its elements. For $j=0,1,\dots,m-1$, let
$\tilde{\bm{u}}_{m,j}$ denote the $j$-th column of $\tilde{\bm{U}}_{m}$, and
let $\pi_{1}(G)$ denote the projection of the rectangle $G$ onto its first
coordinate. Then
$(2/n)\langle\tilde{\bm{u}}_{m,j},\tilde{\bm{u}}_{m,j^{\prime}}\rangle$ is a
Riemann sum corresponding to the integral of the function
$(\varphi_{\sigma^{2}}\mathbin{\ast}g_{j})(\varphi_{\sigma^{2}}\mathbin{\ast}g_{j^{\prime}})$
over $[-1,1]$. We have from the Leibniz rule

$\displaystyle\left\lVert(\varphi_{\sigma^{2}}\mathbin{\ast}g_{j})(\varphi_{\sigma^{2}}\mathbin{\ast}g_{j^{\prime}})\right\rVert_{\mathrm{Lip}}$
$\displaystyle=\lVert\varphi_{\sigma^{2}}\mathbin{\ast}g_{j}\rVert_{L^{\infty}}\lVert\varphi_{\sigma^{2}}\mathbin{\ast}g_{j^{\prime}}\rVert_{\mathrm{Lip}}+\lVert\varphi_{\sigma^{2}}\mathbin{\ast}g_{j}\rVert_{\mathrm{Lip}}\lVert\varphi_{\sigma^{2}}\mathbin{\ast}g_{j^{\prime}}\rVert_{L^{\infty}}$
$\displaystyle=\frac{1}{\sqrt{2}\alpha}\left(\lVert
g_{j}\rVert_{\mathrm{Lip}}+\lVert g_{j^{\prime}}\rVert_{\mathrm{Lip}}\right)$
$\displaystyle=\frac{\pi(j+j^{\prime}+1)}{2\alpha^{2}},$

where we use the fact that convolution with a gaussian does not increase
$L^{\infty}$ norms (a special case of Young’s inequality [5, Ch. I, Thm 1.3])
nor Lipschitz seminorms (the functions $g_{j}$ are all in $C^{\infty}$, so we
can differentiate under the integral and then apply Jensen’s inequality, since
the gaussian has unit $L^{1}$ norm). Thus, by Lemma D.15 and Lemma D.1 and the
triangle inequality, we have

$\displaystyle\left\lvert\langle\tilde{\bm{u}}_{m,j},\tilde{\bm{u}}_{m,j^{\prime}}\rangle-\frac{n}{2}{\mathds{1}}_{j=j^{\prime}}\right\rvert$
$\displaystyle\leq\left\lvert\langle\tilde{\bm{u}}_{m,j},\tilde{\bm{u}}_{m,j^{\prime}}\rangle-\frac{n}{2}\langle\varphi_{\sigma^{2}}\mathbin{\ast}g_{j},\varphi_{\sigma^{2}}\mathbin{\ast}g_{j^{\prime}}\rangle_{L^{2}}\right\rvert+\left\lvert\frac{n}{2}\langle\varphi_{\sigma^{2}}\mathbin{\ast}g_{j},\varphi_{\sigma^{2}}\mathbin{\ast}g_{j^{\prime}}\rangle_{L^{2}}-\frac{n}{2}{\mathds{1}}_{j=j^{\prime}}\right\rvert$
$\displaystyle\leq\frac{n}{2}\left\lvert\langle\varphi_{\sigma^{2}}\mathbin{\ast}g_{j},\varphi_{\sigma^{2}}\mathbin{\ast}g_{j^{\prime}}\rangle_{L^{2}}-{\mathds{1}}_{j=j^{\prime}}\right\rvert+\frac{\pi(j+j^{\prime}+1)}{2\alpha^{2}}.$
(D.22)

To handle the remaining residual, we will apply Lemma D.18. This gives

$\frac{n}{2}\left\lvert\langle\varphi_{\sigma^{2}}\mathbin{\ast}g_{j},\varphi_{\sigma^{2}}\mathbin{\ast}g_{j^{\prime}}\rangle_{L^{2}}-{\mathds{1}}_{j=j^{\prime}}\right\rvert\leq\frac{n\sigma^{2}}{2}\lVert
g_{j}^{\prime}\rVert_{L^{2}}\lVert g_{j^{\prime}}^{\prime}\rVert_{L^{2}},$

and from Lemma D.1 and a $L^{1}$-$L^{\infty}$ estimate, we have

$\lVert g_{j}^{\prime}\rVert_{L^{2}}\leq\frac{\pi(2j+1)}{2\sqrt{2}\alpha},$

whence

$\frac{n}{2}\left\lvert\langle\varphi_{\sigma^{2}}\mathbin{\ast}g_{j},\varphi_{\sigma^{2}}\mathbin{\ast}g_{j^{\prime}}\rangle_{L^{2}}-{\mathds{1}}_{j=j^{\prime}}\right\rvert\leq\frac{n\sigma^{2}\pi^{2}(2j+1)(2j^{\prime}+1)}{16\alpha^{2}}.$

In particular, substituting this estimate into D.22 gives

$\displaystyle\left\lvert\langle\tilde{\bm{u}}_{m,j},\tilde{\bm{u}}_{m,j^{\prime}}\rangle-\frac{n}{2}{\mathds{1}}_{j=j^{\prime}}\right\rvert\leq\frac{n\sigma^{2}\pi^{2}(2j+1)(2j^{\prime}+1)}{16\alpha^{2}}+\frac{\pi(j+j^{\prime}+1)}{2\alpha^{2}}.$
(D.23)

From the definition of $\bm{\Lambda}_{m}$, it follows

$\displaystyle\left\lVert\lvert\bm{\Lambda}_{m}\rvert^{1/2}\left(\bm{U}_{m}^{\ast}\bm{U}_{m}-\tfrac{n}{2}\bm{I}\right)\lvert\bm{\Lambda}_{m}\rvert^{1/2}\right\rVert_{\mathrm{F}}^{2}$
$\displaystyle\leq\frac{16}{\alpha^{2}}\sum_{1\leq i,j\leq
m}\frac{(i+j-1)^{2}}{(2i-1)(2j-1)}+\frac{\pi^{2}n^{2}\sigma^{4}}{2^{11}\alpha^{2}}\sum_{1\leq
i,j\leq m}(2i-1)(2j-1).$

The second sum evaluates to $m^{4}$. For the first sum, note that
$i+j-1=\tfrac{1}{2}((2i-1)+(2j-1))$, so

$\displaystyle\frac{(i+j-1)^{2}}{(2i-1)(2j-1)}$
$\displaystyle=\frac{1}{4}\left(\sqrt{\frac{2i-1}{2j-1}}+\sqrt{\frac{2j-1}{2i-1}}\right)^{2}$
$\displaystyle\leq\frac{1}{2}\left(\frac{2i-1}{2j-1}+\frac{2j-1}{2i-1}\right),$

by the inequality $a+b\leq 2(a^{2}+b^{2})$. When summed over the grid
$[m]^{2}$, the two functions of $i,j$ in the last inequality must be equal by
symmetry. Thus

$\displaystyle\sum_{1\leq i,j\leq m}\frac{(i+j-1)^{2}}{(2i-1)(2j-1)}$
$\displaystyle\leq\sum_{1\leq i,j\leq m}\frac{2i-1}{2j-1}$
$\displaystyle=m^{2}\sum_{j=1}^{m}\frac{1}{2j-1}.$

By the usual estimates $\log m\leq\sum_{j=1}^{m}\tfrac{1}{j}\leq 1+\log m$ for
the harmonic numbers, we have $\sum_{j=1}^{m}\tfrac{1}{2j-1}\leq
1+\log(2m)-\tfrac{1}{2}\log m$, which in turn is less than $1+\log m$ when
$m\geq 4$. In addition, one can check numerically that the same estimate holds
for $m\in\\{1,2,3,4\\}$. We have thus shown

$\left\lVert\lvert\bm{\Lambda}_{m}\rvert^{1/2}\left(\bm{U}_{m}^{\ast}\bm{U}_{m}-\tfrac{n}{2}\bm{I}\right)\lvert\bm{\Lambda}_{m}\rvert^{1/2}\right\rVert_{\mathrm{F}}^{2}\leq\frac{8m^{2}(1+\log
m)}{\alpha^{2}}+\frac{\pi^{2}n^{2}\sigma^{4}m^{4}}{2^{11}\alpha^{2}},$

which establishes the claim when combined with our previous estimates.

∎

######  Lemma D.3.

For all $m\in\mathbb{N}$ and any $k\in[n]$, one has for the operator defined
in D.11

$\left\lVert\bm{\Lambda}_{m}\right\rVert_{(k)}^{(2)}\leq\sqrt{4\alpha^{2}-\frac{16\alpha^{2}}{\pi^{2}}\frac{1}{2\min\\{m,k\\}+1}}.$

###### Proof.

We have by definition

$\displaystyle\left(\left\lVert\bm{\Lambda}_{m}\right\rVert_{(k)}^{(2)}\right)^{2}$
$\displaystyle=\frac{32\alpha^{2}}{\pi^{2}}\sum_{i=1}^{\min\\{k,m\\}}\frac{1}{(2k-1)^{2}}$
$\displaystyle=\frac{32\alpha^{2}}{\pi^{2}}\left(\sum_{i=1}^{\infty}\frac{1}{(2k-1)^{2}}-\sum_{i=1+\min\\{k,m\\}}^{\infty}\frac{1}{(2k-1)^{2}}\right).$
(D.24)

For the first term, we have

$\displaystyle\sum_{i=1}^{\infty}\frac{1}{(2k-1)^{2}}$
$\displaystyle=\sum_{i=1}^{\infty}\frac{1}{k^{2}}-\sum_{i=1}^{\infty}\frac{1}{(2k)^{2}}$
$\displaystyle=\frac{3}{4}\sum_{i=1}^{\infty}\frac{1}{k^{2}}$
$\displaystyle=\frac{\pi^{2}}{8}.$

For the second term, we have from the integral test estimate

$\displaystyle\sum_{i=1+\min\\{k,m\\}}^{\infty}\frac{1}{(2k-1)^{2}}$
$\displaystyle\geq\int_{1+\min\\{k,m\\}}^{\infty}\frac{1}{(2t-1)^{2}}\mathop{}\\!\mathrm{d}t$
$\displaystyle=\frac{\tfrac{1}{2}}{2\min\\{k,m\\}+1}.$

Plugging into D.24 and taking square roots gives the claim. ∎

######  Lemma D.4.

Consider the smoothed template $\bar{X}$, as in Theorem D.1, with sampling
$\bar{\bm{X}}$ on the grid $G$. Let $\bm{X}$ denote the “directly sampled”
template

$({\bm{X}})_{ij}={\mathds{1}}_{\lVert(\bm{\tau}_{\pi/4})_{ij}\rVert_{\infty}\leq\alpha},$

where we recall D.97 and D.98. Then if $\sigma\leq\tfrac{1}{2}$ and
$\alpha=\tfrac{1}{\sqrt{2}}$, one has

$\left\lVert\bar{\bm{X}}-\bm{X}\right\rVert_{\ell^{2}(G)}^{2}\leq\frac{n^{2}\sigma^{8}}{\pi^{2}}+\frac{2n}{\pi}+\frac{n^{2}\sqrt{48\sigma^{2}\log(1/\sigma)}}{\pi}.$

###### Proof.

Note that by definition

$\bar{X}(i,j)=\int_{\mathbb{R}^{2}}\varphi_{\sigma^{2}}((i,j)-\bm{x}^{\prime})X(\bm{x}^{\prime})\mathop{}\\!\mathrm{d}\bm{x}^{\prime}.$

Because

$\varphi_{\sigma^{2}}(\bm{x})=\frac{1}{2\pi\sigma^{2}}e^{-\frac{1}{2\sigma^{2}}\lVert\bm{x}\rVert_{2}^{2}},$

for $\lVert\bm{x}\rVert_{2}^{2}\geq 12\sigma^{2}\log(1/\sigma)$, one has

$\varphi_{\sigma^{2}}(\bm{x})\leq\frac{\sigma^{4}}{2\pi}.$ (D.25)

Since $\lVert\bm{x}\rVert_{2}\geq\lVert\bm{x}\rVert_{\infty}$ and
$\lVert\bm{R}_{\nu}\bm{x}\rVert_{2}=\lVert\bm{x}\rVert_{2}$, if
$\lVert\bm{R}_{\pi/4}\bm{x}\rVert_{\infty}^{2}\geq
12\sigma^{2}\log(1/\sigma)$, then D.25 also holds.

Consider the set

$S=\left\\{(i,j)\in
G\nonscript\>\middle|\allowbreak\nonscript\>\mathopen{}\left\lvert\left\lVert(\bm{\tau}_{\pi/4})_{ij}\right\rVert_{\infty}-\alpha\right\rvert>\sqrt{12\sigma^{2}\log(1/\sigma)}\right\\},$
(D.26)

and write $S^{\mathsf{c}}$ for the complement of $S$ relative to $G$. First,
suppose that $(i,j)\in S$ is not in the support of $X$. We have $X(i,j)=0$,
and

$\displaystyle\bar{X}(i,j)$
$\displaystyle=\int_{\mathbb{R}^{2}}\varphi_{\sigma^{2}}((i,j)-\bm{x}^{\prime})X(\bm{x}^{\prime})\mathop{}\\!\mathrm{d}\bm{x}^{\prime}$
$\displaystyle=\int_{\lVert\bm{R}_{\pi/4}\bm{x}\rVert_{\infty}\leq\alpha}\varphi_{\sigma^{2}}((i,j)-\bm{x}^{\prime})X(\bm{x}^{\prime})\mathop{}\\!\mathrm{d}\bm{x}^{\prime}+\int_{\lVert\bm{R}_{\pi/4}\bm{x}\rVert_{\infty}\geq\alpha}\varphi_{\sigma^{2}}((i,j)-\bm{x}^{\prime})X(\bm{x}^{\prime})\mathop{}\\!\mathrm{d}\bm{x}^{\prime}$
$\displaystyle\leq\frac{\sigma^{4}}{2\pi}\int_{\lVert\bm{R}_{\pi/4}\bm{x}\rVert_{\infty}\leq\alpha}X(\bm{x}^{\prime})\mathop{}\\!\mathrm{d}\bm{x}^{\prime}$
$\displaystyle=\frac{\sigma^{4}}{\pi}$

by the triangle inequality. Evidently $\bar{X}(i,j)\geq 0$ as well. A
symmetric argument applies when $(i,j)\in S$ is in the support of $X$, except
that we obtain

$\displaystyle\bar{X}(i,j)$
$\displaystyle=\int_{\mathbb{R}^{2}}\varphi_{\sigma^{2}}(\bm{x}^{\prime})X((i,j)-\bm{x}^{\prime})\mathop{}\\!\mathrm{d}\bm{x}^{\prime}$
$\displaystyle=\int_{\lVert\bm{R}_{\pi/4}((i,j)-\bm{x}^{\prime})\rVert_{\infty}\leq\alpha}\varphi_{\sigma^{2}}(\bm{x}^{\prime})\mathop{}\\!\mathrm{d}\bm{x}^{\prime}$
$\displaystyle=1-\int_{\lVert\bm{R}_{\pi/4}((i,j)-\bm{x}^{\prime})\rVert_{\infty}\geq\alpha}\varphi_{\sigma^{2}}(\bm{x}^{\prime})\mathop{}\\!\mathrm{d}\bm{x}^{\prime},$

whence

$\displaystyle\left\lvert\bar{X}(i,j)-1\right\rvert$
$\displaystyle\leq\int_{\lVert\bm{R}_{\pi/4}((i,j)-\bm{x}^{\prime})\rVert_{\infty}\geq\alpha}\varphi_{\sigma^{2}}(\bm{x}^{\prime})\mathop{}\\!\mathrm{d}\bm{x}^{\prime}$
$\displaystyle\leq\int_{\lVert\bm{R}_{\pi/4}\bm{x}^{\prime}\rVert_{\infty}\geq\sqrt{12\sigma^{2}\log(1/\sigma)}}\varphi_{\sigma^{2}}(\bm{x}^{\prime})\mathop{}\\!\mathrm{d}\bm{x}^{\prime}$
$\displaystyle\leq\int_{\lVert\bm{x}^{\prime}\rVert_{\infty}\geq\sqrt{6\sigma^{2}\log(1/\sigma)}}\varphi_{\sigma^{2}}(\bm{x}^{\prime})\mathop{}\\!\mathrm{d}\bm{x}^{\prime}.$

The last integral can be estimated with the fact that the gaussian tail
integral is bounded by the density—in particular, [36, Proposition 2.1.2]
gives

$\int_{\lVert\bm{x}^{\prime}\rVert_{\infty}\geq\sqrt{6\sigma^{2}\log(1/\sigma)}}\varphi_{\sigma^{2}}(\bm{x}^{\prime})\mathop{}\\!\mathrm{d}\bm{x}^{\prime}\leq\left(\frac{1}{\sqrt{12\pi\log(1/\sigma)}}e^{-3\log(1/\sigma)}\right)^{2}=\frac{\sigma^{6}}{12\pi\log(1/\sigma)},$

so we have

$\left\lvert\bar{X}(i,j)-1\right\rvert\leq\frac{\sigma^{4}}{\pi},$