P-Channels: Robust Multivariate M-Estimation of Large Datasets

In this paper we introduce a new technique that allows to estimate modes of a high-dimensional probability density function with linear time-complexity in the number of dimensions and the number of samples. The method can be implemented in an order-independent incremental way, such that the space-complexity is linear in the number of dimensions and the number of modes. The number of required samples to get reliable estimates depends linearly on the number of dimensions even if we replace the assumption of independent stochastic variables with the weaker assumption of data clustered in submanifolds. These submanifolds need not to be known, but smoothness assumptions are made. The new technique is based on representing data in what we call P-channels