Scalable anomaly detection via a univariate Christoffel function
For practitioners needing robust anomaly detection, this work provides a theoretically grounded method that scales to high-dimensional data, overcoming a key limitation of prior Christoffel function approaches.
The paper tackles the scalability bottleneck of Christoffel function-based anomaly detection, which previously required inverting an exponentially large matrix. The proposed UCF method uses a univariate Christoffel function based on squared distances, achieving state-of-the-art performance by outperforming 14 baselines on the ADBench benchmark in Average Precision.
Anomaly detection plays a critical role in identifying unusual patterns across domains such as fraud detection, network intrusion, and system fault diagnosis. Recently, Christoffel function-based methods, rooted in polynomial optimization, have emerged as promising alternatives to deep learning due to their strong mathematical foundations and computational frugality. However, their practical applicability is hindered by the need to invert a matrix whose size grows exponentially with the data dimension, rendering the method intractable even for moderate-dimensional datasets. This paper addresses the dimensionality limitations of Christoffel function-based anomaly detection while preserving its key theoretical properties, i.e., the on-off support dichotomy behavior and the accurate support shape capture. We introduce UCF, a univariate Christoffel function which is based on the squared distance between the query point and the support points. Extensive experiments on the ADBench benchmark demonstrate that UCF consistently outperforms 14 state-of-the-art baselines in terms of Average Precision. By resolving the scalability bottleneck of the Christoffel Function, this work expands the toolkit of anomaly detection methods with a robust, theoretically grounded, and universally applicable approach.