# what is determinantal process?

Would anyone please explain what does this mean?

A random point process $P$ on a discrete base set $Y = \{1,\ldots,N\}$ is a probability measure on the set $2^Y$ of all subsets of $Y$. Let $K$ be a semidefinite matrix with rows and columns indexed by the elements of $Y$. $P$ is called a determinantal point process (DPP) if there exists some matrix $K$ with all eigenvalues less than or equal to $1$, such that if $Z$ is a random set drawn according to $P$, then for every $A ⊆ Y$: $P(Z ⊇ A) = \det(K_A)$.

my problem is exactly this: we know an of example of point process is poisson process,but how does it define a probability measure on Y? and what does it mean: " Z is a random set drawn according to P."?

thanks!

• What is $K_A$ ?
– zoli
May 1, 2015 at 10:09
• @zoli $K_A ≡ [K_{i,j}]$ for $i,j\in A$ denotes the restriction of $K$ to the entries indexed by elements of $A$, and we adopt $det(K_∅) = 1$. May 1, 2015 at 10:40
• $\det A$=the product of the eigenvalues.
– zoli
May 1, 2015 at 10:48
• @zoli yes but i can't understand how is P a probability measure May 1, 2015 at 11:08
• @user115608 I think you are looking at it backwards: a probability measure is called a DPP if there exists such a matrix which describes it. You are not necessarily guaranteed (at least from what you've already written) that all semidefinite matrices with eigenvalues at most 1 induce a probability measure this way. The more interesting question, I think, is what is one example of such a matrix. For that I think it is probably most natural to think about diagonal matrices. For instance, is there a multiple of the identity that induces such a matrix?
– Ian
May 1, 2015 at 11:55

$P$ is a distribution over $2^Y$, the set of all subsets of $Y$. $P$ is just a discrete distribution that assigns a probability to each $Z\subseteq Y$. For a DPP, this discrete probability is defined in terms of a "marginal," in the sense that if you fix some $A\subseteq Y$, then you have a matrix $K_A$ that defines the probability of containing $A$:

$$P(A\subseteq Z) \equiv \sum_{Z\supseteq A} P(Z) = \det(K_A)$$

I agree that this definition is a bit lopsided. Perhaps someone else can motivate why this is a natural definition. I find that L-ensembles somewhat easier to get an intuition for. I highly recommend taking a look at Alex Kulesza and Ben Taskar's work on DPPs in machine learning. This has a dense but good introduction and this is a great review of their work.

The key idea of the given definition is as follows: If $$P$$ is a DPP defined over a set $$Y$$, then if you draw a random subset $$Z$$ of $$Y$$, the probability of some elements(given by $$A$$) such that they appear in this sampled $$Z$$ is given by the corresponding minor of the determinant of kernel matrix $$K$$.

For example, consider the following illlustrative kernel matrix $$K$$ over three elements $$\{1, 2, 3\}$$ $$K = \left[ \begin{matrix} x_{11} & x_{12} & x_{13}\\ x_{21} & x_{22} & x_{23}\\ x_{31} & x_{32} & x_{33}\\ \end{matrix} \right]$$

If $$K$$ represents the kernel matrix of DPP $$P$$ (assuming all required mathematical properties of positive definiteness and bounded spectrum), let say we sample a $$Z$$ of length 2, then the probability that set $$A = \{1, 3\}$$ is part of Z is given by the following determinant:

$$\Rightarrow \left| \begin{matrix} x_{11} && x_{13} \\ x_{31} && x_{33} \end{matrix} \right|$$

$$\Rightarrow (x_{11}\cdot x_{33} - x_{13}\cdot x_{31})$$