Exact sampling of determinantal point processes without eigendecomposition
Claire Launay, Bruno Galerne, Agnès Desolneux
Abstract
Abstract Determinantal point processes (DPPs) enable the modeling of repulsion: they provide diverse sets of points. The repulsion is encoded in a kernel K that can be seen, in a discrete setting, as a matrix storing the similarity between points. The main exact algorithm to sample DPPs uses the spectral decomposition of K , a computation that becomes costly when dealing with a high number of points. Here we present an alternative exact algorithm to sample in discrete spaces that avoids the eigenvalues and the eigenvectors computation. The method used here is innovative, and numerical experiments show competitive results with respect to the initial algorithm.
Topics & Concepts
MathematicsEigenvalues and eigenvectorsPoint processComputationEigendecomposition of a matrixMatrix (chemical analysis)Sampling (signal processing)Applied mathematicsAlgorithmPoint (geometry)Determinantal point processRandom matrixSimilarity (geometry)Sample (material)Matrix decompositionDiscrete time and continuous timeStochastic processDecompositionMathematical optimizationSample mean and sample covarianceSample size determinationLimit pointNumerical analysisSpectrum (functional analysis)CombinatoricsMathematical analysisStatistical physicsPoint processes and geometric inequalitiesRandom Matrices and ApplicationsMarkov Chains and Monte Carlo Methods