Fast multivariate empirical cumulative distribution function with connection to kernel density estimation - EDF Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2020

Fast multivariate empirical cumulative distribution function with connection to kernel density estimation

Xavier Warin
  • Fonction : Auteur
  • PersonId : 858650
EDF

Résumé

This paper revisits the problem of computing empirical cumulative distribution functions (ECDF) efficiently on large, multivariate datasets. Computing an ECDF at one evaluation point requires O(N) operations on a dataset composed of N data points. Therefore, a direct evaluation of ECDFs at N evaluation points requires a quadratic O(N^2) operations, which is prohibitive for large-scale problems. Two fast and exact methods are proposed and compared. The first one is based on fast summation in lexicographical order, with a O(N logN) complexity and requires the evaluation points to lie on a regular grid. The second one is based on the divide-and-conquer principle, with a O(N log(N)^max(d−1,1)) complexity and requires the evaluation points to coincide with the input points. The two fast algorithms are described and detailed in the general d-dimensional case, and numerical experiments validate their speed and accuracy. Secondly, the paper establishes a direct connection between cumulative distribution functions and kernel density estimation (KDE) for a large class of kernels. This connection paves the way for fast exact algorithms for multivariate kernel density estimation and kernel regression. Numerical tests with the Laplacian kernel validate the speed and accuracy of the proposed algorithms. A broad range of large-scale multivariate density estimation, cumulative distribution estimation, survival function estimation and regression problems can benefit from the proposed numerical methods.
Fichier principal
Vignette du fichier
2005.03246.pdf (2.08 Mo) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-02910373 , version 1 (02-08-2020)

Identifiants

Citer

Nicolas Langrené, Xavier Warin. Fast multivariate empirical cumulative distribution function with connection to kernel density estimation. 2020. ⟨hal-02910373⟩

Collections

EDF
40 Consultations
129 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More