Real-world anomaly detection problems rarely involve just two or three features. Financial fraud detection might consider hundreds of transaction attributes. Network intrusion detection examines dozens of protocol features. Healthcare anomaly detection processes thousands of gene expressions or sensor readings.

When density-based methods move from low-dimensional toy examples to these high-dimensional realities, fundamental challenges emerge. Distances become less meaningful, volumes explode exponentially, and the intuitions that guide us in 2D or 3D spaces fail spectacularly.

This page confronts these challenges directly, exploring both the theoretical foundations of multivariate density estimation and the practical techniques that make density-based anomaly detection viable in high dimensions.

The curse of dimensionality—coined by Richard Bellman—describes how algorithms that work well in low dimensions often fail catastrophically as dimensionality increases. For density-based anomaly detection, this curse manifests in several devastating ways.

Volume Concentration

Consider the volume of a d-dimensional hypersphere of radius r: $$V_d(r) = \frac{\pi^{d/2}}{\Gamma(d/2 + 1)} r^d$$

The ratio of the volume of a hypersphere to its enclosing hypercube: $$\frac{V_{\text{sphere}}}{V_{\text{cube}}} = \frac{\pi^{d/2}}{\Gamma(d/2 + 1) \cdot 2^d}$$

As d increases:

• For d=2: ratio ≈ 0.785
• For d=10: ratio ≈ 0.0025
• For d=100: ratio ≈ 10⁻⁷⁰

The volume of a hypersphere becomes negligibly small compared to its enclosing cube. Most of the volume is concentrated in the 'corners' of hypercubes, regions that distance-based methods cannot reach efficiently.

Formal Analysis: Distance Concentration

For n random points uniformly distributed in [0, 1]^d:

$$\lim_{d \to \infty} \mathbb{E}\left[\frac{D_{\max}}{D_{\min}}\right] = 1$$

where $D_{\max}$ and $D_{\min}$ are maximum and minimum pairwise distances.

More precisely, for fixed n and growing d: $$\frac{D_{\max} - D_{\min}}{D_{\min}} = O(1/\sqrt{d})$$

This concentration means:

• k-NN becomes unreliable: The k-th nearest neighbor is barely closer than the (k+100)-th neighbor
• Density estimates lose discriminative power: All points have similar local densities
• Anomaly detection degrades: True anomalies aren't distinguishable from normal points by distance

Sample Complexity Explosion

To maintain the same statistical accuracy as sample size n in d dimensions, we need: $$n' = n^{d/d_0}$$

where d₀ is the original dimensionality. This exponential growth is called the sample size curse.

For practical density estimation, we need sample density: $$\rho = \frac{n}{V} = \frac{n}{L^d}$$

As d grows, for fixed n, this density drops exponentially, making any local neighborhood estimation statistically unsound.

The multivariate Gaussian distribution provides a principled parametric approach to density-based anomaly detection, particularly effective when data approximately follows a normal distribution.

Multivariate Gaussian Density

For d-dimensional data, the multivariate Gaussian density: $$p(\mathbf{x}) = \frac{1}{(2\pi)^{d/2} |\mathbf{\Sigma}|^{1/2}} \exp\left(-\frac{1}{2}(\mathbf{x} - \boldsymbol{\mu})^T \mathbf{\Sigma}^{-1} (\mathbf{x} - \boldsymbol{\mu})\right)$$

where:

• $\boldsymbol{\mu}$ is the mean vector
• $\mathbf{\Sigma}$ is the covariance matrix
• $|\mathbf{\Sigma}|$ is the determinant of the covariance matrix

Mahalanobis Distance

The exponent in the Gaussian density defines the Mahalanobis distance: $$D_M(\mathbf{x}) = \sqrt{(\mathbf{x} - \boldsymbol{\mu})^T \mathbf{\Sigma}^{-1} (\mathbf{x} - \boldsymbol{\mu})}$$

Mahalanobis distance accounts for:

• Correlations between features: Correlated features are weighted appropriately
• Different scales: Features with high variance don't dominate
• Ellipsoidal structure: Captures the true shape of the data distribution

Anomaly Detection via Mahalanobis Distance

For Gaussian-distributed data, the squared Mahalanobis distance $D_M^2(\mathbf{x})$ follows a chi-squared distribution with d degrees of freedom: $$D_M^2(\mathbf{x}) \sim \chi^2_d$$

This provides a principled threshold for anomaly detection: $$\text{IsAnomaly}(\mathbf{x}) = \mathbb{1}\left[D_M^2(\mathbf{x}) > \chi^2_{d, 1-\alpha}\right]$$

where $\chi^2_{d, 1-\alpha}$ is the $(1-\alpha)$ quantile of the chi-squared distribution.

For example, with α = 0.01 and d = 10:

• $\chi^2_{10, 0.99} \approx 23.2$
• Points with $D_M^2 > 23.2$ are flagged as anomalies

This gives a probabilistic interpretation: an anomaly has less than 1% probability under the fitted Gaussian model.

The Achilles' heel of Mahalanobis-based anomaly detection is covariance estimation. The standard empirical covariance is highly sensitive to outliers—the very things we're trying to detect!

The Masking Effect

When outliers contaminate the training data:

1. They inflate the covariance estimate
2. The inflated covariance makes outliers appear less anomalous (swamping)
3. Normal points near the boundary may appear more anomalous (masking)

This circular problem—needing to know outliers to estimate covariance, but needing covariance to find outliers—requires robust estimation techniques.

Minimum Covariance Determinant (MCD)

MCD finds the subset of h points (typically h = ⌈(n+d+1)/2⌉) whose covariance matrix has the smallest determinant:

$$\hat{\Sigma}{\text{MCD}} = \arg\min{|H|=h} |\mathbf{\Sigma}_H|$$

The intuition: the subset with minimum covariance determinant best represents the 'core' of the data, excluding outliers.

Properties of MCD:

• Breakdown point: Can tolerate up to ⌊(n-h)/n⌋ fraction of outliers
• Affine equivariant: Robust to coordinate transformations
• Computationally intensive: Fast-MCD algorithms make it practical

Other Robust Estimators

Minimum Volume Ellipsoid (MVE): Finds the ellipsoid of minimum volume containing h points. Similar concept to MCD but with different optimization objective.

S-Estimators: Minimize a robust scale estimate: $$\hat{\Sigma}S = \arg\min\Sigma \det(\Sigma) \text{ s.t. } \frac{1}{n}\sum_i \rho(d_M^i(\Sigma)) = k$$ where ρ is a robust loss function (e.g., Tukey's biweight).

M-Estimators: Iteratively reweight observations based on their Mahalanobis distance: $$\hat{\Sigma}^{(t+1)} = \frac{\sum_i w(d_M^{(t)}(\mathbf{x}_i)) (\mathbf{x}_i - \hat{\mu})(\mathbf{x}_i - \hat{\mu})^T}{\sum_i w(d_M^{(t)}(\mathbf{x}_i))}$$ where w(d) downweights points with large distances.

Shrinkage Estimators: Regularize towards a simpler covariance structure: $$\hat{\Sigma}{\text{shrink}} = (1-\alpha) \hat{\Sigma}{\text{sample}} + \alpha \cdot \text{diag}(\hat{\Sigma}_{\text{sample}})$$

When full-dimensional density estimation fails due to the curse of dimensionality, subspace methods offer a powerful alternative: detect anomalies in lower-dimensional projections where density estimation remains tractable.

The Subspace Outlier Hypothesis

In high-dimensional data, anomalies may only be anomalous in certain feature subsets. A point could appear normal when considering all features but be clearly anomalous in a specific 2D or 3D projection.

Example: A fraudulent transaction might have normal amounts and normal times, but the combination of <location, merchant_category> is rare.

Feature Bagging

Inspired by ensemble methods, feature bagging repeatedly samples feature subsets and applies anomaly detection in each:

1. Sample m feature subsets $S_1, S_2, \ldots, S_m$ of size r < d
2. Apply a detector (e.g., LOF) to data projected onto each $S_i$
3. Aggregate scores: $\text{score}(\mathbf{x}) = \frac{1}{m}\sum_{i=1}^m \text{score}_{S_i}(\mathbf{x})$

Benefits:

• Bypasses curse of dimensionality by working in low dimensions
• Can detect subspace outliers
• Averaging provides robustness

High Contrast Subspaces (HiCS)

HiCS searches for subspaces where a point deviates most from the local distribution:

Contrast Function: $$\text{contrast}(\mathbf{x}, S) = \frac{p_S(\mathbf{x}|N(\mathbf{x}))}{p_S(\mathbf{x})}$$

where $p_S$ is the marginal distribution in subspace S, and $N(\mathbf{x})$ is the local neighborhood.

Algorithm:

1. For candidate subspaces S:
   • Estimate $p_S(\mathbf{x})$ via KDE or histograms
   • Compute contrast score
2. Aggregate across high-contrast subspaces
3. Report points with consistently low local probability

The key insight: Instead of searching all 2^d subspaces (exponential), HiCS uses statistical tests to prune uninteresting subspaces.

SOD: Subspace Outlier Degree

SOD leverages the observation that outliers often deviate in low-variance subspaces:

1. For each point, find its k-nearest neighbors
2. Compute PCA on the neighbors → identify subspace where neighbors cluster
3. Measure distance from the point to this subspace (reconstruction error)

$$\text{SOD}(\mathbf{x}) = \frac{1}{|S|} \sum_{j \in S} (x_j - \tilde{x}_j)^2$$

where $\tilde{x}_j$ is the projection onto the neighbor-defined subspace.

Points far from their neighbors' subspace are anomalies—they don't 'fit' the local pattern.

Rather than working in subspaces, another approach is to reduce dimensionality first, then apply density-based detection in the reduced space.

PCA-Based Reduction

PCA projects data onto directions of maximum variance:

1. Compute principal components of training data
2. Project to top k components (capturing most variance)
3. Apply density-based detection in k-dimensional space

Caveat: PCA preserves variance, not necessarily anomaly structure. An anomaly in a low-variance direction may be lost.

Reconstruction Error Approaches

PCA reconstruction error itself can indicate anomalies: $$\text{error}(\mathbf{x}) = |\mathbf{x} - \mathbf{P}_k \mathbf{x}|^2$$

where $\mathbf{P}_k$ projects onto top k principal components.

Insight: Anomalies often have high reconstruction error because they don't conform to the learned principal subspace. This is the basis for autoencoder-based anomaly detection in deep learning.

Random Projections

The Johnson-Lindenstrauss lemma states that random projections approximately preserve distances:

$$\text{For } k = O\left(\frac{\log n}{\epsilon^2}\right)$$

a random projection to k dimensions preserves all pairwise distances within factor $(1 \pm \epsilon)$ with high probability.

For anomaly detection:

1. Generate random projection matrix $\mathbf{R} \in \mathbb{R}^{k \times d}$
2. Project: $\tilde{\mathbf{X}} = \mathbf{X} \mathbf{R}^T$
3. Apply detection in projected space

Benefits:

• No training required (unlike PCA)
• Distance-preserving (good for distance-based methods)
• Multiple projections can be ensembled

Combined Strategy: Project and Detect

A robust pipeline for high-dimensional anomaly detection:

1. Feature selection: Remove obviously irrelevant features
2. Normalization: Standardize to common scale
3. Reduction: Apply PCA, keeping components explaining 95% variance
4. Detection: Apply LOF or Mahalanobis in reduced space
5. Validation: Check top anomalies in original feature space

Multivariate density estimation for anomaly detection presents unique challenges that require thoughtful approaches.

Key Takeaways

1. Curse of Dimensionality: In high dimensions, distances concentrate, volumes explode, and density estimation degrades. Beyond ~20 dimensions, standard methods struggle.

2. Mahalanobis Distance: For approximately Gaussian data, Mahalanobis distance provides principled anomaly detection with proper handling of correlations and scales.

3. Robust Covariance: Standard covariance is sensitive to outliers. Use MCD or other robust estimators when contamination is suspected.

4. Subspace Methods: Anomalies may only be visible in certain feature subsets. Feature bagging and SOD detect subspace outliers.

5. Dimensionality Reduction: Reducing dimensionality via PCA or random projections can make density estimation tractable, though care is needed to preserve anomaly structure.

Looking Ahead

With multivariate density challenges addressed, the final piece of the puzzle is making these methods work at scale:

• Next Page (Scalability): Techniques for efficient density-based anomaly detection on large datasets, including approximate nearest neighbors, streaming algorithms, and distributed computation.

The density paradigm, when properly adapted for high dimensions and large scales, remains one of the most interpretable and effective approaches to anomaly detection.