#  Variance Norms for Kernelized Anomaly Detection

Thomas Cass1,2, Lukas Gonon1, Nikita Zozoulenko1,* 1 Department of
Mathematics, Imperial College London, London, UK
2 Institute for Advanced Study, Princeton, USA
* Corresponding author, email<EMAIL_ADDRESS>
###### Abstract

We present a unified theory for Mahalanobis-type anomaly detection on Banach
spaces, using ideas from Cameron-Martin theory applied to non-Gaussian
measures. This approach leads to a basis-free, data-driven notion of anomaly
distance through the so-called variance norm of a probability measure, which
can be consistently estimated using empirical measures. Our framework
generalizes the classical $\bbR^{d}$, functional $(L^{2}[0,1])^{d}$, and
kernelized settings, including the general case of non-injective covariance
operator. We prove that the variance norm depends solely on the inner product
in a given Hilbert space, and hence that the kernelized Mahalanobis distance
can naturally be recovered by working on reproducing kernel Hilbert spaces.

Using the variance norm, we introduce the notion of a kernelized nearest-
neighbour Mahalanobis distance for semi-supervised anomaly detection. In an
empirical study on 12 real-world datasets, we demonstrate that the kernelized
nearest-neighbour Mahalanobis distance outperforms the traditional kernelized
Mahalanobis distance for multivariate time series anomaly detection, using
state-of-the-art time series kernels such as the signature, global alignment,
and Volterra reservoir kernels. Moreover, we provide an initial theoretical
justification of nearest-neighbour Mahalanobis distances by developing
concentration inequalities in the finite-dimensional Gaussian case.

Keywords: Mahalanobis distance; covariance operator; kernel methods; semi-
supervised anomaly detection; multivariate time series

###### Contents

  1. 1 Introduction
    1. 1.1 Mahalanobis distance on $\bbR^{d}$ and $(L^{2}[0,1])^{d}$
    2. 1.2 Overview of the unified framework
    3. 1.3 Organization of the paper
  2. 2 Theoretical Foundations of Variance Norms
    1. 2.1 Covariance operators
    2. 2.2 Extended Cameron-Martin spaces
    3. 2.3 Hilbert space setting
    4. 2.4 Mahalanobis distance and conformance score
    5. 2.5 Finite-dimensional concentration inequalities
    6. 2.6 Regularized variance norms
    7. 2.7 Kernelized variance norms
  3. 3 Computing Variance Norms
    1. 3.1 Hilbert Case
    2. 3.2 Algorithms
    3. 3.3 Banach case
  4. 4 Application to Multivariate Time Series
    1. 4.1 Time series kernels
      1. 4.1.1 Static and integral class kernels
      2. 4.1.2 Global alignment kernel
      3. 4.1.3 Volterra reservoir kernel
      4. 4.1.4 Signature kernels
    2. 4.2 Experiments
      1. 4.2.1 Experimental setup
      2. 4.2.2 Hyper-parameter selection
      3. 4.2.3 Pre-processing
      4. 4.2.4 Data and results
      5. 4.2.5 Discussion

##  1 Introduction

The field of anomaly detection encompasses various techniques to identify data
that deviate significantly from expected patterns in a given dataset. Some
widely used methods include the Mahalanobis distance [Mah36, DJM00], density-
based local outlier factors [Bre+00], clustering methods [HXD03], nearest-
neighbour distances [HKF04, VF11], angle-based outlier detection [KSZ08],
isolation forests [LTZ08], support vector machines [AGA13], and neural
networks [Ruf+20, Pan+21]. For a review of both classical and modern
approaches to anomaly detection, we refer to [Ruf+21]. This paper concerns the
semi-supervised setting, where data is only available for the non-anomalous
class.

In this article we propose a novel framework for Mahalanobis-type anomaly
detection on any Banach or Hilbert space, based on a generalized notion of
variance norm [Sha+23] and ideas from Cameron-Martin spaces (see e.g. [Bog15,
Lif12]). Our extended framework includes the classical Mahalanobis distance on
$\bbR^{d}$ [Mah36, DJM00], the functional Mahalanobis distance on
$(L^{2}[0,1])^{d}$ [PL15, BBC20], and the kernelized Mahalanobis distance
[RL01] as special cases. Notably, our formulation includes the general case of
non-injective covariance operators, which is not addressed in the current
literature. Using the variance norm, we derive theory and computational
formulas for the Mahalanobis distance, as well as the nearest-neighbour
Mahalanobis distance, in the infinite-dimensional setting. One key
contribution of this paper is the introduction of a kernelized nearest-
neighbour Mahalanobis distance, which we demonstrate can be efficiently
computed with the same time complexity as the kernelized Mahalanobis distance.

We begin by giving a brief overview of the current literature on Mahalanobis
distance, to motivate the need for a general theory.

###  1.1 Mahalanobis distance on $\bbR^{d}$ and $(L^{2}[0,1])^{d}$

A classical approach to semi-supervised anomaly detection on $\bbR^{d}$ is via
the Mahalanobis distance [Mah36, DJM00]. Suppose we have a random vector $X$
in $\bbR^{d}$ with non-singular covariance matrix $\Sigma\in\bbR^{d\times d}$
and mean $\frakm\in\bbR^{d}$. The Mahalanobis distance $d_{M}(\cdot;X)$ is
defined as the covariance-adjusted distance to the mean, and can be expressed
in any of the three following ways for a new sample $y\in\bbR^{d}$

$\displaystyle d_{M}(y;X)$
$\displaystyle:=\sqrt{(y-\frakm)^{T}\Sigma^{-1}(y-\frakm)}$ (1)
$\displaystyle=\big{\|}\Sigma^{-\frac{1}{2}}(y-\frakm)\big{\|}_{\bbR^{d}}$
$\displaystyle=\sqrt{\sum_{i=1}^{d}\frac{1}{\lambda_{i}}\langle
y-\frakm,e_{i}\rangle^{2}},$

where $(e_{n},\lambda_{n})_{n=1}^{N}$ are the eigenvector-eigenvalue pairs of
the covariance matrix $\Sigma$. Anomaly detection is performed by classifying
new samples with a Mahalanobis distance greater than some fixed threshold as
anomalous. This method was originally used by [Mah36], but has since also been
employed in a variety of fields such as chemometrics [DJM00], unmanned vehicle
detection [LKK10], medicine [Wan+11], cybersecurity [Dan+20], supervised
classification [XNZ08], data clustering [Bro+22], and financial market anomaly
detection [Aky+22].

In the case of Gaussian data, the distribution of $d_{M}(y;X)$ is explicitly
known, which allows for the construction of a test statistic (see e.g.
[DJM00]). A popular method to extend the use of Mahalanobis distances to non-
Gaussian data is through the use of kernel learning [CS01, Sch09], where
samples are embedded into RKHSs using non-linear feature maps. The kernelized
Mahalanobis distance was first studied in [RL01] by replacing the implicit dot
products in (1) with inner products of the feature map, or equivalently, by
positive definite kernel evaluations. The method has since been used in
supervised classification [WYT07, PH09, Cha+20] and anomaly detection [Lah+17,
SCZ18, Dan+20].

Recently, the Mahalanobis distance was generalized to the Hilbert space
$L^{2}[0,1]$ in the context of functional data analysis [PL15, BBC20]. This
extension uses Hilbert-Schmidt covariance operators to define functional
analogues of the Mahalanobis distance. In this setting, we consider a
stochastic process $\big{(}X(t)\big{)}_{t\in[0,1]}$ in $L^{2}[0,1]$ with
continuous covariance function $a(s,t):=\cov[X(s),X(t)]$ and functional mean
$\frakm(t):=\E[X(t)]\in L^{2}[0,1]$. The covariance operator $\calK$, defined
by $\calK f(t):=\int_{0}^{1}a(s,t)f(s)ds$ for $f\in L^{2}[0,1]$, is symmetric,
positive, compact, and hence diagonalizable by the spectral theorem via the
eigenvector-eigenvalue pairs $(e_{n},\lambda_{n})_{n=1}^{\infty}$ with non-
negative eigenvalues. The naive definition of the functional Mahalanobis
distance $d_{FM}$ reads

$\displaystyle d_{FM}(f;X):=\|\calK^{-\frac{1}{2}}f\|_{L^{2}[0,1]},$ (2)

and the problem we face in this infinite-dimensional setting is the non-
invertibility of $\calK^{\frac{1}{2}}$. When the inverse exists, it is given
by
$\calK^{-\frac{1}{2}}f=\sum_{n=1}^{\infty}\frac{1}{\sqrt{\lambda_{n}}}\langle
e_{n},f\rangle e_{n},$ but since $\calK$ is of trace class, we have that
$\sum_{n=1}^{\infty}\lambda_{n}<\infty$. This restricts the set of elements
for which the inverse is well defined. In fact, if $X$ is a Gaussian process
and $f$ is a sample path of $X$, then a classical result from Gaussian
probability theory states that $\calK^{-\frac{1}{2}}f$ will almost surely not
exist, see e.g. [Hai23, Proposition 4.45]. The first paper to use $d_{FM}$
resolved this issue by approximating $\calK$ via its $M$ biggest eigenvalues,
where $M$ was determined via cross-validation [PL15]. Further theoretical
advances were later made to the functional theory under the assumption that
$\calK$ is injective [BBC20], using the RKHS
$\calH(\calK):=\calK^{1/2}(L^{2}[0,1])$ to regularize $d_{FM}$ by considering
the minimization problem

$\displaystyle f_{\alpha}$
$\displaystyle:=\argmin_{h\in\calH(\calK)}\|f-h\|^{2}+\alpha\|\calK^{-\frac{1}{2}}h\|^{2}$
$\displaystyle=(\calK+\alpha I)^{-1}\calK f$
$\displaystyle=\sum_{n=1}^{\infty}\frac{\lambda_{n}}{\lambda_{n}+\alpha}\langle
f,e_{n}\rangle e_{n},$

for some $\alpha>0$. The regularized functional Mahalanobis distance is
defined by replacing $f$ with $f_{\alpha}$ in (2), or equivalently by
considering Tikhonov regularization on the operator $\calK^{\frac{1}{2}}$.
This effectively bypasses the previous invertibility issues, allowing for a
well-behaved anomaly distance on $L^{2}[0,1]$ with theoretical guarantees like
consistency of the sample estimator, and well-understood distributional
properties under Gaussian assumptions on $X$ [BBC20].

A key limitation of the current functional Mahalanobis theory is that the
sample estimator of $d_{FM}$ is special to the $L^{2}[0,1]$ setting, and
essentially reverts to the finite-dimensional Euclidean theory. The procedure
involves discretizing $d$-dimensional sample paths on a grid of $T$ time
steps, and computing the Mahalanobis distance in $\mathbb{R}^{Td}$ [PL15,
RS05]. While this method works for $L^{2}[0,1]$, it fails for other Hilbert
spaces since the construction relies on special properties of $L^{2}[0,1]$.
Our aim in this paper is to derive computational formulas and theoretical
results for the Mahalanobis distance in the most general infinite-dimensional
setting. The current functional approach has several limitations, including
the injectivity assumption of $\calK$. In practical, data-driven settings, the
rank of $\calK$ is finite and bounded by the number of data points, making the
injectivity assumption problematic. Our unified framework does not require
injectivity, and overcomes these issues by showing that the sample Mahalanobis
estimator arises naturally by considering Cameron-Martin spaces with respect
to empirical measures. This framework encompasses non-injective, general
Hilbert space, and finite-dimensional cases within a single theory,
eliminating the need for separate constructions.

###  1.2 Overview of the unified framework

In our unified framework we work on a Banach space $(V,\|\cdot\|)$ with
continuous dual denoted by $V^{*}$. Our main object of study is Borel
probability measures $\mu$ on $V$ of finite second moment, denoted
$\mu\in\calM_{V}$ as per Definition 2.2. For such measures $\mu$, we are able
to define the vector-valued mean

$\frakm:=\int_{V}xd\mu(x),$

and covariance operator $\calK:V^{*}\to V$

$\calK f:=\int_{V}xf(x)d\mu_{\frakm}(x),$

through the use of Bochner integrals, where $\mu_{\frakm}$ is the measure
$\mu$ shifted by $\frakm$. The fundamental object we will work with is the
$\mu$-variance norm defined by

$\|x\|_{\mu\text{-cov}}:=\sup_{\begin{subarray}{c}\cov^{\mu}[f,f]\leq 1,\\\
f\in V^{*}\end{subarray}}f(x),$ (3)

which is well-defined for all $x\in V$, but is allowed to be infinite. This
measure-theoretic notion was first suggested in the original pre-print of
[Sha+23], but the authors provided no formal theory for the infinite
dimensional case, and the idea was subsequently reworked into a variance norm
with respect to a finite sample only, without the use of probability measures
or laws. Our construction presented in this paper extends the data-driven
finite-dimensional variance norm, to a variance norm with respect to the law
$\mu$. In particular, when $\mu$ is a Gaussian measure
$\|x\|_{\mu\text{-cov}}$ coincides with the Cameron-Martin norm of $x$.
Crucially, our construction relies only on the fact that $\mu$ has second
finite moment, and does not use any Gaussian probability theory. In this
extended setting, the Banach space Mahalanobis distance is subsequently
defined as

$d_{M}(x;\mu):=\|x-\frakm\|_{\mu\text{-cov}},$

which is well-defined for all $x\in V$, and coincides with the classical
$\bbR^{d}$, functional, and kernelized Mahalanobis distances, with the added
benefit that our definition supports the case of non-injective covariance
operator $\calK$.

By introducing Tikhonov regularization on the operator $\calK^{\frac{1}{2}}$
when $V$ is a Hilbert space, we are able to define a regularized variance norm
similar to the functional $L^{2}[0,1]$ setting [BBC20]. In our case, the
$\alpha$-regularized $\mu$-variance norm with $\alpha>0$ is given by

$\displaystyle\|x_{\alpha}\|_{\mu\text{-cov}}$
$\displaystyle=\big{\|}(\calK+\alpha I)^{-1}\calK^{\frac{1}{2}}x\big{\|}$
$\displaystyle=\sum_{n=1}^{\infty}\frac{\lambda_{n}}{(\lambda_{n}+\alpha)^{2}}\langle
e_{n},x\rangle,$ (4)

where $(e_{n},\lambda_{n})_{n=1}^{\infty}$ are the eigenvector-eigenvalue
pairs of the covariance operator $\calK$ (the sum in (4) is a finite sum if
dim $V<\infty$). We prove in Theorem 2.33 that a consistent estimator of (4)
is given by $\|x_{\alpha}\|_{\mu^{N}\text{-cov}}$, where
$\mu^{N}=\frac{1}{N}\sum_{i=1}^{N}\delta_{x_{i}}$ is the empirical measure of
a finite sample $\\{x_{1},\cdots,x_{N}\\}\subset V$ assumed to be drawn from
$\mu$. More importantly, this entails that we no longer need one theory for
the covariance operator of a random process, and a different theory for the
finite sample estimator. Our framework allows to use the same results,
theorems, and definitions for the sample estimator and the underlying random
process by considering the variance norm with respect to the empirical measure
$\mu^{N}$.

When $\mu$ is a Gaussian measure, the exact distribution of the Mahalanobis
distance is known and is equal to that of an infinite sum of independent
$\chi^{2}_{1}$ random variables. This generalizes the work of [BBC20] to the
non-injective and general Hilbert case. The expression (4) for empirical
measures can be efficiently computed through an SVD decomposition of the inner
product Gram matrix of the data, as detailed in Theorem 3.3. This procedure,
fully outlined in Algorithms 1 to 3, has strong connections to kernel
principal component analysis [SSM98]. Specifically, this framework allows us
to define a kernelized nearest-neighbour Mahalanobis distance, which we show
can be computed with the same time complexity as the classical kernelized
Mahalanobis distance. This is $\calO(N^{3}+N^{2}K)$ time for fitting the
model, and $\calO(NK+NM)$ time for inference, where $N$ is the number of data
points, $K$ is the time complexity of a single inner product evaluation, and
$M$ is the number of eigenvalues considered.

Our work was motivated by the lack of theory surrounding anomaly detection on
Banach spaces, and more specifically work on anomaly detection for time series
data using the signature transform [Sha+23, Aky+22, Arr+24], an object
originating from the theory of rough paths [Lyo98]. Existing methods for
signature-based anomaly detection have been limited to very low-dimensional
time series due to the exponential $\mathcal{O}(Td^{m})$ time complexity in
the path dimension $d$ when computing $m$-level truncated signatures of time
series of length $T$. Our unified framework addresses this bottleneck,
allowing for efficient computations of signature Mahalanobis distances in
linear time with respect to $d$ through the use of signature kernels [KO19,
Sal+21]. This improvement in time complexity enables these methods to be
applied to high-dimensional time series data.

###  1.3 Organization of the paper

This paper is organized as follows: Section 2 presents results on the
theoretical foundation of variance norms and Mahalanobis distance on Banach
and Hilbert spaces. We begin by constructing the variance norm using ideas
originating from the theory of Cameron-Martin spaces, an approach that
classically involves Gaussian probability measures. However, our construction
is done purely functional-analytically, without relying on any Gaussian
assumptions. Additionally, we present some initial theoretical results for
nearest-neighbour Mahalanobis distances by developing concentration
inequalities in the finite-dimensional Gaussian case via Lipschitz functions
on the Stiefel manifold.

In Section 3, we derive algorithms for computing the variance norm with
respect to empirical measures of observed data in the Hilbert and Banach space
settings, including the kernelized setting. We show that the variance norm —
and hence also the Mahalanobis distance — depends solely on the choice of
inner product, and hence that it can naturally be kernelized in the sense of
kernel learning by working on RKHSs. The full procedure is detailed in
Algorithms 1 to 3.

We conclude the paper with Section 4, where we conduct an extensive empirical
study of kernelized multivariate time series semi-supervised anomaly detection
using 12 real-world datasets from the multivariate UEA archive [Bag+18]. We
demonstrate how the kernelized nearest-neighbor variance norm outperforms the
kernelized Mahalanobis distance on both PR-AUC and ROC-AUC on average,
including the linear non-kernelized case. We find that the non-kernelized
anomaly distances perform well on average but are often outperformed by
dynamic-time kernels such as the signature kernel, the global alignment
kernel, and the Volterra reservoir kernel, which comparatively have the most
first-place rankings across all datasets. Inspired by the $L^{2}[0,1]$ inner
product, we also experiment with a class of positive definite integral-type
kernels, which can be connected to the family of linear time warping kernels.
Our code is publicly available at https://github.com/nikitazozoulenko/kernel-
timeseries-anomaly-detection.

##  2 Theoretical Foundations of Variance Norms

Throughout this section, we consider a Banach space $(V,|\cdot|)$ with its
continuous dual $V^{*}$, and a Borel probability measure $\mu$ defined on $V$.
The primary objective of this section is to develop a comprehensive theory of
variance norms on Banach spaces by extending the concepts of Cameron-Martin
spaces and norms to non-Gaussian measures. For the classical treatment of
Gaussian measures on Banach spaces we refer to [Lif12, Bog15, Hai23].

This section is organized as follows: Section 2.1 introduces the necessary
setup, assumptions on $\mu$, and the covariance operator associated with
$\mu$. In Section 2.2, we define the Cameron-Martin space with respect to a
potentially non-Gaussian measure and prove that the variance norm coincides
with the extended Cameron-Martin norm. Section 2.2 presents specialized
results for the Hilbert space case, expressed in terms of the eigenvectors and
eigenvalues of the covariance operator. Section 2.4 defines the Mahalanobis
distance and the nearest-neighbor Mahalanobis distance in terms of the
variance norm. Section 2.5 presents a method for obtaining concentration
inequalities for the nearest-neighbor Mahalanobis distance in the finite-
dimensional Gaussian case. In Section 2.6, we introduce the concept of
Tikhonov-regularized variance norms, and we prove that they can be
consistently estimated using empirical measures of a sample. We also provide
distributional results for the case of a Gaussian measure. Finally, Section
2.7 discusses the kernelized variance norm, obtained by letting $V$ be a RKHS.

###  2.1 Covariance operators

In order to extend the classical theory beyond Gaussian measures, we first
need to identify suitable conditions on the underlying measures to obtain a
well-defined Cameron-Martin space. Note that we will not assume that our
underlying Banach space is separable. We do this in order to consider possibly
non-separable reproducing kernel Hilbert spaces in the sequel. We will
consider the following class of measures:

######  Definition 2.1.

We say that a measure $\mu$ on a Banach space $V$ has finite $p$-th moment if
$\|\cdot\|\in L^{p}(V,\mu)$.

######  Definition 2.2.

Let $V$ be a Banach space. We denote by $\calM_{V}$ the set of all Borel
probability measures $\mu$ of finite second moment such that the identity map
$V\ni x\mapsto x\in V$ is strongly $\mu$-measurable in the Bochner sense, see
e.g. [AB07, Definition 11.36].

The assumptions in Definition 2.2 allow us to consider non-separable Banach
spaces $V$. In particular, empirical measures of the form
$\frac{1}{N}\sum_{i=1}^{N}\delta_{x_{i}}$ always belong to $\calM_{V}$. On the
other hand, if $V$ were to be separable, then measurability on $V$ would be
equivalent to strong measurability, and in that case $\calM_{V}$ would be the
set of all Borel probability measures on $V$ with finite second moment.

######  Definition 2.3.

Suppose that $\mu\in\calM_{V}$ for a Banach space $V$. Using the Bochner
integral, we define

$\frakm:=\int_{V}xd\mu(x)=\E^{x\sim\mu}\big{[}x\big{]}$

to be the mean of the measure $\mu$. This integral is well defined since the
identity was assumed to be strongly measurable, and it is finite since
$\|\cdot\|\in L^{2}(V,\mu)\subset L^{1}(V,\mu)$. On the continuous dual
$V^{*}$ we define the covariance quadratic form $q:V^{*}\times V^{*}\to\bbR$
by

$\displaystyle q(f,g)$ $\displaystyle:=\cov^{\mu}[f,g]$
$\displaystyle=\E^{x\sim\mu}\bigg{[}f(x-\frakm)g(x-\frakm)\bigg{]}$
$\displaystyle=\langle i^{*}f,i^{*}g\rangle_{L^{2}(V,\mu_{\frakm})},$

for $f,g\in V^{*}$. Here $\mu_{\frakm}$ is the measure obtained by shifting
$\mu$ by the mean $\frakm$, i.e. the pushforward of $x\mapsto x+\frakm$, and
$i^{*}:V^{*}\to L^{2}(V,\mu_{\frakm})$ is the inclusion map sending $f\in
V^{*}$ to its equivalence class in $L^{2}(V,\mu_{\frakm})$.

Note that the inclusion map $i^{*}:V^{*}\to L^{2}(V,\mu_{\frakm})$ is not
necessarily injective. The quadratic form $q$ and the map $i^{*}$ are well-
defined since

$\displaystyle\int_{V}|f(x-y)|^{2}d\mu(x)$
$\displaystyle\leq\|f\|_{V^{*}}^{2}\int_{V}\big{(}\|x\|^{2}+2\|y\|\|x\|+\|y\|^{2}\big{)}d\mu(x)<\infty,$

for all $f\in V^{*}$ and all shifts $y\in V$. Moreover, we have that
$\mu\in\calM_{V}\iff\mu_{y}\in\calM_{V}$. We observe that $q$ defines a
positive quadratic form on $V^{*}$, but that it may fail to be an inner
product if we have that $q(f,f)=0$ for $f\neq 0$. We will sometimes refer to
the quadratic form $q$ as the functional covariance of $\mu$.

An alternative characterization of the quadratic form $q$ is through the so-
called covariance operator of $\mu$. This turns out to be a natural
functional-analytic object to study when we no longer have access to the
Gaussian tools from the classical theory of Cameron-Martin spaces.

######  Definition 2.4.

Let $\mu\in\calM_{V}$ for a Banach space $V$. We define the covariance
operator of $\mu$ to be the bounded linear operator $\calK:V^{*}\to V$ defined
via

$\calK f:=\int_{V}xf(x)d\mu_{\frakm}(x),$

for $f\in V^{*}$.

Note that the map $x\mapsto xf(x)$ is strongly $\mu_{\frakm}$-measurable for
all $f\in V^{*}$ since both $x\mapsto x$ and $x\mapsto f(x)$ are strongly
$\mu_{\frakm}$-measurable, and hence their product also is. The same map is
also Bochner integrable since we have the bound
$\|xf(x)\|\leq\|f\|_{V^{*}}\|x\|^{2}$, which additionally implies that $\calK$
indeed is a bounded linear operator.

######  Remark 2.5.

An alternative way to define $\calK$ is by using the quadratic form $q$ to
first define a linear operator $\calK:V^{*}\to V^{**}$ via $(\calK
f)(g)=q(f,g)$. One then realizes, through Lemma 2.6 below, that $\calK f$
actually is an evaluation functional of the vector
$\int_{V}xf(x)d\mu_{\frakm}(x)\in V$.

######  Lemma 2.6.

Let $\mu\in\calM_{V}$ for some Banach space $V$. The covariance operator
$\calK:V^{*}\to V$ is the unique operator satisfying

$q(f,g)=f(\calK g)$

for all $f,g\in V^{*}$.

Proof  Suppose that $\calK$ is the covariance operator of $\mu$, and fix
$f,g\in V^{*}$. Using the Bochner integral representation of $\calK$ we obtain
that

$\displaystyle q(f,g)$
$\displaystyle=\int_{V}f(x)g(x)d\mu_{\frakm}(x)=\int_{V}f(xg(x))d\mu_{\frakm}(x)$
$\displaystyle=f\bigg{(}\int_{V}xg(x)d\mu_{\frakm}(x)\bigg{)}=f(\calK g),$

where the second to last equality follows from the fact that bounded operators
commute with Bochner integrals, see e.g. [AB07, Lemma 11.45].

Conversely, if $q(f,g)=f(\widetilde{\calK}g)$ for all $f,g\in V^{*}$ and some
operator $\widetilde{\calK}$, then $0=f(\widetilde{\calK}g-\calK g)$.
Consequently $\widetilde{\calK}g=\calK g$ by the Hahn-Banach theorem, for each
$g\in V^{*}$.

In the sequel we will need the fact that $\calK$ is a compact operator. This
will be used in the Hilbert space setting to diagonalize $\calK$ (where
$\calK$ will additionally be of trace class) to obtain a computable expression
for the variance norm. We choose to prove the result in the Banach case for
full generality.

######  Theorem 2.7.

Suppose that $\mu\in\calM_{V}$ for a Banach space $V$. Then the covariance
operator $\calK:V^{*}\to V$ is a compact operator.

Proof  Suppose that $f_{n}$ is a bounded sequence in $V^{*}$, say
$\|f_{n}\|_{V^{*}}\leq 1$. By Alaoglu’s Theorem [Lax14, Theorem 12.3] there
exists a weak*-convergent subsequence $f_{n_{k}}$ converging to some $f\in
V^{*}$, that is $\lim_{k}f_{n_{k}}=f$ pointwise. Since
$\|xf_{n_{k}}(x)\|\leq\|x\|^{2}$ for all $x\in V$, it follows by the Dominated
Convergence Theorem for Bochner integrals [AB07, Theorem 11.46] that

$\displaystyle\lim_{k}\calK f_{n_{k}}$
$\displaystyle=\int_{V}\lim_{k}xf_{n_{k}}(x)d\mu_{\frakm}(x)=\calK f$

which concludes the proof that $\calK$ is compact.

######  Example 2.8 (Case $V=\bbR^{d}$).

Let $\mu$ be a measure on $\bbR^{d}$ with well-defined covariance matrix
$\Sigma=\E^{x\sim\mu}[(x-\frakm)(x-\frakm)^{T}]$ and mean
$\frakm=\E^{x\sim\mu}[x]$. The measure $\mu$ can be viewed as the push-forward
measure of some $d$-dimensional random vector $X$ with covariance matrix
$\Sigma$ and mean $\frakm$. In this finite dimensional setting, we have that
$\bbR^{d}=V=V^{*}$, and

$\displaystyle q(a,b)$ $\displaystyle=\E^{x\sim\mu}\bigg{[}\langle
a,x-m\rangle\langle b,x-m\rangle\bigg{]}$
$\displaystyle=\E^{x\sim\mu}\bigg{[}\sum_{i=1}^{n}\sum_{j=1}^{n}a_{i}b_{j}(x-m)_{i}(x-m)_{j}\bigg{]}$
$\displaystyle=\langle a,\Sigma b\rangle$

for all $a,b\in\bbR^{d}$. Lemma 2.6 tells us that the covariance operator
$\calK$ simply is the linear mapping associated with the covariance matrix
$\Sigma$.

######  Example 2.9 (Case $V=C[0,1]$).

Suppose that $V=C[0,1]$ is the Banach space of continuous functions on $[0,1]$
equipped with the sup norm. Then $V^{*}=\calM[0,1]$ is the space of all finite
signed Borel measures on $[0,1]$, and each $\nu\in\calM[0,1]$ acts on $V$ as a
continuous linear functional via the pairing

$\displaystyle\langle\nu,x\rangle=\int_{0}^{1}x(t)d\nu(t).$

Consider $\mu\in\calM_{V}$. Denote the covariance function by
$a(s,t):=\E^{x\sim\mu_{\frakm}}\big{[}x(t)x(s)\big{]}$ for $s,t\in[0,1]$,
which is well-defined since $\mu\in\calM_{V}$. We then see that the covariance
operator $\calK:V^{*}\to V$ is given by

$\displaystyle(\calK\nu)(t)$ $\displaystyle=\int_{V}x(t)\langle\nu,x\rangle
d\mu_{\frakm}(x)$
$\displaystyle=\int_{V}x(t)\int_{0}^{1}x(s)d\nu(s)d\mu_{\frakm}(x)$
$\displaystyle=\int_{0}^{1}a(s,t)d\nu(s),$

where the change of order of integration is permitted by Fubini’s theorem,
since we have that $\int_{V}\|x\|^{2}d\mu_{\frakm}(x)<\infty$ by assumption,
where $\|\cdot\|$ in this case is the supremum norm.

The following example demonstrates how we recover the functional Mahalanobis
setting in $L^{2}[0,1]$ [PL15, BBC20] as a special case in our framework,
without any assumptions on the continuity of the covariance function
$a(s,t):=\E^{x\sim\mu_{\frakm}}\big{[}x(t)x(s)\big{]}$, or injectivity of the
covariance operator $\calK$.

######  Example 2.10 (Case $V=L^{2}[0,1]$).

Consider the case when $\mu\in\calM_{V}$ and $V=L^{2}[0,1]$ is the Hilbert
space of square integrable functions on $[0,1]$. Using that $\mu$ has finite
second moment, one can show that $a(\cdot,t)\in L^{2}[0,1]$ for a.e. $t$. The
covariance operator $\calK:L^{2}[0,1]\to L^{2}[0,1]$ can then be written as

$\displaystyle(\calK f)(t)$
$\displaystyle=\int_{V}x(t)\int_{0}^{1}f(s)x(s)dsd\mu_{\frakm}(x)$
$\displaystyle=\int_{0}^{1}a(s,t)f(s)ds,$

which we see is a Hilbert–Schmidt integral operator, since

$\displaystyle\int_{0}^{1}\int_{0}^{1}|a(s,t)|dsdt$
$\displaystyle\leq\int_{0}^{1}\int_{0}^{1}\int_{V}|x(s)x(t)|d\mu_{\frakm}(x)dsdt$
$\displaystyle=\int_{V}\|x\|^{2}_{L^{1}[0,1]}d\mu_{\frakm}(x)$
$\displaystyle\leq\ \int_{V}\|x\|^{2}d\mu_{\frakm}(x)<\infty,$

where $\|\cdot\|$ is the $L^{2}[0,1]$-norm.

###  2.2 Extended Cameron-Martin spaces

A fundamental challenge when studying the covariance operator $\calK:V^{*}\to
V$ is that $\calK$ may be non-injective. We address this issue by essentially
quotienting out the degenerate part of $\mu$ by taking the closure of $V^{*}$
in the space $L^{2}(V,\mu_{\frakm})$ with respect to the $L^{2}$-norm, which
is intrinsically related to the quadratic form $q$. This is a classical
approach used to study Gaussian measures on Banach spaces, and it will allow
us to extend $\mathcal{K}$ to an injective operator defined on a closed
subspace of $L^{2}(V,\mu_{\mathfrak{m}})$.

######  Definition 2.11.

Let $V$ be a Banach space. For $\mu\in\calM_{V}$ we define the space
$\calR_{\mu}$ to be the closure of $i^{*}(V^{*})$ in the Hilbert space
$L^{2}(V,\mu_{\frakm})$. Here $i^{*}$ is the map sending $f\in V^{*}$ to its
equivalence class in $L^{2}(V,\mu_{\frakm})$.

The space $\calR_{\mu}$ plays a crucial role throughout this section. As a
closed subset of a Hilbert space, $\calR_{\mu}$ inherits a Hilbert space
structure under the $L^{2}(V,\mu_{\frakm})$-norm. Our goal is to extend
$\calK$ to an operator $\calC:\calR_{\mu}\to V$, where the image
$H_{\mu}=\calC(\calR_{\mu})$ will be defined as the Cameron-Martin space of
$\mu$. Furthermore, $\calK$ will be a symmetric compact operator and an
isometry between these two spaces. This is what in the sequel will allow us to
consider empirical measures of a sample, which by definition will give rise to
finite-rank, and in particular non-injective, covariance operators.

######  Proposition 2.12.

The covariance operator $\calK:V^{*}\to V$ extends to a linear operator
$\calC:\calR_{\mu}\to V$, where $\calR_{\mu}$ is the
$L^{2}(V,\mu_{\frakm})$-closure of $i^{*}(V^{*})$, via the limit

$\displaystyle\calC k$ $\displaystyle:=\lim_{n\to\infty}\calK
f_{n}=\int_{V}xk(x)d\mu_{\frakm}(x),$

where $(i^{*}f_{n})_{n=1}^{\infty}$ is any sequence converging to
$k\in\calR_{\mu}\subset L^{2}(V,\mu_{\frakm})$.

######  Remark 2.13.

Note that $\calC i^{*}f=\calK f$ for all $f\in V^{*}$.

Proof  Let $k\in\calR_{\mu}$. Since $i^{*}(V^{*})$ is dense in $\calR_{\mu}$,
there exists a sequence $f_{n}\in V^{*}$ such that
$\|i^{*}f_{n}-k\|_{L^{2}(V,\mu_{\frakm})}\to 0$ as $n\to\infty$. By Hölders
inequality we have that

$\displaystyle\bigg{\|}\calK f_{n}-\int_{V}xk(x)d\mu_{\frakm}(x)\bigg{\|}$
$\displaystyle\leq\int_{V}\|x\|\big{|}(k-f_{n})(x)\big{|}d\mu_{\frakm}(x)$
$\displaystyle=\bigg{(}\int_{V}\|x\|^{2}d\mu_{\frakm}(x)\bigg{)}^{\frac{1}{2}}\bigg{(}\int_{V}\big{|}(k-f_{n})(x)\big{|}^{2}d\mu_{\frakm}(x)\bigg{)}^{\frac{1}{2}},$

which goes to 0 as $n\to\infty$. This holds for any such sequence.

We can now define the Cameron-Martin space of a general (possibly non-
Gaussian) measure $\mu$. The Cameron-Martin space will be a Hilbert space
isometrically isomorphic to $\calR_{\mu}$, whose norm will naturally be given
by the covariance-adjusted distance through the extended covariance operator.

######  Definition 2.14.

Let $V$ be a Banach space, and let $\mu\in\calM_{V}$ with extended covariance
operator $\calC:\calR_{\mu}\to V$. We define the Cameron-Martin space
$H_{\mu}$ of $\mu$ to be the set $H_{\mu}:=\calC(R_{\mu})$.

######  Proposition 2.15.

The operator $\calC:\calR_{\mu}\to H_{\mu}$ is invertible. Hence $H_{\mu}$ is
a Hilbert space under the norm

$\displaystyle\|h\|_{H_{\mu}}$
$\displaystyle:=\|\calC^{-1}h\|_{L^{2}(V,\mu_{\frakm})},$
$\displaystyle\langle h,l\rangle_{H_{\mu}}$
$\displaystyle:=\big{\langle}\calC^{-1}h,\calC^{-1}l\big{\rangle}_{L^{2}(V,\mu_{\frakm})},$

where $h,l\in H_{\mu}$. The spaces $H_{\mu}$ and $\calR_{\mu}$ are
isometrically isomorphic via the map $\calC$.

Proof  We need to prove that $\calC$ is injective. To this end, assume that
$\calC k=0$ for some $k\in\calR_{\mu}$. By definition there exists a sequence
$f_{n}\in V^{*}$ such that $i^{*}f_{n}\to k$ in $\calR_{\mu}$. Lemma 2.6 then
implies that

$\displaystyle 0=\lim_{n}g\big{(}\calK f_{n}\big{)}=\lim_{n}\langle
i^{*}g,i^{*}f_{n}\rangle_{L^{2}(V,\mu_{\frakm})}=\langle
i^{*}g,k\rangle_{L^{2}(V,\mu_{\frakm})}$

for all $g\in V^{*}$. By continuity we obtain that $\langle
g,k\rangle_{L^{2}(V,\mu_{\frakm})}=0$ for all $g\in\calR_{\mu}$. Consequently
we find that $k=0$ ($\mu_{\frakm}$-a.e.), which shows that
$\calC:\calR_{\mu}\to H$ is injective. The latter statement of the Theorem
follows from the Hilbert space structure of $\calR_{\mu}\subset
L^{2}(V,\mu_{\frakm})$ and the linearity of $\calC$.

The following fundamental theorem shows that $\|\cdot\|_{\mu\text{-cov}}$ is a
genuine norm on a subspace of $V$, and infinite otherwise. More precisely,
this subspace is the Cameron-Martin space $H_{\mu}\subset V$, and the
$\mu$-variance norm coincides with the Cameron-Martin Hilbert norm when
restricted to this space. We begin by formally defining the $\mu$-variance
norm.

######  Definition 2.16.

Let $\mu\in\calM_{V}$ for a Banach space $V$. The $\mu$-variance norm for
$x\in V$ is defined as

$\|x\|_{\mu\text{-cov}}:=\sup_{f\in V^{*},\,q(f,f)\leq 1}f(x).$

######  Theorem 2.17.

Suppose that $\mu\in\calM_{V}$ for a Banach space $V$. Then the Cameron-Martin
space of $\mu$ is characterized by

$\displaystyle H_{\mu}=\\{h\in V:\|h\|_{\mu\text{-cov}}<\infty\\}.$

Furthermore, the Cameron-Martin norm $\|\cdot\|_{H_{\mu}}$ and the variance
norm $\|\cdot\|_{\mu\text{-cov}}$ coincide on $H_{\mu}$, or in other words

$\displaystyle\|h\|_{H_{\mu}}:=\|\calC^{-1}h\|_{L^{2}(V,\mu_{\frakm})}=\sup_{f\in
V^{*},\,q(f,f)\leq 1}f(h)=:\|h\|_{\mu\text{-cov}}$

for all $h\in H_{\mu}$.

Proof  Suppose that $h=\calC k$ for some $k\in\calR_{\mu}$. We want to show
that the variance norm $\|h\|_{\mu\text{-cov}}$ is finite and equal to
$\|h\|_{H_{\mu}}$. To this end, observe that

$\displaystyle\|h\|_{\mu\text{-cov}}$ $\displaystyle=\sup_{f\in
V^{*},\,q(f,f)\leq 1}f(\calC k)$ $\displaystyle=\sup_{f\in V^{*},\,q(f,f)\leq
1}\langle i^{*}f,k\rangle_{L^{2}(V,\mu_{\frakm})}$
$\displaystyle=\sup_{l\in\calR_{\mu},\,\|l\|_{L_{2}}\leq 1}\langle
l,k\rangle_{L^{2}(V,\mu_{\frakm})}$
$\displaystyle=\|\calC^{-1}h\|_{L^{2}(V,\mu_{\frakm})},$

where the third equality follows by the fact that $i^{*}(V^{*})$ is dense in
$\calR_{\mu}$.

Conversely, assume that $\|x\|_{\mu\text{-cov}}<\infty$ for some $x\in V$. Let
$T_{x}:V^{*}\to\bbR$ denote the evaluation functional $T_{x}g=g(x)$. For $g\in
V^{*}$ we have the bound

$\displaystyle|T_{x}g|$
$\displaystyle=|g(x)|\leq\|i^{*}g\|_{L^{2}(V,\mu_{\frakm})}\sup_{f\in
V^{*},\,q(f,f)\leq 1}f(x),$

hence $T_{x}$ extends to a linear operator $\calT_{x}:\calR_{\mu}\to\bbR$ by
continuity. More specifically, $\calT_{x}k$ for $k\in\calR_{\mu}$ can be
defined via $\calT_{x}k:=\lim_{n}T_{x}f^{(n)}=\lim_{n}f^{(n)}(x)$ where
$f^{(n)}\in V^{*}$ is any sequence such that
$\|k-i^{*}f^{(n)}\|_{L^{2}(V,\mu_{\frakm})}\to 0$. The operator norm for a
general bounded operator $\calT\in\calR_{\mu}^{*}$ is given by

$\displaystyle\|\calT\|_{\calR^{*}}$
$\displaystyle:=\sup_{k\in\calR_{\mu},\,\|k\|_{L^{2}(V,\mu_{\frakm})}\leq
1}\calT k$ $\displaystyle=\sup_{f\in V^{*},\,q(f,f)\leq 1}\calT i^{*}f,$

where the last equality follows by the fact that $i^{*}(V^{*})$ is dense in
$\calR_{\mu}$. Restricting this to extended evaluation functionals $\calT_{x}$
we obtain that

$\displaystyle\|\calT_{x}\|_{\calR^{*}}$ $\displaystyle=\sup_{f\in
V^{*},\,q(f,f)\leq 1}f(x)=\|x\|_{\mu\text{-cov}}.$

Since $\calT_{x}\in\calR_{\mu}^{*}$ if and only if the operator norm is
finite, we may use the fact that $\calR_{\mu}$ is a Hilbert space to identify
$\calT_{x}$ with an element of $\calR_{\mu}$ itself, say $k_{x}$, such that
$\calT_{x}l=\langle l,k_{x}\rangle$ for all $l\in\calR_{\mu}$. If $f\in
V^{*}$, then

$\displaystyle f\big{(}\calC k_{x}-x\big{)}=\langle
k_{x},i^{*}f\rangle_{L^{2}(V,\mu_{\frakm})}-f(x)=f(x)-f(x)=0,$

and it follows by Hahn-Banach that $\calC k_{x}=h$. This concludes the proof.

######  Remark 2.18.

In the above theorem we proved that $h\in H_{\mu}$ if and only if the
evaluation functional $T_{h}$ extends to a continuous linear functional on
$\calR_{\mu}\subset L^{2}(V,\mu_{\frakm})$. This also proves that $H_{\mu}$ is
a reproducing kernel Hilbert space.

###  2.3 Hilbert space setting

We now specialize to the case where $V$ is a Hilbert space with inner product
$\langle\cdot,\cdot\rangle$. In this setting, we have that $V=V^{*}$, allowing
us to diagonalize the covariance operator $\calK:V\to V$ and express the
$\mu$-variance norm in terms of the eigenvalues of $\calK$, irrespective of
injectivity.

Recall from Lemma 2.6 that

$\langle g,\calK f\rangle=q(g,f)=q(f,g)=\langle f,\calK g\rangle$

for all $f,g\in V$. This, combined with Theorem 2.7 and the fact that $\langle
f,\calK f\rangle\geq 0$ for all $f\in V$, implies that $\calK$ is a symmetric,
positive, compact operator. Consequently, the spectral theorem [Lax14, Theorem
28.3] implies that there exists an orthonormal sequence of eigenvectors
$(e_{n})_{n=1}^{\infty}$ and corresponding non-negative eigenvalues
$(\lambda_{n})_{n=1}^{\infty}$ such that

$\calK f=\sum_{n=1}^{\infty}\lambda_{n}\langle f,e_{n}\rangle
e_{n},\quad\forall f\in V.$ (5)

Our ultimate goal is to derive an explicit computational formula for the
variance norm $\|\cdot\|_{H_{\mu}}$. To achieve this, we first need to
characterize the Cameron-Martin space $H_{\mu}$, as Theorem 2.17 states that
this is the subspace of $V$ where the variance norm is finite. Understanding
$H_{\mu}$ will also be crucial when we later consider empirical measures
constructed from observed data in Section 3.

######  Theorem 2.19.

Let $\mu\in\calM_{V}$ for a Hilbert space $V$, and let
$(e_{n})_{n=1}^{\infty}$ and $(\lambda_{n})_{n=1}^{\infty}$ be orthonormal
eigenvectors and eigenvalues that diagonalizes the covariance operator
$\calK:V\to V$. Then the Cameron-Martin space $H_{\mu}$ is given by

$\displaystyle H_{\mu}$ $\displaystyle=\bigg{\\{}h\in
V:\sum_{n=1,\,\lambda_{n}\neq 0}^{\infty}\frac{\langle
h,e_{n}\rangle^{2}}{\lambda_{n}}<\infty\text{ and }\bigg{(}\forall n\geq
1,\,\lambda_{n}=0\implies\langle h,e_{n}\rangle=0\bigg{)}\bigg{\\}}$
$\displaystyle=\calK^{\frac{1}{2}}(V),$

where $\calK^{\frac{1}{2}}$ is the square root operator of $\calK$. The
variance norm is given by

$\|h\|_{H_{\mu}}^{2}=\begin{cases}\|\calK^{-\frac{1}{2}}h\|^{2}=\sum_{n=1,\,\lambda_{n}\neq
0}^{\infty}\frac{\langle h,e_{n}\rangle^{2}}{\lambda_{n}}&\text{if
}h\in\calK^{\frac{1}{2}}(V),\\\ \infty&\text{otherwise,}\end{cases}$ (6)

for all $h\in V$.

Proof  Let $h\in H_{\mu}$, that is $h=\calC k=\lim_{n}\calK f^{(n)}$ for some
$k\in\calR_{\mu}$ and a sequence $i^{*}f^{(n)}\in i^{*}(V^{*})$ such that
$\|k-i^{*}f^{(n)}\|_{L^{2}(V,\mu_{\frakm})}\to 0$. Using the symmetry of
$\calK$ we obtain that

$\displaystyle\langle h,e_{j}\rangle=\lim_{n}\langle\calK
f^{(n)},e_{j}\rangle=\lim_{n}\langle f^{(n)},\lambda_{j}e_{j}\rangle$

for all $j\geq 1$, and hence $\langle h,e_{j}\rangle=0$ whenever
$\lambda_{j}=0$. Moreover, Lemma 2.6 implies that
$\|i^{*}f^{(n)}\|_{L^{2}(V,\mu_{\frakm})}=\|\calK^{\frac{1}{2}}f^{(n)}\|$ for
all $n\geq 1$, and consequently we find that

$\displaystyle\|h\|_{H_{\mu}}^{2}$
$\displaystyle=\|k\|^{2}_{L^{2}(V,\mu_{\frakm})}=\lim_{n}\|i^{*}f^{(n)}\|_{L^{2}(V,\mu_{\frakm})}^{2}=\lim_{n}\|\calK^{\frac{1}{2}}f^{(n)}\|^{2}$
$\displaystyle=\lim_{n}\sum_{j=1}^{\infty}\lambda_{j}\langle
f^{(n)},e_{j}\rangle^{2}\geq\sum_{j=1}^{\infty}\lim_{n}\lambda_{j}\langle
f^{(n)},e_{j}\rangle^{2}$ $\displaystyle=\sum_{j=1,\,\lambda_{j}\neq
0}^{\infty}\lim_{n}\frac{\langle\calK
f^{(n)},e_{j}\rangle^{2}}{\lambda_{j}}=\sum_{j=1,\,\lambda_{j}\neq
0}^{\infty}\frac{\langle h,e_{j}\rangle^{2}}{\lambda_{j}},$

where the inequality follows by Fatou’s lemma. This shows that
$h\in\calK^{\frac{1}{2}}(V)$ since $\|h\|_{H_{\mu}}^{2}<\infty$.

Conversely, let $h\in\calK^{\frac{1}{2}}(V)$. We want to show that $h=\calC k$
for some $k\in\calR_{\mu}$. We do this by defining the sequence

$\displaystyle f^{(n)}:=\sum_{j=1,\lambda_{j}\neq 0}^{n}\frac{\langle
h,e_{j}\rangle}{\lambda_{j}}e_{j},$

and noting that $\calK f^{(n)}=\sum_{j=1}^{n}\langle h,e_{j}\rangle e_{j}\to
h$ as $n\to\infty$. Furthermore, $i^{*}f^{(n)}$ converges in
$L^{2}(V,\mu_{\frakm})$ to some element $k\in R_{\mu}$ since we have the bound

$\displaystyle\|i^{*}f^{(n)}-i^{*}f^{(m)}\|_{L^{2}(V,\mu_{\frakm})}$
$\displaystyle=\sum_{j=n,\,\lambda_{j}\neq 0}^{m}\frac{\langle
h,e_{j}\rangle^{2}}{\lambda_{j}}\leq\sum_{j=n,\,\lambda_{j}\neq
0}^{\infty}\frac{\langle h,e_{j}\rangle^{2}}{\lambda_{j}}$

for all $n<m$. Consequently we obtain that $h=\calC k=\lim_{n}\calK(f^{(n)})$,
from which (6) follows by definition.

######  Remark 2.20.

Note that the expression for the variance norm is
$\|h\|_{H_{\mu}}=\sqrt{\langle
h,\calK^{-1}h\rangle}=\|\calK^{-\frac{1}{2}}h\|$, analogous to the finite
dimensional $\bbR^{d}$ case.

In the functional Mahalanobis distance literature, [BBC20] argues that the
naive Mahalanobis distance $\|\calK^{-\frac{1}{2}}h\|$ fails to be defined due
to the non-invertibility of the square root operator $\calK^{\frac{1}{2}}$ in
the $L^{2}[0,1]$ setting. However, when viewed through the lens of variance
norms and Cameron-Martin spaces as per Theorem 2.19, we can see how such a
notion can still be made precise despite the difficulties present in the
infinite dimensional and singular settings by allowing the anomaly distance to
be infinite if the covariance structure of the underlying distribution does
not match the new samples. This point of view was for instance taken in
[Sha+23] for their conformance score anomaly distance in the finite
dimensional setting.

###  2.4 Mahalanobis distance and conformance score

Having introduced the necessary theoretical background in the previous
subsections, we are now ready to define the Mahalanobis distance on any
general Banach space $V$. We claim that a natural definition of an anomaly
distance on $V$ is the $\mu$-variance norm of a new sample $x$ against the
mean $\frakm$, as outlined in the following definition:

######  Definition 2.21.

Let $\mu\in\calM_{V}$ for a Banach space $V$. We define the Mahalanobis
distance $d_{M}(x;\mu)$ of the element $x\in V$ with respect to the measure
$\mu$ to be

$d_{M}(x;\mu)=\|x-\frakm\|_{\mu\text{-cov}},$

where $\frakm$ is the mean of $\mu$.

Theorem 2.17 tells us that the Mahalanobis distance is finite for all $x$ such
that $x-\frakm\in H_{\mu}$, where $H_{\mu}$ is the Cameron-Martin space of
$\mu$. When $\mu$ is an empirical measure of the form
$\mu=\frac{1}{N}\sum_{i=1}^{N}\delta_{x_{i}}$, we will show in Section 3 that
the sample Mahalanobis distance $d(x;\mu^{N})$ is finite if and only if $x\in
span(x_{1},\cdots,x_{n})$, and infinite otherwise. This point of view has
previously not been addressed in the infinite-dimensional setting, likely due
to the restrictive assumption that the covariance operator $\calK$ must be
injective [BBC20]. Such an assumption excludes both the sample covariance
operator, which is of finite rank, and the case of a singular covariance
matrix.

The following examples demonstrate that our definition coincides with, and in
fact extends the Mahalanobis distance in $\bbR^{d}$ to random variables with
possibly degenerate covariance matrices $\Sigma$. Furthermore, the estimator
of the Mahalanobis distance will be given by the case where $\mu$ is the
empirical measure of the underlying data. Example 2.23 is equivalent to the
setting presented in [Sha+23].

######  Example 2.22 (Finite Dimensional Case).

Let $\mu$ be a measure on $\bbR^{d}$ with well-defined covariance matrix
$\Sigma=\E^{x\sim\mu}[(x-\frakm)(x-\frakm)^{T}]$ and mean
$\frakm=\E^{x\sim\mu}[x]$. We have that

$\displaystyle q(a,b)$ $\displaystyle=\E^{x\sim\mu}\bigg{[}\langle
a,x-\frakm\rangle\langle b,x-\frakm\rangle\bigg{]}$
$\displaystyle=\E^{x\sim\mu}\bigg{[}\sum_{i=1}^{n}\sum_{j=1}^{n}a_{i}b_{j}(x-\frakm)_{i}(x-\frakm)_{j}\bigg{]}$
$\displaystyle=\sum_{i=1}^{n}\sum_{j=1}^{n}a_{i}b_{j}\Sigma_{i,j}=\langle
a,\Sigma b\rangle=\langle\Sigma a,b\rangle=a^{T}\Sigma b$

for all $a,b\in\bbR^{d}$. Lemma 2.6 tells us that the covariance operator of
$\mu$ is simply $\Sigma$. Furthermore, Theorem 2.19 implies that the Cameron-
Martin space is given by $H_{\mu}=Im(\Sigma^{\frac{1}{2}})=Im(\Sigma)$. This,
together with Theorem 2.17, gives that the variance norm is given by

$\displaystyle\|x\|_{H_{\mu}}^{2}=\sup_{a\in\bbR^{d}}\frac{\langle
a,x\rangle^{2}}{a^{T}\Sigma a}=\begin{cases}x^{T}\Sigma^{-1}x&\text{if }x\in
Im(\Sigma),\\\ +\infty&\text{otherwise.}\end{cases}$

Note also that we can write
$x^{T}\Sigma^{-1}x=\langle\Sigma^{-\frac{1}{2}}x,\Sigma^{-\frac{1}{2}}x\rangle=|\Sigma^{-\frac{1}{2}}x|^{2}$.
Replacing the inverse with the pseudo-inverse amounts to calculating the
variance norm of the projection of $x$ onto $H_{\mu}$. The Mahalanobis
distance is then given by $\|x-\frakm\|_{H_{\mu}}$.

######  Example 2.23 (Empirical measure on $\bbR^{d}$).

Let $\mu=\frac{1}{n}\sum_{i=1}^{n}\delta_{x_{i}}$ be the empirical measure
associated with a corpus of $n$ observed data points
$\\{x_{1},\cdots,x_{n}\\}\subset\bbR^{d}$. Then

$\displaystyle\hat{\frakm}=\E^{x\sim\mu}[x]$

and

$\displaystyle\hat{\Sigma}=\E^{x\sim\mu}[(x-\hat{\frakm})(x-\hat{\frakm})^{T}]$

become the sample mean and empirical covariance matrix, and the Cameron-Martin
norm is given by

$\displaystyle\|x\|_{H_{\mu}}^{2}=\begin{cases}x^{T}\hat{\Sigma}^{-1}x&\text{if
}x\in Im(\hat{\Sigma}),\\\ +\infty&\text{otherwise.}\end{cases}$

If $\hat{\Sigma}$ is invertible, then the Cameron-Martin norm evaluated at the
point $x-\hat{\frakm}$ coincides with the classical Mahalanobis distance,
which is given by
$d_{M}(x;\mu)=(x-\hat{\frakm})^{T}\hat{\Sigma}^{-1}(x-\hat{\frakm})$. This
illustrates how $\|x-\hat{\frakm}\|_{H_{\mu}}$, when interpreted through the
Cameron-Martin norm, is the natural choice for a generalization of the
Mahalanobis distance to any Banach space $V$.

The Gaussian Cameron-Martin literature is rich in examples of Cameron-Martin
spaces and norms. A classical example is the Wiener measure on $C[0,1]$, the
space of continuous functions, where the Cameron-Martin space is given by the
space of absolutely continuous functions with square integrable derivative,
with corresponding Cameron-Martin norm

$\|h\|_{H_{\mu}}=\int_{0}^{1}|\dot{h}(t)|^{2}dt.$

More generally, there exist expressions for Cameron-Martin spaces and norms
for Gaussian measures on $C[0,1]$ in the case where the underlying Gaussian
process can be written as an integral with respect to Gaussian white noise. We
refer to [Lif12] for further details.

While the Mahalanobis distance is a widely used anomaly distance for anomaly
detection in the $\bbR^{d}$ setting, it may perform poorly when the underlying
data is not Gaussian. For non-Gaussian data, the mean element might be a poor
choice of reference point when calculating anomaly distances, and so the
$k$-nearest-neighbor (kNN) distance to the normal corpus points may serve as a
better alternative [HKF04, VF11, Sha+23]. This approach requires choosing a
metric for calculating the nearest-neighbours. In the finite dimensional
setting the Euclidean, Minkowski, Manhattan, or even the Mahalanobis distance
itself are commonly used.

[Sha+23] coined the term conformance score for the case when the Mahalanobis
distance is used in conjunction with the $1$-nearest-neighbour Mahalanobis
distance, see also [VF11]. We aim to generalize this notion to the general
setting of a Banach space $V$ and a law $\mu\in\calM_{V}$. Note that the
notion of variance norm in [Sha+23] is restricted to a finite sample only,
while our unified framework considers any law $\mu$.

######  Definition 2.24.

Let $\mu\in\calM_{V}$ for a Banach space $V$, and let
$\\{x_{1},\cdots,x_{N}\\}\subset V$ be a corpus of observed data. We define
the conformance score $d_{C}(x;\mu)$ of $x$ with respect to $\mu$ and the
corpus as

$d_{C}(x;\mu)=\min_{1\leq i\leq N}\|x-x_{i}\|_{\mu\text{-cov}}.$

In other words, the conformance score is the nearest-neighbour $\mu$-variance
distance to the corpus, and in particular is new for the infinite dimensional
setting covering laws $\mu$ not necessarily restricted to empirical measures.
Furthermore, while [Sha+23] do provide a definition of conformance score for
infinite dimensional $V$, the authors were only able to prove results and
derive computational formulas for the case when $V$ is finite dimensional,
since the infinite dimensional definition depends non-trivially on $V^{*}$.
Our framework presented in this paper overcomes this limitation. In Section 3,
we will derive formulas for how to compute variance norms in the general
infinite dimensional setting.

###  2.5 Finite-dimensional concentration inequalities

Despite the growing use of conformance scores for anomaly detection [Sha+23,
Arr+24], their probabilistic properties remain underdeveloped and unexplored.
To address this gap, we aim to provide concentration inequalities for the
conformance score in the finite-dimensional setting under the assumption that
the data is Gaussian. The closest previous work is [SP16], which studied the
finite sample properties of $k$-nearest-neighbour distances for an i.i.d.
sample with a fixed reference point, using independence and binomial
concentration. However, this approach is incompatible with our setting, as the
conformance score is a minimum over a dependent sample. Our goal is to derive
a test statistic for the conformance score at a given significance level,
analogous to Hotelling’s $T^{2}$ test for the classical Mahalanobis distance.

We will focus on the special case of Gaussian data, where the new sample is
assumed to be contained in the normal corpus. This approach is motivated by
the fact that the resulting random variable will be distributed according to
the Haar measure on the Stiefel manifold, or equivalently, as the first $d$
rows of a Haar-distributed random variable over the orthogonal group
$\bbO(n)$. The setting is as follows. Consider an i.i.d. sample
$X_{1},\cdots,X_{n}$ drawn from $N_{d}(0,\Sigma)$ where
$\Sigma\in\bbR^{d\times d}$ is non-singular. Let
$X^{T}=(X_{1}|\cdots|X_{n})\in\bbR^{d\times n}$ be the data matrix. We
approximate the nearest-neighbour Mahalanobis distance by assuming that the
data is mean-centered with known mean, and by including the new sample point
in the normal corpus, say $X_{1}$. We are interested in studying the
concentration properties of

$\displaystyle C(n,d)$ $\displaystyle:=\min_{2\leq i\leq
n}\|\sqrt{n}(X^{T}X)^{-\frac{1}{2}}(X_{1}-X_{i})\|$
$\displaystyle=\sqrt{n}\min_{2\leq i\leq n}\|U(e_{1}-e_{i})\|.$

Here $U:=(X^{T}X)^{-\frac{1}{2}}X^{T}$ is distributed according to the Haar
measure on the Stiefel manifold, and the $e_{i}$ are the standard unit basis
vectors in $\bbR^{n}$. It is important to note that $C(n,d)$ as defined above
is not the exact conformance score, but rather the ‘in-sample’ conformance
since $X_{1}$ is assumed to belong to the normal corpus when estimating the
covariance matrix. This approach simplifies our analysis while still providing
valuable insights into the behaviour of the conformance scores. Notably, this
formulation allows for the use of classical results of random matrix theory on
the Stiefel manifold.

######  Definition 2.25.

Let $d\leq n$ be natural numbers. The Stiefel manifold $\calS_{d,n}$ is the
subset of $d\times n$ matrices defined by $\calS_{d,n}:=\\{P\in\bbR^{d\times
n}:PP^{T}=I_{d}\\}$ with the subspace topology inherited from the normed space
$\bbR^{d\times n}$ and

$\displaystyle\|P\|_{HS}:=\sqrt{tr(PP^{T})}.$

We let $\mu_{d,n}$ denote the Haar measure on $\calS_{d,n}$, and $\mu_{n}$ the
Haar measure on $\bbO(n)$.

If $n=d$ then $\calS_{d,n}=\bbO(n)$ coincides with the orthogonal group. In
this case we have that $\mu_{d,n}=\mu_{n}$. If $W$ is a random variable with
distribution $\mu_{n}$, then the $\calS_{d,n}$-valued random variable obtained
by taking the first $d$ rows of $W$ has distribution $\mu_{d,n}$.

Recall that $X^{T}=(X_{1}|\cdots|X_{n})\in\bbR^{d\times n}$ is the data matrix
of the sample. Thus, $U:=(X^{T}X)^{-\frac{1}{2}}X^{T}\in\calS_{d,n}$
represents the first $d$ rows of a Haar random matrix $W\in\bbO(n)$. Write

$\displaystyle W=(W_{1}|\cdots|W_{n})=\big{(}\begin{smallmatrix}U_{1}\\\
V_{1}\end{smallmatrix}|\cdots|\begin{smallmatrix}U_{n}\\\
V_{n}\end{smallmatrix}\big{)}$

and note that $\|W_{i}-W_{j}\|^{2}=2$ for $i\neq j$. Consequently, we see that
the minimum of $\mu_{d,n}$-distributed random variables can equivalently be
written as a maximum over $\mu_{n-d,n}$-distributed random variables:

$\displaystyle\min_{2\leq i\leq n}\|U_{1}-U_{i}\|^{2}=2-\max_{2\leq i\leq
n}\|V_{1}-V_{i}\|^{2}.$

Our goal is to study the concentration properties of the conformance score
from the perspective of concentration of measure results of Lipschitz
functions on the Stiefel manifold. The analysis relies on the following
classical concentration of measure result on the Stiefel manifold, see e.g.
[Led01, p. 27] for a standard reference.

######  Theorem 2.26.

If $f:\calS_{d,n}\to\bbR$ is $L$-Lipschitz with respect to $\|\cdot\|_{HS}$,
with mean $m_{f}:=\int fd\mu_{d,n}$, then

$\displaystyle\mu_{d,n}(m_{f}-f\geq t)\leq e^{-\frac{(n-1)t^{2}}{8L^{2}}}$

for all $t>0$.

We are interested in the following Lipschitz functions, defined on the Stiefel
manifold.

######  Lemma 2.27.

Let $k\leq n$ and let $f:\calS_{k,n}\to\bbR$ be the function

$\displaystyle f:(V_{1}|\cdots|V_{n})\mapsto\max_{2\leq i\leq
n}\|V_{1}-V_{i}\|.$

Then $f$ and $f^{2}$ are $\sqrt{2}$ and $4$-Lipschitz w.r.t $\|\cdot\|_{HS}$,
respectively.

Proof  Let $A=(A_{1}|\cdots|A_{n})\in\calS_{k,n}$ and
$B=(B_{1}|\cdots|B_{n})\in\calS_{k,n}$. Then

$\displaystyle\big{|}f(A)-f(B)\big{|}$ $\displaystyle=\bigg{|}\max_{2\leq
i\leq n}\|A_{1}-A_{i}\|-\max_{2\leq i\leq n}\|B_{1}-B_{i}\|\bigg{|}$
$\displaystyle\leq\max_{2\leq i\leq n}\|A_{1}-B_{1}+A_{i}-B_{i}\|$
$\displaystyle\leq\sqrt{2}\|A-B\|_{op}\leq\sqrt{2}\|A-B\|_{HS},$

where $\|\cdot\|_{op}$ is the operator norm. Similarly, for $f^{2}$ we find
that

$\displaystyle\big{|}f(A)^{2}-f(B)^{2}\big{|}$
$\displaystyle=\big{|}f(A)-f(B)\big{|}\big{|}f(A)+f(B)\big{|}$
$\displaystyle\leq 2\sqrt{2}\big{|}f(A)-f(B)\big{|}$ $\displaystyle\leq
4\|A-B\|_{HS},$

where we used the fact that $\|A_{1}-A_{i}\|=\sqrt{2}$ for all $2\leq i\leq
n$.

By applying Theorem 2.26 to the Lipschitz function $f^{2}$ in Lemma 2.27 we
obtain that

$\displaystyle P\big{(}C(n,d)^{2}<c^{2}\big{)}$
$\displaystyle=P\big{(}\min_{2\leq i\leq n}n\|U_{1}-U_{i}\|^{2}<c^{2}\big{)}$
$\displaystyle=P\big{(}2-\max_{2\leq i\leq
n}\|V_{1}-V_{i}\|^{2}<\frac{c^{2}}{n}\big{)}$
$\displaystyle=P\big{(}m_{f^{2}}-\max_{2\leq i\leq
n}\|V_{1}-V_{i}\|^{2}<m_{f^{2}}-(2-\frac{c^{2}}{n})\big{)}$ $\displaystyle\geq
1-e^{-\frac{(n-1)}{128}(m_{f^{2}}-2+\frac{c^{2}}{n})^{2}}$ (7)

for all $c$ such that $2-\frac{c^{2}}{n}<m_{f^{2}}$. For a given
$\alpha\in(0,1)$, we can set (2.5) equal to $1-\alpha$ to obtain a test
statistic at the significance level $\alpha$. Similar analysis can be done
using $f$ and $m_{f}$ instead of $f^{2}$ and $m_{f^{2}}$.

######  Example 2.28.

A simple lower bound on the mean $m_{f^{2}}$ reads

$\displaystyle m_{f^{2}}$ $\displaystyle=\E[\max_{2\leq i\leq
n}\|V_{1}-V_{i}\|^{2}]\geq\E[\|V_{1}-V_{i}\|^{2}]=2\frac{n-d}{n}=:l(n,d),$ (8)

which is obtained from the identity
$W=(W_{1}|\cdots|W_{n})=\big{(}\begin{smallmatrix}U_{1}\\\
V_{1}\end{smallmatrix}|\cdots|\begin{smallmatrix}U_{n}\\\
V_{n}\end{smallmatrix}\big{)}\in\bbO(n)$. As a simple application of (2.5), we
can use the lower bound $l(n,d)$ in (8) to obtain the following test
statistic: To choose a valid $c$ we need to use the lower bound on
$m_{f^{2}}$, and to bound the actual probability involving the term
$2-\frac{c^{2}}{n}-m_{f^{2}}$ we must again use the lower bound. To this end,
let $0<\varepsilon\leq 1$ be a free variable controlling the threshold. We
choose $c^{2}$ via

$\displaystyle 2-\frac{c^{2}}{n}=(1-\varepsilon)l(n,d)\iff
c^{2}=2d+2\varepsilon(n-d).$

The term $m_{f^{2}}-2+\frac{c^{2}}{n}$ can then be bounded by

$\displaystyle m_{f}-2+\frac{c^{2}}{n}$
$\displaystyle=m_{f}-(1-\varepsilon)l(n,d)$ $\displaystyle\geq\varepsilon
l(n,d)=2\varepsilon\frac{n-d}{n}.$

The concentration of measure result then reads

$\displaystyle P\bigg{(}Conf(n,d)^{2}<(1-\varepsilon)2d+\varepsilon
2n\bigg{)}$ $\displaystyle\geq
1-e^{-\frac{(n-1)}{128}(m_{f}-2+\frac{c^{2}}{n})^{2}}$
$\displaystyle=1-e^{-\frac{\varepsilon^{2}(n-d)^{2}}{n32}\frac{n-1}{n}}.$

A test statistic is obtained by equating the RHS to $1-\alpha$ for some
significance level $\alpha$, which will determine $\varepsilon$. The lower
bound (8) that we used is not sharp, and to obtain an informative test
statistic a sharper bound is most likely required. A sharper bound could for
instance be achieved by comparing the spherical expectation $m_{f^{2}}$ with a
corresponding Gaussian expectation using spherical coordinates. However,
obtaining such a bound for the maximum is highly nontrivial since it involves
an expectation of a maximum of dependent Erlang or chi-squared distributions.
We leave this to future work.

###  2.6 Regularized variance norms

A classical result from Cameron-Martin theory states that $\mu(H_{\mu})=0$
whenever $\mu$ is a Gaussian measure and $\dim(H_{\mu})=\infty$, see e.g.
[Hai23, Proposition 4.45]. This implies that the sample outcomes of a
$V$-valued random variable will almost surely not lie in the Cameron-Martin
space $H_{\mu}$, making the variance norm infinite with probability one. This
issue was addressed in the functional data analysis literature for
$V=L^{2}[0,1]$ under the assumptions of a continuous covariance function and
an injective covariance operator [BBC20]. Using our unified framework based on
$\mu$-variance norms, we extend these results to the general Hilbert setting
without requiring continuity of the underlying stochastic process or
injectivity of the covariance operator.

Let $V$ be a Hilbert space. Recall by Theorem 2.19 that the $\mu$-variance
norm of $x\in V$ is given by $\|x\|_{H_{\mu}}=\|\calK^{-\frac{1}{2}}x\|$ if
$x\in Im(\calK^{\frac{1}{2}})$, and infinity otherwise. One natural way to
extend this to a finite semi-norm defined on all of $V$, is to replace the
inverse $\calK^{-\frac{1}{2}}$ with the Tikhonov regularized operator
$R_{\alpha}=(\calK+\alpha I)^{-1}\calK^{\frac{1}{2}}$ with smoothing parameter
$\alpha$. Tikhonov regularization is a classical tool used in statistic (e.g.
ridge regression) and functional analysis to deal with ill-posed equations,
see e.g. [Kre13]. In contrast to the inverse $\calK^{-\frac{1}{2}}$, the
Tikhonov operator $R_{\alpha}$ is defined on all of $V$ and is an
approximation of the pseudo-inverse of $\calK^{\frac{1}{2}}$.

######  Definition 2.29.

Let $V$ be a Hilbert space, and let $\mu\in\calM_{V}$. We define the Tikhonov
regularized $\mu$-variance norm with smoothing parameter $\alpha>0$ as

$\|x_{\alpha}\|_{\mu\text{-cov}}:=\big{\|}(\calK+\alpha
I)^{-1}\calK^{\frac{1}{2}}x\big{\|}$ (9)

for $x\in V$, where $\calK$ is the covariance operator of $\mu$.

We will sometimes refer to (9) as the $\alpha$-regularized variance norm.
Since $\calK$ is a positive symmetric compact operator, it can be diagonalized
by some orthonormal sequence of eigenvectors $(e_{n})_{n=1}^{\infty}$ with
non-negative eigenvalues $(\lambda_{n})_{n=1}^{\infty}$. Furthermore, we have
that $(\calK+\alpha
I)^{-1}\calK^{\frac{1}{2}}x=\sum_{n=1}^{\infty}\frac{\sqrt{\lambda_{n}}}{\lambda_{n}+\alpha}\langle
e_{n},x\rangle e_{n}$ for all $x\in V$, and hence the $\alpha$-regularized
variance norm $\|x_{\alpha}\|_{\mu\text{-cov}}$ can be computed via Parseval’s
identity, as summarized below.

######  Proposition 2.30.

Let $V$ be a Hilbert space, and let $\mu\in\calM_{V}$. The
$\alpha$-regularized $\mu$-variance norm is given by

$\|x_{\alpha}\|^{2}_{\mu\text{-cov}}=\sum_{n=1}^{\infty}\frac{\lambda_{n}}{(\lambda_{n}+\alpha)^{2}}\langle
e_{n},x\rangle$

for all $x\in V$.

An equivalent approach to the above, and what will motivate the notation
$x_{\alpha}$ in (9), was first considered in [BBC20] in the special case
$V=L^{2}[0,1]$. We will now present an equivalent construction in our general
setting without the assumption of injectivity on the covariance operator: The
idea is to approximate each $x\in V$ via an element $x_{\alpha}\in H_{\mu}$
where $\alpha$ is a smoothing parameter, and then take the $\mu$-variance norm
of $x_{\alpha}$ which always will be finite since $x_{\alpha}\in H_{\mu}$ by
construction. Since no closest element in $H_{\mu}$ to $x$ exists in the
infinite dimensional case (since $H_{\mu}$ might not closed), $x_{\alpha}$ is
chosen by minimizing

$\displaystyle x_{\alpha}$ $\displaystyle:=\argmin_{h\in
H_{\mu}}\|x-h\|^{2}+\alpha\|h\|^{2}_{H_{\mu}}.$ (10)

Since $H_{\mu}$ is a reproducing kernel Hilbert space as discussed in the
remark proceeding Theorem 2.17, it follows from [CZ07, Theorem 8.4] that the
unique solution $x_{\alpha}$ to (10) is given by

$\displaystyle x_{\alpha}=(\calK+\alpha I)^{-1}\calK
x=\sum_{n=1}^{\infty}\frac{\lambda_{n}}{\lambda_{n}+\alpha}\langle
e_{n},x\rangle e_{n},$

where the second equality is due to diagonalization of $\calK$, analogous to
the Tikhonov case. Moreover, we have that the $\mu$-variance norm of
$x_{\alpha}$ is

$\|x_{\alpha}\|_{\mu\text{-cov}}=\|\calK^{\frac{1}{2}}x_{\alpha}\|_{V}=\|(\calK+\alpha
I)^{-1}\calK^{\frac{1}{2}}x\|,$

and hence this approach coincides with Tikhonov perspective in Definition 2.29
in our generalized setting.

Now that we know that the regularized variance norm $\|x_{\alpha}\|$ is finite
for all $x\in V$, we may proceed analogously as in [BBC20] and find the
distribution of the Mahalanobis distance in the Gaussian setting, but without
assumptions on the continuity of the stochastic process or injectivity of the
covariance operator. We do this by using results from the classical theory of
Gaussian measures on Banach spaces, as well as our own intermediate result
presented in Proposition 2.32.

######  Theorem 2.31.

Let $\mu$ be a Gaussian measure on a Hilbert space $V$, and let $\alpha>0$. If
$x\sim\mu$ is drawn from the measure $\mu$, then the squared
$\alpha$-regularized Mahalanobis distance has distribution

$\|(x-\frakm)_{\alpha}\|^{2}\stackrel{{\scriptstyle
d}}{{=}}\sum_{n=1}^{\infty}\bigg{(}\frac{\lambda_{n}}{\lambda_{n}+\alpha}\bigg{)}^{2}Y_{n},$

where $\frakm$ is the mean of $\mu$, $\lambda_{n}$ are the eigenvalues of the
covariance operator $\calK$ of $\mu$, and $Y_{1},Y_{2},\cdots$ is a sequence
of i.i.d. standard $\chi^{2}_{1}$ random variables.

Proof  Let $(e_{n})_{n=1}^{\infty}$ be an orthonormal sequence of eigenvectors
of $\calK$. It follows by Proposition 2.30 that

$\|(x-\frakm)_{\alpha}\|^{2}=\sum_{n=1}^{\infty}\frac{\lambda_{n}}{(\lambda_{n}+\alpha)^{2}}\langle
e_{n},x-\frakm\rangle^{2}.$

Since $\mu$ is a Gaussian measure, the vectors $e_{n}$ are by definition
Gaussian distributed when acting as continuous linear functionals on $V$.
Moreover, we have that

$\displaystyle\E^{\mu}\big{[}\langle e_{n},x-\frakm\rangle\langle
e_{m},x-\frakm\rangle\big{]}=\langle e_{n}\calK
e_{m}\rangle=\begin{cases}\lambda_{n}&\text{if }n=m,\\\
0&\text{otherwise},\end{cases}$

and

$\displaystyle\E^{\mu}\big{[}\langle e_{n},x-\frakm\rangle\big{]}=\langle
e_{n},\E^{\mu}[x]\rangle-\langle e_{n},\frakm\rangle=0,$

from which the result follows.

In practice we will not know the exact form of the measure $\mu$, but rather
we will work with empirical measures
$\mu^{N}=\frac{1}{N}\sum_{i=1}^{N}\delta_{x_{i}}$ based on a finite sample
$\\{x_{1},\cdots,x_{N}\\}$ drawn from some unknown $\mu$. Hence it would be
useful to know that the sample variance norm
$\|x_{\alpha}\|_{\mu^{N}\text{-cov}}$ is a consistent estimator of the actual
variance norm $\|x_{\alpha}\|_{\mu\text{-cov}}$. Before we are able to prove
consistency in our generalized framework, we first need an intermediate result
deviating from the work in [BBC20] since their arguments for the case
$V=L^{2}[0,1]$ are special for the Hilbert-Schmidt covariance operator with
continuous covariance function.

######  Proposition 2.32.

Let $V$ be a separable Hilbert space, and let
$\mu^{N}=\frac{1}{N}\sum_{i=1}^{N}\delta_{x_{i}}$ be an empirical measure of
an i.i.d. sample drawn from $\mu\in\calM_{V}$. Then we have that

$\|\calK-\calK_{N}\|_{op}\to 0$

almost surely as $N\to\infty$, where $\calK$ and $\calK_{N}$ are the
covariance operators of $\mu$ and $\mu^{N}$ respectively, and $\|\cdot\|_{op}$
is the operator norm.

Proof  First, note that all covariance operators $\calK$ of some measure
$\mu\in\calM_{V}$ are of trace class since

$\displaystyle\text{Tr}(|\calK|)$
$\displaystyle=\sum_{n=1}^{\infty}\langle\calK
e_{n},e_{n}\rangle=\sum_{n=1}^{\infty}\int_{V}\langle
x,e_{n}\rangle^{2}d\mu_{\frakm}(x)$
$\displaystyle=\int_{V}\|x\|^{2}d\mu_{\frakm}(x)=\int_{V}\|x\|^{2}d\mu(x)-\|\frakm\|^{2}$
(11)

for any orthonormal basis $(e_{n})_{n=1}^{\infty}$. Furthermore, since the
empirical measure $\mu^{N}$ converges weakly to $\mu$ [Var58, Theorem 3], it
follows from (2.6) together with the strong law of large numbers that
$\text{Tr}(|\calK_{N}|)\to\text{Tr}(|\calK|)$ as $N\to\infty$ almost surely.
Similarly, for all $y,z\in V$ and all covariance operators $\calK$ we have
that

$\displaystyle\langle z,\calK y\rangle$ $\displaystyle=\int_{V}\langle
z,x\rangle\langle y,x\rangle d\mu(x)-\langle z,\frakm\rangle\langle
y,\frakm\rangle$

almost surely. Hence by weak convergence of measures and the strong law of
large numbers we obtain that $\langle x,\calK_{N}y\rangle\to\langle x,\calK
y\rangle$ almost surely, that is $\calK_{N}\to\calK$ in the weak operator
topology. Since we have convergence in both trace class and weak operator
topology, [Ara81, Theorem II] implies that $\|\calK-\calK_{N}\|_{op}\to 0$
almost surely.

The following theorem proves that the regularized $\mu$-variance norm can be
consistently estimated though the use of empirical measures, or equivalently
through the use of the empirical covariance operator. The convergence in
Theorem 2.33 can in fact be strengthened to uniform convergence on bounded
sets, using the same arguments outlined in the proof.

######  Theorem 2.33.

Let $V$ be a separable Hilbert space, and let
$\mu^{N}=\frac{1}{N}\sum_{i=1}^{N}\delta_{x_{i}}$ be an empirical measure of
an i.i.d. sample drawn from $\mu\in\calM_{V}$. Then the regularized
$\mu_{N}$-variance norm converges pointwise to the regularized $\mu$-variance
norm, or in other words

$\|x_{\alpha}\|_{{\mu^{N}\text{-cov}}}\to\|x_{\alpha}\|_{\mu\text{-cov}}$

almost surely as $N\to\infty$ for all $x\in V$ and all $\alpha>0$.

Proof  Fix $x\in V$ and $\alpha>0$. For brevity we write
$T^{\alpha}_{N}=(\calK_{N}+\alpha I)^{-1}$ and $T^{\alpha}=(\calK+\alpha
I)^{-1}$. By the reverse triangle inequality we obtain that

$\displaystyle\bigg{|}\|x_{\alpha}\|_{\mu_{N}}-\|x_{\alpha}\|_{\mu}\bigg{|}$
$\displaystyle=\bigg{|}\|T^{\alpha}_{N}\calK_{N}^{\frac{1}{2}}x\|-\|T^{\alpha}\calK^{\frac{1}{2}}x\|\bigg{|}$
$\displaystyle\leq\bigg{\|}T_{N}^{\alpha}\calK_{N}^{\frac{1}{2}}x-T^{\alpha}\calK^{\frac{1}{2}}x\bigg{\|}$
$\displaystyle\leq\|T_{N}^{\alpha}\|_{op}\|\calK_{N}^{\frac{1}{2}}x-\calK^{\frac{1}{2}}x\|+\|T_{N}^{\alpha}-T^{\alpha}\|_{op}\|\calK^{\frac{1}{2}}x\|.$
(12)

First note that $T^{\alpha}_{N}$ and $T^{\alpha}$ are bounded by
$\|T^{\alpha}_{N}\|_{op}\leq\frac{1}{\alpha}$. Proposition 2.32 implies that
$\|\calK_{N}-\calK\|_{op}\to 0$ almost surely, from which it follows that the
first term of (2.6) tends to $0$ as $N\to\infty$. The second term also tends
to $0$ as $N\to\infty$ by [GGK12, Corollary 8.3] since
$\calK-\calK_{N}=(\calK+\alpha I)-(\calK_{N}+\alpha I)$, which concludes the
proof.

###  2.7 Kernelized variance norms

In this section we introduce the concept of a kernelized variance norm in the
spirit of kernel learning using reproducing kernel Hilbert spaces (RKHS)
[CS01, Sch09]. We begin by recalling the basic definitions used in RKHS
theory.

######  Definition 2.34.

A positive definite (p.d.) $k$ on a set $\calX$ is defined as a symmetric
function $k:\calX\times\calX\to\bbR$ satisfying

$\sum_{i=1}^{N}\sum_{j=1}^{N}a_{i}a_{j}k(x_{i},x_{j})\geq 0$

for all $x_{1},\cdots x_{N}\in\calX$, all $a_{1},\cdots,a_{N}\in\bbR$ and all
integers $N\geq 1$.

######  Definition 2.35.

Let $\calX$ be a set, and let $\calH$ be a Hilbert space of functions of
$\calX$. A reproducing kernel is defined as a function
$k:\calX\times\calX\to\bbR$ satisfying

  1. (i)

$\forall x\in\calX,\,\,k(\cdot,x)\in\calH$,

  2. (ii)

$\forall x\in\calX,\,\,\forall
f\in\calH,\,\,f(x)=\big{\langle}f,k(\cdot,x)\big{\rangle}_{\calH}$.

Furthermore, $\calH$ is said to be a reproducing kernel Hilbert space (RKHS)
if there exists a reproducing kernel for $\calH$. This kernel is unique by
Riesz representation theorem.

All reproducing kernels are p.d. kernels. Moreover, the Moore-Aronszajn
theorem [Aro50] states that all p.d. kernels define a unique RKHS, with
reproducing kernel given by the p.d. kernel. From a machine learning
standpoint it may be advantageous to view RKHSs through the lens of feature
maps. A feature map is defined as a function $\phi:\calX\to\calF$ where
$\calF$ is a Hilbert space. Every feature map defines a unique p.d. kernel via
$k(x,y):=\langle\phi(x),\phi(y)\rangle_{\calF}$. Conversely, given a RKHS with
reproducing kernel $k$, the feature map $\phi(x):=k(\cdot,x)$ reproduces $k$
since $\langle\phi(x),\phi(y)\rangle_{\calH}=\langle
k(\cdot,x),k(\cdot,y)\rangle_{\calH}=k(x,y)$. Hence we may simply consider
feature maps in our subsequent analysis.

A kernelized variance norm can be constructed by lifting an initial measure
$\mu$ using a feature map $\phi$ via $\nu:=\mu\circ\phi^{-1}$, and then
calculating the $\nu$-variance norm on the RKHS corresponding to $\phi$. From
a machine learning standpoint we will mostly be interested in empirical
measures of the form $\mu=\frac{1}{N}\sum_{i=1}^{N}\delta_{x_{i}}$, hence we
may simple let the kernelized measure be
$\nu=\frac{1}{N}\sum_{i=1}^{N}\delta_{\phi(x_{i})}$.

As we will show in Section 3, the eigenvalues and eigenvectors of the
covariance operator of an empirical measure is uniquely determined by the
inner product Gram matrix of the data. This in turn uniquely determines the
variance norm by Theorem 2.19 and Proposition 2.30. Consequently we will be
able to use the kernel trick to avoid explicitly computing the (possibly
infinite dimensional) feature map, and thus computing the variance norm solely
through the use of kernel evaluations.

Note additionally that a RKHS need not necessarily be separable. It is for
this reason we defined the class of measures $\calM_{V}$ to be compatible with
the non-separable case, to be able to consider the kernelized setting in full
generality.

##  3 Computing Variance Norms

For most machine learning applications, the underlying probability measure
$\mu$ is not explicitly known, and we must base our models on finite samples
assumed to be drawn from $\mu$. A natural estimator of the underlying
distribution is the empirical measure
$\mu^{N}=\frac{1}{N}\sum_{i=1}^{N}\delta_{x_{i}}$, whose variance norm we
showed converges almost surely to the actual $\mu$-variance norm as per
Theorem 2.33. In this section, we derive computational formulas for the
variance norm with respect to $\mu^{N}$.

First, we consider the Hilbert case in Section 3.1, where the variance norm is
determined by the eigenvectors of the covariance operator of $\mu^{N}$ via
Theorem 2.19. These eigenvectors are obtained using an SVD decomposition of
the inner product Gram matrix of our data in $V$, or equivalently, via the
kernel Gram matrix when $V$ is an RKHS. Section 3.2 outlines the full
procedure for calculating the Mahalanobis distance and the nearest-neighbour
Mahalanobis distance. To conclude, we also derive expressions for
$\|x\|_{\mu^{N}\text{-cov}}$ in the general Banach case in Section 3.3,
extending the results of [Sha+23] to the infinite-dimensional setting.

###  3.1 Hilbert Case

By recognizing that the covariance operator $\calK$ is a finite rank operator
when $\mu=\frac{1}{N}\sum_{n=1}^{N}\delta_{x_{i}}$ is an empirical measure, we
can turn the problem of calculating the variance norm $\|h\|_{H_{\mu}}$ into a
finite-dimensional problem. This approach yields an explicit solution in terms
of the covariance operator’s eigenvalues and eigenvectors, as motivated by
Theorem 2.19.

######  Proposition 3.1.

Let $V$ be a Hilbert space, and let
$\mu=\frac{1}{N}\sum_{i=1}^{N}\delta_{x_{i}}$ be an empirical measure. Then
$\mu\in\calM_{V}$, and the covariance operator $\calK:V\to V$ of $\mu$ is
given by

$\displaystyle\calK
y=\frac{1}{N}\sum_{i=1}^{N}(x_{i}-\frakm)\big{\langle}y,x_{i}-\frakm\big{\rangle}$

for $y\in V$, and the Cameron-Martin space $H_{\mu}$ is

$\displaystyle H_{\mu}$
$\displaystyle=span\\{x_{1}-\frakm,\cdots,x_{N}-\frakm\\}=span\\{e_{1},\cdots,e_{M}\\},$

where $\frakm=\frac{1}{N}\sum_{i=1}^{N}x_{i}$ is the empirical mean of the
data, and $e_{1},\cdots,e_{M}$ are the eigenvectors of $\calK$ with positive
eigenvalues.

Proof  The expression for the covariance operator $\calK$ follows directly
from the Bochner integral representation in Definition 2.4. Theorem 2.19 says
that the Cameron-Martin space is given by $H_{\mu}=\calK^{\frac{1}{2}}(V)$,
and the result follows since $\calK$ is a finite rank operator.

######  Corollary 3.2.

Let $V$ be a Hilbert space, and let
$\mu=\frac{1}{N}\sum_{i=1}^{N}\delta_{x_{i}}$ be an empirical measure. If
$(e_{m})_{m=1}^{M}$ is an orthonormal set of all the eigenvectors of $\calK$
possessing positive eigenvalues $(\lambda_{m})_{m=1}^{M}$, then the variance
norm of $\mu$ is given by

$\displaystyle\|h\|_{\mu\text{-cov}}^{2}=\sum_{m=1}^{M}\frac{\langle
h,e_{m}\rangle^{2}}{\lambda_{m}}$

for $h\in H_{\mu}=Im(\calK)$, and $+\infty$ otherwise.

Proof  The result follows directly from Theorem 2.19 and Proposition 3.1.

The following theorem presents an algorithm for computing the eigenvalues and
eigenvectors of the empirical covariance operator, based on an SVD
decomposition of the inner product Gram matrix. This concept is closely
related to the techniques used for kernel PCA [SSM98]. We however give our own
original proof, and relate the results back to the Cameron-Martin space of the
empirical measure.

######  Theorem 3.3.

Let $V$ be a Hilbert space, and let
$\mu=\frac{1}{N}\sum_{i=1}^{N}\delta_{x_{i}}$ be an empirical measure. Let
$A\in\bbR^{N\times N}$ be defined by $A_{i,j}=\langle f_{i},f_{j}\rangle$,
where $f_{i}=\frac{x_{i}-\frakm}{\sqrt{N}}$, with SVD decomposition $A=U\Sigma
U^{T}$. Let $v^{(n)}$ be the $n$-th column of $U$, and
$\lambda_{n}=\Sigma_{n,n}$. Define $M=\max\\{m\leq N:\lambda_{m}>0\\}$. Then
the elements defined by

$\displaystyle e_{n}=\sum_{i=1}^{N}v^{(n)}_{i}f_{i},$ (13)

are orthogonal eigenvectors of $\calK$ with corresponding eigenvalue
$\lambda_{n}$ for $n\leq M$, and $e_{n}=0$ for $M<n\leq N$. Moreover, we have
that $span\\{e_{1},\cdots,e_{M}\\}=H_{\mu}$.

Proof  To prove that $e_{m}$ is an eigenvector of $\calK$ with eigenvalue
$\lambda_{m}$ for $m\in\\{1,\cdots,M\\}$, observe that

$\displaystyle\calK\bigg{(}\sum_{i=1}^{N}v_{i}^{(m)}f_{i}\bigg{)}$
$\displaystyle=\sum_{j=1}^{N}f_{j}\bigg{\langle}\sum_{i=1}^{N}v_{i}^{(m)}f_{i},f_{j}\bigg{\rangle}$
$\displaystyle=\sum_{j=1}^{N}f_{j}\sum_{i=1}^{N}v_{i}^{(m)}\langle
f_{i},f_{j}\rangle$ $\displaystyle=\sum_{j=1}^{N}f_{j}\lambda_{m}v_{j}^{(m)},$

where we used that $\sum_{i=1}^{N}v_{i}^{(m)}\langle
f_{i},f_{j}\rangle=(Av^{(m)})_{j}=\lambda_{m}v^{(m)}_{j}$.

Next, we check that the vectors $\\{e_{1},...,e_{N}\\}$ are linearly
independent. We see that

$\displaystyle\langle e_{n},e_{m}\rangle$
$\displaystyle=\bigg{\langle}\sum_{i=1}^{N}v_{i}^{(m)}f_{i},\sum_{j=1}^{N}v_{j}^{(n)}f_{j}\bigg{\rangle}=\sum_{i=1}^{N}\sum_{j=1}^{N}v_{i}^{(m)}v_{j}^{(n)}\langle
f_{i},f_{j}\rangle$ $\displaystyle=\langle
v^{(n)},Av^{(m)}\rangle_{\bbR^{N}}=\lambda_{m}\langle
v^{(n)},v^{(m)}\rangle_{\bbR^{N}}$

for $n,m\in\\{1,\cdots,N\\}$. When $n\neq m$ we have that $\langle
v^{(n)},v^{(m)}\rangle_{\bbR^{N}}=0$, hence $\langle e_{n},e_{m}\rangle=0$.
For $1\leq m\leq M$ the element $e_{m}$ is non-zero since $\langle
e_{m},e_{m}\rangle=\lambda_{m}\langle v^{(m)},v^{(m)}\rangle_{\bbR^{N}}>0$. On
the other hand, if $M<n\leq N$ then $\lambda_{n}=0$, hence $\langle
e_{n},e_{n}\rangle=0$ and consequently $e_{n}=0$.

Finally, we want to use Proposition 3.1 to conclude that
$H_{\mu}=span\\{e_{1},\cdots,e_{M}\\}$. To this end, define
$f=(f_{1},\cdots,f_{N})$ and $e=(e_{1},\cdots,e_{N})$ as column vectors. Using
this notation, (13) can be written as $f=Ue\iff e=U^{T}f$, from which it
follows that
$span\\{f_{1},\cdots,f_{N}\\}=span\\{e_{1},\cdots,e_{N}\\}=span\\{e_{1},\cdots,e_{M}\\}$.
This concludes the proof.

The generality of Theorem 3.3, which only assumes $V$ is a Hilbert space,
allows us to extend its application to compute eigenvalues of a kernelized
covariance operator. Consider the setting where we have observations
$\\{x_{1},\cdots,x_{N}\\}\subset\calX$ where $\calX$ is any set, and a feature
map $\phi:\calX\to\calF$ where $\calF$ is a Hilbert space. By forming the
empirical measure $\mu=\frac{1}{N}\sum_{i=1}^{N}\delta_{\phi(x_{i})}$ on the
feature space, we can let our underlying space $V$ be the RKHS associated with
$\phi$. In this case, the inner product Gram matrix becomes the Gram matrix of
the reproducing kernel. This gives us an alternative theoretical foundation
for the kernelized Mahalanobis distance, first introduced in [RL01].
Furthermore, if a kernel trick is known for $\phi$, then we can avoid
expensive direct computations of $\phi$ when computing the kernelized variance
norm.

###  3.2 Algorithms

To handle the fact that the $\mu$-variance norm $\|x\|_{\mu\text{-cov}}$ is
only finite for vectors in the Cameron-Martin space $H_{\mu}$, we can consider
three alternative approaches:

  1. (i)

Use the Tikhonov $\alpha$-regularized variance norm as per Definition 2.29
which always is finite.

  2. (ii)

Project $x$ onto to the space $H_{\mu}$ before calculating the variance norm
of the projection. This is equivalent to using the Tikhonov formula with
$\alpha=0$, or in the finite dimensional $\bbR^{d}$ setting replacing the
inverse with the pseudo-inverse.

  3. (iii)

Define the anomaly distance as infinite if the distance from $x$ to $H_{\mu}$
exceeds a predetermined threshold. Otherwise, compute the distance using
either approach (ii) or (iii).

We will present our algorithms from the perspective of (i) and (ii) above, in
the setting using the kernelized variance norm, e.g. empirical measures of the
form $\mu=\frac{1}{N}\sum_{i=1}^{N}\delta_{\phi(x_{i})}$ with respect to data
$\\{x_{1},\cdots,x_{N}\\}\subset\calX$, where $\calX$ is any set, and
$\phi:\calX\to\calF$ is a feature map for some Hilbert space $\calF$. We can
without loss of generality consider algorithms for the variance norm in the
RKHS setting, since if we let $\calX=V$ be a Hilbert space, and $\phi=Id$ the
identity, then our original non-kernelized setting is recovered. In this
sense, the kernelized version serves as a strict generalization of the
standard Hilbert setting. We will sometimes refer to the non-kernelized
setting as the linear kernel case.

Due to possible non-linearities of the feature map, we might not be able to
directly compute the inner product of the normalized elements $\langle
f_{n},f_{m}\rangle$. We address this by expressing the inner products of the
scaled vectors $f_{i}$ as linear combinations of $\langle x_{n},x_{m}\rangle$.
Furthermore, since we are mapping the data into a possibly infinite
dimensional Hilbert space, we might not be able to store the eigenvectors in
memory. To overcome this, we instead directly compute the inner products of
our corpus elements with the eigenvectors of $\calK$ via the following: Let
$N$, $f_{i}$, $M$, $v_{i}^{(m)}$, $e_{m}$, and $\lambda_{m}$ be given as per
Theorem 3.3. Then by bilinearity of the inner product, we obtain that

$\displaystyle\langle f_{m},f_{n}\rangle=\frac{1}{N}\bigg{(}\langle
x_{m},x_{n}\rangle-\frac{1}{N}\sum_{j=1}^{N}\langle
x_{m},x_{j}\rangle-\frac{1}{N}\sum_{j=1}^{N}\langle
x_{n},x_{j}\rangle+\frac{1}{N^{2}}\sum_{j=1}^{N}\sum_{i=1}^{N}\langle
x_{i},x_{j}\rangle\bigg{)},$

and

$\displaystyle\langle\frac{e_{m}}{\sqrt{\lambda_{m}}},h\rangle=\sum_{i=1}^{N}\frac{v^{(m)}_{i}}{\sqrt{\lambda_{m}N}}\bigg{(}\langle
x_{i},h\rangle-\frac{1}{N}\sum_{j=1}^{N}\langle x_{j},h\rangle\bigg{)},$

for all $i\in\\{1,\cdots,N\\}$ and $m\in\\{1,\cdots,M\\}$.

Next, we present algorithms for computing the kernelized variance norm for the
empirical measure $\mu=\frac{1}{N}\sum_{i=1}^{N}\delta_{\phi(x_{i})}$ with
respect to a corpus $\\{\phi(x_{1}),\cdots,\phi(x_{N})\\}$, where $\phi$ is a
feature map corresponding to a reproducing kernel $k$, with known kernel
trick. Recall that the non-kernelized setting is recovered by setting
$\phi=Id$ to be the identity, or equivalently by using the linear kernel
$k(x,y)=\langle x,y\rangle$. The model fitting procedure is detailed in
Algorithm 1, which has time complexity $\calO(N^{2}(K+N))$ where $K$ is the
time complexity of a single kernel evaluation. Inference using the Mahalanobis
distance and conformance score anomaly distances is detailed by Algorithm 2
and Algorithm 3, respectively. The time complexity of both methods is
$\calO(N(K+M))$ where $M$ is the number of eigenvalues used in the
computation.

1

Input: Data $\\{x_{1},\cdots,x_{N}\\}$.

2

// Compute normalized Gram matrix via kernel trick

3

$B_{i,j}\leftarrow\big{\langle}\phi(x_{i}),\phi(x_{j})\big{\rangle}=k(x_{i},x_{j})$
for $i,j\in\\{1,\cdots,N\\}$

// $B_{i,j}=\langle\phi(x_{i}),\phi(x_{j})\rangle$

4

5Column mean $a_{i}\leftarrow\frac{1}{N}\sum_{j=1}^{N}B_{i,j}$ for
$i\in\\{1,\cdots,N\\}$

6Matrix mean $b\leftarrow\frac{1}{N}\sum_{i=1}^{N}a_{i}$

$A_{i,j}\leftarrow\frac{1}{N}(B_{i,j}-a_{i}-a_{j}+b)$ for
$i,j\in\\{1,\cdots,N\\}$

// $A_{i,j}=\langle f_{i},f_{j}\rangle$

7

// Compute inner products of eigenvectors and data

8 Compute SVD decomposition $U\Sigma U^{t}=A$

9Set $M\leftarrow\max\\{m\leq N:\Sigma_{m,m}>\lambda\\}$

10for  _$n=1$ to $N$_ do

11 for  _$m=1$ to $M$_ do

$E_{n,m}\leftarrow\sum_{i=1}^{N}\frac{U_{i,m}}{\sqrt{N\Sigma_{m,m}}}(B_{i,n}-a_{n})$

// $E_{n,m}=\langle e_{m},\phi(x_{n})\rangle$

12

13

Output: Matrix $E$, and SVD decomposition $A=U\Sigma U^{t}$.

Algorithm 1 Kernelized Gram matrix w.r.t.
$\mu=\frac{1}{N}\sum_{i=1}^{N}\delta_{\phi(x_{i})}$.

Input: Data $\\{x_{1},\cdots,x_{N}\\}$. SVD decomposition matrices
$U,\Sigma\in\bbR^{N\times N}$ and $E\in\bbR^{N\times M}$ as per Algorithm 1. A
new sample $y$.

1

// Compute inner product of eigenvectors and sample

2 Use kernel trick
$s_{i}\leftarrow\langle\phi(y),\phi(x_{i})\rangle=k(y,x_{i})$ for
$i\in\\{1,\cdots,N\\}$

3Average $r\leftarrow\frac{1}{N}\sum_{i=1}^{N}s_{i}$

$p_{m}\leftarrow\frac{1}{\sqrt{N\Sigma_{m,m}}}\sum_{i=1}^{N}U_{i,m}(s_{i}-r)$
for $m\in\\{1,\cdots,M\\}$

// $p_{m}=\big{\langle}e_{m},\phi(y)\big{\rangle}$

4

// Calculate Mahalanobis distance

Average $c_{m}\leftarrow\frac{1}{N}\sum_{i=1}^{N}E_{i,m}$ for
$m\in\\{1,\cdots,M\\}$

//
$c_{m}=\big{\langle}e_{m},\frac{1}{N}\sum_{n=1}^{N}\phi(x_{n})\big{\rangle}$

5

$d\leftarrow\sqrt{\sum_{m=1}^{M}\frac{(p_{m}-c_{m})^{2}}{\Sigma_{m,m}}}$

// $d=\|\phi(y)-\frac{1}{N}\sum_{n=1}^{N}\phi(x_{n})\|^{2}_{H_{\mu}}$

6

Output: Kernelized Mahalanobis distance $d_{M}(y;\mu)$.

Algorithm 2 Kernelized Mahalanobis distance w.r.t.
$\mu=\frac{1}{N}\sum_{i=1}^{N}\delta_{\phi(x_{i})}$.

Input: Data $\\{x_{1},\cdots,x_{N}\\}$. SVD decomposition matrices
$U,\Sigma\in\bbR^{N\times N}$ and $E\in\bbR^{N\times M}$ as per Algorithm 1. A
new sample $y$.

1

// Compute inner product of eigenvectors and sample

2 Use kernel trick
$s_{i}\leftarrow\langle\phi(y),\phi(x_{i})\rangle=k(y,x_{i})$ for
$i\in\\{1,\cdots,N\\}$

3Average $r\leftarrow\frac{1}{N}\sum_{i=1}^{N}s_{i}$

$p_{m}\leftarrow\frac{1}{\sqrt{N\Sigma_{m,m}}}\sum_{i=1}^{N}U_{i,m}(s_{i}-r)$
for $m\in\\{1,\cdots,M\\}$

// $p_{m}=\big{\langle}e_{m},\phi(y)\big{\rangle}$

4

// Calculate nearest-neighbour Mahalanobis distance

$d_{n}\leftarrow\sum_{m=1}^{M}\frac{(p_{m}-E_{n,m})^{2}}{\Sigma_{m,m}}$ for
$n\in\\{1,\cdots,N\\}$

// $d_{n}=\|\phi(y)-\phi(x_{n})\|^{2}_{H_{\mu}}$

5

6$c\leftarrow\sqrt{\min_{n}d_{n}}$

Output: Kernelized conformance score $c$.

Algorithm 3 Kernelized conformance score w.r.t.
$\mu=\frac{1}{N}\sum_{i=1}^{N}\delta_{\phi(x_{i})}$.

###  3.3 Banach case

In this section we prove a formula for the $\mu$-variance norm when the
underlying space $V$ is any general Banach space not necessarily a Hilbert
space, and $\mu$ is an empirical measure. [Sha+23] proved a similar theorem
for the case when $V$ is finite dimensional, for their non-measure-theoretic
definition of variance norms using elementary linear algebra. The difficulty
in the general infinite dimensional setting stems from the fact that the
variance norm depends non-trivially on all of $V^{*}$, which might be infinite
dimensional, despite the fact that the Cameron-Martin space $H_{\mu}$ is
finite dimensional.

######  Theorem 3.4.

Let $\mu=\frac{1}{N}\sum_{i=1}^{N}\delta_{x_{i}}$ be an empirical measure on a
Banach space $V$. Write $y_{i}:=x_{i}-\frakm$, $i\in\\{1,\cdots,N\\}$, for the
centered data, where $\frakm=\frac{1}{N}\sum_{i=1}^{N}x_{i}$ is the empirical
mean. Then the following statements hold:

  1. (i)

The Cameron-Martin space is given by $H_{\mu}=span\\{y_{1},\cdots,y_{N}\\}$.

  2. (ii)

Suppose that $\\{e_{1},\cdots,e_{M}\\}$ is a basis of $H_{\mu}$, and denote by
$a^{(x)}\in\bbR^{M}$ the coordinates of a fixed projection of $x$ onto
$H_{\mu}$. Then the $\mu$-variance norm is given by

$\|x\|_{\mu\text{-cov}}=\begin{cases}(a^{(x)})^{T}\Sigma^{-1}a^{(x)}&\text{if
}a^{(x)}\in Im(\Sigma),\\\ +\infty&\text{otherwise,}\end{cases}$

for $x\in V$, where $\Sigma\in\bbR^{M\times M}$ is the empirical covariance
matrix of the coordinates $a^{(y_{1})},\cdots,a^{(y_{N})}$.

Proof  We begin by proving $(ii)$, from which $(i)$ will follow. Since the
covariance operator $\calK:V^{*}\to V$ is a finite rank operator, we have that
$\calC(\calR_{\mu})=\calK(V^{*})$, where $\calC:\calR_{\mu}\to V$ is the
extended covariance operator. Hence it follows from the expression

$\calK f=\frac{1}{N}\sum_{i=1}^{N}(x_{i}-\frakm)f(x_{i}-\frakm)$

that $H_{\mu}=\calK(V^{*})\subset span\\{y_{1},\cdots,y_{N}\\}$, which by
Theorem 2.17 implies that $\|x\|_{\mu\text{-cov}}$ is infinite for all
$x\notin span\\{y_{1},\cdots,y_{N}\\}$. Consequently we will only need to
consider this finite span in the subsequent analysis.

Next, observe that by writing $y_{i}=\sum_{m=1}^{M}a^{(y_{i})}_{m}e_{m}$, we
obtain the following expression for the functional quadratic form of $\mu$ for
all $f\in V^{*}$

$\displaystyle q(f,f)$ $\displaystyle=\frac{1}{N}\sum_{i=1}^{N}f(y_{i})^{2}$
$\displaystyle=\frac{1}{N}\sum_{i=1}^{N}\bigg{(}\sum_{m=1}^{M}a^{(y_{i})}_{m}f(e_{m})\bigg{)}^{2}$
$\displaystyle=\frac{1}{N}\sum_{i=1}^{N}\langle
a^{(y_{i})},b\rangle^{2}_{\bbR^{M}}$ $\displaystyle=\langle b,\Sigma
b\rangle_{\bbR^{M}},$

with $b$ given by $b_{m}=f(e_{m})$, and where $\Sigma\in\bbR^{M\times M}$ is
the empirical covariance matrix of the coordinates
$a^{(y_{1})},\cdots,a^{(y_{N})}$. Conversely, if $b\in\bbR^{M}$ is fixed, then
$f_{b}(x):=\langle a^{(x)},b\rangle_{\bbR^{M}}$ defines a continuous linear
functional on $span\\{y_{1},\cdots,y_{N}\\}$, which extends continuously to
$V$ via Hahn-Banach. Consequently we obtain that

$\displaystyle\|x\|_{\mu\text{-cov}}^{2}$ $\displaystyle=\sup_{f\in
V^{*}}\frac{f(x)^{2}}{q(f,f)}$ $\displaystyle=\sup_{b\in\bbR^{M}}\frac{\langle
a^{(x)},b\rangle^{2}_{\bbR^{M}}}{\langle b,\Sigma b\rangle_{\bbR^{M}}}$
$\displaystyle=\begin{cases}(a^{(x)})^{T}\Sigma^{-1}a^{(x)}&\text{if
}a^{(x)}\in Im(\Sigma),\\\ +\infty&\text{otherwise,}\end{cases}$

where the last equality follows from Example 2.22. The fact that we have
equality in $H_{\mu}=span\\{y_{1},\cdots,y_{N}\\}$ follows by Theorem 2.17
since $a^{(x)}\in Im(\Sigma)$ if and only if $x\in
span\\{y_{1},\cdots,y_{N}\\}$, which proves $(i)$.

We want to stress that the choice of basis and projection map is purely for
computational convenience. Different choices of basis and projection map will
lead to the same expression for the variance norm, since it is independent of
basis by Definition 2.16.

######  Corollary 3.5.

If $V$ is a Banach space, then for all $x\in V$ we have that

$\|x\|_{\mu\text{-cov}}=\|a^{(x)}\|_{\nu-\text{cov}},$

where $\mu=\frac{1}{N}\sum_{i=1}^{N}\delta_{x_{i}}$ and $a^{(x)}$ are defined
as in Theorem 3.4, and $\nu=\frac{1}{N}\sum_{\delta_{a^{(y_{i})}}}$ is an
empirical measure on $\bbR^{M}$.

While Corollary 3.5 gives us a way to calculate the variance norm in terms of
the coordinates of the data with respect to some basis of the Cameron-Martin
space $H_{\mu}$, the method of obtaining said basis will depend heavily on the
structure of $V$. A priori it is not clear how one would obtain a computable
algorithm that works for any general Banach space $V$ without imposing a
Hilbert space structure, contrary to the Hilbert case in Section 3.2.

##  4 Application to Multivariate Time Series

In this section, we apply the theory developed in Section 2 and Section 3 to
semi-supervised multivariate time series anomaly detection. Given a collection
of non-anomalous multivariate time series, referred to as the normal data
corpus, we are presented with new time series samples that we want to classify
as either belonging to the normal class or as anomalies. We achieve this by
defining an anomaly distance with respect to the corpus using either the
Mahalanobis distance or the conformance score (see Definitions 2.21 and 2.24),
assuming that our data originates from some suitable Hilbert space. For this
particular problem, a natural choice for the Hilbert space is
$V=(L^{2}[0,1])^{d}$. However, our framework is agnostic to the specific
Hilbert space used, so the same procedure can be applied for anomaly detection
on any other Hilbert space.

For a given normal corpus $\\{x_{1},\cdots,x_{N}\\}\subset V$ we form either
the standard empirical measure $\mu=\frac{1}{N}\sum_{i=1}^{N}\delta_{x_{i}}$,
or the kernelized empirical measure
$\mu=\frac{1}{N}\sum_{i=1}^{N}\delta_{\phi(x_{i})}$ where $\phi$ is a feature
map corresponding to a positive definite kernel. The empirical measure $\mu$
can be interpreted as an estimator of the underlying distribution of the
normal corpus. Given a new sample $y$, we proceed by calculating either the
Mahalanobis distance

$d_{M}(y;\mu)=\|y-\frakm\|_{\mu\text{-cov}},$

where $\frakm=\frac{1}{N}\sum_{i=1}^{N}x_{i}$ is the mean of the normal
corpus, or the conformance score

$d_{C}(y;\mu)=\min_{1\leq n\leq N}\|y-x_{n}\|_{\mu\text{-cov}},$

using Algorithms 1 to 3, which defines an anomaly distance to the normal
corpus. We then classify each new sample $y$ as being anomalous or non-
anomalous based on a threshold $\gamma>0$.

The threshold $\gamma$ can be determined through various approaches. A data-
driven method involves splitting the normal corpus into training and
validation sets, then choosing $\gamma$ as an empirical quantile of the
anomaly distances in the validation set. Alternatively, a theoretical approach
uses the guarantees for the Mahalanobis distance and conformance score, as
outlined in Theorem 2.31 and the concentration results of Section 2.5,
assuming the data follows a Gaussian distribution. If a labelled subset of
outliers is available, a supervised optimization method can be employed, using
$k$-fold cross-validation to determine an optimal threshold; however, this
requires access to a supervised dataset of anomalies. In our experiments, we
evaluate each anomaly distance using Precision-Recall AUC and ROC-AUC metrics,
which consider sensitivity across all positive thresholds, thus eliminating
the need to select a fixed threshold explicitly.

Since Theorem 3.3 implies that the $\mu$-variance norm depends solely on the
Gram matrix $\langle x_{i},x_{j}\rangle$ of the normal corpus, our anomaly
distances depend only on how we choose to measure the similarity of two
elements $x_{i}$ and $x_{j}$ via some inner product. We could for instance
keep to the linear inner product given by our choice of Hilbert space, or we
could choose to kernelize our method which corresponds to working with non-
linear inner products given by a positive definite kernel $k$ via
$\langle\phi(x_{i}),\phi(x_{j})\rangle=k(x_{i},x_{j})$ using a kernel trick.
Here we consider both alternatives.

Although semi-supervised anomaly detection using the nearest-neighbour
Mahalanobis distance, as opposed to the classical Mahalanobis distance, has
been successfully employed in the finite-dimensional $\bbR^{d}$ setting [VF11,
SK20, Sha+23, Arr+24], to our knowledge no comprehensive comparison of these
two anomaly distances has been carried out in the literature. In this section
we carry out an extensive comparison of our newly introduced kernelized
conformance score (including the non-kernelized linear case) against the
kernelized Mahalanobis distance for the task of semi-supervised time series
anomaly detection, using the infinite-dimensional framework developed in the
previous sections.

###  4.1 Time series kernels

We begin by giving a brief summary of the time series kernels we will consider
in our experimentation. These will consist of the linear kernel given by the
$(L^{2}[0,1])^{d}$ inner product, a family of generalized integral-class
kernels related to linear time warping, and a collection of time-dynamic
state-of-the-art time series kernels including the global alignment kernel,
the Volterra reservoir kernel, and the signature kernel.

####  4.1.1 Static and integral class kernels

Consider first the natural Hilbert space $(L^{2}[0,1])^{d}$, where the inner
product is given by

$\displaystyle\langle x,y\rangle=\int_{[0,1]}\langle
x_{t},y_{t}\rangle_{\bbR^{d}}dt$ (14)

for $x,y\in(L^{2}[0,1])^{d}$. If $x$ and $y$ are discretized on a regular time
grid of size $T$, and consequently can be viewed as $d$-dimensional time
series of length $T$, then the inner product (14) can simply be computed by
flattening $x$ and $y$ into vectors in $\bbR^{Td}$, and then calculating their
Euclidean dot product. Instead of using the Euclidean dot product, or in other
words the linear kernel, one could just as well replace this with any static
kernel defined on $\bbR^{dT}$ as per Definition 4.1 below. Similarly, we can
also replace the linear static kernel in (14) to obtain a class of integral-
type kernels with respect to a static kernel. In our experimentation we will
consider both flattened and integral-type kernels. We give the following
definitions:

######  Definition 4.1.

A static kernel on $\bbR^{d}$ is a defined as a positive definite kernel
$k:\bbR^{d}\times\bbR^{d}\to\bbR$.

######  Definition 4.2.

Let $k$ be a static kernel on $\bbR^{d}$. We define the time series integral
class kernel of $k$ to be the kernel

$\displaystyle K_{k}(x,y)=\int_{[0,1]}k(x_{t},y_{t})dt,$

defined for $d$-dimensional time series $x$ and $y$.

The positive definiteness of $K_{k}$ follows trivially from that of $k$. By
replacing the Euclidean dot product with a possibly non-linear static kernel,
an algorithm may be able to take certain non-linearities of the data into
account to increase classification accuracies. The integral type kernels can
in fact be seen as a variant of linear time warping kernels, which was first
introduced in [Shi+01]. The static kernels we consider in this paper are:

  1. (i)

The linear kernel $k_{linear}(x,y)=\langle x,y\rangle$, which does not have
any hyperparameters.

  2. (ii)

The polynomial kernel $k_{poly}(x,y)=(c+\langle x,y\rangle)^{p}$ with
hyperparameters $c\in\bbR$ and $p\in\bbZ$.

  3. (iii)

The RBF kernel $k_{RBF}(x,y)=e^{-\frac{|x-y|^{2}}{2\sigma^{2}}}$ with
hyperparameter $\sigma>0$.

We thus have two distinct classes of time series kernels parametrized by
static kernels: One is to consider flattened time series and static kernels in
$\bbR^{Td}$, and the other is integral class kernels with respect to static
kernels on $\bbR^{d}$. Note that the integral and static class kernels
coincide when $k$ is the linear kernel, and are distinct otherwise. These time
series kernels can be computed in $\calO(Td)$ time.

####  4.1.2 Global alignment kernel

The global alignment kernel (GAK) [Cut+07, Cut11] is a dynamic-time kernel
which is able to take non-linear time lags into account when measuring the
similarity of two time series via dynamic time warping. While the classical
dynamic time warping fails to define positive definite kernels due to failing
to satisfy the triangle inequality, the global alignment kernel is able to
overcome this by summing over all possible global alignments of the time
series.

######  Definition 4.3.

Let $x=(x_{1},\cdots,x_{T})$ and $y=(y_{1},\cdots,x_{L})$ be two time series
of length $T$ and $L$ respectively. An alignment $\pi$, denoted
$\pi\in\calA(T,L)$, is defined as a pair $\pi=(\pi_{1},\pi_{2})$ of vectors of
length $p\leq T+L-1$ such that $1=\pi_{1}(1)\leq\cdots\leq\pi_{1}(p)=T$ and
$1=\pi_{2}(1)\leq\cdots\leq\pi_{2}(p)=L$. Given a similarity measure
$\varphi:\bbR^{d}\times\bbR^{d}\to[0,\infty)$, the cost $D_{x,y}(\pi)$ is
defined as

$\displaystyle
D_{x,y}(\pi):=\sum_{i=1}^{|\pi|}\varphi(x_{\pi_{1}(i)},y_{\pi_{2}(i)}),$

and the global alignment kernel is defined as

$\displaystyle K_{GA}(x,y)$
$\displaystyle=\sum_{\pi\in\calA(T,L)}e^{-D_{x,y}(\pi)}$
$\displaystyle=\sum_{\pi\in\calA(T,L)}\prod_{i=1}^{|\pi|}\kappa(x_{\pi_{1}(i)},y_{\pi_{2}(i)}),$
(15)

where $\kappa=e^{-\varphi}$ is the local similarity.

[Cut+07] proved that $K_{GA}$ defined via a local kernel $\kappa$ is positive
definite if $\frac{\kappa}{1+\kappa}$ is positive definite. A sufficient
condition for this is for $\kappa$ to be geometrically or infinitely
divisible. In practice the local kernel $\kappa=\frac{k_{RBF}}{2-k_{RBF}}$ is
often used, and due to the exponential nature of (15) the GAK kernel is always
made to be normalized in feature space via
$\frac{K_{GA}(x,y)}{\sqrt{K_{GA}(x,x)K_{GA}(y,y)}}$. The GAK kernel has a
single hyperparameter $\sigma>0$ inherited from the static RBF kernel, and
$K_{GA}(x,y)$ can be computed in $\calO(TLd)$ time using dynamic programming.

####  4.1.3 Volterra reservoir kernel

The Volterra Reservoir Kernel (VRK) [GGO22] is a universal dynamic kernel
designed for sequences of arbitrary length. The kernel is built by
constructing a state-space representation of the classical Volterra series
expansions [Wie58, San83, BC85], a series representation for analytic maps
between sequences. As discussed in detail in [GGO22, Cuc+22] this idea is
closely related to the principle of reservoir computing [MNM02, JH04] and
associated kernels [GO21]. The VRK kernel was recently shown to outperform the
RBF, GAK, and signature kernels in a market forecasting task [GGO22].

For sequences of length $T$ the VRK kernel with hyperparameters $\tau\in\bbR$
and $\lambda\in(0,1)$ is defined as

$\displaystyle K^{\textsc{Volt}}(x,y)$
$\displaystyle=1+\sum_{k=1}^{T}\lambda^{2k}\prod_{t=0}^{k-1}\frac{1}{1-\tau^{2}\langle
x_{T-t},y_{T-t}\rangle},$

for time series $x$ and $y$ of equal length such that $\tau^{2}\|x\|\|y\|<1$,
where $\langle\cdot,\cdot\rangle$ is the Euclidean inner product on
$\bbR^{d}$. The solution can be computed in $\calO(Td)$ time using a recursive
relation between the kernel at different time steps.

####  4.1.4 Signature kernels

The signature kernel [KO19, Sal+21] is a positive definite kernel for
sequential data based on tools originating from stochastic analysis and rough
path theory [Lyo98]. It has many desirable theoretical properties such as
invariance to time-reparametrization, universality, and characteristicness on
compact sets. Algorithms using signature kernels have successfully been
applied to a wide variate of fields since their inception, for instance in
Bayesian forecasting [TO20], hypothesis testing [Sal+21a], and for support
vector machines [Sal+21, TOS23] achieveing state-of-the-art accuracies.

Below we give a very brief construction of the signature kernel, which is
defined as an inner product in the extended tensor algebra via the so-called
signature transform. For a detailed introduction to signature kernels we refer
to the seminal papers [KO19, Sal+21], the review article [LO23], and the
lecture notes [CS24].

######  Definition 4.4.

Let $\calH$ be a Hilbert space. The $m$-fold iterated integral of a bounded
variation path $x\in BV([0,1],\calH)$ is recursively defined as

$\displaystyle S_{0}(x):=1,\qquad S_{m+1}(x)=\int_{0}^{1}S_{m}(x)\otimes
dx_{t}.$

We define the signature transform as the map

$\displaystyle S:BV([0,1],\calH)$
$\displaystyle\to\prod_{m=0}^{\infty}\calH^{\otimes m}$ $\displaystyle x$
$\displaystyle\mapsto\big{(}S_{m}(x)\big{)}_{m=0}^{\infty},$

and similarly, we define the truncated signature as the map
$S_{0:n}(x):=\big{(}S_{m}(x)\big{)}_{m=0}^{n}$. Here we use the convention
that $\calH^{\otimes 0}=\bbR$.

Given a path $x\in BV([0,1],\bbR^{d})$ and a static kernel $k$ on $\bbR^{d}$,
we may canonically lift $k$ to a path $k_{x}$ taking values in its RKHS
$\calH$ via $t\mapsto k(x_{t},\cdot)\in\calH$ using the reproducing kernel
property of $k$. If $k$ is the linear kernel $k(x,y)=\langle
x,y\rangle_{\bbR^{d}}$, then $k_{x}$ is simply the original path $x$. However,
if we choose $k$ to be a non-linear kernel such as the RBF kernel, then
$k_{x}$ would genuinely be different to $x$, and in this particular case
$k_{x}$ would take values in an infinite dimensional Hilbert space where
direct computations of truncated signature features are impossible. The main
idea behind the signature kernel is to define the sequential kernel $k^{sig}$
w.r.t. a static kernel $k$ as the inner product of signature transforms
$S(k_{x})$ and $S(k_{y})$ given two paths $x$ and $y$.

######  Definition 4.5.

Let $k$ be a static kernel on $\bbR^{d}$. We define the $k$-lifted signature
kernel as the mapping $k^{sig}:BV([0,1],\bbR^{d})\times
BV([0,1],\bbR^{d})\to\bbR$,

$\displaystyle
k^{sig}(x,y)=\sum_{m=0}^{\infty}\big{\langle}S_{m}(k_{x}),S_{m}(k_{y})\big{\rangle}_{\calH^{\otimes
m}},$

where $\langle\cdot,\cdot\rangle_{\calH^{\otimes m}}$ is the Hilbert-Schmidt
inner product defined as $\langle a,b\rangle_{\calH^{\otimes
m}}=\sum_{i=1}^{n}\langle a_{i},b_{i}\rangle_{\calH}$ for elements
$a=a_{1}\otimes\cdots\otimes a_{m}$ and $b=b_{1}\otimes\cdots\otimes b_{m}$.
The truncated singature kernel $k^{sig}_{0:n}$ is defined similarly using the
truncated signature.

There are currently three main algorithms for computing signature kernels,
each of which come with their separate advantages and disadvantages. We list
the methods below:

  1. 1.

If $\dim\calH=d<\infty$, then the truncated signature $S_{0:m}(x)$ can be
computed exactly in $\calO(Td^{m})$ time, when treating the time series $x$ as
a piecewise linear path of length $T$. The truncated signature can then be
computed by taking the inner product of the truncated signature. In practice
this method is only applicable when $k$ is the trivial linear kernel, and when
$d$ is very small (e.g. $d<5$) due to the exponential time complexity.

  2. 2.

The second method takes advantage of the kernel trick to compute
$k_{0:m}^{sig}(x,y)$ via a Horner-type scheme [KO19]. This can be computed in
$\calO(LTmd)$ time using a non-geometric approximation of $k^{sig}(x,y)$, or
exactly in $\calO(LT(md+m^{3}))$ when viewing $x$ and $y$ as piecewise linear
paths of lengths $T$ and $L$ with state-space $\bbR^{d}$. We refer the reader
to [KO19, Algorithms 3 and 6] for more details.

  3. 3.

The last method is due to [Sal+21], who proved that the signature kernel
$k^{sig}(x|_{[0,s]},y|_{[0,t]})$ solves the Goursat PDE

$\displaystyle
k^{sig}(x|_{[0,s]},y|_{[0,t]})=1+\int_{0}^{s}\int_{0}^{t}k^{sig}(x|_{[0,u]},y|_{[0,v]})\langle
dk_{x_{u}},dk_{x_{v}}\rangle_{\bbR^{d}},$ (16)

where $x|_{[0,x]}$ denotes the restriction of $x$ to the interval $[0,s]$.
Equation (16) can be solved for piecewise linear paths using numerical PDE
methods in $\calO(LTd)$ time [Sal+21], but is often much slower than the
truncated approaches.

Generally the RBF-lifted signature kernel is preferred over the vanilla
signature kernel. This is partly due to the latter having a tendency to blow
up when the underlying time series are not properly normalized, something
which is particularly pronounced for the PDE signature kernel which
essentially acts as an inner product of tensor exponentials. In our
experimentation we will use the truncated signature kernel with the linear and
RBF static kernels, as well as the RBF-lifted PDE signature kernel.

Another recently introduced variant of the signature and its signature kernel
is the so-called randomized signature [Cuc+21], which we now define.

######  Definition 4.6.

Let $M\geq 1$ be an integer. Fix an initial condition $z_{0}\in\bbR^{M}$,
random matrices $A_{1},\cdots,A_{d}\in\bbR^{M\times M}$, random biases
$b_{1},\cdots,b_{d}\in\bbR^{M}$ and an activation function $\sigma$. The
randomized signature $Z$ of $x\in BV([0,1],\bbR^{d})$ is defined as the
solution of the controlled differential equation (CDE)

$\displaystyle
dZ_{t}=\sum_{i=1}^{d}\sigma(A_{i}Z_{t}+b_{i})dx_{t}^{(i)},\qquad Z_{0}=z_{0},$
(17)

where $x^{(i)}$ denotes the $i$’th component of $x$.

The randomized signature was first constructed by [Cuc+21] as a random
projection of the signature, with an argument based on a non-trivial
application of the Johnson-Lindenstrauss lemma. It is a reservoir system and,
in theory, has the same expressive power as the signature transform in the
limit as $M\to\infty$. Randomized signatures have recently been successfully
used for market anomaly detection [Aky+22], graph conversion [Sch+23], optimal
portfolio selection [Aky+23, CM24], generative time series modelling [BGW24],
and for learning rough dynamical systems [Com+23]. The CDE (17) has since been
studied from the perspective of randomly initialized ResNets [CLS23], and path
developments on compact Lie groups [LLN22, LLN23, CT24]. In our experiments,
we will use Gaussian random matrices and biases, with tanh activation
function.

###  4.2 Experiments

In this section we present an empirical study comparing the (potentially
kernelized) Mahalanobis distance to the conformance score for semi-supervised
multivariate time series anomaly detection. Our primary objective is to
validate Algorithms 1 to 3 presented in this paper for this infinite
dimensional setting. For comparisons of the finite-dimensional conformance
score against other established methods like isolation forests, shapelets, and
local outlier factors, we refer readers to [Sha+23]. Within the functional
data analysis literature, the $(L^{2}[0,1])^{d}$ Mahalanobis distance has been
evaluated against other common functional anomaly detection methodologies such
as boxplots, outliergrams, and depth-based trimming [AR14, BBC20].

We will use UEA multivariate time series repository [Bag+18, Rui+21] in our
experimentation, which in recent years has become a standard benchmark for
multivariate time series classification. The repository contains 30 real world
datasets consisting of multivariate time series, 26 of which are of equal
lengths ranging from 8 to 2500 time steps, with state-space dimension ranging
from 2 to 1345, see Table 1 for a summary. For the task of semi-supervised
anomaly detection task we employ a one-versus-rest approach. In each
experiment, we designate a single class label as the normal corpus, while
considering all other classes as anomalous. We evaluate the performance using
both precision-recall AUC (PR AUC) and ROC AUC. The results are then averaged
across all class labels for a comprehensive assessment. Our experiment code is
publically available at https://github.com/nikitazozoulenko/kernel-timeseries-
anomaly-detection.

Code | Name | Train size | Test size | Dims | Length | Classes | Avg. Corpus Size
---|---|---|---|---|---|---|---
AWR | ArticularyWordRecognition | 275 | 300 | 9 | 144 | 25 | 11
AF | AtrialFibrillation | 15 | 15 | 2 | 640 | 3 | 5
BM | BasicMotions | 40 | 40 | 6 | 100 | 4 | 10
CR | Cricket | 108 | 72 | 6 | 1197 | 12 | 9
DDG | DuckDuckGeese | 50 | 50 | 1345 | 270 | 5 | 10
EW | EigenWorms | 128 | 131 | 6 | 17,984 | 5 | 26
EP | Epilepsy | 137 | 138 | 3 | 206 | 4 | 34
EC | EthanolConcentration | 261 | 263 | 3 | 1751 | 4 | 65
ER | ERing | 30 | 270 | 4 | 65 | 6 | 5
FD | FaceDetection | 5890 | 3524 | 144 | 62 | 2 | 2945
FM | FingerMovements | 316 | 100 | 28 | 50 | 2 | 158
HMD | HandMovementDirection | 160 | 74 | 10 | 400 | 4 | 40
HW | Handwriting | 150 | 850 | 3 | 152 | 26 | 6
HB | Heartbeat | 204 | 205 | 61 | 405 | 2 | 102
LIB | Libras | 180 | 180 | 2 | 45 | 15 | 12
LSST | LSST | 2459 | 2466 | 6 | 36 | 14 | 176
MI | MotorImagery | 278 | 100 | 64 | 3000 | 2 | 139
NATO | NATOPS | 180 | 180 | 24 | 51 | 6 | 30
PD | PenDigits | 7494 | 3498 | 2 | 8 | 10 | 749
PEMS | PEMS-SF | 267 | 173 | 963 | 144 | 7 | 38
PS | PhonemeSpectra | 3315 | 3353 | 11 | 217 | 39 | 85
RS | RacketSports | 151 | 152 | 6 | 30 | 4 | 38
SRS1 | SelfRegulationSCP1 | 268 | 293 | 6 | 896 | 2 | 134
SRS2 | SelfRegulationSCP2 | 200 | 180 | 7 | 1152 | 2 | 100
SWJ | StandWalkJump | 12 | 15 | 4 | 2500 | 3 | 4
UW | UWaveGestureLibrary | 120 | 320 | 3 | 315 | 8 | 15

Table 1: Summary of the 26 equal length UEA multivariate time series datasets.
In our empirical study we consider all datasets of total size less than 8000,
where the average corpus size is greater than 30.

####  4.2.1 Experimental setup

In total we will consider two different anomaly distances, namely the
Mahalanobis distance and the conformance score, together with 11 different
time series kernels. This includes the linear Euclidean kernel corresponding
to the non-kernelized $(L^{2}[0,1])^{d}$ setting. In our open-source code we
provide efficient PyTorch implementations of each kernel on both GPU and CPU,
as well as an implementation of Algorithms 1 to 3 for computing the kernelized
Mahalanobis distance and the kernelized conformance score. We will consider
the following time series kernels in our experimentation, all of which were
defined in Section 4.1:

  1. 1.

The family of time series kernels obtained by flattening a given time series
of length $T$ into a vector in $\bbR^{Td}$, and then applying a static kernel.
We will use the RBF, polynomial, and linear kernels as our choices of static
kernels, the latter of which corresponds to the $(L^{2}[0,1])^{d}$ inner
product.

  2. 2.

The family of integral-class kernels (linear time warping), with RBF and
polynomial static kernels.

  3. 3.

The global alignment kernel (GAK).

  4. 4.

The Volterra reservoir kernel (VRK).

  5. 5.

Four different variants of the signature kernel: The truncated signature
kernel, the RBF-lifted truncated signature kernel, the RBF-lifted PDE
signature kernel, and randomized signatures with tanh activation.

Our work adds to the growing body of literature on anomaly detection using
signature features, which was first studied in [Sha+23]. This was done by
explicitly computing $m$-level truncated signature features, which has
$\calO(Td^{m})$ time complexity. Truncated signatures were later successfully
used for market anomaly detection [Aky+22], and radio astronomy [Arr+24]. The
use of signatures has however been limited to very low-dimensional time series
due to the exponential time complexity of explicitly computing truncated
signatures. Our unified framework addresses this bottleneck, allowing for
efficient computations of both signature conformance scores and signature
Mahalanobis distances in $\calO(T^{2}d)$ time. This significant improvement in
$d$ opens up the use of these methods for high-dimensional time series data.

####  4.2.2 Hyper-parameter selection

For each kernel, dataset, and class label, we run an extensive grid search on
the designated training set using repeated $k$-fold cross-validation with 4
folds and 10 repeats to find the optimal kernel hyper-parameters. Let
$\bbR^{d}$ be the state-space, and let $T$ be the length of the time series
for a given dataset. For each method using the RBF static kernel we use the
range $\sigma\in\frac{1}{\sqrt{d}}\\{e^{-2},e^{-1},1,e^{1},e^{2}\\}$, and
similarly for the polynomial kernel we use $p\in\\{2,3,4\\}$, and
$c\in\\{\frac{1}{4},\frac{1}{2},1,2,4\\}$. For the GAK kernel we use the
previously specified $\sigma$ without the $\sqrt{d}$ term, multiplied by
$\sqrt{T}\cdot\text{med}(\|x-y\|)$ as is recommended in [Cut11]. For the VRK
kernel we use
$\tau\in\frac{1}{\sqrt{d}}\\{\frac{1}{8},\frac{1}{4},\frac{1}{2},1\\}$, and we
let $\lambda$ vary from $0.25$ to $0.999$ on an inverse logarithmic grid of
size $10$.

The signature kernels inherit hyper-parameters from their respective static
kernels. We additionally scale the kernel-lifted paths by
$s\in\frac{1}{\sqrt{d}}\\{\frac{1}{4},\frac{1}{2},1,2,4\\}$ for the truncated
signature, and by
$s\in\frac{1}{\sqrt{d}}\\{\frac{1}{8},\frac{1}{4},\frac{1}{2},1\\}$ for the
untruncated PDE kernel. We use lower values for the PDE signature kernel since
untruncated signatures essentially can be viewed as tensor exponentials, whose
inner products will blow up if the input values are too big. For the truncated
signature kernel we let the truncation level be in $\\{1,2,3,4,5,6,7\\}$. For
the randomized signature we use the tanh activation function with number of
features in $\\{10,25,50,100,200\\}$, and random matrix variances taken from a
logarithmic grid of size $8$ from $0.00001$ to $1$. Since the randomized
signature is a randomized kernel, we perform the cross validation with $5$
different random seeds for the random matrix initializations, and take the
best performing model (using the training set only), as is common practice for
randomized methods.

Furthermore, for each method we also cross-validate over the Tikhonov
regularization parameter $\alpha\in\\{10^{-8},10^{-5},10^{-2}\\}$, whether to
concatenate time as an additional dimension to each time series, and the
eigenvalue threshold $\lambda$ in Algorithm 1. We set an upper limit of 50
eigenvalues for the computation of the variance norm. For numerical stability,
and to make the choices of $\alpha$ and $\lambda$ be comparable across all
kernels and datasets, we normalize all time series kernels $K$ in feature
space via $\frac{K(x,y)}{\sqrt{K(x,x)K(y,y)}}$.

####  4.2.3 Pre-processing

For each dataset and each class label, we normalize the data to have mean zero
and standard deviation one, using the statistics of the normal corpus.
Average-pooling is then performed to reduce the maximum length of all time
series to 100 time steps. After this, we concatenate the zero vector to each
time series to allow each dynamic kernel to be translation-sensitive, and we
clip all values to be in $[-5,5]$ for additional numerical stability.
Furthermore, in our cross-validation we also include the choice of adding time
as an additional dimension to all time series. For the VRK kernel
specifically, we perform further clipping of the data based on the $\tau$
hyper-parameter, which is required to make the VRK kernel well-defined.

####  4.2.4 Data and results

Due to the high computational cost of evaluating 11 time series kernels on all
26 UEA datasets, with up to 40 experiments per dataset-kernel combination,
each of which goes through an extensive repeated k-fold cross-validation, we
focus our analysis on UEA datasets with a total size under 8,000 entries (see
Table 1). This excluded PenDigits and FaceDetection. Additionally, to ensure a
sufficient statistical sample size, we only considered datasets where the
average corpus size exceeded 30 entries, resulting in a final selection of 12
datasets.

The anomaly distances were computed as described by Algorithms 1 to 3. The
optimal kernel hyper-parameters were obtained separately for the Mahalanobis
distance and the conformance score, via a 10 times repeated 4-fold cross-
validation on the training data for each dataset. The objective score used in
the cross-validation was the sum of ROC-AUC and PR-AUC. When calculating the
precision-recall metric, we let the non-anomalous class be the positive class.
The final model was then evaluated on the out-of-sample test set to obtain the
final results, presented in Table 2 and Table 3.

Dataset | ROC AUC
---|---
| linear | RBF | poly | $I_{\text{RBF}}$ | $I_{\text{poly}}$ | GAK | VRK | $S_{\text{lin}}$ | $S_{\text{RBF}}$ | $S^{\infty}_{\text{RBF}}$ | $S^{\text{rand}}_{\text{tanh}}$
EP | C | .89 | .95 | .91 | .94 | .91 | .97 | .94 | .98 | .98 | .92 | .94
M | .70 | .81 | .80 | .80 | .81 | .88 | .90 | .98 | .97 | .91 | .95
EC | C | .55 | .56 | .55 | .55 | .55 | .56 | .58 | .59 | .55 | .56 | .55
M | .57 | .56 | .58 | .55 | .57 | .57 | .60 | .56 | .56 | .56 | .56
FM | C | .58 | .52 | .54 | .54 | .53 | .60 | .53 | .49 | .49 | .48 | .54
M | .58 | .51 | .53 | .50 | .52 | .54 | .48 | .49 | .48 | .51 | .56
HMD | C | .55 | .43 | .54 | .53 | .49 | .46 | .52 | .53 | .48 | .50 | .57
M | .45 | .50 | .47 | .46 | .51 | .55 | .54 | .50 | .50 | .52 | .52
HB | C | .63 | .64 | .60 | .61 | .61 | .59 | .67 | .70 | .72 | .62 | .61
M | .61 | .59 | .61 | .62 | .59 | .61 | .62 | .69 | .60 | .59 | .60
LSST | C | .54 | .61 | .53 | .61 | .56 | .68 | .53 | .57 | .67 | .62 | .62
M | .62 | .68 | .66 | .67 | .66 | .67 | .67 | .67 | .65 | .63 | .67
MI | C | .51 | .54 | .57 | .57 | .53 | .50 | .54 | .43 | .57 | .60 | .45
M | .51 | .52 | .47 | .46 | .49 | .50 | .54 | .47 | .49 | .43 | .46
PEMS | C | .91 | .92 | .90 | .91 | .89 | .93 | .90 | .93 | .92 | .93 | .87
M | .48 | .69 | .53 | .66 | .52 | .77 | .90 | .80 | .79 | .71 | .72
PS | C | .62 | .65 | .65 | .64 | .63 | .66 | .67 | .70 | .69 | .56 | .67
M | .65 | .67 | .65 | .65 | .64 | .65 | .68 | .71 | .70 | .54 | .69
RS | C | .79 | .73 | .74 | .80 | .81 | .77 | .46 | .73 | .77 | .68 | .76
M | .34 | .58 | .48 | .60 | .42 | .83 | .61 | .79 | .73 | .75 | .69
SRS1 | C | .68 | .81 | .79 | .80 | .81 | .77 | .81 | .61 | .77 | .71 | .77
M | .73 | .60 | .70 | .59 | .58 | .62 | .72 | .77 | .77 | .77 | .75
SRS2 | C | .57 | .51 | .53 | .53 | .53 | .54 | .50 | .49 | .48 | .53 | .50
M | .57 | .55 | .54 | .55 | .59 | .55 | .53 | .54 | .50 | .50 | .52
Avg. AUC | C | .65 | .66 | .65 | .67 | .65 | .67 | .64 | .65 | .67 | .64 | .66
M | .57 | .60 | .58 | .59 | .58 | .65 | .65 | .66 | .65 | .62 | .64
Avg. Rank | C | 11.0 | 10.7 | 10.9 | 10.0 | 11.8 | 8.8 | 9.9 | 10.4 | 8.8 | 12.4 | 11.1
M | 13.5 | 13.2 | 14.1 | 14.8 | 14.8 | 9.6 | 10.2 | 8.8 | 12.1 | 15.0 | 11.3

Table 2: One-versus-rest ROC-AUC for the semi-supervised anomaly detection
experiments on the UEA multivariate time series repository. The conformance
and Mahalanobis methods are denoted by C and M, respectively. The symbols $I$,
$S$, $S^{\infty}$ and $S^{\text{rand}}$ represent the integral, truncated
signature, PDE signature, and randomized signature kernels, respectively.

Dataset | Precision-Recall AUC
---|---
| linear | RBF | poly | $I_{\text{RBF}}$ | $I_{\text{poly}}$ | GAK | VRK | $S_{\text{lin}}$ | $S_{\text{RBF}}$ | $S^{\infty}_{\text{RBF}}$ | $S^{\text{rand}}_{\text{tanh}}$
EP | C | .79 | .88 | .81 | .87 | .75 | .92 | .86 | .96 | .96 | .80 | .85
M | .42 | .58 | .54 | .57 | .58 | .73 | .73 | .95 | .94 | .78 | .89
EC | C | .28 | .28 | .29 | .28 | .31 | .29 | .32 | .32 | .29 | .30 | .28
M | .30 | .32 | .31 | .30 | .32 | .32 | .33 | .28 | .28 | .30 | .30
FM | C | .56 | .52 | .55 | .57 | .56 | .60 | .54 | .54 | .52 | .53 | .54
M | .55 | .51 | .52 | .50 | .52 | .52 | .51 | .52 | .49 | .53 | .55
HMD | C | .30 | .24 | .31 | .30 | .28 | .26 | .27 | .28 | .29 | .27 | .29
M | .25 | .29 | .26 | .28 | .27 | .31 | .33 | .29 | .29 | .33 | .27
HB | C | .58 | .60 | .53 | .56 | .55 | .55 | .63 | .63 | .63 | .58 | .60
M | .58 | .56 | .57 | .61 | .55 | .59 | .61 | .64 | .55 | .56 | .58
LSST | C | .12 | .12 | .10 | .15 | .11 | .14 | .10 | .12 | .19 | .14 | .10
M | .14 | .15 | .16 | .17 | .14 | .14 | .15 | .17 | .17 | .14 | .15
MI | C | .54 | .54 | .57 | .57 | .54 | .49 | .55 | .47 | .56 | .60 | .49
M | .55 | .54 | .53 | .49 | .53 | .53 | .57 | .51 | .50 | .46 | .48
PEMS | C | .79 | .82 | .79 | .81 | .79 | .83 | .83 | .83 | .81 | .82 | .72
M | .34 | .41 | .33 | .39 | .31 | .48 | .64 | .50 | .52 | .38 | .40
PS | C | .05 | .06 | .06 | .05 | .05 | .07 | .06 | .07 | .07 | .03 | .06
M | .05 | .06 | .05 | .05 | .05 | .05 | .06 | .07 | .08 | .03 | .07
RS | C | .65 | .64 | .66 | .72 | .70 | .62 | .40 | .56 | .67 | .52 | .55
M | .20 | .33 | .26 | .34 | .23 | .66 | .36 | .61 | .53 | .57 | .44
SRS1 | C | .69 | .78 | .76 | .78 | .77 | .74 | .76 | .63 | .76 | .70 | .75
M | .77 | .67 | .69 | .66 | .64 | .69 | .68 | .75 | .73 | .74 | .74
SRS2 | C | .57 | .51 | .53 | .54 | .52 | .55 | .52 | .51 | .50 | .54 | .51
M | .55 | .55 | .54 | .56 | .58 | .55 | .54 | .55 | .51 | .51 | .52
Avg. AUC | C | .49 | .50 | .50 | .52 | .49 | .51 | .49 | .49 | .52 | .49 | .48
M | .39 | .41 | .40 | .41 | .39 | .46 | .46 | .49 | .47 | .44 | .45
Avg. Rank | C | 11.0 | 11.1 | 10.6 | 8.0 | 11.4 | 10.3 | 9.8 | 10.6 | 7.7 | 11.2 | 12.8
M | 13.2 | 13.1 | 15.2 | 13.8 | 15.1 | 10.5 | 10.0 | 8.8 | 12.4 | 14.5 | 12.0

Table 3: One-versus-rest PR-AUC for the semi-supervised anomaly detection
experiments on the UEA multivariate time series repository. The conformance
and Mahalanobis methods are denoted by C and M, respectively. The symbols $I$,
$S$, $S^{\infty}$ and $S^{\text{rand}}$ represent the integral, truncated
signature, PDE signature, and randomized signature kernels, respectively.

####  4.2.5 Discussion

For the Mahalanobis distance, there seems to be a clear advantage to working
in the kernelized setting, as the results show that the linear
$(L^{2}[0,1])^{d}$ inner product achieves the lowest average test scores out
of all methods, with ROC-AUC and PR-AUC scores of 0.57 and 0.39, respectively.
The GAK, VRK and truncated signature kernels on the other hand perform best in
this regard, obtaining AUC scores of 0.65-0.66 and 0.46-0.49, respectively.

The average test scores for the conformance score (nearest-neighbour
Mahalanobis distance) do not differ much between the choices of kernels, but
can have significant differences within a single dataset. The average ROC and
PR AUC scores calculated over all datasets range from 0.64-0.67 and 0.49-0.52,
respectively, with the best results obtained from the RBF integral, RBF
signature, and GAK kernel.

When it comes to average rank, the Mahalanobis linear truncated signature and
conformance RBF truncated signature takes the number one spot, with the VRK
and GAK kernels as close second place contenders. These kernels also have the
most number of first places across all datasets, especially the linear
truncated signature kernel. However, since the results are very dataset
dependent, the best performing model and kernel combination will vary on a
case-by-case basis.

Fig. 2 shows a pairwise scatter plot of the Mahalanobis distance and
conformance score test results for all kernels and all datasets. The results
suggest that most of the time there is no significant advantage to using one
anomaly distance over the other, except for a few cases seen in the upper left
quadrant where the conformance score greatly outperforms the Mahalanobis
distance. The difference in performance seem to be more pronounced for the
simple flattened and integral-class kernels, where the average difference is
0.07 points, as opposed to the dynamic-time kernels where the average
difference is 0.02 points. This difference is more pronounced for the PR-AUC
metric, and two interesting examples are RacketSports and PEMS-SF where the
PR-AUC doubles for select kernels when using the conformance method.

When it comes to computing the variance norm according to Algorithms 1 to 3,
both the Mahalanobis and conformance methods on average obtained their highest
cross validation scores using a low number of eigenvalues, as seen in Fig. 1.
Furthermore, we see that both methods in general preferred a low
regularization parameter $\alpha$, with $\alpha=1\text{e-08}$ being most
commonly used.

|
---|---
Figure 1: Optimal hyper-parameters for computing the anomaly distance as per
Algorithms 1 to 3, sampled across all datasets and all kernels, normalized by
the number of classes per dataset. The results were obtained via a repeated
$k$-fold cross-validation on the train set. Figure 2: Pairwise comparison of
one-versus-rest test scores for the Mahalanobis distance and the Conformance
score. Each point represents one kernel and one dataset.

## Acknowledgements

TC has been supported by the EPSRC Programme Grant EP/S026347/1 and
acknowledges the support of the Erik Ellentuck Fellowship at the Institute for
Advanced Study. NZ has been supported by the Roth Scholarship at Imperial
College London. For the purpose of open access, the author(s) has applied a
Creative Commons Attribution (CC BY) licence (where permitted by UKRI, ‘Open
Government Licence’ or ‘Creative Commons Attribution No-derivatives (CC BY-ND)
licence’ may be stated instead) to any Author Accepted Manuscript version
arising.

## References

  * [AB07] C.D. Aliprantis and K.C. Border “Infinite Dimensional Analysis: A Hitchhiker’s Guide” Springer, 2007
  * [AGA13] Mennatallah Amer, Markus Goldstein and Slim Abdennadher “Enhancing one-class Support Vector Machines for unsupervised anomaly detection” In _Proceedings of the ACM SIGKDD Workshop on Outlier Detection and Description, ODD 2013_ , 2013, pp. 8–15
  * [Aky+22] Erdinc Akyildirim, Matteo Gambara, Josef Teichmann and Syang Zhou “Applications of Signature Methods to Market Anomaly Detection” In _Preprint, arXiv 2201.02441_ , 2022
  * [Aky+23] Erdinc Akyildirim, Matteo Gambara, Josef Teichmann and Syang Zhou “Randomized Signature Methods in Optimal Portfolio Selection” In _Preprint, arXiv 2312.16448_ , 2023
  * [AR14] Ana Arribas-Gil and Juan Romo “Shape outlier detection and visualization for functional data: the outliergram” In _Biostatistics_ 15.4, 2014, pp. 603–619
  * [Ara81] Jonathan Arazy “More on Convergence in Unitary Matrix Spaces” In _Proceedings of the American Mathematical Society_ 83.1, 1981, pp. 44–48