what is determinantal process?

Question

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!

Answer 1

$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.

Answer 2

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}) $$