Fast multivariate log-concave density estimation

A novel computational approach to log-concave density estimation is proposed. Previous approaches utilize the piecewise-affine parametrization of the density induced by the given sample set. The number of parameters as well as non-smooth subgradient-based convex optimization for determining the maximum likelihood density estimate cause long runtimes for dimensions d≥2 and large sample sets. The presented approach is based on mildly non-convex smooth approximations of the objective function and sparse, adaptive piecewise-affine density parametrization. Established memory-efficient numerical optimization techniques enable to process larger data sets for dimensions d≥2. While there is no guarantee that the algorithm returns the maximum likelihood estimate for every problem instance, we provide comprehensive numerical evidence that it does yield near-optimal results after significantly shorter runtimes. For example, 10000 samples in R2 are processed in two seconds, rather than in ≈14 hours required by the previous approach to terminate. For higher dimensions, density estimation becomes tractable as well: Processing 10000 samples in R6 requires 35 min. The software is publicly available as CRAN R package fmlogcondens.