Open AccessArticle

Self-Supervised Autoencoders for Visual Anomaly Detection

Alexander Bauer

^1,2,*,

Shinichi Nakajima

^1,2,3

and

Klaus-Robert Müller

^1,2,4,5,*

Berlin Institute for the Foundations of Learning and Data, 10587 Berlin, Germany

Machine Learning Group, Technische Universität Berlin, 10587 Berlin, Germany

RIKEN Center for AIP, Tokyo 103-0027, Japan

⁴

Department of Artificial Intelligence, Korea University, Anam-dong, Seongbuk-gu, Seoul 02841, Republic of Korea

⁵

Max-Planck-Institut für Informatik, Saarland Informatics Campus E1 4, 66123 Saarbrücken, Germany

Authors to whom correspondence should be addressed.

Mathematics 2024, 12(24), 3988; https://doi.org/10.3390/math12243988

Submission received: 18 November 2024 / Revised: 13 December 2024 / Accepted: 15 December 2024 / Published: 18 December 2024

(This article belongs to the Special Issue Advanced Research in Neural Networks, Machine Learning, and Image Processing)

Download

Browse Figures

Versions Notes

Abstract

We focus on detecting anomalies in images where the data distribution is supported by a lower-dimensional embedded manifold. Approaches based on autoencoders have aimed to control their capacity either by reducing the size of the bottleneck layer or by imposing sparsity constraints on their activations. However, none of these techniques explicitly penalize the reconstruction of anomalous regions, often resulting in poor detection. We tackle this problem by adapting a self-supervised learning regime that essentially implements a denoising autoencoder with structured non-i.i.d. noise. Informally, our objective is to regularize the model to produce locally consistent reconstructions while replacing irregularities by acting as a filter that removes anomalous patterns. Formally, we show that the resulting model resembles a nonlinear orthogonal projection of partially corrupted images onto the submanifold of uncorrupted examples. Furthermore, we identify the orthogonal projection as an optimal solution for a specific regularized autoencoder related to contractive and denoising variants. In addition, orthogonal projection provides a conservation effect by largely preserving the original content of its arguments. Together, these properties facilitate an accurate detection and localization of anomalous regions by means of the reconstruction error. We support our theoretical analysis by achieving state-of-the-art results (image/pixel-level AUROC of 99.8/99.2%) on the MVTec AD dataset—a challenging benchmark for anomaly detection in the manufacturing domain.

Keywords:

anomaly detection; self-supervised; autoencoders; manifolds

MSC:

68T07

1. Introduction

The task of anomaly detection (AD) in a broad sense corresponds to searching for patterns that considerably deviate from some concept of normality. The criteria for what is normal and what is an anomaly can be very subtle and depend heavily on the application. Visual AD specifically aims to detect and locate anomalous regions in imagery data, with practical applications in the industrial, medical, and other domains [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17]. The continuous research in this area has produced a variety of methods ranging from classical unsupervised approaches like PCA [18,19,20], one-class SVM [21], SVDD [22], nearest neighbor algorithms [23,24], and KDE [25] to more recent methods including various types of autoencoders [5,12,26,27,28,29,30,31,32], deep one-class classification [33,34,35], generative models [6,13], self-supervised approaches [1,3,36,37,38,39,40,41], and others [3,7,8,9,10,11,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79].

The one-class classifiers [21,22], for example, aim at learning a tight decision boundary around the normal examples in the feature space and define a distance-based anomaly score relative to the center of the training data. The success of this approach strongly depends on the availability of suitable features. Therefore, it usually allows only for the detection of outliers that greatly deviate from the normal structure. In practice, however, we are often interested in more subtle deviations, which require a good representation of the data manifold. The same applies to combined approaches based on training deep neural networks (DNNs) with a one-class objective [35,80,81]. Although this objective encourages the network to concentrate the training data in a small region in the feature space, there is no explicit motivation for anomalous examples to be mapped outside of the decision boundary. In fact, the one-class objective gives preference to models that map its input domain to a narrower region and does not explicitly focus on separating anomalous examples from the normal data.

Recently, deep autoencoders (AEs) have been used for the task of anomaly detection in the visual domain [1,40,41]. Unlike the one-class approaches, they additionally enable the localization of anomalous regions by exploiting the pixel-wise nature of a corresponding training objective. By optimizing for the reconstruction error using anomaly-free examples, a common belief is that the corresponding network should fail to reconstruct anomalous regions in the application phase. Typically, this goal is achieved by controlling the capacity of the model either directly by reducing the size of the bottleneck layer or implicitly by imposing sparsity constraints on parts of the corresponding network [32,82,83,84,85]. However, neither of these techniques explicitly penalizes the reconstruction of anomalous regions, often resulting in poor detection. This is similar to the problem of training with the one-class objective, where no explicit mechanism exists for preventing anomalous examples from being mapped to the normal region. In fact, unsupervised trained AEs aim to compress and accurately reconstruct the input images and do not care much about the actual distinction between normal and anomalous samples. As a result, the reconstruction errors for the anomalous and normal regions can be very similar, preventing reliable detection and localization.

In this paper, we propose a self-supervised learning framework, which introduces discriminative information during training to prevent the good reconstruction of anomalous patterns in the testing phase. We begin with an observation that the abnormality of a region in the image is partially characterized by how well it can be reconstructed from the context of the surrounding pixels. Imagine an image where a small patch has been cut out by setting the corresponding pixel values to zeros. We can try to reconstruct this patch by interpolating the surrounding pixel values according to our knowledge about the distribution of the training data. If the reconstruction significantly deviates from the original content, we consider a corresponding patch to be anomalous and normal otherwise. Following this idea, we feed partially distorted images to the network during training while forcing it to recreate the original content—similar to the task of neural image completion [86,87,88,89,90,91]. However, instead of setting the individual pixel values to zeros—as for the completion task—we apply a patch transformation, which avoids introducing easily detectable artifacts. To succeed, our model must accomplish two different tasks: (a) detection of regions deviating from the expected pattern and (b) recreation of the original content from the uncorrupted areas. The second task, in particular, imposes an important regularization effect on the model. Together, they provide a powerful training signal for an accurate AD.

Technically, our approach can be seen as training a denoising autoencoder (DAE) on artificially corrupted inputs following a specific noise model. Although the general objective of DAEs allows for arbitrary stochastic corruptions, previous works [85,92,93] only considered simple unstructured noise, which can be characterized by the i.i.d. assumption on the distribution of the individual pixels. In contrast, we consider structured noise with spatial dependencies between the corruption variables implemented by a specific form of partial occlusions. Altogether, the resulting training effect regularizes the model to produce locally consistent reconstructions while replacing irregularities, therefore acting as a filter that removes anomalous patterns. Figure 1 illustrates a few examples to give a sense of visual quality of the resulting heatmaps when training according to our approach.

To support our idea, we performed a theoretical analysis of the proposed method, which provided a number of interesting insights. Specifically, we show that the resulting model approximates a mapping, which, with an increasing number of image pixels, converges (stochastically) to the orthogonal projection of partially corrupted images onto the submanifold of normal examples. This is consistent with the findings in [85] showing that, in a non-degenerate case (i.e., for distributions

p (x)

with support of nonzero volume) with i.i.d. pixel noise, the optimal reconstruction

r^{*}

is given by a mapping that corrects the noisy inputs by pushing them toward the region of high probability density according to

r^{*} (x) = x + σ^{2} \nabla log p (x) + o (σ^{2})

σ^{2} \to 0

. These results approach a point mass distribution collapsing to a lower-dimensional manifold, where we talk about projections and establish here the following complementary connection. While the gradient

\nabla log p (x)

points in the direction of the maximal increase in probability at point

x

, the orthogonal projection onto the data manifold is characterized by the shortest distance between

x

and its projected image. Therefore, we can naturally measure the abnormality of anomalous samples according to their distance from the manifold of normal examples.

Additionally, we investigate the effect of projection mappings on the segmentation accuracy of anomalous regions. Specifically, we analyze the conservation property of the orthogonal projection, which removes anomalous patterns in a way that largely preserves the original content. Furthermore, we establish a close connection of our approach to the previous autoencoding models including the contractive and denoising variants. In particular, we show that the orthogonal projection provides an optimal solution for the reconstruction contractive autoencoder.

The rest of this paper is organized as follows: In Section 2, we outline the main differences between our approach and related methods, concluding with a concise summary of our contributions. In Section 3, we formally introduce the proposed framework including training objective, data generation, and model architecture, followed by a theoretical analysis in Section 4. In Section 5, we evaluate the performance of our approach and provide a conclusion in Section 6.

2. Related Works

The plethora of existing AD methods (see [78] for an overview) can be roughly divided in three groups: probabilistic models, one-class classification methods, and reconstruction models; our approach is a member of the latter. Without going deeper into the details, we note that the first two groups appear less suitable in our case, where the data distribution is supported by a lower-dimensional embedded manifold. Due to this fact, the Lebesgue measure of the data manifold is zero excluding the existence of a density function over the input space, which takes positive values only on the manifold. On the other hand, one-class approaches implicitly assume a nonzero volume of the corresponding data in order to provide accurate detection results, which again violates our assumption about the data distribution.

Here, we focus on the reconstruction methods represented by the regularized AEs including the contractive [84] and denoising [92] variants and a number of self-supervised methods inspired by the task of neural image completion [1,40,41]. The central idea behind the contractive autoencoder (CAE), for example, is to learn a reconstruction mapping

r (x) = d (e (x))

composed of encoder and decoder parts by adding a regularization term

∥ D_{x} {e ∥}_{F}^{2}

to the objective, which implicitly promotes a reduction in the magnitude of gradients

\partial_{v} e (x)

in direction

v

pointing outside the tangent plane on the data manifold. In contrast, the denoising autoencoder (DAE) aims to minimize the reconstruction error without regularization terms but augments the training procedure by adding stochastic noise to the inputs.

Previous work [85] demonstrated that a DAE with small noise corruption of variance

σ^{2}

is similar to a CAE with penalty coefficient

λ = σ^{2}

but where the contraction is imposed explicitly on the whole reconstruction function rather than on the encoder part alone. Our approach is also based on training a model to reconstruct original content from modified inputs but differs from the previous works on DAE by using more involved input modifications beyond the i.i.d. corruption noise. Specifically, the corruptions introduced during training may represent additive noise, stochastic occlusions, and even deterministic modifications (e.g., geometric transformations), allowing for a wider range of anomalous patterns to be detectable during the application phase.

Another group of related methods has been inspired by the task of neural image completion [86,87,88,89,90,91]. This group includes a number of self-supervised methods like LSR [3], RIAD [39], CutPaste [40], InTra [41], DRAEM [38], and SimpleNet [94], which (similar to our approach) aim at training a model to reconstruct the original content from corrupted inputs in either the latent or the input space. The main differences of these methods from our approach are in the choice of data augmentation during training and the specific network architecture of our model, which in summary ked to higher performance in our experiments on the MVTec AD dataset [95]. Another two recent studies (PatchCore) [10] and (PNI) [68] reported impressive results on this benchmark. Both are based on the usage of memory banks comprising locally aware nominal patch-level feature representations extracted from pretrained networks. In contrast, our approach neither requires pretraining nor additional storage room for the memory bank and performs on par with the two methods. In the following, we briefly summarize our contributions.

As our first contribution, we formulated an effective AD framework for a special use case (e.g., natural images), where the normal examples exist on a lower-dimensional submanifold embedded in the input space and are restricted by an additional assumption on the covariance between the spatially close components to vanish with increasing distance. While similar ideas have been used in different domains, our approach distinguishes itself by the specific form of the noise model (implemented by partial occlusions with complex shapes) and the network architecture (SDC-AE and SDC-CCM) that together produce a solution which consistently outperforms previous methods. In particular, we achieved state-of-the-art results for both detection (AUROC of 99.8%) and localization (AUROC of 99.2%) tasks on the MVTec AD dataset—a challenging benchmark for visual anomaly detection in the manufacturing domain.

As our second contribution, we performed a rigorous theoretical analysis of our method, which provided a number of interesting insights. Specifically, we show that with an increasing number of input pixels, the corresponding model resembles the orthogonal projection of partially corrupted images onto the submanifold of uncorrupted examples. This covers various forms of input modifications including partial occlusions and additive noise (see Theorem 1 and Theorem 2). At the same time, orthogonal projection acts as a filter for irregularities by removing anomalous patterns from the inputs in a way that largely preserves the original content (see Proposition 2 and Proposition 3). Together, these properties facilitate the accurate detection and localization of the anomalous regions by means of the reconstruction error, supporting our hypothesis around the training procedure.

As our third contribution, we improved upon the previous understanding of the connections between contractive and denoising autoencoders. Specifically, we identified the nonlinear orthogonal projection as an optimal solution (see Proposition 1), minimizing the training objective of the reconstruction contractive autoencoder (RCAE). On the other hand, our training objective essentially corresponds to training a DAE with a specific noise model, imposing strong spatial correlation on the corruption variables. A corresponding model, in turn, approximates a mapping that (with the increasing number of input pixels) converges stochastically to the orthogonal projection—the optimal solution of the RCAE. In contrast to the previous results [85], our findings extend beyond the i.i.d. variable noise and are not limited by the assumption of small variance.

3. Methodology

In the following, we formally introduce our self-supervised framework for training a model to detect and localize anomalous regions in images. We provide a detailed description of the objective function, the structure of artificially generated anomalies used during training, and the rationale behind our choice of model architecture.

3.1. Training Objective

We identify an autoencoder with input and output tensors corresponding to color images with a parameterized map

f_{θ} : {[0, 1]}^{h \times w \times 3} \to {[0, 1]}^{h \times w \times 3}

h, w \in N

. Furthermore,

x \in {[0, 1]}^{h \times w \times 3}

denotes an original (anomaly-free) image, and

\hat{x}

denotes a copy of

x

that has been partially modified. The modified regions within

\hat{x}

are encoded through a real-valued mask

M \in {[0, 1]}^{h \times w \times 3}

, while

\bar{M} : = 1 - M

denotes a corresponding complement, with

1 \in {1}^{h \times w \times 3}

being a tensor of ones. Our goal is to train a model

f_{θ}

that projects arbitrary inputs from the data space to the submanifold of normal images by minimizing for each triple

(x, \hat{x}, M)

, with the following objective:

\begin{matrix} L (\hat{x}, x, M) = \frac{(1 - λ)}{∥ \bar{M} ∥_{1}} \cdot ∥ \bar{M} ⊙ (f_{θ} (\hat{x}) - x) ∥_{2}^{2} + \frac{λ}{{∥ M ∥}_{1}} \cdot {∥ M ⊙ (f_{θ} (\hat{x}) - x) ∥}_{2}^{2}, \end{matrix}

(1)

where ⊙ denotes an element-wise tensor multiplication, and

λ \in [0, 1]

is a hyperparameter controlling the importance of the two terms during training. Here,

{∥ \cdot ∥}_{p}

denotes the

l^{p}

-norm on a corresponding tensor space. In terms of supervised learning, we feed a partially corrupted image

\hat{x}

as input to the network, which is trained to recreate the original image

x

representing the ground truth label.

By minimizing the above objective, the corresponding autoencoder aims to interpolate between two different tasks. The first term steers the model to reproduce uncorrupted image regions

\bar{M} ⊙ x

, while the second term requires the network to correct the corrupted regions

M ⊙ \hat{x}

by recreating the original content. Altogether, the objective in (1) encourages the model to produce a locally consistent reconstruction of the input while replacing irregularities, acting as a filter for anomalous patterns. Figure 2 shows a few reconstruction examples produced by our model

f_{θ}

. We can see how normal regions are accurately replicated, while irregularities (e.g., scratches or threads) are replaced by locally consistent patterns. During training, we use a specific procedure to generate corrupted images

\hat{x}

from normal examples

x

based on randomly generated masks

M

marking the corrupted regions. We provide a detailed description of this process in the next subsection.

Given a trained model

f_{θ}

, we can perform AD on an input image

\hat{x}

as follows: First, we compute the difference map

Diff [\hat{x}, f_{θ} (\hat{x})] \in R^{h \times w}

between the input

\hat{x}

and its reconstruction

f_{θ} (\hat{x})

by averaging the pixel-wise squared difference

{(\hat{x} - f_{θ} (\hat{x}))}^{2}

over the color channels according to

Diff [\hat{x}, f_{θ} (\hat{x})] : = \frac{1}{3} \sum_{c = 1}^{3} [{({\hat{x}}_{*, *, c} - f {(\hat{x})}_{*, *, c})}^{2}] .

(2)

The binary segmentation mask can be computed by thresholding the difference map. To obtain a more robust result, we smooth the difference map before thresholding according to the following formula:

{anomap}_{f_{θ}}^{n, k} (\hat{x}) : = G_{k}^{n} (Diff [\hat{x}, f_{θ} (\hat{x})]),

(3)

where

G_{k}^{n} = {\underset{︸}{G_{k} \circ \dots \circ G_{k}}}_{n - times}

denotes a repeated application of a convolution mapping

G_{k}

defined by an averaging filter of size

k \times k

with all entries set to

1 / k^{2}

. We treat the numbers

n, k \in N

k ⩾ 1

as hyperparameters, where

G_{k}^{0}

is the identity mapping. By thresholding

{anomap}_{f_{θ}}^{n, k} (\hat{x})

, we obtain a binary segmentation mask for the anomalous regions. We compute the anomaly score for the entire image

\hat{x}

from

{anomap}_{f_{θ}}^{n, k} (\hat{x})

by summing the scores for the individual pixels. Note that for

n = 0

, if we skip the averaging step over the color-channels in (2), this reduces to

∥ \hat{x} - f_{θ} (\hat{x}) ∥_{2}^{2}

. Alternatively to the summation, we could take the maximum over the pixel scores, making the anomaly score potentially less sensitive to size variations in the anomalous regions. The complete detection procedure is summarized in Figure 3. In Section 4, we investigate which image corruptions approximately preserve the orthogonality of the corresponding transformations.

3.2. Generating Artificial Anomalies for Training

We use a self-supervised approach representing the training data as input–output

(\hat{x}, x)

pairs. Here, the ground truth outputs are given by the original images

x

corresponding to the normal examples. The inputs

\hat{x}

are generated from these images by partially modifying some regions according to the procedure illustrated in Figure 4.

For each normal example

x

, we first randomly sample the number, the size, and the location of the patches to be modified. In the next step, each randomly selected patch is modified according to the following procedure: First, we create a real-valued mask

M \in {[0, 1]}^{\tilde{h} \times \tilde{w} \times 3}

based on the elastic deformation technique to mark the corrupted regions within the selected patch. Precisely, we start with a static mask shaped as a disk at the center of the patch with a smoothly fading boundary toward the exterior of the disk. We then apply Gaussian distortion (with random parameters) to this mask, resulting in the varying shapes illustrated on the right side in Figure 4. These masks are used to smoothly merge the original patches with the new content given by the replacement patches. Here, we consider two types of replacements. On the one hand, we can use any natural image (sufficiently different from the original patch) as a potential replacement. In our experiments, we used the publicly available Describable Textures Dataset (DTD) [96], consisting of images of varying backgrounds. On the other hand, we can use the extracted patches as replacements after passing them through a Gaussian distortion process, similar to how we create the masking shapes. An important aspect here is that the corresponding corruptions approximately preserve the original color distribution.

Given an input

x

and a replacement

y

, we create a corrupted image

\hat{x}

by smoothly gluing the two images together according to the formula

\hat{x} : = M ⊙ y + \bar{M} ⊙ x

. In the last step, the patches extracted at the beginning are replaced with their modified versions in the original image. The individual shape masks are embedded in a two-dimensional zero-array at the corresponding locations to create a global mask

M \in {[0, 1]}^{h \times w \times 3}

. During testing phase, there are no input modifications, and images are passed unchanged to the network. Anomalous regions are detected by thresholding the anomaly heatmap

{anomap}_{f_{θ}}^{n, k} (\hat{x})

defined in Equation (3).

3.3. Model Architecture

We adopt a well-established encoder–decoder architecture commonly used in computer vision tasks such as semantic segmentation [97,98], image inpainting [87,88,89], representation learning [86], and anomaly detection [1,2,91]. Specifically, the encoder is composed of convolutional layers that progressively reduce spatial dimensions while increasing the number of feature maps. Conversely, the decoder gradually restores spatial dimensions while reducing the number of output channels. In contrast to common practices, we also incorporate dilated convolutions [99], which enable the model to efficiently capture long-range dependencies between individual pixels and their local neighborhoods. This modification has two key effects: it allows access to richer contextual information without increasing the network depth and helps address larger anomalous regions that would otherwise be affected by a blind spot phenomenon, as shown in Figure A3 in Appendix I. Due to the interplay between the training objective and the network architecture, the model naturally adopts a filtering behavior by replacing anomalous patterns in the input images with locally consistent reconstructions. We demonstrate the reconstruction effect with several examples in Figure 2.

The overall architecture is summarized in Table 1.

Here, after each convolution Conv (except in the last layer), we use batch normalization and rectified linear units (ReLUs) as the activation function. Max-pooling MaxPool is applied to reduce the spatial dimension of the intermediate feature maps. TranConv denotes the convolution transpose operation and also uses batch normalization with ReLUs. In the last layer, we use a sigmoid activation function without batch normalization.

{SDC}_{1, 2, 4, 8, 16, 32}

refers to a stacked dilated convolution block in which multiple dilated convolutions are stacked together. The corresponding subscript

{1, 2, 4, 8, 16, 32}

denotes the dilation rates of the six individual convolutions in each stack. After each stack we add an additional convolutional layer with the kernel size

3 \times 3

and the same number of feature maps as in the stack followed by a batch normalization and ReLU activation. We refer to this baseline architecture as SDC-AE, indicating an autoencoder (AE) that relies on stacked dilated convolutions (SDCs).

In our experiments, we observed that SDC-AE struggled to reproduce finer visual patterns, sometimes resulting in false positive detections. In order to improve the reconstruction ability, we proposed the following adjustment illustrated in Figure 5. Similar to the approach commonly used in image segmentation, we introduce skip connections into the network. However, direct access to the feature maps from earlier stages appears counterproductive, as it may interfere with other parts of the computational flow that are essential for suppressing corrupted regions in intermediate representations. Instead, we combine information from different layers of the network using a specific type of attention mechanism. Specifically, we first compute a tensor of coefficients ranging from zero to one, which we then use to calculate a component-wise convex combination of the individual feature maps. The corresponding procedure is illustrated in Figure 6. The idea behind this approach is that it provides the model with a more explicit mechanism for reusing, refining, or replacing regions of the input based on its assessment of the abnormality of a given region. We consolidate the corresponding computations into a single convex combination module (CCM), highlighted in brown in Figure 5. We refer to this architecture as SDC-CCM.

In our experiments on the MVTec AD dataset, we observed a significant performance boost in some object categories when using SDC-CCM over SDC-AE. See Figure A4 in Appendix J for a comparison of the reconstruction quality between the models.

4. Theoretical Analysis

In this section, we provide a number of theoretical insights supporting our idea behind the proposed AD method. We begin by establishing a close connection to the related regularized AEs by identifying the orthogonal projection as an optimal solution for the optimization problem of the RCAE. We then investigate the conservation properties of the orthogonal projection with respect to the segmentation accuracy in the context of AD. As our main result, we show that under certain conditions the resulting model approximates a mapping that stochastically converges (with an increasing number of input pixels) to the orthogonal projection of partially corrupted images onto the submanifold of uncorrupted examples.

For the purpose of the following analysis, we identify each projecting autoencoder (PAE) with an idempotent mapping

f : U \to R^{n}

from an input space

U \subseteq R^{n}

n \in N

to a differentiable manifold

D : = f (U) \subseteq U

\dim (D) < n

. In the context of AD, we refer to the manifold

D

as the (nonlinear) subspace of normal examples, while each

\hat{x} \in R^{n} ∖ D

is considered anomalous. In particular, we exploit a generalization of orthogonal projection to nonlinear mappings defined below and illustrated in Figure 7.

Definition 1.

For

n \in N

in a metric space

(R^{n}, d (\cdot, \cdot))

, we call a (nonlinear) mapping

f : U \to R^{n}

U \subseteq R^{n}

the orthogonal projection onto

D \subseteq R^{n}

if it satisfies the equality

d (\hat{x}, f (\hat{x})) = inf_{y \in D} d (\hat{x}, y)

(4)

for all

\hat{x} \in U

Note that the expression in (4) can be written as a set of inequalities. Namely, for

d (\hat{x}, f (\hat{x})) : = {∥ \hat{x} - f (\hat{x}) ∥}_{2}

, we obtain the following alternative description:

\forall y \in D : ∥ \hat{x} - f (\hat{x}) ∥_{2} ⩽ {∥ \hat{x} - y ∥}_{2} .

(5)

We use form (5) in Section 4.3.

In order to train a PAE, we minimize the following objective

L_{PAE} [f] = E_{x, T} [{∥ f (T (x)) - x ∥}_{p}^{p}],

(6)

where

p \in N_{+}

, and

T : D \to R^{n}

denotes some random data transformation. That is, the expectation in (6) is taken with respect to

x \in D

and

T \in T

. Note how the above objective is related to our training objective in (1). There, we explicitly use a mask

M

only to balance the training with respect to the reconstruction accuracy of normal and anomalous regions. If we fix the value of

{∥ M ∥}_{1}

and set

λ = {∥ M ∥}_{1} / {(∥ M ∥}_{1} + ∥ \bar{M} ∥_{1})

, the objective (1) reduces to minimizing the loss

L (\hat{x}, x) = {∥ f_{θ} (\hat{x}) - x ∥}_{2}^{2}

. Here, the shape of

T

mainly determines the properties of the projection map to be learned, which in turn simulates the inverse mapping of the corresponding input corruptions T. Depending on our goal,

T

can be very specific ranging from additive noise (e.g., Gaussian noise) to partial occlusions and elastic deformations. In Section 4.3, we identify a number of input transformations that (asymptotically) preserve the orthogonality of the corresponding projections.

4.1. Connections to Regularized Autoencoders

Typically, an autoencoder is composed from two building blocks: the encoder

e (\cdot)

, which maps the input

x

to some internal representation, and the decoder

d (\cdot)

, which maps

e (x)

back to the input space. The composition

f (x) = d (e (x))

is often referred to as the reconstruction mapping. Most of the regularized autoencoders aim to capture the structure of the training distribution based on an interplay between the reconstruction error and the regularization term. They are trained by minimizing the reconstruction loss on the training data either by directly adding a regularization term to the objective or by introducing the regularization through some kind of data augmentation.

Specifically, the contractive autoencoder (CAE) [84] is trained to minimize the following regularized reconstruction loss

L_{CAE} [f] = E_{x} [{∥ f (x) - x ∥}_{2}^{2} + λ {∥ D_{x} e ∥}_{F}^{2}],

(7)

where

λ \in R_{+}

is a weighting hyperparameter, and

∥ D_{x} {e ∥}_{F}

is the Frobenius norm of the Jacobian of the encoder

e (\cdot)

The denoising autoencoder (DAE) [92], on the other hand, is trained to minimize the following denoising criterion

L_{DAE} [f] = E_{x, ε} [{∥ f (x + ε) - x ∥}_{2}^{2}],

(8)

where

ε

represents some additive noise, and the expectation is over the training distribution and the corruption noise. Specifically, the term noise includes additive (e.g., isotropic Gaussian noise) and non-additive transformation (e.g., masking pepper-noise). However, the unifying feature of the considered corruptions is that the transformations of the individual entries in the input are statistically independent. In contrast, in (6), we consider more complex modifications, which result in the strong spatial correlation of the corruption variables). Note that the general objective of the DAE allows for arbitrary stochastic corruptions. However, previous theoretical investigations including [85] focused on (mostly additive) unstructured noise, which can be characterized by the i.i.d. assumption on the distribution of the individual pixels. The results in [85] demonstrate that there is close connection between the CAE and DAE when the standard deviation of the corruption noise approaches zero

σ \to 0

. More precisely, under some technical assumptions, the objective of the DAE can be written as

L DAE [f] = E_{x} [{∥ f (x) - x ∥}_{2}^{2} + σ^{2} {∥ D_{x} f ∥}_{F}^{2}]

(9)

σ \to 0

. That is, for a small variance

σ^{2}

of the corruption noise, the DAE becomes similar to a CAE with penalty coefficient

λ = σ^{2}

but where the contraction is imposed explicitly on the whole reconstruction mapping f. This connection motivated the authors to define the RCAE, a variation of the CAE by minimizing the following objective:

L_{RCAE} [f] = E_{x} [{∥ f (x) - x ∥}_{2}^{2} + λ {∥ D_{x} f ∥}_{F}^{2}],

(10)

where the regularization term affects the whole reconstruction mapping. Finally, a common variant of the SAE applies an

l^{1}

penalty on the hidden unit activations, effectively making them saturate toward zero—similar to the effect in the CAE.

We now show that a PAE, realized by the orthogonal projection onto the submanifold of normal examples, is an optimal solution that minimizes the objective of the RCAE in (10). We provide a formal proof in Appendix F.

Proposition 1.

Let

f^{*} : U \subseteq R^{n} \to R^{n}, n \in N

be an orthogonal projection onto

D : = f^{*} (U)

with respect to an

l^{p}

-norm,

p \in N_{+}

. Then,

f^{*}

is an optimal solution to the following optimization problem:

\underset{f \in C^{1}}{minimize} E_{x \sim D} [{∥ f (x) - x ∥}_{2}^{2} + λ {∥D_{x} f∥}_{q}^{2}],

(11)

where

λ \in R_{+}

, and

q \in {F, 2}

is a placeholder denoting either the Frobenius or the spectral norm.

Note that the objective in the above proposition is slightly more general than that in (10) allowing the use of the spectral norm. Although being closely related to each other, the Frobenius and the spectral norm might have different effects on the optimization. Namely, the spectral norm measures the maximal scale by which a unit vector is stretched by a corresponding linear transformation and is determined by the maximal singular value, while the Frobenius norm measures the overall distortion of the unit circle taking into account all the singular values. In a more general sense, Proposition 1 implies a close connection between the PAE and other types of regularized autoencoders (see Figure 8 for an overview).

Orthogonal projection, in particular, appears to be an appropriate choice with respect to the shared goals of the autoencoding models discussed in this section. In Section 4.3.2, we show that in the limit when the dimensionality of the inputs goes to infinity, the DAE converges stochastically to the orthogonal projection when restricted to the specific noise corruptions.

4.2. Conservation Effect of Orthogonal Projections

Here, we focus on the subtask of AD regarding the segmentation of anomalous regions in the inputs. In the following, we identify each image tensor with a column vector

x \in R^{n}

, where

S \subset {1, \dots, n}

and

\bar{S} : = {1, \dots, n} ∖ S

denote a set of pixel indices and its complement, respectively. We write

x_{S}

to denote a restriction of a vector

x

to the indices in S.

Consider an

\hat{x} \in R^{n}

that has been generated by a (partial) modification

\hat{x} : = T (x)

T \in T

from an

x \in D

. We define the modified region as the set of disagreeing indices according to

S (\hat{x}, x) : = \{i \in {1, \dots, n} : {\hat{x}}_{i} \neq x_{i}\} .

(12)

There is some ambiguity about what might be considered an anomalous region, which motivates the following definition:

Definition 2.

Let

D \in R^{n}

n \in N

be a data manifold. Given

\hat{x} \in R^{n} ∖ D

, we define the set of anomalous regions in

\hat{x}

as the areas of smallest disagreement according to

A (\hat{x}) : = \{S (\hat{x}, x) : x \in \underset{y \in D}{argmin} | S (\hat{x}, y) |\} .

(13)

We refer to each

S \in A (\hat{x})

as an anomalous region to the pair

(S, {\hat{x}}_{S})

as an anomalous patternand to

\hat{x}

as an anomalous sample.

We now provide some explanation of the motivation of our definition of anomalous patterns. Consider an example of binary sequences

x \in {0, 1}^{8}

restricted by a condition that the pattern “11” is forbidden. For example, the sequence (0, 1, 0, 1, 1, 1, 1, 0) is invalid because it contains “11”. If we define the anomalous region as the smallest subset of indices that need to be corrected in order for the point to be projected to the data manifold, we encounter the following ambiguity problem. Namely, there are three different ways to correct the above example using minimal number of changes:

(0, 1, 0, 1, 0, 1, 0, 0); (0, 1, 0, 0, 1, 0, 1, 0); and (0, 1, 0, 1, 0, 0, 1, 0), which we denote as

y_{1}

y_{2}

and

y_{3}

, respectively. All three sequences correspond to orthogonal projections to the feasible set, where

∥ \hat{x} - y_{1} ∥_{2} = ∥ \hat{x} - y_{2} ∥_{2} = {∥ \hat{x} - y_{3} ∥}_{2} = \sqrt{2}

. However,

⋂_{i = 1}^{3} S (\hat{x}, y_{i}) \neq ⋃_{i = 1}^{3} S (\hat{x}, y_{i}) .

(14)

That is, there are multiple anomalous patterns giving rise to the same corrupted point

\hat{x}

. In particular, the anomalous regions in

\hat{x}

are not uniquely determined and depend on the structure of

D

. Based on this observation, we highlight a special projection map below, which maximally preserves the content of its arguments.

Definition 3.

For

n \in N

p \in N_{+}

, we call an idempotent mapping

f : U \to R^{n}

U \subseteq R^{n}

the conservative projection onto

D : = f (U) \subseteq U

with respect to the

l^{p}

-norm if, for each pair

(\hat{x}, x) \in U \times D

with

f (\hat{x}) = x

and

S : = S (\hat{x}, x)

, it satisfies the following properties:

\begin{matrix} (a) & S \in A (\hat{x}) \\ (b) & ∥ {\hat{x}}_{S} - f_{S} (\hat{x}) ∥_{p} ⩽ {inf}_{x \in D : {\hat{x}}_{\bar{S}} = x_{\bar{S}}} {∥ {\hat{x}}_{S} - x_{S} ∥}_{p} . \end{matrix}

The next proposition relates the conservation properties of orthogonal projections for different

l^{p}

-norms. See Figure 9 for an illustration. A corresponding proof is provided in Appendix G.

Proposition 2.

Let

D \subseteq R^{n}

n \in N

be a data manifold and

\hat{x} \in R^{n} ∖ D

be an anomalous sample. Furthermore, let

S \in A (\hat{x})

and

S_{p} : = S (\hat{x}, y_{p}^{*})

, where

y_{p}^{*} \in {inf}_{y \in D} {∥ \hat{x} - y ∥}_{p}

corresponds to the orthogonal projection of

\hat{x}

onto

D

with respect to the

l^{p}

-norm. For all

p, q \in N_{+}

p < q

, the following statements are true:

\begin{matrix} (a) & S \subseteq S_{p} \subseteq S_{q} \\ (b) & \exists D \subseteq R^{n} : S_{1} \neq S_{2} . \end{matrix}

The above proposition shows that orthogonal projection with respect to the

l^{p}

-norm is more conservative for lower

p ⩾ 1

values regarding the preservation of normal regions. However,

l^{2}

-norm has practical advantages over the

l^{1}

-norm regarding the optimization process and is, therefore, often a better choice. Furthermore, the orthogonal projection with respect to the

l^{2}

-norm (unlike the conservative projection) is not maximally preserving in general. We show later, however, that within the limit of the increasing input dimensionality, the conservative and the orthogonal projections (with respect to

l^{2}

-norm) disagree only on a zero-measure probability set.

While Proposition 2 describes the conservation properties of orthogonal projections relative to each other, the following proposition specifies (asymptotically) how accurate the corresponding reconstruction error is in describing the anomalous region. As an auxiliary concept, we here introduce the notion of a transition set (illustrated in Figure 10), which glues the disconnected parts of an input together. We provide more details in Appendix H.

Proposition 3.

Let

f : {[0, 1]}^{n} \to D \subseteq {[0, 1]}^{n}

n \in N

be the orthogonal projection with respect to an

l^{p}

-norm,

p \in N_{+}

and

x \in D

with a finite set of states

x_{i} \in I \subseteq [0, 1]

| I | < \infty

. Consider an

\hat{x} \in {[0, 1]}^{n}

that has been generated from

x

via partial modification with

{\hat{x}}_{\bar{S}} = x_{\bar{S}}

for some

S \subset {1, \dots, n}

\bar{S} : = {1, \dots, n} ∖ S

. Furthermore, let

B \subseteq {1, \dots, n}

denote a transition set from S to

\bar{S} ∖ B

. For all

p \in N_{+}

, the following holds true:

∥ f_{\bar{S}} (\hat{x}) - x_{\bar{S}} ∥_{p} ⩽ {| B |}^{\frac{1}{p}},

(15)

where

| B |

grows asymptotically according to

O (\sqrt{| S |})

When projecting corrupted points onto the data manifold, we would like the transition set B around the anomalous region S to be as small as possible. The inequality in (15) implicitly upper-bounds the number of entries in the normal region

\bar{S}

that are not preserved by the projection. This is mostly practical for lower values of p and least informative in the case

p = \infty

. Namely,

\lim_{n \to \infty} {| B |}^{\frac{1}{p}} = 1

provides a trivial upper bound, since

{∥ x ∥}_{\infty} ⩽ 1

for

x \in {[0, 1]}^{n}

. For

p = 1

, for example, the interpretation is the simplest in the case of finite sequences of binary values. The number of disagreeing components is then upper-bounded by the number

| B |

, corresponding to the size of the transition set, which, in turn, is determined by the form of the underlying data distribution.

To summarize, we showed that orthogonal projection with respect to the

l^{p}

-norm preserves the normal regions more accurately for smaller p-values. Furthermore, we identified the conservative projection as the one that is maximally preserving (unlike the orthogonal projection). As previously mentioned, we show in Section 4.3 that within the limit (when the dimensionality of the input vectors goes to infinity), the

l^{2}

-conservative and the

l^{2}

-orthogonal projection are the same up until a zero-measure probability set.

4.3. Convergence Guarantees for Input Corruptions

In the following, we specify a range of input modifications that (approximately) preserve the orthogonality of the corresponding projections. In the context of image processing, the plethora of existing data augmentation techniques can be roughly divided into five groups: affine transformations, color jittering, mixing strategies, elastic deformations, and additive noise. Here, we characterize each image transformation either as

(a)

a partial modification (of any type) or as

(b)

a modification affecting the entire image represented by the additive noise methods. Image mixing strategies like MixUp can simply be seen as a transformation with additive noise, while CutMix is an example of partial modification. On the other hand, linear and affine data transformations like shift, rotation, or color-channel permutation, in general, do not preserve orthogonality.

For the purpose of the subsequent analysis, we identify the image tensors in our input space with a multivariate random variable

x \in R^{n}

corresponding to Markov random fields (MRFs) [100,101,102,103,104,105,106,107,108]. In particular, we assume that the variables representing the individual pixels are organized in a two-dimensional grid. Based on this view, we consider sequences

D^{(n)} \subseteq {[0, 1]}^{n}

of spaces of increasing dimensionality

n \in N

, representing images of gradually increasing size by adding new nodes along the rows and columns of the grid. Furthermore, we use the notation

d_{G} (x_{i}, x_{j})

to denote the distance between the variables

x_{i}

and

x_{j}

in a corresponding MRF graph G defined by the number of edges on a shortest path connecting the two nodes.

4.3.1. Partial Modification

The following theorem describes the technical conditions under which a corresponding partial modification corresponds to the orthogonal projection. We provide a formal proof in Appendix D.

Theorem 1.

Consider a pair

x, y \in D^{(n)}

of independent MRFs over identically distributed variables

x_{i}, y_{j}

with finite fourth moment

E [x_{i}^{4}] < \infty

, variance

σ^{2} : = Var [x_{i}]

and vanishing covariance

Cov [x_{i}^{k}, x_{j}^{l}] ⟶ 0 f o r d_{G} (x_{i}, x_{j}) ⟶ \infty

(16)

for all

k, l \in {1, 2}

. Furthermore, let

\hat{x} \in {[0, 1]}^{n}

be a copy of

x

that has been partially modified, where

{\hat{x}}_{\bar{S}} = x_{\bar{S}}

for some

S \subset {1, \dots, n}

\bar{S} : = {1, \dots, n} ∖ S

. The following is true,

\lim_{n \to \infty} P_{x, y} (∥ \hat{x} {- x ∥}_{2} ⩽ {∥ \hat{x} - y ∥}_{2}) = 1,

(17)

provided the inequality

| S | ⩽ 2 \cdot σ^{2} \cdot | \bar{S} |

(18)

holds for all

n \in N

Given two samples

x, y \in D

and a corrupted copy

\hat{x} \in {[0, 1]}^{n}

, Theorem 1 describes how the expression

∥ \hat{x} {- x ∥}_{2} ⩽ {∥ \hat{x} - y ∥}_{2}

approaches a true statement when the dimensionality of the embedding space

n \in N

goes to infinity. In particular,

x

can be identified with the image of

\hat{x}

under the conservative projection

f (\hat{x}) = x

. That is,

\lim_{n \to \infty} P_{x, y} (∥ \hat{x} - f (\hat{x}) ∥_{2} ⩽ {∥ \hat{x} - y ∥}_{2}) = 1 .

(19)

Therefore, the conservative projection converges stochastically to the orthogonal projection (compare to the definition of the orthogonal projection in (5)), while the inequality in (18) controls the maximal size of corrupted regions

| S |

by taking into account the distribution of normal examples. On the other hand, Equation (19) suggests that (in the limit) the orthogonal and the conservative projection disagree at most on a subset of the data manifold

D

, which has a zero probability measure under the training distribution.

4.3.2. Additive Noise

The following theorem describes the technical conditions under which the denoising process (with additive noise) corresponds to the orthogonal projection. We provide a formal proof in Appendix E.

Theorem 2.

Consider a pair

x, y \in D^{(n)}

of independent MRFs over identically distributed variables

x_{i}, y_{j}

with finite fourth moment

E [x_{i}^{4}] < \infty

, variance

σ^{2} : = Var [x_{i}]

, and vanishing covariance

Cov [x_{i}^{k}, x_{j}^{l}] ⟶ 0 f o r d_{G} (x_{i}, x_{j}) ⟶ \infty

(20)

for all

k, l \in {1, 2}

. Furthermore, let

\hat{x} : = x + ε

be another MRF, where

ε = (ϵ_{1}, \dots, ϵ_{n})

is an additive noise vector of i.i.d. variables with

μ_{ε} : = E [ϵ_{i}]

and

σ_{ε}^{2} : = Var [ϵ_{i}]

. Then, the following holds true:

\lim_{n \to \infty} P_{x, y} (∥ \hat{x} {- x ∥}_{2} ⩽ {∥ \hat{x} - y ∥}_{2}) = 1,

(21)

provided

μ_{ε}^{2} + σ_{ε}^{2} ⩽ \frac{1}{2} σ^{2} .

(22)

In the special example of isotropic Gaussian noise

ε \sim N (0, σ_{ε}^{2} \cdot I)

, the condition in (22) is reduced to

σ_{ε}^{2} ⩽ \frac{1}{2} σ^{2}

. Here, again,

x

can be identified with the image of the conservative projection, which removes the specific type of noise from its arguments. The equation in (21) then implies its convergence to the orthogonal projection.

5. Experiments

In our experiments, we used the publicly available MVTec AD dataset [95,109]—a popular benchmark for anomaly detection in the manufacturing domain. It provides a diverse dataset with significant variations in materials and anomaly types, organized into 5 texture categories and 10 object categories. Each category encompasses multiple classes of anomalies, with the number of training examples ranging up to several hundred images. For a detailed technical description of the dataset, we direct the reader to the original publication [109]. During training, we artificially increased the amount of data by applying simple data augmentations, such as rotation and flipping, depending on the category. We used 5% of the data as a validation set. For the sake of reproducibility, we mention that for the transistor category, we used a random image rotation by multiples of 90 degrees, in addition to the artificial corruptions, during training. This made the training procedure considerably more challenging, but it proved essential for detecting missing objects.

For each category, we trained a separate model based on the proposed architectures (SDC-AE and SDC-CCM). For both models, we used the same image resolution of

512 \times 512

pixels for texture and

256 \times 256

pixels for object categories and the Adam optimizer [110] with initial learning rate of

10^{- 4}

. Note that our model architecture makes no assumptions about the size of the input images. The SDC-AE architecture, in particular, is fully convolutional and can be applied to any input size that is a multiple of the network’s stride after training. However, the input size is an important hyperparameter that influences the final performance of the anomaly detection. The resolution choices of 512 × 512 and 256 × 256 pixels appeared to work well with the considered dataset.

We report the pixel-level and the image-level AUROC metric to illustrate both segmentation and recognition performance in Table 2 and Table 3, respectively. We compare our results (for SCD-AE and SDC-CCM) with a number of previous methods like AnoGAN [6], VAE [9], and LSR [3], including top-ranking algorithms such as RIAD [39], CutPaste [40], InTra [41], DRAEM [38], SimpleNet [94], PatchCore [10], MSFlow [111], and PNI [68]. Our method achieves high performance with both architectures. However, SDC-CCM significantly outperforms SDC-AE in the cable, capsule, and transistor categories due to a reduction in false positive detections, supporting our idea about the CCM module. To further validate our choice of network architecture, we describe an additional ablation study in Appendix I. This study demonstrates the importance of dilated convolutions and the use of fine-grained information from earlier layers in subsequent layers, either through skip connections or the proposed CCM module. To give a sense of the visual quality of the resulting anomaly heatmaps produced by our method, we show a few additional examples in Figure 11.

6. Conclusions

We focused on an important use case for anomaly detection, where the data distribution is supported by a lower-dimensional manifold, and the covariance between neighboring input components vanishes as the distance increases. Our self-supervised approach aims to learn a reconstruction model that repairs artificially corrupted inputs based on a specific form of stochastic occlusions. The resulting training effect regularizes the model to produce locally consistent reconstructions while replacing irregularities, thus acting as a filter that removes anomalous patterns. We demonstrated the effectiveness of our approach by achieving state-of-the-art results on the MVTec AD dataset, a challenging benchmark for visual anomaly detection in the manufacturing domain.

Additionally, we performed a theoretical analysis of the proposed method, providing several interesting insights. As our main result, we showed that as the dimensionality of the inputs increases, the corresponding model approximates a mapping that stochastically converges to the orthogonal projection of partially corrupted inputs onto the submanifold of uncorrupted examples. (According to our training objective in (1), an optimal solution is given by a model

f^{*}

, such that

f_{S}^{*} (\hat{x}) = E_{x \sim D} [x_{S} | {\hat{x}}_{\bar{S}}]

. Therefore,

f^{*} (\hat{x})

does not necessarily lie in

D

and the corresponding approximation error depends on the variance of

x_{S}

given

x_{\bar{S}}

). If the covariance between the input variables (with increasing distance) rapidly approaches zero, the orthogonal projection maps its input in a way that largely preserves the original content, supporting our intuition about the filtering behavior of the model. Therefore, we can jointly perform the detection and localization of corrupted regions using the pixel-wise reconstruction error.

Furthermore, we deepened the understanding of the relationship between regularized autoencoders. Specifically, we showed that the orthogonal projection provides an optimal solution for the RCAE, which was demonstrated to be equivalent to the DAE for small variance in the corruption noise. Our results extend this equivalence to more complex input modifications beyond i.i.d. pixel corruptions and provide a unifying perspective on the regularized autoencoders that is not limited by the assumption of small variance.

Author Contributions

Conceptualization, A.B.; Methodology, A.B.; Software, A.B.; Validation, A.B.; Formal Analysis, A.B.; Investigation, A.B., S.N. and K.-R.M.; Writing—Original Draft, A.B.; Writing—Review and Editing, A.B., S.N. and K.-R.M.; Funding Acquisition, K.-R.M. All authors have read and agreed to the published version of this manuscript.

Funding

A.B., S.N. and K.-R.M. acknowledge support from the German Federal Ministry of Education and Research (BMBF) for BIFOLD under grant Nr. BIFOLD24B. K.-R.M. was also supported by the Institute of Information & communications Technology Planning & Evaluation (IITP) grants funded by the Korea government (MSIT) (No. RS-2019-II190079, Artificial Intelligence Graduate School Program, Korea University and No. RS-2024-00457882, AI Research Hub Project) and by the German Federal Ministry for Education and Research (BMBF) under grants 01IS14013B-E and 01GQ1115.

Data Availability Statement

No new data were created or analyzed in this study.

Conflicts of Interest

The authors declare no conflicts of interest. The funders had no role in the design of this study; in the collection, analyses, or interpretation of data; in the writing of this manuscript; or in the decision to publish the results.

Abbreviations

The following abbreviations are used in this manuscript:

AD	Anomaly Detection
AE	Autoencoder
CAE	Contractive Autoencoder
DAE	Denoising Autoencoder
CCM	Convex Combination Module
DNN	Deep Neural Network
PAE	Projecting Autoencoder
RCAE	Reconstruction Contractive Autoencoder
SDC	Stacked Dilated Convolutions

Appendix A. Auxiliary Statements

In order to prove the formal statements in the main body of this paper, we first introduce a set of auxiliary statements including Theorem A1 and Corollary A1, which themselves provide an additional contribution. For convenience, we extend our notation as follows: Given a vector

x \in R^{n}

, a set of indices

S \subset {1, \dots, n}

, and its complement

\bar{S} : = {1, \dots, n} ∖ S

, we interpret the restriction

x_{S}

in two different ways depending on the context either as an element

x_{S} \in R^{| S |}

or as an element

x_{S} \in R^{n}

, where the indices in

\bar{S}

are set to zeros, that is,

x_{\bar{S}} = 0 \in R^{| \bar{S} |}

, and vice versa. Given such notation, we can write

x = x_{S} + x_{\bar{S}}

Lemma A1.

Consider an

x \in R^{n}

n \in N

and

S \subset {1, \dots, n}

\bar{S} : = {1, \dots, n} ∖ S

. The following holds true for all

p \in N_{+} :

∥ x_{S} \pm x_{\bar{S}} ∥_{p}^{p} = ∥ x_{S} ∥_{p}^{p} \pm {∥ x_{\bar{S}} ∥}_{p}^{p} .

(A1)

The proof follows directly by writing

∥ x_{S} \pm x_{\bar{S}} ∥_{p}^{p} = {(\sum_{i \in S} {(x_{i} \pm 0)}^{p} \pm \sum_{j \in \bar{S}} {(0 \pm x_{j})}^{p})}^{\frac{1}{p} \cdot p} = ∥ x_{S} ∥_{p}^{p} + {∥ x_{\bar{S}} ∥}_{p}^{p} .

Lemma A2.

For all

\hat{x}, x, y \in R^{n}, n \in N

with

{\hat{x}}_{\bar{S}} = x_{\bar{S}}

for some non-empty sets

S \subset {1, \dots, n}

\bar{S} : = {1, \dots, n} ∖ S

, the following holds true for all

p \in N_{+} :

∥ \hat{x} {- x ∥}_{p} ⩽ ∥ \hat{x} {- y ∥}_{p} ⟺ ∥ {\hat{x}}_{S} - x_{S} ∥_{p}^{p} - ∥ {\hat{x}}_{S} - y_{S} ∥_{p}^{p} ⩽ {∥ x_{\bar{S}} - y_{\bar{S}} ∥}_{p}^{p} .

(A2)

Proof.

\begin{matrix} ∥ \hat{x} {- x ∥}_{p} ⩽ {∥ \hat{x} - y ∥}_{p} & ⟺ ∥ \hat{x} {- x ∥}_{p}^{p} ⩽ {∥ \hat{x} - y ∥}_{p}^{p} \\ ⟺ ∥ ({\hat{x}}_{S} - x_{S}) + ({\hat{x}}_{\bar{S}} - x_{\bar{S}}) ∥_{p}^{p} ⩽ {∥ ({\hat{x}}_{S} - y_{S}) + ({\hat{x}}_{\bar{S}} - y_{\bar{S}}) ∥}_{p}^{p} \\ \overset{(*)}{⟺} ∥ {\hat{x}}_{S} - x_{S} ∥_{p}^{p} ⩽ ∥ {\hat{x}}_{S} - y_{S} ∥_{p}^{p} + {∥ {\hat{x}}_{\bar{S}} - y_{\bar{S}} ∥}_{p}^{p} \\ ⟺ ∥ {\hat{x}}_{S} - x_{S} ∥_{p}^{p} - ∥ {\hat{x}}_{S} - y_{S} ∥_{p}^{p} ⩽ {∥ {\hat{x}}_{\bar{S}} - y_{\bar{S}} ∥}_{p}^{p} \end{matrix}

where, in step

(*)

, we used Lemma A1 and our assumption

{\hat{x}}_{\bar{S}} = x_{\bar{S}}

. □

Appendix B. Weak Law of Large Numbers for MRFs

Here, we derive a version of the weak law of large numbers adjusted to our case of MRFs with identically distributed but nonindependent variables.

Theorem A1

(Weak Law of Large Numbers for MRFs). Let

{({x_{1}, \dots, x_{n}})}_{n \in N}

be a sequence of MRFs over identically distributed variables

x_{i}

with finite variance

Var [x_{i}] < \infty

and vanishing covariance

Cov [x_{i}, x_{j}] ⟶ 0 f o r d_{G} (x_{i}, x_{j}) ⟶ \infty .

(A3)

Then the following is true:

\frac{1}{n} \sum_{i = 1}^{n} x_{i} \overset{P}{⟶} E [x_{1}] f o r n ⟶ \infty .

(A4)

Proof.

First, we reorganize the individual terms in the definition of variance as follows:

\begin{matrix} Var [\sum_{i = 1}^{n} x_{i}] = & E [{(\sum_{i = 1}^{n} x_{i} - E [\sum_{i = 1}^{n} x_{i}])}^{2}] \\ = & E [{(\sum_{i = 1}^{n} x_{i} - E [x_{i}])}^{2}] \\ = & \sum_{i = 1}^{n} \sum_{j = 1}^{n} Cov [x_{i}, x_{j}] \\ = & \sum_{i = 1}^{n} Var [x_{i}] + 2 \sum_{i = 1}^{n} \sum_{j = i + 1}^{n} Cov [x_{i}, x_{j}] . \end{matrix}

Let

ϵ > 0

. Since

Cov [x_{i}, x_{j}] ⟶ 0

for

d_{G} (x_{i}, x_{j}) ⟶ \infty

, there is an

L \in N

, such that for all

i, j

satisfying

d_{G} (x_{i}, x_{j}) > L

, we obtain

|Cov [x_{i}, x_{j}]| < ϵ

. Later, we consider

n ⟶ \infty

. Therefore, we can assume

n > L

and split the inner sum of the covariance term in the last equation in two sums as follows: Here, we abbreviate the index set

{j \in N : i + 1 ⩽ j ⩽ n, d_{G} (x_{i}, x_{j}) ⩽ L}

and

{j \in N : i + 1 ⩽ j ⩽ n, d_{G} (x_{i}, x_{j}) > L}

d_{G} (x_{i}, x_{j}) ⩽ L

and

d_{G} (x_{i}, x_{j}) > L

, respectively. That is,

\begin{matrix} \sum_{i = 1}^{n} \sum_{j = i + 1}^{n} Cov [x_{i}, x_{j}] \\ = & \sum_{i = 1}^{n} (\sum_{j : d_{G} (x_{i}, x_{j}) ⩽ L} \underset{⩽ σ^{2}}{\underset{︸}{Cov [x_{i}, x_{j}]}} + \sum_{j : d_{G} (x_{i}, x_{j}) > L} \underset{< ϵ}{\underset{︸}{Cov [x_{i}, x_{j}]}}) < n \cdot L \cdot σ^{2} + n^{2} \cdot ϵ, \end{matrix}

where, in the last step, we used, on the one hand, the Cauchy–Schwarz inequality

| Cov [x_{i}, x_{j}] | ⩽ \sqrt{Var [x_{i}] \cdot Var [x_{j}]} = Var [x_{i}] = : σ^{2}

, and, on the other hand, an upper bound L on the cardinality of the running index set in the second sum. Altogether, we obtain the following estimation:

\begin{matrix} \frac{1}{n^{2}} Var [\sum_{i = 1}^{n} x_{i}] < & \frac{σ^{2}}{n} + \frac{2 \cdot L \cdot σ^{2}}{n} + 2 \cdot ϵ . \end{matrix}

Since the first two terms on the right-hand side converge to zero (for

n ⟶ \infty

), and

ϵ

is chosen arbitrarily small, this implies

\lim_{n \to \infty} \frac{1}{n^{2}} Var [\sum_{i = 1}^{n} x_{i}] = 0 .

(A5)

Finally, for all

ϵ > 0

P (|\frac{1}{n} \sum_{i = 1}^{n} x_{i} - E [x_{1}]| > ϵ) \overset{(*)}{⩽} \frac{1}{ϵ^{2}} Var [\frac{1}{n} \sum_{i = 1}^{n} x_{i}] = \frac{1}{ϵ^{2} n^{2}} Var [\sum_{i = 1}^{n} x_{i}]

where in step

(*)

, we used Chebyshev’s inequality. The convergence

\lim_{n \to \infty} P (|\frac{1}{n} \sum_{i = 1}^{n} x_{i} - E [x_{1}]| > ϵ) = 0

(A6)

follows from Equation (A5). □

Appendix C. Corollary of Theorem A1

Applying Theorem A1 to our discussion in this paper, we obtain the following useful Corollary.

Corollary A1.

Consider a pair

x, y

of independent MRFs over identically distributed variables

x_{i}, y_{j}

with finite fourth moment

E [x_{i}^{4}] < \infty

and vanishing covariance according to

Cov [x_{i}^{k}, x_{j}^{l}] ⟶ 0 for d_{G} (x_{i}, x_{j}) ⟶ \infty

(A7)

for all

k, l \in {1, 2}

. The following statements are true:

\begin{matrix} (a) & \frac{1}{| S |} {∥ x_{S} ∥}_{2}^{2} \overset{P}{⟶} μ^{2} + σ^{2} & for | S | ⟶ \infty, \end{matrix}

(A8)

\begin{matrix} (b) & \frac{1}{| S |} {∥ x_{S} - y_{S} ∥}_{2}^{2} \overset{P}{⟶} 2 σ^{2} & for | S | ⟶ \infty, \end{matrix}

(A9)

\begin{matrix} (c) & \frac{1}{| S |} x_{S}^{⊤} y_{S} \overset{P}{⟶} μ^{2} & for | S | ⟶ \infty, \end{matrix}

(A10)

\begin{matrix} (d) & cos ϕ [x_{S}, y_{S}] \overset{P}{⟶} \frac{μ^{2}}{μ^{2} + σ^{2}} & for | S | ⟶ \infty, \end{matrix}

(A11)

where

μ : = E [x_{i}]

σ^{2} : = Var [x_{i}]

ϕ [x_{S}, y_{S}]

is the angle between the two vectors, and

S \subseteq N

denotes a subset of the variable indices.

Proof.

First, we prove statement

(a)

in (A8). By setting

z_{i} : = x_{i}^{2}

, we have

E [z_{1}] = E [x_{1}^{2}] = Var [x_{1}] + E {[x_{1}]}^{2} = σ^{2} + μ^{2} .

(A12)

On the other hand, we have

\frac{1}{| S |} {∥ x_{S} ∥}^{2} = \frac{1}{| S |} \sum_{i \in S} x_{i}^{2} = \frac{1}{| S |} \sum_{i \in S} z_{i} .

(A13)

Since we assumed

E [x_{i}^{4}] < \infty

, it holds that

Var [z_{i}] = Var [x_{i}^{2}] = E [x_{i}^{4}] - E {[x_{i}^{2}]}^{2} = E [x_{i}^{4}] - {(σ^{2} + μ^{2})}^{2} < \infty .

Furthermore, due to our assumption in (A7),

Cov [z_{i}, z_{j}] = Cov [x_{i}^{2}, x_{j}^{2}] ⟶ 0 f o r d_{G} (x_{i}, x_{j}) ⟶ \infty .

That is, the variables

z_{i}

satisfy all the requirements in Theorem A1. Applying this Theorem directly to the above derivations proves the claim in (A8).

Now, we prove the statement

(b)

in (A9). For this purpose, we set

z_{i} : = {(x_{i} - y_{i})}^{2}

. It holds that

E [z_{1}] = E [{(x_{1} - y_{1})}^{2}] = E [x_{1}^{2}] - 2 E [x_{1} y_{1}] + E [y_{1}^{2}] = 2 (E [x_{1}^{2}] - E {[x_{1}]}^{2}) = 2 Var [x_{1}] = 2 σ^{2} .

On the other hand, we obtain

\frac{1}{| S |} {∥ x_{S} - y_{S} ∥}^{2} = \frac{1}{| S |} \sum_{i \in S} {(x_{i} - y_{i})}^{2} = \frac{1}{| S |} \sum_{i \in S} z_{i} .

(A14)

It remains to be shown that the corresponding variance is finite and that the covariance vanishes. The following holds:

\begin{matrix} E [{(x_{i} - y_{i})}^{2} {(x_{j} - y_{j})}^{2}] \\ = & E [(x_{i}^{2} - 2 x_{i} y_{i} + y_{i}^{2}) (x_{j}^{2} - 2 x_{j} y_{j} + y_{j}^{2})] \\ = & E [x_{i}^{2} x_{j}^{2} - 2 x_{i}^{2} x_{j} y_{j} + x_{i}^{2} y_{j}^{2} - 2 x_{i} y_{i} x_{j}^{2} + 4 x_{i} y_{i} x_{j} y_{j} - 2 x_{i} y_{i} y_{j}^{2} + y_{i}^{2} x_{j}^{2} - 2 y_{i}^{2} x_{j} y_{j} + y_{i}^{2} y_{j}^{2}] \\ = & E [x_{i}^{2} x_{j}^{2}] - 2 E [x_{i}^{2} x_{j} y_{j}] + E [x_{i}^{2} y_{j}^{2}] - 2 E [x_{i} y_{i} x_{j}^{2}] + 4 E [x_{i} y_{i} x_{j} y_{j}] - 2 E [x_{i} y_{i} y_{j}^{2}] + E [y_{i}^{2} x_{j}^{2}] - 2 E [y_{i}^{2} x_{j} y_{j}] + E [y_{i}^{2} y_{j}^{2}] \\ = & E [x_{i}^{2} x_{j}^{2}] - 2 E [x_{i}^{2} x_{j}] E [y_{j}] + E [x_{i}^{2}] E [y_{j}^{2}] - 2 E [x_{i} x_{j}^{2}] E [y_{i}] + 4 E [x_{i} x_{j}] E [y_{i} y_{j}] - 2 E [x_{i}] E [y_{i} y_{j}^{2}] + E [y_{i}^{2}] E [x_{j}^{2}] - 2 E [x_{j}] E [y_{i}^{2} y_{j}] + E [y_{i}^{2} y_{j}^{2}] \\ = & 2 E [x_{i}^{2} x_{j}^{2}] - 8 E [x_{i}^{2} x_{j}] E [x_{j}] + 2 E [x_{i}^{2}] E [x_{j}^{2}] + 4 E {[x_{i} x_{j}]}^{2} . \end{matrix}

On the other hand,

\begin{matrix} E [{(x_{i} - y_{i})}^{2}] E [{(x_{j} - y_{j})}^{2}] \\ = & E [(x_{i}^{2} - 2 x_{i} y_{i} + y_{i}^{2})] E [(x_{j}^{2} - 2 x_{j} y_{j} + y_{j}^{2})] \\ = & (E [x_{i}^{2}] - 2 E [x_{i} y_{i}] + E [y_{i}^{2}]) (E [x_{j}^{2}] - 2 E [x_{j} y_{j}] + E [y_{j}^{2}]) \\ = & E [x_{i}^{2}] E [x_{j}^{2}] - 2 E [x_{i}^{2}] E [x_{j} y_{j}] + E [x_{i}^{2}] E [y_{j}^{2}] - 2 E [x_{i} y_{i}] E [x_{j}^{2}] + 4 E [x_{i} y_{i}] E [x_{j} y_{j}] - 2 E [x_{i} y_{i}] E [y_{j}^{2}] + E [y_{i}^{2}] E [x_{j}^{2}] \\ - 2 E [y_{i}^{2}] E [x_{j} y_{j}] + E [y_{i}^{2}] E [y_{j}^{2}] \\ = & E [x_{i}^{2}] E [x_{j}^{2}] - 2 E [x_{i}^{2}] E [x_{j}] E [y_{j}] + E [x_{i}^{2}] E [y_{j}^{2}] - 2 E [x_{i}] E [y_{i}] E [x_{j}^{2}] + 4 E [x_{i}] E [y_{i}] E [x_{j}] E [y_{j}] - 2 E [x_{i}] E [y_{i}] E [y_{j}^{2}] + E [y_{i}^{2}] E [x_{j}^{2}] \\ - 2 E [y_{i}^{2}] E [x_{j}] E [y_{j}] + E [y_{i}^{2}] E [y_{j}^{2}] \\ = & E [x_{i}^{2}] E [x_{j}^{2}] - 2 E [x_{i}^{2}] E {[x_{j}]}^{2} + E [x_{i}^{2}] E [x_{j}^{2}] - 2 E {[x_{i}]}^{2} E [x_{j}^{2}] + 4 E {[x_{i}]}^{2} E {[x_{j}]}^{2} - 2 E {[x_{i}]}^{2} E [x_{j}^{2}] + E [x_{i}^{2}] E [x_{j}^{2}] - 2 E [x_{i}^{2}] E {[x_{j}]}^{2} + E [x_{i}^{2}] E [x_{j}^{2}] \\ = & 4 E [x_{i}^{2}] E [x_{j}^{2}] - 8 E [x_{i}^{2}] E {[x_{j}]}^{2} + 4 E {[x_{i}]}^{2} E {[x_{j}]}^{2} . \end{matrix}

Based on the above derivations, we now analyze the covariance term,

Cov [z_{i}, z_{j}] = E [{(x_{i} - y_{i})}^{2} {(x_{j} - y_{j})}^{2}] - E [{(x_{i} - y_{i})}^{2}] E [{(x_{j} - y_{j})}^{2}]

in the limit

d_{G} (z_{i}, z_{j}) ⟶ \infty

. Because of our assumption in (A7), the terms

E [x_{i}^{2} x_{j}^{2}]

E [x_{i}^{2} x_{j}]

and

E [x_{i} x_{j}]

converge against

E [x_{i}^{2}] E [x_{j}^{2}]

E [x_{i}^{2}] E [x_{j}]

and

E [x_{i}] E [x_{j}]

, respectively. It follows:

\begin{matrix} \lim_{d_{G} (z_{i}, z_{j}) \to \infty} E [{(x_{i} - y_{i})}^{2} {(x_{j} - y_{j})}^{2}] & = \lim_{d_{G} (z_{i}, z_{j}) \to \infty} (2 E [x_{i}^{2} x_{j}^{2}] - 8 E [x_{i}^{2} x_{j}] E [x_{j}] + 2 E [x_{i}^{2}] E [x_{j}^{2}] + 4 E {[x_{i} x_{j}]}^{2}) \\ = 2 E [x_{i}^{2}] E [x_{j}^{2}] - 8 E [x_{i}^{2}] E [x_{j}] E [x_{j}] + 2 E [x_{i}^{2}] E [x_{j}^{2}] + 4 E {[x_{i}]}^{2} E {[x_{j}]}^{2} \\ = 4 E [x_{i}^{2}] E [x_{j}^{2}] - 8 E [x_{i}^{2}] E {[x_{j}]}^{2} + 4 E {[x_{i}]}^{2} E {[x_{j}]}^{2} \\ = E [{(x_{i} - y_{i})}^{2}] E [{(x_{j} - y_{j})}^{2}] . \end{matrix}

Therefore,

Cov [z_{i}, z_{j}] ⟶ 0 f o r d_{G} (z_{i}, z_{j}) ⟶ \infty

. Finally, by writing out

Var [z_{i}] = E [z_{i}^{2}] - E {[z_{i}]}^{2} = E [{(x_{i} - y_{i})}^{4}] - E {[{(x_{i} - y_{i})}^{2}]}^{2}

and using the independence assumption of

x_{i}

and

y_{i}

, we can see that the degree of each monomial is upper-bounded by 4. Due to our assumption of a finite fourth moment, this implies

Var [z_{i}] < \infty

. Altogether, the variables

z_{i}

satisfy the requirements in Theorem A1. Applying this theorem directly to the above derivations proves the claim in (A9).

The statement

(c)

in (A10) can be proven in a similar way. Alternatively, we can use the statements in

(a)

and

(b)

and apply the limit algebra of convergence in probability

\underset{\overset{P}{⟶} 2 σ^{2}}{\underset{︸}{\frac{1}{| S |} {∥ x_{S} - y_{S} ∥}^{2}}} = \underset{\overset{P}{⟶} μ^{2} + σ^{2}}{\underset{︸}{\frac{1}{| S |} {∥ x_{S} ∥}^{2}}} - \frac{2}{| S |} x_{S}^{⊤} y_{S} + \underset{\overset{P}{⟶} μ^{2} + σ^{2}}{\underset{︸}{\frac{1}{| S |} {∥ y_{S} ∥}^{2}}},

which implies

\frac{1}{| S |} x_{S}^{⊤} y_{S} \overset{P}{⟶} μ^{2}

Similarly, we prove the statement

(d)

in (A11) as follows:

\begin{matrix} cos ϕ [x_{S}, y_{S}] \cdot ∥ x_{S} ∥ \cdot ∥ y_{S} ∥ = x_{S}^{⊤} y_{S} \\ ⟺ & cos ϕ [x_{S}, y_{S}] \cdot \underset{\overset{P}{⟶} \sqrt{μ^{2} + σ^{2}}}{\underset{︸}{\frac{1}{\sqrt{| S |}} ∥ x_{S} ∥}} \cdot \underset{\overset{P}{⟶} \sqrt{μ^{2} + σ^{2}}}{\underset{︸}{\frac{1}{\sqrt{| S |}} ∥ y_{S} ∥}} = \underset{\overset{P}{⟶} μ^{2}}{\underset{︸}{\frac{1}{| S |} x_{S}^{⊤} y_{S}}} \\ ⟹ & cos ϕ [x_{S}, y_{S}] \overset{P}{⟶} \frac{μ^{2}}{μ^{2} + σ^{2}} f o r | S | ⟶ \infty . \end{matrix}

□

Appendix D. Proof of Theorem 1

Proof.

Consider the case

∥ x_{\bar{S}} - y_{\bar{S}} ∥_{2}^{2} < ∥ {\hat{x}}_{S} - x_{S} ∥_{2}^{2} - ∥ {\hat{x}}_{S} - y_{S} ∥_{2}^{2} ⩽ ∥ {\hat{x}}_{S} - x_{S} ∥_{2}^{2} ⩽ | S |,

(A15)

where we assume the first inequality to be true and the last inequality holds due to

{\hat{x}}_{i}, y_{j} \in [0, 1]

. This implies that

{(x, y) : ∥ x_{\bar{S}} - y_{\bar{S}} ∥^{2} < ∥ {\hat{x}}_{S} - x_{S} ∥^{2} - ∥ {\hat{x}}_{S} - y_{S} ∥^{2}} \subseteq {(x, y) : ∥ x_{\bar{S}} - y_{\bar{S}} ∥^{2} < | S |}

(A16)

Consider now the following derivation:

\begin{matrix} ∥ x_{\bar{S}} - y_{\bar{S}} ∥^{2} < | S | ⟺ & \frac{1}{| \bar{S} |} {∥ x_{\bar{S}} - y_{\bar{S}} ∥}^{2} < \frac{| S |}{| \bar{S} |} \\ ⟹ & \frac{1}{| \bar{S} |} {∥ x_{\bar{S}} - y_{\bar{S}} ∥}^{2} < 2 σ^{2} \\ ⟹ & |\frac{1}{| \bar{S} |} {∥ x_{\bar{S}} - y_{\bar{S}} ∥}^{2} - 2 σ^{2}| > 0, \end{matrix}

where, in the second step, we use

| S | ⩽ 2 σ^{2} | \bar{S} |

. Therefore, it follows from (A16) that

\begin{matrix} {(x, y) : ∥ x_{\bar{S}} - y_{\bar{S}} ∥^{2} < ∥ {\hat{x}}_{S} - x_{S} ∥^{2} - ∥ {\hat{x}}_{S} - y_{S} ∥^{2}} \\ \subseteq & {(x, y) : |\frac{1}{| \bar{S} |} {∥ x_{\bar{S}} - y_{\bar{S}} ∥}^{2} - 2 σ^{2}| > 0} \\ = & {(x, y) : |\frac{1}{| \bar{S} |} {∥ x_{\bar{S}} - y_{\bar{S}} ∥}^{2} - 2 σ^{2}| > 1} \cup ⋃_{k ⩾ 2} {(x, y) : \frac{1}{k - 1} ⩾ |\frac{1}{| \bar{S} |} {∥ x_{\bar{S}} - y_{\bar{S}} ∥}^{2} - 2 σ^{2}| > \frac{1}{k}} \end{matrix}

Using the above derivations, we now upper-bound the probability of the corresponding events, where

P = P_{x, y}

denotes a joint probability distribution over

(x, y)

\begin{matrix} P (∥ x_{\bar{S}} - y_{\bar{S}} ∥^{2} < ∥ {\hat{x}}_{S} - x_{S} ∥^{2} - {∥ {\hat{x}}_{S} - y_{S} ∥}^{2}) \\ ⩽ & P (⋃_{k} {\frac{1}{k - 1} ⩾ |\frac{1}{| \bar{S} |} {∥ x_{\bar{S}} - y_{\bar{S}} ∥}^{2} - 2 σ^{2}| > \frac{1}{k}}) \\ \overset{(*)}{=} & \sum_{k} P (\frac{1}{k - 1} ⩾ |\frac{1}{| \bar{S} |} {∥ x_{\bar{S}} - y_{\bar{S}} ∥}^{2} - 2 σ^{2}| > \frac{1}{k}), \end{matrix}

where, in step

(*)

, we use the fact that all the sets in the union are disjoint. Note that we use a short notation

⋃_{k}

and

\sum_{k}

, which runs over all previously defined terms (including

k = 1

). Next, we consider the above derivations in the limit

n ⟶ \infty

for

S \subseteq {1, \dots, n}

\bar{S} : = {1, \dots, n} ∖ S

with a fixed ratio

| S | / | \bar{S} | ⩽ 2 σ^{2}

. The following holds:

\begin{matrix} \lim_{n \to \infty} P (∥ x_{\bar{S}} - y_{\bar{S}} ∥^{2} < ∥ {\hat{x}}_{S} - x_{S} ∥^{2} - {∥ {\hat{x}}_{S} - y_{S} ∥}^{2}) \\ ⩽ & \lim_{n \to \infty} \underset{⩽ 1}{\underset{︸}{\sum_{k} P (\frac{1}{k - 1} ⩾ |\frac{1}{| \bar{S} |} {∥ x_{\bar{S}} - y_{\bar{S}} ∥}^{2} - 2 σ^{2}| > \frac{1}{k})}} \\ \overset{(*)}{=} & \sum_{k} \lim_{n \to \infty} P (\frac{1}{k - 1} ⩾ |\frac{1}{| \bar{S} |} {∥ x_{\bar{S}} - y_{\bar{S}} ∥}^{2} - 2 σ^{2}| > \frac{1}{k}) \\ ⩽ & \sum_{k} \underset{= 0}{\underset{︸}{\lim_{n \to \infty} P (|\frac{1}{| \bar{S} |} {∥ x_{\bar{S}} - y_{\bar{S}} ∥}^{2} - 2 σ^{2}| > \frac{1}{k})}} \\ = & 0, \end{matrix}

where, in step

(*)

, we can swap the limit and the sum signs because the series converges for all

n \in N

. The last step follows from Corollary A1. To summarize, we have just shown that

\lim_{n \to \infty} P_{x, y} (∥ {\hat{x}}_{S} - x_{S} ∥^{2} - ∥ {\hat{x}}_{S} - y_{S} ∥^{2} ⩽ {∥ x_{\bar{S}} - y_{\bar{S}} ∥}^{2}) = 1 .

(A17)

According to Lemma A2, the following holds:

∥ {\hat{x}}_{S} - x_{S} ∥_{2}^{2} - ∥ {\hat{x}}_{S} - y_{S} ∥_{2}^{2} ⩽ ∥ x_{\bar{S}} - y_{\bar{S}} ∥_{2}^{2} ⟺ ∥ \hat{x} {- x ∥}_{2} ⩽ {∥ \hat{x} - y ∥}_{2} .

(A18)

Together, it follows from (A17) and (A18) that

\lim_{n \to \infty} P_{x, y} (∥ \hat{x} {- x ∥}_{2} ⩽ {∥ \hat{x} - y ∥}_{2}) = 1 .

Note that

x

in the above derivation can be identified with the image of

\hat{x}

under the conservative projection. In order to prove the following equality (where

f : = f_{c o n}

\lim_{n \to \infty} P_{x, y} (∥ \hat{x} - f (\hat{x}) ∥_{2} ⩽ ∥ \hat{x} - y ∥_{2}) = 1,

it suffices to show that for all pairs

(x, y) \in D \times D

, the following implication holds true:

∥ \hat{x} {- x ∥}_{2} ⩽ ∥ \hat{x} - {y ∥}_{2} ⟹ ∥ \hat{x} - f (\hat{x}) ∥_{2} ⩽ {∥ \hat{x} - y ∥}_{2} .

(A19)

Namely, the following holds:

\begin{matrix} ∥ \hat{x} - f (\hat{x}) ∥^{2} & = \underset{⩽ ∥ {\hat{x}}_{S} - x_{S} ∥^{2}}{\underset{︸}{∥ {\hat{x}}_{S} - f_{S} (\hat{x}) ∥^{2}}} + \underset{= 0}{\underset{︸}{∥ {\hat{x}}_{\bar{S}} - f_{\bar{S}} (\hat{x}) ∥^{2}}} \\ \overset{(*)}{⩽} {∥ {\hat{x}}_{S} - x_{S} ∥}^{2} + \underset{= 0}{\underset{︸}{∥ {\hat{x}}_{\bar{S}} - x_{\bar{S}} ∥^{2}}} \\ = ∥ \hat{x} {- x ∥}^{2} ⩽ {∥ \hat{x} - y ∥}^{2}, \end{matrix}

where, in step

(*)

, we use our Definition 3 of the conservative projection. □

Appendix E. Proof of Theorem 2

Lemma A3.

Let

x, y, \hat{x}, ϵ \in R^{n}

, where

\hat{x} : = x + ϵ

. Then, the following holds true:

∥ ϵ ∥ ⩽ \frac{1}{2} ∥ x - y ∥ ⟹ ∥ \hat{x} - x ∥ ⩽ ∥ \hat{x} - y ∥ .

(A20)

Proof.

The following holds:

\begin{matrix} ∥ \hat{x} - x ∥ ⩽ ∥ \hat{x} - y ∥ \Leftrightarrow ∥ x + ϵ - x ∥ ⩽ ∥ x + ϵ - y ∥ \Leftrightarrow & ∥ ϵ ∥ ⩽ \underset{⩾ ∥ x - y ∥ - ∥ ϵ ∥}{\underset{︸}{∥ (x - y) + ϵ ∥}} \\ \Leftarrow & ∥ ϵ ∥ ⩽ ∥ x - y ∥ - ∥ ϵ ∥ \\ \Leftrightarrow & ∥ ϵ ∥ ⩽ \frac{1}{2} ∥ x - y ∥ \end{matrix}

□

We now prove Theorem 2. First, we show that

\lim_{n \to \infty} P (∥ ϵ ∥ ⩽ \frac{1}{2} ∥ x - y ∥) = 1 .

(A21)

It holds:

\begin{matrix} {∥ ϵ ∥}^{2} ⩽ \frac{1}{4} {∥ x - y ∥}^{2} \\ \Leftrightarrow & \underset{= : X}{\underset{︸}{(\frac{1}{n} {∥ ϵ ∥}^{2} - (μ_{ϵ}^{2} + σ_{ϵ}^{2}))}} ⩽ \underset{= : Y}{\underset{︸}{\frac{1}{4} (\frac{1}{n} {∥ x - y ∥}^{2} - 2 σ^{2})}} + \underset{= : C}{\underset{︸}{(\frac{1}{2} σ^{2} - (μ_{ϵ}^{2} + σ_{ϵ}^{2}))}} \end{matrix}

It follows that

\begin{matrix} {X > Y + C} \\ \subseteq & {X > Y} \\ = & {X > Y, X ⩾ 0, Y ⩾ 0} \cup {X > Y, X ⩾ 0, Y < 0} \cup {X > Y, X < 0, Y < 0} \\ \cup {X > Y, X < 0, Y ⩾ 0} \\ = & {| X | > | Y |, X ⩾ 0, Y ⩾ 0} \cup {| X | ⩾ 0, X ⩾ 0, Y < 0} \cup {| X | < | Y |, X < 0, Y < 0} \\ = & {| X | > | Y |, X ⩾ 0, Y ⩾ 0} \cup {| X | > 0, X > 0, Y < 0} \cup {X = 0, | Y | > 0} \\ \cup {| X | < | Y |, X < 0, Y < 0} \\ \subseteq & {| X | > | Y |} \cup {| X | > 0} \cup {| Y | > 0} \cup {| X | < | Y |} . \end{matrix}

That is,

P (X > Y + C) ⩽ P ({| X | > | Y |}) + P ({| X | > 0}) + P ({| Y | > 0}) + P ({| X | < | Y |}) .

(A22)

We can represent

{| X | > | Y |}

and

{| X | > 0}

as a union of disjoint sets according to

\begin{matrix} {| X | > | Y |} = (⋃_{k ⩾ 1} {k + 1 ⩾ | Y | > k, | X | > k + 1}) \cup (⋃_{k ⩾ 2} {\frac{1}{k - 1} ⩾ | Y | > \frac{1}{k}, | X | > \frac{1}{k - 1}}) \end{matrix}

and

\begin{matrix} {| X | > 0} = (⋃_{k ⩾ 1} {k + 1 ⩾ | X | > k}) \cup (⋃_{k ⩾ 2} {\frac{1}{k - 1} ⩾ | X | > \frac{1}{k}}) . \end{matrix}

We obtain a similar representation for

{| X | < | Y |}

and

{| Y | > 0}

. Now, we consider the above derivations in the limit

n \to \infty

We look at the individual terms on the right-hand side of the equation in (A22) separately.

\begin{matrix} \lim_{n \to \infty} P ({| X | > | Y |}) \\ = & \lim_{n \to \infty} P ((⋃_{k ⩾ 1} {k + 1 ⩾ | Y | > k, | X | > k + 1}) \cup (⋃_{k ⩾ 2} {\frac{1}{k - 1} ⩾ | Y | > \frac{1}{k}, | X | > \frac{1}{k - 1}})) \\ \overset{(*)}{=} & \lim_{n \to \infty} \underset{⩽ 1}{\underset{︸}{\sum_{k ⩾ 1} P (k + 1 ⩾ | Y | > k, | X | > k + 1)}} + \underset{⩽ 1}{\underset{︸}{\sum_{k ⩾ 2} P (\frac{1}{k - 1} ⩾ | Y | > \frac{1}{k}, | X | > \frac{1}{k - 1})}} \\ \overset{(+)}{=} & \sum_{k ⩾ 1} \lim_{n \to \infty} P (k + 1 ⩾ | Y | > k, | X | > k + 1) + \sum_{k ⩾ 2} \lim_{n \to \infty} P (\frac{1}{k - 1} ⩾ | Y | > \frac{1}{k}, | X | > \frac{1}{k - 1}) \\ ⩽ & \sum_{k ⩾ 1} \lim_{n \to \infty} P (| X | > k + 1) + \sum_{k ⩾ 2} \lim_{n \to \infty} P (| Y | > \frac{1}{k}) \\ = & \sum_{k ⩾ 2} \underset{= 0}{\underset{︸}{\lim_{n \to \infty} P (|\frac{1}{n} {∥ ϵ ∥}^{2} - (μ_{ϵ}^{2} + σ_{ϵ}^{2})| > k + 1)}} + \sum_{k ⩾ 2} \underset{= 0}{\underset{︸}{\lim_{n \to \infty} P (|\frac{1}{n} {∥ x - y ∥}^{2} - 2 σ^{2}| > \frac{1}{k})}} \\ = & 0, \end{matrix}

where, in step

(*)

, we use the fact that all the sets are disjoint. In step

(+)

, we swap the limit and the sum signs because the two sums are finite for all

n \in N

. In the last step, we use the weak law of big numbers and its variant for dependent variables with vanishing covariance. Similarly, we obtain

\lim_{n \to \infty} P (| X | < | Y |) = \lim_{n \to \infty} P (| X | > 0) = \lim_{n \to \infty} P (| Y | > 0) = 0 .

(A23)

Therefore,

\lim_{n \to \infty} P (∥ ϵ ∥ ⩽ \frac{1}{2} ∥ x - y ∥) = \lim_{n \to \infty} P (X ⩽ Y + C) = 1 - \lim_{n \to \infty} P (X > Y + C) = 1 .

(A24)

Applying Lemma A3 to the above equation completes the proof:

\lim_{n \to \infty} P (∥ \hat{x} - x ∥ ⩽ ∥ \hat{x} - y ∥) = 1 .

(A25)

Appendix F. Proof of Proposition 1

In order to prove Proposition 1 in the main body of this paper, we first introduce a set of auxiliary statements.

Lemma A4.

Let

f : R^{n} \supseteq U ⟶ R^{n}

n \in R

be idempotent. Then, the equality

f (x) = x

(A26)

holds for all

x \in f (U)

Proof.

For any

x \in f (U)

, there is

z \in U

with

f (z) = x

. It follows that

f (z) = x ⟹ f (f (z)) = f (x) ⟹ f (z) = f (x) ⟹ x = f (x),

where, in the penultimate step, we use the idempotency assumption, and, in the last step,

x = f (z)

. □

Lemma A5.

Let

D \subseteq R^{n}, n \in N

be a differentiable manifold and

f, g : R^{n} \to R^{n}

be differentiable mappings such that

f (x) = g (x)

for all

x \in D

. Then, the equality

D_{x} f (v) = D_{x} g (v)

(A27)

holds true for all

x \in D

v \in T_{x} D

Proof.

Let

x \in D

and

v \in T_{x} D ∖ {0}

. Since

D

is a differentiable manifold, there exists a parametrization

ϕ : U \to R^{m}

x \in U

such that

f \circ ϕ^{- 1}, g \circ ϕ^{- 1}

are differentiable. Because

D_{q} ϕ^{- 1} (R^{m}) = T_{x} D

for

q = ϕ (x)

holds, there exists

w \in R^{m}

such that

D_{q} ϕ^{- 1} (w) = v

. It follows:

\begin{matrix} f (x) = g (x) for all x \in D \\ ⟹ & f \circ ϕ^{- 1} (q) = g \circ ϕ^{- 1} (q) for all q \in ϕ (U) \\ ⟹ & D_{q} f \circ ϕ^{- 1} = D_{q} g \circ ϕ^{- 1} \\ ⟹ & D_{ϕ^{- 1} (q)} f \circ D_{q} ϕ^{- 1} = D_{ϕ^{- 1} (q)} g \circ D_{q} ϕ^{- 1} \\ ⟹ & D_{x} f \circ D_{q} ϕ^{- 1} (w) = D_{x} g \circ D_{q} ϕ^{- 1} (w) for all w \in R^{m} \\ ⟹ & D_{x} f (v) = D_{x} g (v) . \end{matrix}

□

Lemma A6.

Let

D \subseteq R^{n}

be a differentiable manifold. Consider an orthogonal projection f and another projection g onto

D

. The following holds true for all

x \in D

∥ D_{x} {f ∥}_{2} ⩽ {∥ D_{x} g ∥}_{2} .

(A28)

Proof.

Let

x \in D

be fixed. Because

R^{n} = T_{x} D \oplus {(T_{x} D)}^{⊥}

, each

v \in R^{n}

can be represented as a sum of two vectors

v = u + w

, where

u \in T_{x} D

w \in {(T_{x} D)}^{⊥}

. In particular,

u^{⊤} w = 0

holds. It follows that

\begin{matrix} ∥ D_{x} {f ∥}_{2} & = sup_{v \neq 0} \frac{∥ D_{x} {f (v) ∥}_{2}}{{∥ v ∥}_{2}} = sup_{u + w \neq 0} \frac{∥ D_{x} {f (u + w) ∥}_{2}}{{∥ u + w ∥}_{2}} \overset{(*)}{=} sup_{u + w \neq 0} \frac{∥ D_{x} {g (u) ∥}_{2}}{{∥ u + w ∥}_{2}} \\ \overset{(* *)}{=} sup_{u + w \neq 0, u \neq 0} \frac{∥ D_{x} {g (u) ∥}_{2}}{{∥ u + w ∥}_{2}} \overset{(* * *)}{⩽} sup_{u + w \neq 0, u \neq 0} \frac{∥ D_{x} {g (u) ∥}_{2}}{{∥ u ∥}_{2}} = sup_{u \neq 0} \frac{∥ D_{x} {g (u) ∥}_{2}}{{∥ u ∥}_{2}} \\ = ∥ D_{x} {g ∥}_{2}, \end{matrix}

where, in step

(*)

, we use the orthogonality of f, according to which

D_{x} f (w) = 0

for all

w \in {(T_{x} D)}^{⊥}

, and

D_{x} f (u) = D_{x} g (u)

for all

u \in T_{x} D

(according to Lemma A5). In step

(* *)

, we use the fact that the supremum of a corresponding term is achieved for

u \neq 0

, since

∥ D_{x} {g (0) ∥}_{2} = 0

, and we can always find a

u \neq 0

with

∥ D_{x} {g (u) ∥}_{2}, {∥ u + w ∥}_{2} > 0

. In step

(* * *)

, we use the following argument:

u^{⊤} w = 0 ⟹ {∥ u + w ∥}_{2} ⩾ {∥ u ∥}_{2}

. □

Corollary A2.

Let

D

be a differentiable manifold. Consider an orthogonal projection f and another projection g onto

D

. The following holds true for all

x \in D

∥ D_{x} {f ∥}_{F} ⩽ {∥ D_{x} g ∥}_{F} .

(A29)

Proof.

The proof follows directly from Lemma A6. Namely, based in the geometric interpretation, the singular values of matrix A correspond to the length of the major axis of the ellipsoid

E_{A}

, which is given by the image of the Euclidian unit ball under the linear transformation A. If the inequality

∥ A x ∥ ⩽ ∥ B x ∥

holds for all

x

E_{A}

is completely contained within

E_{B}

. Let

λ_{1}, \dots, λ_{r}

and

μ_{1}, \dots, μ_{k}

r ⩽ k

denote the positive singular values (in descending order) of A and B, respectively. Then, this implies

λ_{i} ⩽ μ_{i}

for all

i \in {1, \dots, r}

. It follows that

{∥ A ∥}_{F} = \sqrt{λ_{1}^{2} + \dots λ_{n}^{2}} ⩽ \sqrt{μ_{1}^{2} + \dots μ_{n}^{2}} = {∥ B ∥}_{F} .

In particular, since

D_{x} f (v) = D_{x} g (v)

for all

v \in T_{x} D

, the singular vectors lying in

T_{x} D

(and the corresponding singular values) are the same for both matrices. □

Now, we can prove the statement in Proposition 1. Note that any idempotent mapping

f \in C^{1} (U)

satisfies

∥ f (x) - x ∥ = 0

and (according to Lemma A5 and Corollary A2)

∥ D_{x} f^{*} ∥_{2} ⩽ {∥ D_{x} f ∥}_{2}

and

∥ D_{x} f^{*} ∥_{F} ⩽ {∥ D_{x} f ∥}_{F}

for all

x \in D

and

f \in C^{1} (U)

. Since

f^{*}

minimizes both terms of the sum in (11), it is an optimal solution.

Appendix G. Proof of Proposition 2

Consider the plot in Figure 9 illustrating the unit circles with respect to the

l^{p}

-norm for

p \in {1, 2, \infty}

centered around the point

\hat{x} \in R^{2}

. Now, choose some p and increase the radius of the unit circle around

\hat{x}

until it touches the set D, which it represents the submanifold of normal examples. Note that the touching points

y_{p}^{*}

correspond to the orthogonal projections of

\hat{x}

onto D with respect to the

l^{p}

-norm. For

p = 1

, there are two possible cases for the position of touching points independent of the shape of D. In the first case, the

l^{1}

nunit circle touches D at one of its corners. Without loss of generality, assume that this corner is the point

(r, 0)

for some

r > 0

. This implies that

{\hat{x}}_{1} \neq y_{1}^{*}

and

{\hat{x}}_{2} = y_{2}^{*}

; that is,

S_{1} = {1}

. However, since all norms are equal at the corners of the

l^{1}

circle, it also holds that

1 \in S_{p}

for

p ⩾ 2

. On the other hand, if the touching point lies on a side (or on an edge in the higher-dimensional case) of the

l_{1}

circle, it implies

S_{1} = {1, 2}

. Obviously, we also obtain

S_{\infty} = {1, 2}

. Consider now an orthogonal projection of D onto

R^{2}

spanned by a pair of axes. Note that each

l^{p}

circle for

2 ⩽ p < \infty

at such a touching point has a nonzero curvature toward the interior of the circle. See Figure 9 for an illustration. This implies that the touching point with respect to the

l^{p}

-norm must lie within the rectangular triangle shaped by the touching points

y_{1}^{*}

y_{\infty}^{*}

and the lines through these points parallel to the two axes. In particular, for all

p < q

, the touching point

y_{q}^{*}

lies in a smaller triangle shaped by the points

y_{p}^{*}

y_{\infty}^{*}

and the lines through these points parallel to the coordinated axes. For the plot in Figure 9, this means that

y_{q}^{*}

lies on a red curve between the points

y_{p}^{*}

and

y_{\infty}^{*}

implying

S_{q} = {1, 2}

. Since this argument is independent of our choice of the axes, it proves statement

(a)

In order to prove the statement in

(b)

, we provide a counterexample for the equality. Consider an example of a Markov chain describing a simple random walk on the one-dimensional grid of integers illustrated in Figure A1. Precisely, we consider a sequence of i.i.d variables

{(ξ_{i})}_{i \in N}

with values in

{- 1, 1}

and define a Markov chain

{(x_{n})}_{n \in N}

according to

x_{n} : = \sum_{i = 1}^{n} ξ_{i}

with

x_{0} : = 0

. Finally, we define the set of normal examples

D \subseteq {(x_{n + 1}, \dots, x_{n + 5}) \in Z^{5} | n \in N}

as the set of all feasible configurations for subsequences of length 5. We can see that there is a mismatch between

S (\hat{x}, x)

and

S (\hat{x}, f (\hat{x}))

. This provides a counterexample for the claim that orthogonal projection maximally preserves uncorrupted regions.

Figure A1. Illustration of a counterexample for the claim that orthogonal projections maximally preserve normal regions in the inputs. Here,

\hat{x} \in Z^{5}

is the modified version of the original input

x \in D

according to the partition

S, \bar{S}

and

f (\hat{x})

denotes the orthogonal projection of

\hat{x}

onto

D

with respect to the

l_{2}

-norm. This example also shows that orthogonality property is dependent on our choice of the distance metric.

Figure A1. Illustration of a counterexample for the claim that orthogonal projections maximally preserve normal regions in the inputs. Here,

\hat{x} \in Z^{5}

is the modified version of the original input

x \in D

according to the partition

S, \bar{S}

and

f (\hat{x})

denotes the orthogonal projection of

\hat{x}

onto

D

with respect to the

l_{2}

-norm. This example also shows that orthogonality property is dependent on our choice of the distance metric.

Appendix H. Proof of Proposition 3

In the following, we naturally generalize some properties of Markov chains to the two-dimensional case of MRFs, where the nodes are organized in a grid-like structure similar to that of the Ising model. Here, we omit a formal definition and provide only an idea, which is sufficient for our purposes. Informally, we introduce the notion of the order of an MRF by relating the definition for Markov chains to the width of the corresponding Markov blanket. Furthermore, we generalize the notion of irreducible Markov chains to irreducible MRFs by assuming that each state is reachable from any other state on the chain subgraphs of the MRF, where each node

x_{j}

on the chain is farther (with respect to the topology of the MRF graph G) to the start node

x_{1}

than all of the previous nodes

x_{i}

according to the metric

d_{G} (\cdot, \cdot)

. That is,

i < j ⟹ d_{G} (x_{i}, x_{1}) < d_{G} (x_{j}, x_{1})

. Note that the notion of a state at position i on the path now also involves the values of the variables in the neighborhood (corresponding to the Markov blanket) of

x_{i}

in the MRF. Essentially, this property is covered by our assumption on the variables being identically distributed with vanishing covariance. Based on this informal extension, we introduce an auxiliary concept that we refer to as the transition set. Consider first a Markov chain of the order

K \in N

with a finite set of possible states

x_{i} \in I, | I | < \infty

. Then, the maximal number of steps required to reach a state

j \in I

from a state

i \in I

is upper-bounded by

{| I |}^{K}

, that is, by a constant independent of the graph size of the MRF. Namely, when traveling from one node to another, we see at most

{| I |}^{K}

combinations of states

(x_{n - K}, \dots, x_{n - 1}, x_{n})

with

P (x_{n} | x_{n - K}, \dots, x_{n - 1}) > 0

, which locally affect our path. The shortest path would have no redundant configurations

(x_{n - K}, \dots, x_{n - 1})

. Therefore, given two patterns

(x_{m + 1}, \dots, x_{m + r - 1})

and

(x_{m + r}, \dots, x_{m + n})

, we can always find (for sufficiently large numbers

r, n \in N

) a sequence

B = (x_{m + r - b}, \dots, x_{m + r - 1})

b ⩽ {| I |}^{K}

such that

P (x_{m + 1}, \dots, x_{m + r - b + 1}, x_{m + r - b}, \dots, x_{m + r - 1}, x_{m + r}, \dots, x_{m + n}) > 0

. This example can be generalized to the MRF by considering the transitions between the individual nodes that respect the values of the surrounding variables in their neighborhoods (or Markov blankets). Basically, this corresponds to considering Markov chains with an increased set of states upper-bounded by

{| I |}^{K^{2}}

. We refer to the set of pixels B as a transition set. See Figure A2 for an illustration.

Figure A2. Illustration of the concept of a transition set on two examples with different shapes. Each of the two images represents an MRF

x = (x_{1}, \dots, x_{n})

n \in N

of the Markov order

K \in N

with nodes corresponding to the individual pixels with values from a finite set of states

x_{i} \in I

| I | < \infty

. The grey area marks the corrupted region

S \subseteq {1, \dots, n}

, where the union of the dark blue and light blue areas is the complement

\bar{S} : = {1, \dots, n} ∖ S

marking the normal region. The dark blue part of

\bar{S}

corresponds to the transition set

B \subseteq \bar{S}

W ⩽ {| I |}^{K}

denotes (loosely) the width at the thickest part of the tube B around S.

Figure A2. Illustration of the concept of a transition set on two examples with different shapes. Each of the two images represents an MRF

x = (x_{1}, \dots, x_{n})

n \in N

of the Markov order

K \in N

with nodes corresponding to the individual pixels with values from a finite set of states

x_{i} \in I

| I | < \infty

. The grey area marks the corrupted region

S \subseteq {1, \dots, n}

, where the union of the dark blue and light blue areas is the complement

\bar{S} : = {1, \dots, n} ∖ S

marking the normal region. The dark blue part of

\bar{S}

corresponds to the transition set

B \subseteq \bar{S}

W ⩽ {| I |}^{K}

denotes (loosely) the width at the thickest part of the tube B around S.

Now, we can prove the statement in Proposition 3. In the following, we use the notation

y^{*} : = f (\hat{x})

. Consider now

y : = {({y_{S}^{*}}^{⊤}, y_{B}^{⊤}, x_{\bar{S} ∖ B}^{⊤})}^{⊤}

for some feasible

y_{B}

. Provided

min {| S |, | \bar{S} |}

is sufficiently greater than K, we can always find a feasible transition set B such that

y \in D

. It follows that

\begin{matrix} ∥ \hat{x} - y^{*} ∥_{p} ⩽ {∥ \hat{x} - y ∥}_{p} \overset{A 1}{⟺} & ∥ {\hat{x}}_{S} - y_{S}^{*} ∥_{p}^{p} + ∥ {\hat{x}}_{\bar{S}} - y_{\bar{S}}^{*} ∥_{p}^{p} ⩽ ∥ {\hat{x}}_{S} - y_{S}^{*} ∥_{p}^{p} + {∥ {\hat{x}}_{B} - y_{B} ∥}_{p}^{p} + \underset{= 0}{\underset{︸}{∥ {\hat{x}}_{\bar{S} ∖ B} - x_{\bar{S} ∖ B} ∥_{p}^{p}}} \\ ⟺ & ∥ {\hat{x}}_{\bar{S}} - y_{\bar{S}}^{*} ∥_{p}^{p} ⩽ ∥ {\hat{x}}_{B} - y_{B} ∥_{p}^{p} ⩽ | B | \\ ⟹ & ∥ x_{\bar{S}} - f_{\bar{S}} (\hat{x}) ∥_{p}^{p} ⩽ | B |, \end{matrix}

where, in the penultimate step, we use

x_{i}, y_{i} \in [0, 1]

Now, we show

| B | \in O (\sqrt{| S |})

. Without loss of generality, we assume that S and B have a square shape with equal-length sides, as illustrated in the right part in Figure A2. That is, each side of the grey square has length

\sqrt{| S |}

. The area of the region corresponding to B is then given by

| B | = 4 \sqrt{| S |} W + 4 W^{2}

, where W is a graph-independent constant. Furthermore, by putting the last equation in the inequality

| B | < | S |

and solving the resulting quadratic equation, we obtain a criterion

min {| S |, | \bar{S} |} > {(2 + \sqrt{8})}^{2} W^{2}

that guarantees the existence of a feasible transition set B.

Appendix I. Ablation Study on the Impact of Architectural Components

To highlight the benefits of our model architecture, we performed an additional ablation study on several categories of the MVTec AD dataset. In this study, we compared different architectures, including U-net, SDC-AE, SDC-AE with skip connections, and SDC-CCM. For consistency, we used the same hyperparameters

k = 15

n = 3

in Equation (3) when evaluating performance, except for the ’transistor’ category, where

n = 15

. The corresponding results are presented in the tables below. Note that U-net-small refers to a simplified version of U-net [98], where the middle layers with the smallest resolution were removed to roughly match the number of layers in SDC-AE and SDC-CCM. This modification resulted in a significant performance boost, suggesting that the original U-net may be too deep. The evaluation results underscore the importance of utilizing fine-grained information from the earlier layers in the network, either through skip connections or the proposed CCM module.

Table A1. Experimental results for anomaly segmentation measured with pixel-level AUROC on the MVTec AD dataset.

Category	U-Net	U-Net-Small	SDC-AE	SDC-AE (+Skip)	SDC-CCM
carpet	65.7 ± 0.81	99.4 ± 0.02	99.6 ± 0.02	99.4 ± 0.03	99.4 ± 0.09
grid	70.3 ± 1.94	99.6 ± 0.00	99.6 ± 0.00	99.6 ± 0.00	99.6 ± 0.00
leather	80.3 ± 0.80	99.6 ± 0.03	99.4 ± 0.08	99.1 ± 0.36	99.4 ± 0.07
tile	58.6 ± 1.16	98.4 ± 0.10	97.9 ± 0.00	98.5 ± 0.08	98.4 ± 0.25
cable	89.4 ± 0.10	96.8 ± 0.09	94.5 ± 0.05	97.7 ± 0.26	98.1 ± 0.16
transistor	87.1 ± 0.49	88.5 ± 0.20	89.2 ± 0.17	91.0 ± 0.27	91.3 ± 0.84
avg. all	75.2 ± 11.25	97.05 ± 0.07	96.7 ± 3.79	97.6 ± 2.99	97.7 ± 2.98

Table A2. Experimental results for anomaly recognition measured with image-level AUROC on the MVTec AD dataset.

Category	U-Net	U-Net-Small	SDC-AE	SDC-AE (+Skip)	SDC-CCM
carpet	39.5 ± 0.58	99.2 ± 0.24	99.3 ± 0.04	99.4 ± 0.00	99.6 ± 0.25
grid	84.2 ± 0.13	100 ± 0.00	100 ± 0.00	100 ± 0.00	100 ± 0.00
leather	77.4 ± 3.45	98.0 ± 1.24	99.0 ± 0.19	97.9 ± 0.82	99.4 ± 0.15
tile	81.6 ± 0.78	98.9 ± 0.18	98.5 ± 0.05	99.6 ± 0.41	99.6 ± 0.25
cable	57.0 ± 0.66	93.6 ± 0.23	67.4 ± 1.64	94.2 ± 0.03	96.2 ± 0.16
transistor	64.5 ± 1.94	97.6 ± 0.02	81.2 ± 1.54	97.2 ± 0.19	96.6 ± 0.38
avg. all	67.4 ± 15.70	97.9 ± 0.32	90.9 ± 12.4	98.1 ± 1.98	98.6 ± 1.55

Finally, we note that dilated convolutions allow access to more context within the image, which in some cases improves upon the reconstruction quality. In particular, models without dilated convolutions (without SDC) suffer from the blind spot illustrated in Figure A3. This might occur in larger anomalous regions due to the insufficient context provided by the normal areas, ultimately resulting in predictions that average all possibilities.

Figure A3. Illustration of the importance of modeling long-range dependencies facilitated by dilated convolutions for achieving accurate reconstruction. We can observe how the reconstruction of the model without the SDC modules (middle image) suffers from a blind spot effect toward the center of the corrupted region. This happens due to the insufficient context provided by the normal areas, forcing the model to predict an average of all possibilities.

Appendix J. Illustration of Qualitative Improvement in Reconstruction When Using SDC-CCM over SDC-AE

As outlined in the main body of this paper, in order to achieve high detection and localization performance based on the reconstruction error, the model must replace corrupted regions in the input images with a different content. At the same time, it is important to reproduce uncorrupted regions as accurately as possible to reduce the chance of false positive detections. In this sense, the overall reconstruction quality of the original content during training correlates strongly with the ability of the corresponding model to detect anomalous samples. We compared the reconstruction performance of two model architecture, which we refer to as SDC-AE and SDC-CCM in this paper. During our empirical evaluation, we observed that while SDC-AE generally achieved good reconstruction, it could sometimes result in a higher number of false positive detections compared to SDC-CCM. For example, it struggled to reproduce normal regions that were characterized by frequent changes in the gradient along neighboring pixel values in two object categories, “cable” and “transistor”, from the MVTec AD dataset. In contrast, SDC-CCM accurately reconstructs these regions, resulting in a significant reduction in false positive detections. We show several examples in Figure A4. Similarly, we observed an improvement in reconstruction quality for texture categories. However, the corresponding heatmaps show similar quality. We provide a few examples in Figure A5.

Figure A4. Illustration of the qualitative improvement when using SDC-CCM over SDC-AE. We show six examples: three from the "cable" category and three from the "transistor" category of the MVTec AD dataset. Each row displays the original image, the reconstruction produced by SDC-CCM (reconstruction II), the reconstruction produced by SDC-AE (reconstruction I), the anomaly heatmap from SDC-CCM (anomaly heatmap II), and the anomaly heatmap from SDC-AE (anomaly heatmap I). Note the significant improvement in the quality of the heatmaps.

Figure A5. Illustration of the qualitative improvement when using SDC-CCM over SDC-AE on texture categories from the MVTec AD dataset. We show five examples, one from each of the following categories: “carpet”, “grid”, “leather”, “tile”, and “wood”. Each row displays the original image, the reconstruction produced by SDC-CCM (reconstruction II), the reconstruction produced by SDC-AE (reconstruction I), the anomaly heatmap from SDC-CCM (anomaly heatmap II), and the anomaly heatmap from SDC-AE (anomaly heatmap I).

References

Haselmann, M.; Gruber, D.P.; Tabatabai, P. Anomaly Detection Using Deep Learning Based Image Completion. In Proceedings of the 17th IEEE International Conference on Machine Learning and Applications, ICMLA 2018, Orlando, FL, USA, 17–20 December 2018; Wani, M.A., Kantardzic, M.M., Mouchaweh, M.S., Gama, J., Lughofer, E., Eds.; IEEE: Piscataway, NJ, USA, 2018; pp. 1237–1242. [Google Scholar]
Bergmann, P.; Löwe, S.; Fauser, M.; Sattlegger, D.; Steger, C. Improving Unsupervised Defect Segmentation by Applying Structural Similarity to Autoencoders. In Proceedings of the 14th International Joint Conference on Computer Vision, Imaging and Computer Graphics Theory and Applications, VISIGRAPP 2019, Volume 5: VISAPP, Prague, Czech Republic, 25–27 February 2019; Trémeau, A., Farinella, G.M., Braz, J., Eds.; SciTePress: Setúbal Municipality, Portugal, 2019; pp. 372–380. [Google Scholar]
Wang, L.; Zhang, D.; Guo, J.; Han, Y. Image Anomaly Detection Using Normal Data only by Latent Space Resampling. Appl. Sci. 2020, 10, 8660. [Google Scholar] [CrossRef]
Bergmann, P.; Fauser, M.; Sattlegger, D.; Steger, C. Uninformed Students: Student-Teacher Anomaly Detection with Discriminative Latent Embeddings. In Proceedings of the 2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition, CVPR 2020, Seattle, WA, USA, 13–19 June 2020; pp. 4182–4191. [Google Scholar]
Venkataramanan, S.; Peng, K.; Singh, R.V.; Mahalanobis, A. Attention Guided Anomaly Localization in Images. In Proceedings of the Computer Vision—ECCV 2020—16th European Conference, Glasgow, UK, 23–28 August 2020; Proceedings, Part XVII; Lecture Notes in Computer Science. Vedaldi, A., Bischof, H., Brox, T., Frahm, J., Eds.; Springer: Berlin/Heidelberg, Germany, 2020; Volume 12362, pp. 485–503. [Google Scholar]
Schlegl, T.; Seeböck, P.; Waldstein, S.M.; Schmidt-Erfurth, U.; Langs, G. Unsupervised Anomaly Detection with Generative Adversarial Networks to Guide Marker Discovery. In Proceedings of the Information Processing in Medical Imaging—25th International Conference, IPMI 2017, Boone, NC, USA, 25–30 June 2017; Proceedings; Lecture Notes in Computer Science. Niethammer, M., Styner, M., Aylward, S.R., Zhu, H., Oguz, I., Yap, P., Shen, D., Eds.; Springer: Berlin/Heidelberg, Germany, 2017; Volume 10265, pp. 146–157. [Google Scholar]
Napoletano, P.; Piccoli, F.; Schettini, R. Anomaly Detection in Nanofibrous Materials by CNN-Based Self-Similarity. Sensors 2018, 18, 209. [Google Scholar] [CrossRef]
Böttger, T.; Ulrich, M. Real-time texture error detection on textured surfaces with compressed sensing. Pattern Recognit. Image Anal. 2016, 26, 88–94. [Google Scholar] [CrossRef]
Liu, W.; Li, R.; Zheng, M.; Karanam, S.; Wu, Z.; Bhanu, B.; Radke, R.J.; Camps, O.I. Towards Visually Explaining Variational Autoencoders. In Proceedings of the 2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition, CVPR 2020, Seattle, WA, USA, 13–19 June 2020; pp. 8639–8648. [Google Scholar]
Roth, K.; Pemula, L.; Zepeda, J.; Schölkopf, B.; Brox, T.; Gehler, P.V. Towards Total Recall in Industrial Anomaly Detection. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, CVPR 2022, New Orleans, LA, USA, 18–24 June 2022; pp. 14298–14308. [Google Scholar]
Wan, Q.; Gao, L.; Li, X.; Wen, L. Industrial Image Anomaly Localization Based on Gaussian Clustering of Pretrained Feature. IEEE Trans. Ind. Electron. 2022, 69, 6182–6192. [Google Scholar] [CrossRef]
Chen, X.; Konukoglu, E. Unsupervised Detection of Lesions in Brain MRI using constrained adversarial auto-encoders. arXiv 2018, arXiv:1806.04972. [Google Scholar]
Schlegl, T.; Seeböck, P.; Waldstein, S.M.; Langs, G.; Schmidt-Erfurth, U. f-AnoGAN: Fast unsupervised anomaly detection with generative adversarial networks. Med. Image Anal. 2019, 54, 30–44. [Google Scholar] [CrossRef]
Tan, J.; Hou, B.; Day, T.; Simpson, J.M.; Rueckert, D.; Kainz, B. Detecting Outliers with Poisson Image Interpolation. In Proceedings of the Medical Image Computing and Computer Assisted Intervention—MICCAI 2021—24th International Conference, Strasbourg, France, 27 September–1 October 2021; Proceedings, Part V; Lecture Notes in Computer Science. de Bruijne, M., Cattin, P.C., Cotin, S., Padoy, N., Speidel, S., Zheng, Y., Essert, C., Eds.; Springer: Berlin/Heidelberg, Germany, 2021; Volume 12905, pp. 581–591. [Google Scholar]
Zimmerer, D.; Isensee, F.; Petersen, J.; Kohl, S.; Maier-Hein, K.H. Unsupervised Anomaly Localization Using Variational Auto-Encoders. In Proceedings of the Medical Image Computing and Computer Assisted Intervention—MICCAI 2019—22nd International Conference, Shenzhen, China, 13–17 October 2019; Proceedings, Part IV; Lecture Notes in Computer Science. Shen, D., Liu, T., Peters, T.M., Staib, L.H., Essert, C., Zhou, S., Yap, P., Khan, A.R., Eds.; Springer: Berlin/Heidelberg, Germany, 2019; Volume 11767, pp. 289–297. [Google Scholar]
Abati, D.; Porrello, A.; Calderara, S.; Cucchiara, R. Latent Space Autoregression for Novelty Detection. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2019, Long Beach, CA, USA, 16–20 June 2019; pp. 481–490. [Google Scholar]
Defard, T.; Setkov, A.; Loesch, A.; Audigier, R. PaDiM: A Patch Distribution Modeling Framework for Anomaly Detection and Localization. In Proceedings of the Pattern Recognition. ICPR International Workshops and Challenges, Virtual Event, 10–15 January 2021; Proceedings, Part IV; Lecture Notes in Computer Science. Bimbo, A.D., Cucchiara, R., Sclaroff, S., Farinella, G.M., Mei, T., Bertini, M., Escalante, H.J., Vezzani, R., Eds.; Springer: Berlin/Heidelberg, Germany, 2020; Volume 12664, pp. 475–489. [Google Scholar]
Hotelling, H. Analysis of a complex of statistical variables into principal components. J. Educ. Psychol. 1933, 24, 417–441. [Google Scholar] [CrossRef]
Schölkopf, B.; Smola, A.J.; Müller, K. Nonlinear Component Analysis as a Kernel Eigenvalue Problem. Neural Comput. 1998, 10, 1299–1319. [Google Scholar] [CrossRef]
Hoffmann, H. Kernel PCA for novelty detection. Pattern Recognit. 2007, 40, 863–874. [Google Scholar] [CrossRef]
Schölkopf, B.; Platt, J.C.; Shawe-Taylor, J.; Smola, A.J.; Williamson, R.C. Estimating the Support of a High-Dimensional Distribution. Neural Comput. 2001, 13, 1443–1471. [Google Scholar] [CrossRef] [PubMed]
Tax, D.M.J.; Duin, R.P.W. Support Vector Data Description. Mach. Learn. 2004, 54, 45–66. [Google Scholar] [CrossRef]
Knorr, E.M.; Ng, R.T.; Tucakov, V. Distance-Based Outliers: Algorithms and Applications. VLDB J. 2000, 8, 237–253. [Google Scholar] [CrossRef]
Ramaswamy, S.; Rastogi, R.; Shim, K. Efficient Algorithms for Mining Outliers from Large Data Sets. In Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data, Dallas, TX, USA, 16–18 May 2000; Chen, W., Naughton, J.F., Bernstein, P.A., Eds.; ACM: New York, NY, USA, 2000; pp. 427–438. [Google Scholar]
Parzen, E. On estimation of a probability density function and mode. Ann. Math. Statist 1962, 33, 106–1076. [Google Scholar] [CrossRef]
Principi, E.; Vesperini, F.; Squartini, S.; Piazza, F. Acoustic novelty detection with adversarial autoencoders. In Proceedings of the 2017 International Joint Conference on Neural Networks, IJCNN 2017, Anchorage, AK, USA, 14–19 May 2017; pp. 3324–3330. [Google Scholar]
Chalapathy, R.; Menon, A.K.; Chawla, S. Robust, Deep and Inductive Anomaly Detection. In Proceedings of the Machine Learning and Knowledge Discovery in Databases—European Conference, ECML PKDD 2017, Skopje, Macedonia, 18–22 September 2017; Proceedings, Part I; Lecture Notes in Computer Science. Ceci, M., Hollmén, J., Todorovski, L., Vens, C., Dzeroski, S., Eds.; Springer: Berlin/Heidelberg, Germany, 2017; Volume 10534, pp. 36–51. [Google Scholar]
Kieu, T.; Yang, B.; Guo, C.; Jensen, C.S. Outlier Detection for Time Series with Recurrent Autoencoder Ensembles. In Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI 2019, Macao, China, 10–16 August 2019; Kraus, S., Ed.; 2019; pp. 2725–2732. [Google Scholar]
Zhou, C.; Paffenroth, R.C. Anomaly Detection with Robust Deep Autoencoders. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Halifax, NS, Canada, 13–17 August 2017; ACM: New York, NY, USA, 2017; pp. 665–674. [Google Scholar]
Zong, B.; Song, Q.; Min, M.R.; Cheng, W.; Lumezanu, C.; Cho, D.; Chen, H. Deep Autoencoding Gaussian Mixture Model for Unsupervised Anomaly Detection. In Proceedings of the 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, 30 April–3 May 2018. [Google Scholar]
Kim, K.H.; Shim, S.; Lim, Y.; Jeon, J.; Choi, J.; Kim, B.; Yoon, A.S. RaPP: Novelty Detection with Reconstruction along Projection Pathway. In Proceedings of the 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, 26–30 April 2020. [Google Scholar]
Deng, J.; Zhang, Z.; Marchi, E.; Schuller, B.W. Sparse Autoencoder-Based Feature Transfer Learning for Speech Emotion Recognition. In Proceedings of the 2013 Humaine Association Conference on Affective Computing and Intelligent Interaction, ACII 2013, Geneva, Switzerland, 2–5 September 2013; pp. 511–516. [Google Scholar]
Erfani, S.M.; Rajasegarar, S.; Karunasekera, S.; Leckie, C. High-dimensional and large-scale anomaly detection using a linear one-class SVM with deep learning. Pattern Recognit. 2016, 58, 121–134. [Google Scholar] [CrossRef]
Kim, M.; Kim, J.; Yu, J.; Choi, J.K. Active anomaly detection based on deep one-class classification. Pattern Recognit. Lett. 2023, 167, 18–24. [Google Scholar] [CrossRef]
Ruff, L.; Görnitz, N.; Deecke, L.; Siddiqui, S.A.; Vandermeulen, R.A.; Binder, A.; Müller, E.; Kloft, M. Deep One-Class Classification. In Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, 10–15 July 2018; Proceedings of Machine Learning Research. Dy, J.G., Krause, A., Eds.; 2018; Volume 80, pp. 4390–4399. [Google Scholar]
Golan, I.; El-Yaniv, R. Deep Anomaly Detection Using Geometric Transformations. In Proceedings of the Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, Montréal, QC, Canada, 3–8 December 2018; Bengio, S., Wallach, H.M., Larochelle, H., Grauman, K., Cesa-Bianchi, N., Garnett, R., Eds.; pp. 9781–9791. [Google Scholar]
Tack, J.; Mo, S.; Jeong, J.; Shin, J. CSI: Novelty Detection via Contrastive Learning on Distributionally Shifted Instances. In Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, Virtual, 6–12 December 2020; Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M., Lin, H., Eds.; [Google Scholar]
Zavrtanik, V.; Kristan, M.; Skocaj, D. DRÆM—A discriminatively trained reconstruction embedding for surface anomaly detection. In Proceedings of the 2021 IEEE/CVF International Conference on Computer Vision, ICCV 2021, Montreal, QC, Canada, 10–17 October 2021; pp. 8310–8319. [Google Scholar]
Zavrtanik, V.; Kristan, M.; Skocaj, D. Reconstruction by inpainting for visual anomaly detection. Pattern Recognit. 2021, 112, 107706. [Google Scholar] [CrossRef]
Li, C.; Sohn, K.; Yoon, J.; Pfister, T. CutPaste: Self-Supervised Learning for Anomaly Detection and Localization. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2021, Virtual, 19–25 June 2021; pp. 9664–9674. [Google Scholar]
Pirnay, J.; Chai, K. Inpainting Transformer for Anomaly Detection. In Proceedings of the Image Analysis and Processing—ICIAP 2022—21st International Conference, Lecce, Italy, 23–27 May 2022; Proceedings, Part II; Lecture Notes in Computer Science. Sclaroff, S., Distante, C., Leo, M., Farinella, G.M., Tombari, F., Eds.; Springer: Berlin/Heidelberg, Germany, 2022; Volume 13232, pp. 394–406. [Google Scholar]
Lee, S.; Lee, S.; Song, B.C. CFA: Coupled-Hypersphere-Based Feature Adaptation for Target-Oriented Anomaly Localization. IEEE Access 2022, 10, 78446–78454. [Google Scholar] [CrossRef]
Kim, D.; Park, C.; Cho, S.; Lee, S. FAPM: Fast Adaptive Patch Memory for Real-time Industrial Anomaly Detection. arXiv 2022, arXiv:2211.07381. [Google Scholar]
Bae, J.; Lee, J.; Kim, S. Image Anomaly Detection and Localization with Position and Neighborhood Information. arXiv 2022, arXiv:2211.12634. [Google Scholar]
Tsai, C.; Wu, T.; Lai, S. Multi-Scale Patch-Based Representation Learning for Image Anomaly Detection and Segmentation. In Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision, WACV 2022, Waikoloa, HI, USA, 3–8 January 2022; pp. 3065–3073. [Google Scholar]
Zou, Y.; Jeong, J.; Pemula, L.; Zhang, D.; Dabeer, O. SPot-the-Difference Self-supervised Pre-training for Anomaly Detection and Segmentation. In Proceedings of the Computer Vision—ECCV 2022—17th European Conference, Tel Aviv, Israel, 23–27 October 2022; Proceedings, Part XXX; Lecture Notes in Computer Science. Avidan, S., Brostow, G.J., Cissé, M., Farinella, G.M., Hassner, T., Eds.; Springer: Berlin/Heidelberg, Germany, 2022; Volume 13690, pp. 392–408. [Google Scholar]
Li, N.; Jiang, K.; Ma, Z.; Wei, X.; Hong, X.; Gong, Y. Anomaly Detection Via Self-Organizing Map. In Proceedings of the 2021 IEEE International Conference on Image Processing, ICIP 2021, Anchorage, AK, USA, 19–22 September 2021; pp. 974–978. [Google Scholar]
Salehi, M.; Sadjadi, N.; Baselizadeh, S.; Rohban, M.H.; Rabiee, H.R. Multiresolution Knowledge Distillation for Anomaly Detection. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2021, Virtual, 19–25 June 2021; pp. 14902–14912. [Google Scholar]
Deng, H.; Li, X. Anomaly Detection via Reverse Distillation from One-Class Embedding. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, CVPR 2022, New Orleans, LA, USA, 18–24 June 2022; pp. 9727–9736. [Google Scholar]
Rudolph, M.; Wehrbein, T.; Rosenhahn, B.; Wandt, B. Asymmetric Student-Teacher Networks for Industrial Anomaly Detection. In Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision, WACV 2023, Waikoloa, HI, USA, 2–7 January 2023; pp. 2591–2601. [Google Scholar]
Cao, Y.; Wan, Q.; Shen, W.; Gao, L. Informative knowledge distillation for image anomaly segmentation. Knowl. Based Syst. 2022, 248, 108846. [Google Scholar] [CrossRef]
Zhang, K.; Wang, B.; Kuo, C.J. PEDENet: Image anomaly localization via patch embedding and density estimation. Pattern Recognit. Lett. 2022, 153, 144–150. [Google Scholar] [CrossRef]
Wan, Q.; Gao, L.; Li, X.; Wen, L. Unsupervised Image Anomaly Detection and Segmentation Based on Pretrained Feature Mapping. IEEE Trans. Ind. Inform. 2023, 19, 2330–2339. [Google Scholar] [CrossRef]
Wan, Q.; Cao, Y.; Gao, L.; Shen, W.; Li, X. Position Encoding Enhanced Feature Mapping for Image Anomaly Detection. In Proceedings of the 18th IEEE International Conference on Automation Science and Engineering, CASE 2022, Mexico City, Mexico, 20–24 August 2022; pp. 876–881. [Google Scholar]
Zheng, Y.; Wang, X.; Deng, R.; Bao, T.; Zhao, R.; Wu, L. Focus Your Distribution: Coarse-to-Fine Non-Contrastive Learning for Anomaly Detection and Localization. In Proceedings of the IEEE International Conference on Multimedia and Expo, ICME 2022, Taipei, Taiwan, 18–22 July 2022; pp. 1–6. [Google Scholar]
Gudovskiy, D.A.; Ishizaka, S.; Kozuka, K. CFLOW-AD: Real-Time Unsupervised Anomaly Detection with Localization via Conditional Normalizing Flows. In Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision, WACV 2022, Waikoloa, HI, USA, 3–8 January 2022; pp. 1819–1828. [Google Scholar]
Kim, Y.; Jang, H.; Lee, D.; Choi, H. AltUB: Alternating Training Method to Update Base Distribution of Normalizing Flow for Anomaly Detection. arXiv 2022, arXiv:2210.14913. [Google Scholar]
Yi, J.; Yoon, S. Patch SVDD: Patch-Level SVDD for Anomaly Detection and Segmentation. In Proceedings of the Computer Vision—ACCV 2020—15th Asian Conference on Computer Vision, Kyoto, Japan, 30 November–4 December 2020; Revised Selected Papers, Part VI; Lecture Notes in Computer Science. Ishikawa, H., Liu, C., Pajdla, T., Shi, J., Eds.; Springer: Berlin/Heidelberg, Germany, 2020; Volume 12627, pp. 375–390. [Google Scholar]
Hu, C.; Chen, K.; Shao, H. A Semantic-Enhanced Method Based On Deep SVDD for Pixel-Wise Anomaly Detection. In Proceedings of the 2021 IEEE International Conference on Multimedia and Expo, ICME 2021, Shenzhen, China, 5–9 July 2021; pp. 1–6. [Google Scholar]
Yang, M.; Wu, P.; Feng, H. MemSeg: A semi-supervised method for image surface defect detection using differences and commonalities. Eng. Appl. Artif. Intell. 2023, 119, 105835. [Google Scholar] [CrossRef]
Yan, Y.; Wang, D.; Zhou, G.; Chen, Q. Unsupervised Anomaly Segmentation Via Multilevel Image Reconstruction and Adaptive Attention-Level Transition. IEEE Trans. Instrum. Meas. 2021, 70, 5015712. [Google Scholar] [CrossRef]
Collin, A.; Vleeschouwer, C.D. Improved anomaly detection by training an autoencoder with skip connections on images corrupted with Stain-shaped noise. In Proceedings of the 25th International Conference on Pattern Recognition, ICPR 2020, Virtual Event/Milan, Italy, 10–15 January 2021; pp. 7915–7922. [Google Scholar]
Tao, X.; Zhang, D.; Ma, W.; Hou, Z.; Lu, Z.; Adak, C. Unsupervised Anomaly Detection for Surface Defects with Dual-Siamese Network. IEEE Trans. Ind. Inform. 2022, 18, 7707–7717. [Google Scholar] [CrossRef]
Liu, T.; Li, B.; Zhao, Z.; Du, X.; Jiang, B.; Geng, L. Reconstruction from edge image combined with color and gradient difference for industrial surface anomaly detection. arXiv 2022, arXiv:2210.14485. [Google Scholar]
Kim, D.; Jeong, D.; Kim, H.; Chong, K.; Kim, S.; Cho, H. Spatial Contrastive Learning for Anomaly Detection and Localization. IEEE Access 2022, 10, 17366–17376. [Google Scholar] [CrossRef]
Huang, C.; Xu, Q.; Wang, Y.; Wang, Y.; Zhang, Y. Self-Supervised Masking for Unsupervised Anomaly Detection and Localization. arXiv 2022, arXiv:2205.06568. [Google Scholar] [CrossRef]
Liznerski, P.; Ruff, L.; Vandermeulen, R.A.; Franks, B.J.; Kloft, M.; Müller, K.R. Explainable Deep One-Class Classification. In Proceedings of the 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, 3–7 May 2021. [Google Scholar]
Bae, J.; Lee, J.; Kim, S. PNI: Industrial Anomaly Detection using Position and Neighborhood Information. In Proceedings of the IEEE/CVF International Conference on Computer Vision, ICCV 2023, Paris, France, 1–6 October 2023; pp. 6350–6360. [Google Scholar]
Schlüter, H.M.; Tan, J.; Hou, B.; Kainz, B. Natural Synthetic Anomalies for Self-supervised Anomaly Detection and Localization. In Proceedings of the Computer Vision—ECCV 2022—17th European Conference, Tel Aviv, Israel, 23–27 October 2022; Proceedings, Part XXXI; Lecture Notes in Computer Science. Avidan, S., Brostow, G.J., Cissé, M., Farinella, G.M., Hassner, T., Eds.; Springer: Berlin/Heidelberg, Germany, 2022; Volume 13691, pp. 474–489. [Google Scholar]
Dehaene, D.; Frigo, O.; Combrexelle, S.; Eline, P. Iterative energy-based projection on a normal data manifold for anomaly localization. In Proceedings of the 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, 26–30 April 2020. [Google Scholar]
Höner, J.; Nakajima, S.; Bauer, A.; Müller, K.R.; Görnitz, N. Minimizing Trust Leaks for Robust Sybil Detection. In Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6–11 August 2017; Proceedings of Machine Learning Research. Precup, D., Teh, Y.W., Eds.; 2017; Volume 70, pp. 1520–1528. [Google Scholar]
Song, J.W.; Kong, K.; Park, Y.I.; Kim, S.G.; Kang, S. AnoSeg: Anomaly Segmentation Network Using Self-Supervised Learning. arXiv 2021, arXiv:2110.03396. [Google Scholar]
Kohlbrenner, M.; Bauer, A.; Nakajima, S.; Binder, A.; Samek, W.; Lapuschkin, S. Towards Best Practice in Explaining Neural Network Decisions with LRP. In Proceedings of the 2020 International Joint Conference on Neural Networks, IJCNN 2020, Glasgow, UK, 19–24 July 2020; pp. 1–7. [Google Scholar]
Lee, Y.; Kang, P. AnoViT: Unsupervised Anomaly Detection and Localization with Vision Transformer-Based Encoder-Decoder. IEEE Access 2022, 10, 46717–46724. [Google Scholar] [CrossRef]
Jiang, J.; Zhu, J.; Bilal, M.; Cui, Y.; Kumar, N.; Dou, R.; Su, F.; Xu, X. Masked Swin Transformer Unet for Industrial Anomaly Detection. IEEE Trans. Ind. Inform. 2023, 19, 2200–2209. [Google Scholar] [CrossRef]
Wu, J.; Chen, D.; Fuh, C.; Liu, T. Learning Unsupervised Metaformer for Anomaly Detection. In Proceedings of the 2021 IEEE/CVF International Conference on Computer Vision, ICCV 2021, Montreal, QC, Canada, 10–17 October 2021; pp. 4349–4358. [Google Scholar]
Jiang, X.; Liu, J.; Wang, J.; Nie, Q.; Wu, K.; Liu, Y.; Wang, C.; Zheng, F. SoftPatch: Unsupervised Anomaly Detection with Noisy Data. In Proceedings of the NeurIPS, New Orleans, LA, USA, 28 November–9 December 2022. [Google Scholar]
Ruff, L.; Kauffmann, J.R.; Vandermeulen, R.A.; Samek, W.; Kloft, M.; Dietterich, T.G.; Müller, K.R. A Unifying Review of Deep and Shallow Anomaly Detection. Proc. IEEE 2021, 109, 756–795. [Google Scholar] [CrossRef]
Kauffmann, J.; Müller, K.R.; Montavon, G. Towards explaining anomalies: A deep Taylor decomposition of one-class models. Pattern Recognit. 2020, 101, 107198. [Google Scholar] [CrossRef]
Chong, P.; Ruff, L.; Kloft, M.; Binder, A. Simple and Effective Prevention of Mode Collapse in Deep One-Class Classification. In Proceedings of the 2020 International Joint Conference on Neural Networks, IJCNN 2020, Glasgow, UK, 19–24 July 2020; pp. 1–9. [Google Scholar]
Hu, C.; Feng, Y.; Kamigaito, H.; Takamura, H.; Okumura, M. One-class Text Classification with Multi-modal Deep Support Vector Data Description. In Proceedings of the 16th Conference of the European Chapter of the Association for Computational Linguistics: Main Volume, EACL 2021, Online, 19–23 April 2021; Merlo, P., Tiedemann, J., Tsarfaty, R., Eds.; Association for Computational Linguistics: Stroudsburg, PA, USA, 2021; pp. 3378–3390. [Google Scholar]
Ranzato, M.A.; Boureau, Y.l.; Cun, Y. Sparse Feature Learning for Deep Belief Networks. In Proceedings of the Advances in Neural Information Processing Systems, Vancouver, Canada, 3–6 December 2007; Platt, J., Koller, D., Singer, Y., Roweis, S., Eds.; Curran Associates, Inc.: New York, NY, USA, 2007; Volume 20. [Google Scholar]
Le, Q.V.; Ngiam, J.; Coates, A.; Lahiri, A.; Prochnow, B.; Ng, A.Y. On optimization methods for deep learning. In Proceedings of the 28th International Conference on Machine Learning ICML 2011, Bellevue, WA, USA, 28 June–2 July 2011; Getoor, L., Scheffer, T., Eds.; pp. 265–272. [Google Scholar]
Rifai, S.; Vincent, P.; Muller, X.; Glorot, X.; Bengio, Y. Contractive Auto-Encoders: Explicit Invariance During Feature Extraction. In Proceedings of the 28th International Conference on Machine Learning, ICML 2011, Bellevue, WI, USA, 28 June–2 July 2011; Omnipress: Madison, WI, USA, 2011; pp. 833–840. [Google Scholar]
Alain, G.; Bengio, Y. What regularized auto-encoders learn from the data-generating distribution. J. Mach. Learn. Res. 2014, 15, 3563–3593. [Google Scholar]
Pathak, D.; Krähenbühl, P.; Donahue, J.; Darrell, T.; Efros, A.A. Context Encoders: Feature Learning by Inpainting. In Proceedings of the 2016 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2016, Las Vegas, NV, USA, 27–30 June 2016; pp. 2536–2544. [Google Scholar]
Iizuka, S.; Simo-Serra, E.; Ishikawa, H. Globally and locally consistent image completion. ACM Trans. Graph. 2017, 36, 107:1–107:14. [Google Scholar] [CrossRef]
Yu, J.; Lin, Z.; Yang, J.; Shen, X.; Lu, X.; Huang, T.S. Generative Image Inpainting with Contextual Attention. In Proceedings of the 2018 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2018, Salt Lake City, UT, USA, 18–22 June 2018; pp. 5505–5514. [Google Scholar]
Liu, G.; Reda, F.A.; Shih, K.J.; Wang, T.; Tao, A.; Catanzaro, B. Image Inpainting for Irregular Holes Using Partial Convolutions. In Proceedings of the Computer Vision—ECCV 2018—15th European Conference, Munich, Germany, 8–14 September 2018; Proceedings, Part XI; Lecture Notes in Computer Science. Ferrari, V., Hebert, M., Sminchisescu, C., Weiss, Y., Eds.; Springer: Berlin/Heidelberg, Germany, 2018; Volume 11215, pp. 89–105. [Google Scholar]
Yu, J.; Lin, Z.; Yang, J.; Shen, X.; Lu, X.; Huang, T.S. Free-Form Image Inpainting with Gated Convolution. In Proceedings of the 2019 IEEE/CVF International Conference on Computer Vision, ICCV 2019, Seoul, Republic of Korea, 27 October–2 November 2019; pp. 4470–4479. [Google Scholar]
Bhattad, A.; Rock, J.; Forsyth, D.A. Detecting Anomalous Faces with ‘No Peeking’ Autoencoders. arXiv 2018, arXiv:1802.05798. [Google Scholar]
Vincent, P.; Larochelle, H.; Bengio, Y.; Manzagol, P. Extracting and composing robust features with denoising autoencoders. In Proceedings of the Machine Learning, Proceedings of the Twenty-Fifth International Conference (ICML 2008), Helsinki, Finland, 5–9 June 2008; ACM International Conference Proceeding, Series. Cohen, W.W., McCallum, A., Roweis, S.T., Eds.; ACM: New York, NY, USA, 2008; Volume 307, pp. 1096–1103. [Google Scholar]
Kascenas, A.; Pugeault, N.; O’Neil, A.Q. Denoising Autoencoders for Unsupervised Anomaly Detection in Brain MRI. In Proceedings of the 5th International Conference on Medical Imaging with Deep Learning, PMLR, Zurich, Switzerland, 6–8 July 2022; Volume 172, pp. 653–664. [Google Scholar]
Liu, Z.; Zhou, Y.; Xu, Y.; Wang, Z. SimpleNet: A Simple Network for Image Anomaly Detection and Localization. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, CVPR 2023, Vancouver, BC, Canada, 17–24 June 2023; pp. 20402–20411. [Google Scholar]
Bergmann, P.; Batzner, K.; Fauser, M.; Sattlegger, D.; Steger, C. The MVTec Anomaly Detection Dataset: A Comprehensive Real-World Dataset for Unsupervised Anomaly Detection. Int. J. Comput. Vis. 2021, 129, 1038–1059. [Google Scholar] [CrossRef]
Cimpoi, M.; Maji, S.; Kokkinos, I.; Mohamed, S.; Vedaldi, A. Describing Textures in the Wild. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), Columbus, OH, USA, 23–28 June 2014. [Google Scholar]
Badrinarayanan, V.; Kendall, A.; Cipolla, R. SegNet: A Deep Convolutional Encoder-Decoder Architecture for Image Segmentation. IEEE Trans. Pattern Anal. Mach. Intell. 2017, 39, 2481–2495. [Google Scholar] [CrossRef]
Ronneberger, O.; Fischer, P.; Brox, T. U-Net: Convolutional Networks for Biomedical Image Segmentation. In Proceedings of the Medical Image Computing and Computer-Assisted Intervention—MICCAI 2015—18th International Conference, Munich, Germany, 5–9 October 2015; Proceedings, Part III; Lecture Notes in Computer Science. Navab, N., Hornegger, J., III, Wells, W.M., Frangi, A.F., Eds.; Springer: Berlin/Heidelberg, Germany, 2015; Volume 9351, pp. 234–241. [Google Scholar]
Schuster, R.; Wasenmüller, O.; Unger, C.; Stricker, D. SDC—Stacked Dilated Convolution: A Unified Descriptor Network for Dense Matching Tasks. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2019, Long Beach, CA, USA, 16–20 June 2019; pp. 2556–2565. [Google Scholar]
Koller, D.; Friedman, N. Probabilistic Graphical Models: Principles and Techniques—Adaptive Computation and Machine Learning; The MIT Press: Cambridge, MA, USA, 2009. [Google Scholar]
Wainwright, M.J.; Jordan, M.I. Graphical Models, Exponential Families, and Variational Inference. Found. Trends Mach. Learn. 2008, 1, 1–305. [Google Scholar] [CrossRef]
Lafferty, J. Conditional random fields: Probabilistic models for segmenting and labeling sequence data. In Proceedings of the ICML, Williamstown, MA, USA, 28 June–1 July 2001; Morgan Kaufmann: Burlington, MA, USA, 2001; pp. 282–289. [Google Scholar]
Bauer, A.; Görnitz, N.; Biegler, F.; Müller, K.R.; Kloft, M. Efficient Algorithms for Exact Inference in Sequence Labeling SVMs. IEEE Trans. Neural Netw. Learn. Syst. 2014, 25, 870–881. [Google Scholar] [CrossRef] [PubMed]
Bauer, A.; Braun, M.L.; Müller, K.R. Accurate Maximum-Margin Training for Parsing with Context-Free Grammars. IEEE Trans. Neural Netw. Learn. Syst. 2017, 28, 44–56. [Google Scholar] [CrossRef]
Bauer, A.; Nakajima, S.; Müller, K.R. Efficient Exact Inference with Loss Augmented Objective in Structured Learning. IEEE Trans. Neural Netw. Learn. Syst. 2017, 28, 2566–2579. [Google Scholar] [CrossRef]
Bauer, A.; Nakajima, S.; Görnitz, N.; Müller, K.R. Optimizing for Measure of Performance in Max-Margin Parsing. IEEE Trans. Neural Netw. Learn. Syst. 2019, 21, 2680–2684. [Google Scholar] [CrossRef] [PubMed]
Bauer, A.; Nakajima, S.; Görnitz, N.; Müller, K.R. Partial Optimality of Dual Decomposition for MAP Inference in Pairwise MRFs. In Proceedings of the Machine Learning Research, Naha, Japan, 16–18 April 2019; Proceedings of Machine Learning Research. Chaudhuri, K., Sugiyama, M., Eds.; Volume 89, pp. 1696–1703. [Google Scholar]
Bauer, A.; Nakajima, S.; Müller, K.R. Polynomial-Time Constrained Message Passing for Exact MAP Inference on Discrete Models with Global Dependencies. Mathematics 2023, 11, 2628. [Google Scholar] [CrossRef]
Bergmann, P.; Fauser, M.; Sattlegger, D.; Steger, C. MVTec AD—A Comprehensive Real-World Dataset for Unsupervised Anomaly Detection. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2019, Long Beach, CA, USA, 16–20 June 2019; pp. 9592–9600. [Google Scholar]
Kingma, D.P.; Ba, J. Adam: A Method for Stochastic Optimization. In Proceedings of the 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, 7–9 May 2015; Bengio, Y., LeCun, Y., Eds.; Conference Track Proceedings. [Google Scholar]
Zhou, Y.; Xu, X.; Song, J.; Shen, F.; Shen, H.T. MSFlow: Multi-Scale Flow-based Framework for Unsupervised Anomaly Detection. arXiv 2023, arXiv:2308.15300. [Google Scholar]

Figure 1. Anomaly detection results of our approach on a few images from the MVTec AD dataset. The first row shows the input images and the second row an overlay with the predicted anomaly heatmap.

Figure 2. Illustration of the reconstruction effect of our model trained either on the wood, carpet, or grid images (without defects) from the MVTec AD dataset.

Figure 3. Illustration of our anomaly detection process after the training. Given input

\hat{x}

, we first, see (1) compute an output

f_{θ} (\hat{x})

by replicating normal regions and replacing irregularities with locally consistent patterns. Then, see (2), we compute a pixel-wise squared difference

{(\hat{x} - f_{θ} (\hat{x}))}^{2}

, which is subsequently averaged over the color channels to produce the difference map

Diff [\hat{x}, f_{θ} (\hat{x})] \in R^{h \times w}

. In the last step, see (3), we apply a series of averaging convolutions

G_{k}

to the difference map to produce our final anomaly heatmap

{anomap}_{f_{θ}}^{n, k} (\hat{x})

Figure 3. Illustration of our anomaly detection process after the training. Given input

\hat{x}

, we first, see (1) compute an output

f_{θ} (\hat{x})

by replicating normal regions and replacing irregularities with locally consistent patterns. Then, see (2), we compute a pixel-wise squared difference

{(\hat{x} - f_{θ} (\hat{x}))}^{2}

, which is subsequently averaged over the color channels to produce the difference map

Diff [\hat{x}, f_{θ} (\hat{x})] \in R^{h \times w}

. In the last step, see (3), we apply a series of averaging convolutions

G_{k}

to the difference map to produce our final anomaly heatmap

{anomap}_{f_{θ}}^{n, k} (\hat{x})

Figure 4. Illustration of data generation for training. After randomly choosing the number and locations of the patches to be modified, we create new content by gluing the extracted patches with the corresponding replacements. Given a real-valued mask

M \in {[0, 1]}^{\tilde{h} \times \tilde{w} \times 3}

marking corrupted regions within a patch, an original image patch

x

, and a corresponding replacement

y

, we create the next corrupted patch by merging the two patches together according to the formula

\hat{x} : = M ⊙ y + \bar{M} ⊙ x

. All mask shapes

M

are created by applying Gaussian distortion to the same (static) mask, representing a filled disk at the center of the patch with a smoothly fading boundary toward the exterior of the disk.

M \in {[0, 1]}^{\tilde{h} \times \tilde{w} \times 3}

marking corrupted regions within a patch, an original image patch

x

, and a corresponding replacement

y

, we create the next corrupted patch by merging the two patches together according to the formula

\hat{x} : = M ⊙ y + \bar{M} ⊙ x

. All mask shapes

M

are created by applying Gaussian distortion to the same (static) mask, representing a filled disk at the center of the patch with a smoothly fading boundary toward the exterior of the disk.

Figure 5. Illustration of our network architecture SDC-CCM including the convex combination module (CCM) marked in brown and the skip-connections represented by the horizontal arrows. Without these additional elements, we obtain our baseline architecture SDC-AE.

Figure 6. Illustration of the CCM module. The module receives two inputs:

x_{s}

along the skip connection and

x_{c}

from the current layer below. In the first step (image on the left), we compute the squared difference of the two and stack it together with the original values

[x_{s}, x_{c}, {(x_{s} - x_{c})}^{2}]

. This combined feature map is processed by two convolutional layers. The first layer uses batch normalization with ReLU activation. The second layer uses batch normalization and a sigmoid activation function to produce a coefficient matrix

β

. In the second step (image on the right), we compute the output of the module as a (component-wise) convex combination

x_{o} = β \cdot x_{s} + (1 - β) \cdot x_{c}

, where

1

is a tensor of ones.

Figure 6. Illustration of the CCM module. The module receives two inputs:

x_{s}

along the skip connection and

x_{c}

from the current layer below. In the first step (image on the left), we compute the squared difference of the two and stack it together with the original values

[x_{s}, x_{c}, {(x_{s} - x_{c})}^{2}]

β

. In the second step (image on the right), we compute the output of the module as a (component-wise) convex combination

x_{o} = β \cdot x_{s} + (1 - β) \cdot x_{c}

, where

1

is a tensor of ones.

Figure 7. Illustration of the general concept of the orthogonal projection f onto a data manifold

D

. Here, anomalous samples

\hat{x} \in R^{n}

(red dots) are projected to points

x : = f (\hat{x}) \in D

(blue dots) in a way that minimizes the distance

d (\hat{x}, x) = {inf}_{y \in D} d (\hat{x}, y)

Figure 7. Illustration of the general concept of the orthogonal projection f onto a data manifold

D

. Here, anomalous samples

\hat{x} \in R^{n}

(red dots) are projected to points

x : = f (\hat{x}) \in D

(blue dots) in a way that minimizes the distance

d (\hat{x}, x) = {inf}_{y \in D} d (\hat{x}, y)

Figure 8. Illustration of the connections between the different types of regularized autoencoders. For a small variance of the corruption noise, the DAE becomes similar to the CAE. This, in turn, gives rise to the RCAE, where the contraction is imposed explicitly on the whole reconstruction mapping. A special instance of PAE given by the orthogonal projection yields an optimal solution for the optimization problem of the RCAE. On the other hand, the training objective for PAE can be seen as an extension of DAE to more complex input modifications beyond additive noise. Finally, a common variant of the sparse autoencoder (SAE) applies an

l^{1}

penalty on the hidden units, resulting in saturation toward zero similar to the CAE.

l^{1}

penalty on the hidden units, resulting in saturation toward zero similar to the CAE.

Figure 9. Illustration of the conservation effect of the orthogonal projections with respect to different

l^{p}

-norms. Here, the anomalous sample

\hat{x}

is orthogonally projected onto the manifold

D

(depicted by a red ellipsoid) according to

∥ \hat{x} - y_{p}^{*} ∥_{p} = {inf}_{y \in D} {∥ \hat{x} - y ∥}_{p}

for

p \in {1, 2, \infty}

. The remaining three colors (green, blue, and yellow) represent rescaled unit circles around

\hat{x}

with respect to

l^{1}

l^{2}

and

l^{\infty}

-norms. The intersection points of each circle with

D

mark the orthogonal projection of

x

onto

D

for the corresponding norm. We can see that projections

y_{p}^{*}

for lower p-values better preserve the content in

\hat{x}

according to the higher sparsity of the difference

\hat{x} - y_{p}^{*}

, which results in smaller modified regions

S (\hat{x}, y_{p}^{*})

Figure 9. Illustration of the conservation effect of the orthogonal projections with respect to different

l^{p}

-norms. Here, the anomalous sample

\hat{x}

is orthogonally projected onto the manifold

D

(depicted by a red ellipsoid) according to

∥ \hat{x} - y_{p}^{*} ∥_{p} = {inf}_{y \in D} {∥ \hat{x} - y ∥}_{p}

for

p \in {1, 2, \infty}

. The remaining three colors (green, blue, and yellow) represent rescaled unit circles around

\hat{x}

with respect to

l^{1}

l^{2}

and

l^{\infty}

-norms. The intersection points of each circle with

D

mark the orthogonal projection of

x

onto

D

for the corresponding norm. We can see that projections

y_{p}^{*}

for lower p-values better preserve the content in

\hat{x}

according to the higher sparsity of the difference

\hat{x} - y_{p}^{*}

, which results in smaller modified regions

S (\hat{x}, y_{p}^{*})

Figure 10. Illustration of the concept of a transition set. Consider a 2D image tensor identified with a column vector

x \in R^{n}

n = 20^{2}

, which is partitioned according to

S \subseteq {1, \dots, n}

(gray area) and

\bar{S} : = {1, \dots, n} ∖ S

(union of light blue and dark blue areas). The transition set B (dark blue area) glues the two disconnected sets S and

\bar{S} ∖ B

together such that

x \in D

is feasible.

Figure 10. Illustration of the concept of a transition set. Consider a 2D image tensor identified with a column vector

x \in R^{n}

n = 20^{2}

, which is partitioned according to

S \subseteq {1, \dots, n}

(gray area) and

\bar{S} : = {1, \dots, n} ∖ S

(union of light blue and dark blue areas). The transition set B (dark blue area) glues the two disconnected sets S and

\bar{S} ∖ B

together such that

x \in D

is feasible.

Figure 11. Illustration of our anomaly segmentation results (with SDC-CCM) as an overlay of the original image and the anomaly heatmap. Each row shows three random examples from a category (carpet, grid, leather, transistor, and cable) in the MVTec AD dataset. In each pair, the first image represents the input to the model and the second image a corresponding anomaly heatmap.

Table 1. Our network architecture SDC-AE.

Layer Type	Number of Filters	Filter Size	Output Size
Conv	64	$3 \times 3$	$512 \times 512 \times 64$
Conv	64	$3 \times 3$	$512 \times 512 \times 64$
MaxPool		$2 \times 2$ /2	$256 \times 256 \times 64$
Conv	128	$3 \times 3$	$256 \times 256 \times 128$
Conv	128	$3 \times 3$	$256 \times 256 \times 128$
MaxPool		$2 \times 2$ /2	$128 \times 128 \times 128$
Conv	256	$3 \times 3$	$128 \times 128 \times 256$
Conv	256	$3 \times 3$	$128 \times 128 \times 256$
MaxPool		$2 \times 2$ /2	$64 \times 64 \times 256$
${SDC}_{1, 2, 4, 8, 16, 32}$	$64 \times 6$	$3 \times 3$	$64 \times 64 \times 384$
${SDC}_{1, 2, 4, 8, 16, 32}$	$64 \times 6$	$3 \times 3$	$64 \times 64 \times 384$
${SDC}_{1, 2, 4, 8, 16, 32}$	$64 \times 6$	$3 \times 3$	$64 \times 64 \times 384$
${SDC}_{1, 2, 4, 8, 16, 32}$	$64 \times 6$	$3 \times 3$	$64 \times 64 \times 384$
TranConv	256	$3 \times 3$ /2	$128 \times 128 \times 256$
Conv	256	$3 \times 3$	$128 \times 128 \times 256$
Conv	256	$3 \times 3$	$128 \times 128 \times 256$
TranConv	128	$3 \times 3$ /2	$256 \times 256 \times 128$
Conv	128	$3 \times 3$	$256 \times 256 \times 128$
Conv	128	$3 \times 3$	$256 \times 256 \times 128$
TranConv	64	$3 \times 3$ /2	$512 \times 512 \times 64$
Conv	64	$3 \times 3$	$512 \times 512 \times 64$
Conv	64	$3 \times 3$	$512 \times 512 \times 64$
Conv	3	$1 \times 1$	$512 \times 512 \times 3$

Table 2. Experimental results for anomaly segmentation measured with pixel-level AUROC on the MVTec AD dataset.

Category	AnoGAN	VAE	LSR	RIAD	CutPaste	InTra	DRAEM	SimpleNet	PatchCore	MSFlow	PNI	SDC-AE	SDC-CCM
carpet	54	78	94	96.3	98.3	99.2	95.5	98.2	98.7	99.4	99.4	99.7	99.8
grid	58	73	99	98.8	97.5	98.8	99.7	98.8	98.8	99.4	99.2	99.7	99.8
leather	64	95	99	99.4	99.5	99.5	98.6	99.2	99.3	99.7	99.6	99.7	99.7
tile	50	80	88	89.1	90.5	94.4	99.2	97.0	96.3	98.2	98.4	99.2	99.2
wood	62	77	87	85.8	95.5	88.7	96.4	94.5	95.2	97.1	97.0	98.4	98.4
avg. tex.	57.6	80.6	93.4	93.9	96.3	96.1	97.9	97.5	97.7	98.8	98.7	99.3	99.4
bottle	86	87	95	98.4	97.6	97.1	99.1	98.0	98.6	99.0	98.9	98.6	98.9
cable	86	87	95	94.2	90.0	91.0	94.7	97.6	98.7	98.5	99.1	98.2	98.5
capsule	84	74	93	92.8	97.4	97.7	94.3	98.9	99.1	99.1	99.3	99.1	99.1
hazelnut	87	98	95	96.1	97.3	98.3	99.7	97.9	98.8	98.7	99.4	98.9	99.1
metal nut	76	94	91	92.5	93.1	93.3	99.5	98.8	99.0	99.3	99.3	98.5	98.5
pill	87	83	91	95.7	95.7	98.3	97.6	98.6	98.6	98.8	99.0	99.3	99.3
screw	80	97	96	98.8	96.7	99.5	97.6	99.3	99.5	99.1	99.6	99.7	99.7
toothbrush	90	94	97	98.9	98.1	98.9	98.1	98.5	98.9	98.5	99.1	99.1	99.4
transistor	80	93	91	87.7	93.0	96.1	90.9	97.6	97.1	98.3	98.0	98.6	98.9
zipper	78	78	98	97.8	99.3	99.2	98.8	98.9	99.0	99.2	99.4	99.5	99.6
avg. obj.	83.4	88.5	94.6	95.3	95.8	96.9	97.0	98.4	98.7	98.8	99.1	99.0	99.1
avg. all	74.8	85.9	94.2	94.8	96.0	96.7	97.3	98.1	98.4	98.8	99.0	99.1	99.2

Table 3. Experimental results for anomaly recognition measured with image-level AUROC on the MVTec AD dataset.

Category	AnoGAN	VAE	LSR	RIAD	CutPaste	InTra	DRAEM	SimpleNet	PatchCore	MSFlow	PNI	SDC-AE	SDC-CCM
carpet	49	78	71	84.2	93.1	98.8	97.0	99.7	98.2	100	100	100	100
grid	51	73	91	99.6	99.9	100	99.9	99.7	98.3	99.8	98.4	100	100
leather	52	95	96	100	100	100	100	100	100	100	100	100	100
tile	51	80	95	93.4	93.4	98.2	99.6	99.8	98.9	100	100	100	100
wood	68	77	96	93.0	98.6	97.5	99.1	100	99.9	100	99.6	100	100
avg. textures	54.2	80.6	89.8	94.0	97.0	98.9	99.1	99.8	99.0	99.9	99.6	100	100
bottle	69	87	99	99.9	98.3	100	99.2	100	100	100	100	100	100
cable	53	90	72	81.9	80.6	70.3	91.8	99.9	99.7	99.5	99.8	98.0	99.9
capsule	58	74	68	88.4	96.2	86.5	98.5	97.7	98.1	99.2	99.7	98.2	98.8
hazelnut	50	98	94	83.3	97.3	95.7	100	100	100	100	100	100	100
metal nut	50	94	83	88.5	99.3	96.9	98.7	100	100	100	100	100	100
pill	62	83	68	83.8	92.4	90.2	98.9	99.0	97.1	99.6	96.9	99.5	99.6
screw	35	97	80	84.5	86.3	95.7	93.9	98.2	99.0	97.8	99.5	98.9	98.9
toothbrush	57	94	92	100	98.3	100	100	99.7	98.9	100	99.7	100	100
transistor	67	93	73	90.9	95.5	95.8	93.1	100	99.7	100	100	98.8	100
zipper	59	78	97	98.1	99.4	99.4	100	99.9	99.7	100	99.9	100	100
avg. objects	56.0	88.8	82.6	89.9	94.4	93.1	97.4	99.5	99.2	99.6	99.5	99.3	99.7
avg. all	55.4	86.1	85.0	91.3	95.2	95.0	98.0	99.6	99.2	99.7	99.6	99.6	99.8

Disclaimer/Publisher’s Note: The statements, opinions and data contained in all publications are solely those of the individual author(s) and contributor(s) and not of MDPI and/or the editor(s). MDPI and/or the editor(s) disclaim responsibility for any injury to people or property resulting from any ideas, methods, instructions or products referred to in the content.

© 2024 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (https://creativecommons.org/licenses/by/4.0/).

Share and Cite

MDPI and ACS Style

Bauer, A.; Nakajima, S.; Müller, K.-R. Self-Supervised Autoencoders for Visual Anomaly Detection. Mathematics 2024, 12, 3988. https://doi.org/10.3390/math12243988

AMA Style

Bauer A, Nakajima S, Müller K-R. Self-Supervised Autoencoders for Visual Anomaly Detection. Mathematics. 2024; 12(24):3988. https://doi.org/10.3390/math12243988

Chicago/Turabian Style

Bauer, Alexander, Shinichi Nakajima, and Klaus-Robert Müller. 2024. "Self-Supervised Autoencoders for Visual Anomaly Detection" Mathematics 12, no. 24: 3988. https://doi.org/10.3390/math12243988

APA Style

Bauer, A., Nakajima, S., & Müller, K. -R. (2024). Self-Supervised Autoencoders for Visual Anomaly Detection. Mathematics, 12(24), 3988. https://doi.org/10.3390/math12243988

Note that from the first issue of 2016, this journal uses article numbers instead of page numbers. See further details here.

Article Menu

Self-Supervised Autoencoders for Visual Anomaly Detection

Abstract

1. Introduction

2. Related Works

3. Methodology

3.1. Training Objective

3.2. Generating Artificial Anomalies for Training

3.3. Model Architecture

4. Theoretical Analysis

4.1. Connections to Regularized Autoencoders

4.2. Conservation Effect of Orthogonal Projections

4.3. Convergence Guarantees for Input Corruptions

4.3.1. Partial Modification

4.3.2. Additive Noise

5. Experiments

6. Conclusions

Author Contributions

Funding

Data Availability Statement

Conflicts of Interest

Abbreviations

Appendix A. Auxiliary Statements

Appendix B. Weak Law of Large Numbers for MRFs

Appendix C. Corollary of Theorem A1

Appendix D. Proof of Theorem 1

Appendix E. Proof of Theorem 2

Appendix F. Proof of Proposition 1

Appendix G. Proof of Proposition 2

Appendix H. Proof of Proposition 3

Appendix I. Ablation Study on the Impact of Architectural Components

Appendix J. Illustration of Qualitative Improvement in Reconstruction When Using SDC-CCM over SDC-AE

References

Share and Cite

Article Metrics

Article Access Statistics

Further Information

Guidelines

MDPI Initiatives

Follow MDPI