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 textitsparse, 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 ℝ2 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 ℝ6 requires 35 minutes. The software is publicly available as CRAN R package fmlogcondens.