📊 statistics

Fast localization of anomalous patches in spatial data under dependence

This paper introduces SPLADE, a scalable and provably accurate two-stage method for localizing multiple axis-aligned anomalous patches in spatial data under general dependence, which demonstrates superior computational efficiency, accuracy, and robustness compared to existing approaches in both synthetic benchmarks and real-world video surveillance applications.

Original authors: Soham Bonnerjee, Sayar Karmakar, George Michailidis

Published 2026-03-31

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Soham Bonnerjee, Sayar Karmakar, George Michailidis

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are looking at a giant, high-resolution digital map of a city. Most of the city is quiet and normal (the "background noise"), but somewhere hidden within it, there are a few small, glowing "hotspots" where something unusual is happening—maybe a sudden crowd of people, a traffic jam, or a spike in crime.

Your job is to find these hotspots. But there's a catch: everything in the city is connected. If a car stops at a red light, the cars behind it stop too. If one person starts running, others might follow. This is called spatial dependence. The data isn't a bunch of independent dots; it's a web of connected events.

This paper introduces a new, super-fast, and super-accurate tool called SPLADE (Spatial Patch Localization of Anomalies under DEpendence) to solve this exact problem.

Here is how it works, broken down into simple concepts:

1. The Problem: The "Needle in a Haystack" that is Sticky

Traditional methods for finding these hotspots often treat every single pixel or data point as if it were alone in a room. They assume that what happens in one spot has nothing to do with the spot next to it.

The Analogy: Imagine trying to find a whisper in a library by asking every single person, "Did you hear a whisper?" independently.
The Reality: In the real world (like video surveillance or weather patterns), if one person whispers, the person next to them hears it too. The noise is "sticky." When you ignore this stickiness, old methods get confused. They either miss the hotspots entirely or, worse, they see "ghost" hotspots where nothing is happening (false alarms).

2. The Solution: The "Smart Scout" Strategy

The authors realized that trying to check every single pixel in a massive grid is like trying to read every word in a library to find a typo. It takes too long. Instead, they built a two-step "Smart Scout" system.

Step 1: The "Coarse Net" (The Scout)

Instead of checking every pixel, SPLADE throws a wide, coarse net over the area. It looks at big blocks of the map at once.

The Analogy: Imagine you are looking for a lost dog in a huge park. Instead of walking every single inch, you first look at the park from a hill. You see a few big areas where the grass is moving strangely. You don't know exactly where the dog is, but you know it's in one of those three big zones.
Why it's fast: By skipping the tiny details initially, the computer doesn't get bogged down. It quickly narrows the search from "the whole city" to "just these three neighborhoods."

Step 2: The "Fine Comb" (The Detective)

Once the "Coarse Net" identifies the suspicious neighborhoods, SPLADE zooms in only on those specific areas. It uses a much more detailed, precise method to find the exact boundaries of the hotspot.

The Analogy: Now that you know the dog is in the "North Park" zone, you send a detective with a magnifying glass to that specific area to find the dog's exact location.
The Magic: Because the computer only does the hard, detailed work on the small suspicious areas (not the whole map), it finishes the job incredibly fast—often 15 to 100 times faster than other methods.

3. Why This Matters: The "Video Surveillance" Test

The authors tested their method on real-world video footage of people walking in a lobby.

The Challenge: Two people walk close together. To a standard camera, they look like one big blob. To a standard computer algorithm (which assumes independence), the "stickiness" of the video pixels makes it hard to tell where one person ends and the other begins.
The Result:
- Old Methods: They either missed the second person entirely or saw "ghost" people floating around who weren't there.
- SPLADE: It successfully separated the two people, drawing a perfect box around each one, even when they were walking right next to each other. It understood that the pixels were connected and used that to its advantage.

4. The "Fiber Optic" Bonus

They also tested this on 3D images of glass fibers (like looking at the inside of a plastic bottle under a microscope).

The Problem: Sometimes fibers get squished or bent (anomalies). Because the fibers are woven together, a bend in one affects its neighbors.
The Result: SPLADE found the exact 3D shape of the damaged area, whereas other methods failed to see the damage in certain directions.

Summary: The Big Takeaway

Think of SPLADE as a smart, efficient detective.

It knows the neighborhood: It understands that data points are connected (dependent), so it doesn't get tricked by the "noise."
It's a speedster: It doesn't waste time checking empty rooms. It uses a "coarse net" to find the interesting rooms and a "fine comb" to solve the mystery inside them.
It's accurate: It finds the exact shape and size of the problem, even when the problems are small, close together, or hidden in a noisy, connected environment.

In short, this paper gives us a way to find small, hidden problems in massive, connected data sets (like video feeds, weather maps, or medical scans) fast, accurately, and without getting confused by the connections between the data points.

1. Problem Statement

The paper addresses the challenge of localizing multiple unknown anomalous patches (clusters) within spatial data that exhibits general spatial dependence.

Context: In many applications (public health, surveillance, environmental monitoring), the goal is to detect localized "hotspots" rather than segmenting the entire spatial domain.
Data Model: The observed data $X_i$ on a $d$ -dimensional lattice is modeled as $X_i = \mu_i + \eta_i$ , where $\mu_i$ represents a baseline level outside anomalies and a shifted mean inside anomalous patches, and $\eta_i$ is a spatially dependent noise field.
Key Challenges:
1. Dependence: Most existing methods assume independent observations. Real-world spatial data often exhibits strong autocorrelation, which can lead to spurious detections if ignored.
2. Scalability: Existing methods for dependent data are often computationally prohibitive (e.g., $O(|n|^{3/2})$ or $O(|n|^2)$ ), making them unsuitable for large grids or real-time applications like video surveillance.
3. Multiple Patches: Simultaneously estimating the number of patches and their precise boundaries under dependence is theoretically and computationally difficult.

2. Methodology: The SPLADE Framework

The authors propose SPLADE (Spatial Patch Localization of Anomalies under DEpendence), a two-stage procedure designed for axis-aligned rectangular patches.

Stage 1: Single Patch Localization via Intelligent Sampling

To overcome the computational bottleneck of exhaustive search ( $O(n^{2d})$ ), the authors introduce a fast intelligent sub-sampling algorithm for a single patch:

Coarse Estimation: The data is subsampled on a coarse grid (spacing $L_k \approx n^\alpha$ ). A naive least-squares estimator is applied to this reduced dataset to identify candidate regions containing the patch boundaries.
Refined Search: The search space is restricted to a small neighborhood around the coarse estimates. A refined estimator is applied only within these localized subsets.
Theoretical Guarantee: Under mild conditions (finite $p$ -th moments, $p>2$ ), this approach achieves the optimal minimax localization rate while reducing computational complexity to near-linear time, $O(n)$ , for fixed dimensions.

Stage 2: Multiple Patch Detection (SPLADE)

To handle an unknown number of patches ( $K$ ), the method extends the single-patch algorithm:

Block-Based Screening: The spatial domain is partitioned into blocks. A simultaneous test is performed on block means to identify "active" blocks that likely overlap with anomalies.
Connected Component Analysis: Isolated false positives are filtered out. Connected components of active blocks are identified. Under separation assumptions, each component corresponds to exactly one true anomalous patch.
Parallel Localization: The single-patch intelligent sampling algorithm (Stage 1) is applied in parallel to the region surrounding each connected component to precisely localize the boundaries.

3. Key Contributions

General Dependence Handling: Unlike prior work restricted to $m$ -dependence or specific Gaussian structures, SPLADE accommodates a general class of spatial dependence (including linear random fields and SAR models) requiring only the existence of finite $p$ -th moments ( $p>2$ ). This allows for heavy-tailed noise distributions.
Computational Efficiency: The proposed algorithm achieves $O(n)$ computational complexity (linear in the number of pixels) for fixed dimensions and fixed number of patches. This is a significant improvement over competitors like DCART ( $O(n)$ but with high constant factors/empirical runtime) and DPLS-SAD ( $O(n^{3/2})$ ).
Theoretical Guarantees: The paper establishes simultaneous consistency for:
- The estimated number of patches ( $\hat{K} \to K$ ).
- The boundaries of each individual patch, achieving the optimal localization rate $r_{n,\delta}$ .
Robustness: The method is robust to tuning parameters and performs well under varying signal strengths and dependence structures.

4. Results and Performance Evaluation

The authors conducted extensive experiments on synthetic data and real-world applications.

Synthetic Data:
- Accuracy: SPLADE consistently outperforms baselines (DCART, TV, and DPLS-SAD) in Adjusted Rand Index (ARI) and normalized Hausdorff distance, especially under high spatial dependence ( $\rho = 0.8$ ). Competing methods often fail to detect patches or produce spurious clusters in dependent settings.
- Speed: SPLADE is significantly faster. In high-dependence scenarios, it is 15–20x faster than DCART and 4x faster than TV. Compared to DPLS-SAD, SPLADE is 50–100x faster.
- Scalability: While other methods struggle or fail to terminate on large grids ( $512 \times 512$ ), SPLADE maintains linear scaling.
Real-World Applications:
1. Video Surveillance (CAVIAR Dataset): Applied to frame-to-frame detection of people. SPLADE successfully resolved closely spaced subjects and tracked their merging/splitting, whereas baselines failed to distinguish individuals or produced spurious detections due to unmodeled spatial correlation.
2. 3D Fibrous Media: Applied to 3D tomographic images of glass-fiber reinforced polymers. SPLADE detected anomalous fiber deformations in 3D space, outperforming existing cluster-based methods that failed to detect anomalies in specific directions (e.g., the z-axis).

5. Significance

This paper bridges a critical gap between statistical rigor and computational feasibility in spatial anomaly detection.

Theoretical Impact: It provides the first rigorous localization guarantees for multiple patches under general spatial dependence without assuming sub-Gaussian tails or restrictive $m$ -dependence.
Practical Impact: By achieving linear-time complexity, SPLADE makes real-time anomaly detection feasible for large-scale spatial data (e.g., high-resolution video, medical imaging, environmental sensor networks) where previous methods were too slow or inaccurate.
Versatility: The framework's ability to handle heavy-tailed noise and general dependence structures makes it applicable to a wide range of domains beyond the specific examples tested, including finance, epidemiology, and materials science.