Determinantal Processes and Independence

By John Hough, Manjunath Krishnapur, Yuval Peres, B'alint Vir'ag. 2005

594 citations recorded by the source corpus.

We give a probabilistic introduction to determinantal and per- manental point processes. Determinantal processes arise in physics (fermions, eigenvalues of random matrices) and in combinatorics (nonintersecting paths, random spanning trees). They have the striking property that the number of points in a region D is a sum of independent Bernoulli random variables, with parameters which are eigenvalues of the relevant operator on L 2 (D). Moreover, any determinantal process can be represented as a mixture of determinantal projection processes. We give a simple explanation for these known facts, and establish analogous representations for permanental pro- cesses, with geometric variables replacing the Bernoulli variables. These representations lead to simple proofs of existence criteria and central limit theorems, and unify known results on the distribution of absolute values in certain processes with radially symmetric distributions.

Subfields: Discrete Mathematics and Combinatorics, Mathematical Physics, Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Discrete Mathematics and Combinatorics

In Mathematical Physics

In Statistics and Probability

Citations in the corpus

Determinantal Point Processes for Machine Learning (2012, methodology): “Many good mathematical surveys are now available [12, 68, 97, 132, 133, 137, 145].”
Data-Driven Sparse Structure Selection for Deep Neural Networks (2017, methodology): “They used Determinantal Point Process [25] to select a subset of diverse neurons and subsequently merged similar neurons.”
Structured Determinantal Point Processes (2010, background): “Sampling from P L is also efﬁcient [7].”
Hyperdeterminantal point processes (2008, methodology): “cycles of σ gives the alpha-permanental processes introduced in [VJ97] and further studied in [ST03a, HKPV06 ].”
Monte Carlo with determinantal point processes (2016, methodology): “The standard algorithm is O(N3) [Hough et al., 2006].”
Improved Bounds for the Nyström Method With Application to Kernel Classification (2011, methodology): “e other sampling approaches. We notice that in (Belabbas and Wolfe, 2009), the authors show a signiﬁcantly better approximation bound for the Nystr¨om method when employing the determinantal process (Hough et al., 2006) for column selection; however, it is important to point out that the determinant”
Near-Optimal MAP Inference for Determinantal Point Processes (2012, background): “DPPs offer computationally attractive properties, including exact and efficient computation of marginals [8], sampling [12, 5], and (partial) parameter estimation [13].”
Hyperdeterminantal relations among symmetric principal minors (2006, background): “Determinantal processes arise naturally in several fields, including quantum mechanics of fermions [11], eigenvalues of random matrices, random spanning trees and nonintersecting paths (see [10] and references therein).”
Stochastic geometry and random graphs for the analysis and design of wireless networks (2009, methodology): “, Neyman-Scott cluster processes, permanental point processes [44] or Hawkes point processes [45].”
The Ubiquitous Ewens Sampling Formula (2016, background): “Heuristically, (23) interpolates between (21) and (22), Cauchy’s permanent (22) is the α-permanent with α = 1, and the determinant (21) equals (−1)n per−1(M), but its role is most prominent in modeling bosons and fermions in statistical physics [49, 66].”
Negative dependence and the geometry of polynomials (2007, background): “[5, 57], such measures have important applications ranging from fermionic processes/continuous scaling limits of discrete point processes [23, 59] to the distribution of eigenvalues of random matrices and zeros of the Riemann zeta function [21], transfer current matrices [16], non-intersecting rando”
Fair and Diverse DPP-based Data Summarization (2018, background): “While for unconstrained DPPs there are efficient algorithms to sample (Hough et al., 2006), the problem of sampling from constrained DPPs is intractable; see (Celis et al.”
Fekete points and convergence towards equilibrium measures on complex manifolds (2009, background): “n extremal properties. Even if the precise construction seems to be new, it should be emphasized that it is inspired by the elegant algorithmic construction of determinantal random point processes in [HKPV06]. Fix a weighted measure (µ,φ) where µis as before a probability measure on K. A conﬁguratio”
The Palm measure and the Voronoi tessellation for the Ginibre process (2006, unknown): “([12], Theorem 7) that the random variable NU(ψ) has the distribution of a sum of independent Bernoulli (αi) random variables.”
Lectures on the Poisson Process (2017, background): “A survey of the probabilistic properties of permanental and determinantal point processes can be found in [51].”
Determinantal Point Processes (2016, methodology): “In particular, we describe the (standard) sampling algorithm given in [17] (see Algorithm 1 below) and an alternative simulation algorithm obtained by specializing the well-known routine to sample from the law of a finite point process with bounded Papangelou conditional intensity (see e.”