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.
This paper uses sum-of-squared (SOS) polynomials (i.e. the set of polynomials of degree 2d which can be written as the square of polynomials of degree d) to detect outliers in point sets. In contrast to kernel-based methods such as Gaussian processes, the evaluation of an SOS polynomials depends on the number of monomials (and thus on the ambient dimension) rather than on the number of observations. Thus the approach seems obviously advantageous for evaluating typicality in very large point sets of relatively low dimensionality. The paper provides some nice theoretical analysis that helps to explain empirically-observed properties of SOS polynomials that make them useful for typicality. Finally, the authors apply the technique to a dataset of network
This paper is clear and seems thorough and technically sound, at least up to the depth at which I could follow it. If it is indeed the case that the presented empirical observation of the utility of SOS polynomials for describing typicality in point sets has not been previously noted in the literature, then it would be a clearly useful contribution. The experimental results show that the SOS polynomial technique is competitive with other techniques hand-designed to detect typicality while also being simple and well-justified from a theoretical standpoint.  My only concern is regarding the fitness of the presented work for presentation in NIPS. It seems that this approach would be extremely useful for geometric settings in which the dimensionality is low, e.g. 2 or 3, but the number of points can be in the millions or more, perhaps for 3D point-cloud de-noising applications. As for machine learning, the paper presents one example that seems reasonable, but it would be useful if some additional examples of where this approach my prove advantageous were given, or even just some additional motivation in the text describing potential applications.  Minor points on clarity:  I assume x bar in section 4.4 (introduced in line 239) is referring as usual to the mean of a set of points in R^p but that wasn't made entirely clear and I don't think it was used previously.  On line 257 in section 5 it says that the network intrusion dataset consists of labelled vectors in R^3, but in lines 441-442 of Appendix C it says "the four most important features" are used. Is this a typo or is there some sort of projection from the four features to a 3D space being used?  A very minor point, but it seems that the section describing affine invariance is really describing affine co-variance, i.e. if you transform the point set using an affine transformation, the resulting SOS is different (thus not invariant) but it is equivalent to transforming the underlying coordinate system of the polynomial (thus co-variant).