Density Estimation via Discrepancy Based Adaptive Sequential Partition

Given iid observations from an unknown absolute continuous distribution defined on some domain Ω, we propose a nonparametric method to learn a piecewise constant function to approximate the underlying probability density function. Our density estimate is a piecewise constant function defined on a binary partition of Ω. The key ingredient of the algorithm is to use discrepancy, a concept originates from Quasi Monte Carlo analysis, to control the partition process. The resulting algorithm is simple, efficient, and has a provable convergence rate. We empirically demonstrate its efficiency as a density estimation method. We also show how it can be utilized to find good initializations for k-means.

• Publication year

  2014

• Venue

  Neural Information Processing Systems

• Publication date

  2014-04-05

• Fields of study

  Mathematics, Computer Science, Medicine

• Identifiers
  arXiv 1404.1425PMID 31327913PMCID PMC6640859
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar, PubMed

• No claims are published for this paper.

• No concepts are published for this paper.

• Density Estimation Trees

  2015cited by this paper
• PCA-guided search for K-means

  2015cited by this paper
• An interactive reference framework for modeling a dynamic immune system

  2015cited by this paper
• A Histogram Transform for ProbabilityDensity Function Estimation

  2014influential reference
• Calculation of Discrepancy Measures and Applications

  2014cited by this paper
• Low Discrepancy Constructions in the Triangle

  2014cited by this paper
• Multivariate Density Estimation by Bayesian Sequential Partitioning

  2013influential reference
• Mapping Topographic Structure in White Matter Pathways with Level Set Trees

  2013cited by this paper
• Critical assessment of automated flow cytometry data analysis techniques

  2013cited by this paper
• Building Accurate 3D Spatial Networks to Enable Next Generation Intelligent Transportation Systems

  2013cited by this paper
• Entropy, Randomization, Derandomization, and Discrepancy

  2012influential reference
• Covering numbers, dyadic chaining and discrepancy

  2011cited by this paper
• A New Randomized Algorithm to Approximate the Star Discrepancy Based on Threshold Accepting

  2011cited by this paper
• Extracting a Cellular Hierarchy from High-dimensional Cytometry Data with SPADE

  2011cited by this paper
• A genetic algorithm approach to estimate lower bounds of the star discrepancy

  2010cited by this paper
• Forest Density Estimation

  2010cited by this paper
• Energy landscape of a spin-glass model: exploration and characterization.

  2009influential reference
• A method for initialising the K-means clustering algorithm using kd-trees

  2007cited by this paper
• In search of deterministic methods for initializing K-means and Gaussian mixture clustering

  2007cited by this paper
• k-means++: the advantages of careful seeding

  2007cited by this paper
• Multidimensional variation for quasi-Monte Carlo

  2004cited by this paper
• Mean Shift: A Robust Approach Toward Feature Space Analysis

  2002influential reference
• The inverse of the star-discrepancy depends linearly on the dimension

  2001cited by this paper
• Testing multivariate uniformity and its applications

  2001cited by this paper
• An Algorithm to Compute Bounds for the Star Discrepancy

  2001cited by this paper
• Computing Bounds for the Star Discrepancy

  2000cited by this paper
• Algorithms for Model-Based Gaussian Hierarchical Clustering

  1998cited by this paper
• Vector quantization and density estimation

  1997cited by this paper
• A new initialization technique for generalized Lloyd iteration

  1994cited by this paper
• Uniform distribution of sequences

  1974cited by this paper
• On Estimation of a Probability Density Function and Mode

  1962cited by this paper
• F ¨ Ur Mathematik in Den Naturwissenschaften Leipzig on the Numerical Solution of Convection-dominated Problems Using Hierarchical Matrices on the Numerical Solution of Convection-dominated Problems Using Hierarchical Matrices

  year unknowncited by this paper

• Discrepancy-Controlled Region-Adaptive Learning: Handling Intra-Domain Bias for Crowd Counting

  2026cites this paper
• Adaptive sampling accelerates the hybrid deviational particle simulations

  2026cites this paper
• Density estimation via mixture discrepancy and moments

  2025influential citation
• Adaptive sampling accelerates the hybrid deviational particle simulations

  2024influential citation
• Beta-trees: Multivariate histograms with confidence statements

  2023cites this paper
• Convergence Rates of a Class of Multivariate Density Estimation Methods Based on Adaptive Partitioning

  2023cites this paper
• An efficient stochastic particle method for moderately high-dimensional nonlinear PDEs

  2023cites this paper
• Random Forest Density Estimation

  2022cites this paper
• Adaptive manifold density estimation

  2022cites this paper
• Unsupervised Change Detection using DRE-CUSUM

  2022cites this paper
• An ODE Approach to Multiple Choice Polynomial Programming

  2022cites this paper
• An Optimal Transport Approach for Selecting a Representative Subsample with Application in Efficient Kernel Density Estimation

  2022cites this paper
• Nonparametric Multivariate Density Estimation: Case Study of Cauchy Mixture Model

  2021cites this paper
• Multivariate locally adaptive kernel density estimation

  2021cites this paper
• Accuracy of nonparametric density estimation for univariate Gaussian Mixture Models: a Comparative Study

  2020cites this paper
• Stochastic geometry to generalize the Mondrian Process

  2020cites this paper
• Learning Weighted Model Integration Distributions

  2020cites this paper
• Dependence structure estimation using Copula Recursive Trees

  2020cites this paper
• SPADE: Sequential-clustering Particle Annihilation via Discrepancy Estimation

  2020cites this paper
• Overcoming the numerical sign problem in Wigner dynamics via particle annihilation

  2020cites this paper
• Black-box density function estimation using recursive partitioning

  2020cites this paper
• Tree based credible set estimation

  2020influential citation
• Overcoming the Numerical Sign Problem in the Wigner Dynamics via Adaptive Particle Annihilation

  2020cites this paper
• Density estimation of multivariate samples using Wasserstein distance

  2019cites this paper
• Histogram Transform Ensembles for Density Estimation

  2019cites this paper
• Nonparametric density estimation for high‐dimensional data—Algorithms and applications

  2019influential citation
• Combining Smoothing Spline with Conditional Gaussian Graphical Model for Density and Graph Estimation.

  2019cites this paper
• Towards high performance data analytic on heterogeneous many-core systems: A study on Bayesian Sequential Partitioning

  2018influential citation
• Scalable multi-sample single-cell data analysis by Partition-Assisted Clustering and Multiple Alignments of Networks

  2017cites this paper
• Convergence rates of a partition based Bayesian multivariate density estimation method

  2017cites this paper
• Sparse Density Trees and Lists: An Interpretable Alternative to High-Dimensional Histograms

  2015cites this paper
• co-BPM: a Bayesian Model for Estimating Divergence and Distance of Distributions

  2014cites this paper