Fonction de distribution cumulative empirique multivariée rapide avec connexion à l'estimation de la densité du noyau.

Résumé Cet article revisite le problème du calcul efficace des fonctions de distribution cumulative empirique (ECDF) sur de grands ensembles de données multivariées. Le calcul d'une ECDF à un point d'évaluation nécessite O(N) opérations sur un ensemble de données composé de N points de données. Par conséquent, une évaluation directe des ECDF à N points d'évaluation nécessite une opération quadratique O(N^2), ce qui est prohibitif pour les problèmes à grande échelle. Deux méthodes rapides et exactes sont proposées et comparées. La première est basée sur une sommation rapide dans l'ordre lexicographique, avec une complexité O(N logN) et nécessite que les points d'évaluation soient situés sur une grille régulière. La seconde est basée sur le principe de division et de conquête, avec une complexité de O(N log(N)^max(d-1,1)) et exige que les points d'évaluation coïncident avec les points d'entrée. Les deux algorithmes rapides sont décrits et détaillés dans le cas général à d dimensions, et des expériences numériques valident leur vitesse et leur précision. Deuxièmement, l'article établit une connexion directe entre les fonctions de distribution cumulative et l'estimation de la densité du noyau (KDE) pour une grande classe de noyaux. Cette connexion ouvre la voie à des algorithmes exacts rapides pour l'estimation de la densité du noyau multivarié et la régression du noyau. Des tests numériques avec le noyau Laplacien valident la vitesse et la précision des algorithmes proposés. Un large éventail de problèmes d'estimation de densité multivariée à grande échelle, d'estimation de distribution cumulative, d'estimation de fonction de survie et de régression peut bénéficier des méthodes numériques proposées.