Evaluación eficiente de la estimación multidimensional de la densidad del grano.

He visto una cantidad razonable de literatura sobre cómo elegir núcleos y anchos de banda al calcular una estimación de densidad del núcleo, pero actualmente estoy interesado en cómo mejorar el tiempo que lleva evaluar el KDE resultante en un número arbitrario de puntos.

En mi caso, estoy usando un núcleo gaussiano multidimensional (2D o 3D) con covarianza diagonal (es decir, cada dimensión es independiente). Los anchos de banda en cada dimensión pueden diferir y se seleccionan utilizando los vecinos más cercanos. Sin embargo, mi pregunta probablemente se extiende a diferentes núcleos y métodos de selección de ancho de banda.

Digamos que tengo $M$ puntos de datos y desea evaluar el KDE resultante en $N$puntos de cuadrícula. Una implementación simple implica evaluar el pdf normal multivariante$MN$veces. Para mis propósitos$M$ y $N$ Ambos están en el orden de miles, y la evaluación se ha convertido en el cuello de botella en mi código.

No sé si existen mejoras generalmente aceptadas en este método básico. Encontré este documento, que afirma reducir la complejidad de$O(MN)$ a $O(M+N)$. Sin embargo, el método no se ha implementado en ninguna biblioteca 'estándar' de R o Python que conozca, lo que sugiere que aún no se ha adoptado ampliamente.

Gracias por cualquier sugerencia que puedas dar.

Voy a proporcionar una respuesta (incompleta) aquí en caso de que ayude a alguien más.

1. Existen varios métodos matemáticos recientes para calcular el KDE de manera más eficiente. Una es la Transformada Fast Gauss, publicada en varios estudios, incluido este . Otra es utilizar un enfoque basado en árboles (árbol KD o árbol de bolas) para determinar qué fuentes contribuyen a un punto de cuadrícula determinado. No está claro si esto se ha publicado, pero se implementa en Scikit-learn y se basa en métodos desarrollados por Jake Vanderplas .
2. Si estos métodos son un poco complicados, es posible escribir algo un poco más básico que logre una tarea similar. Intenté construir un cuboide alrededor de cada punto de la cuadrícula, con longitudes laterales relacionadas con el ancho de banda en cada una de esas dimensiones. Esto no permite un gran control de errores, aunque sí le da un poco de velocidad.
3. Finalmente, calcular el KDE es bastante fácil de poner en paralelo, ya sea en múltiples núcleos de CPU o en una GPU. Estoy considerando implementar un KDE en CUDA, pero aún no lo he hecho.