Sorting out typicality with the inverse moment matrix SOS polynomial
We study a surprising phenomenon related to the representation of a cloud of data points using polynomials. We start with the previously unnoticed empirical observation that, given a collection (a cloud) of data points, the sublevel sets of a certain distinguished polynomial capture the shape of the cloud very accurately. This distinguished polynomial is a sum-of-squares (SOS) derived in a simple manner from the inverse of the empirical moment matrix. In fact, this SOS polynomial is directly related to orthogonal polynomials and the Christoffel function. This allows to generalize and interpret extremality properties of orthogonal polynomials and to provide a mathematical rationale for the observed phenomenon. Among diverse potential applications, we illustrate the relevance of our results on a network intrusion detection task for which we obtain performances similar to existing dedicated methods reported in the literature.
Code (0)
등록된 구현이 없습니다.
Tasks
Intrusion DetectionNetwork Intrusion DetectionSimilar Papers 제목 키워드 기반
Gaussianity and typicality in matrix distributional semantics
Constructions in type-driven compositional distributional semantics associate large collections of matrices of size $D$ to linguistic corpora. We develop the proposal of analysing the statistical characteristics of this …
Solving ill-conditioned polynomial equations using score-based priors with application to multi-target detection
Recovering signals from low-order moments is a fundamental yet notoriously difficult task in inverse problems. This recovery process often reduces to solving ill-conditioned systems of polynomial equations. In this work,…
Matrix Reordering for Noisy Disordered Matrices: Optimality and Computationally Efficient Algorithms
Motivated by applications in single-cell biology and metagenomics, we investigate the problem of matrix reordering based on a noisy disordered monotone Toeplitz matrix model. We establish the fundamental statistical limi…
Data analysis from empirical moments and the Christoffel function
Spectral features of the empirical moment matrix constitute a resourceful tool for unveiling properties of a cloud of points, among which, density, support and latent structures. It is already well known that the empiric…
The Complexity of Min-Max Optimization for Quadratic Polynomials
We prove that computing approximate stationary points of min-max optimization over the hypercube is PPAD-hard for quadratic polynomials. This holds even when the polynomials are multilinear, each variable appears in at m…