Determinantal point processes

July 31, 2018 — March 16, 2021

linear algebra
Monte Carlo
point processes
Figure 1

Placeholder notes for a type of point process, with which I am unfamiliar, but about which I am incidentally curious.

Wikipedia says:

Let \(\Lambda\) be a locally compact Polish space and \(\mu\) be a Radon measure on \(\Lambda\). Also, consider a measurable function \(K:\Lambda^2\rightarrow \mathbb{C}\).

We say that \(X\) is a determinantal point process on \(\Lambda\) with kernel \(K\) if it is a simple point process on \(\Lambda\) with a joint intensity/Factorial_moment_densityorcorrelation function (which is the density of its factorial moment measure) given by

\[ \rho_n(x_1,\ldots,x_n) = \det[K(x_i,x_j)]_{1 \le i,j \le n} \]

for every \(n\ geq 1\) and \(x_1,\dots, x_n\in \Lambda.\)

The most popular tutorial introduction to this topic seems to be (Kulesza and Taskar 2012). I found it unhelpful as it is rooted in discrete-space problems which is precisely where I do not work. For continuous state space, (Møller and Waagepetersen 2007; Møller and Waagepetersen 2017) and Terry Tao’s summary of (J. Ben Hough et al. 2006) are good.

Interesting property: The zeros random polynomials with Gaussian coefficients are apparently to be distributed as DPPs (John Ben Hough et al. 2009; Krishnapur 2006).

One idea these processes provoke is use as a source of random low-discrepancy samples for quadrature, which I have seen suggested by Richard Xu Qiao et al. (2016) and Belhadji, Bardenet, and Chainais (2019).

See also its cousin, the permanental point process.

1 References

Agueh, and Carlier. 2011. Barycenters in the Wasserstein Space.” SIAM Journal on Mathematical Analysis.
Alaya, Berar, Gasso, et al. 2019. Screening Sinkhorn Algorithm for Regularized Optimal Transport.” Advances in Neural Information Processing Systems.
Altschuler, Niles-Weed, and Rigollet. 2017. “Near-Linear Time Approximation Algorithms for Optimal Transport via Sinkhorn Iteration.” In.
Bardenet, Lavancier, Mary, et al. 2017. On a Few Statistical Applications of Determinantal Point Processes.” Edited by Jean-François Coeurjolly and Adeline Leclercq-Samson. ESAIM: Proceedings and Surveys.
Belhadji, Bardenet, and Chainais. 2019. Kernel Quadrature with DPPs.” In NeurIPS 2019 - Thirty-Third Conference on Neural Information Processing Systems.
Ben Hough, J., Krishnapur, Peres, et al. 2006. Determinantal Processes and Independence.” Probability Surveys.
Ben Hough, John, Krishnapur, Peres, et al. 2009. Zeros of Gaussian Analytic Functions and Determinantal Point Processes. University Lecture Series, v. 51.
Benamou, Carlier, Cuturi, et al. 2014. Iterative Bregman Projections for Regularized Transportation Problems.” arXiv:1412.5154 [Math].
Blondel, Seguy, and Rolet. 2018. Smooth and Sparse Optimal Transport.” In AISTATS 2018.
Bonneel. n.d. “Displacement Interpolation Using Lagrangian Mass Transport.”
Borodin. 2009. Determinantal Point Processes.” In Oxford Handbook of Random Matrix Theory.
Chizat, Peyré, Schmitzer, et al. 2017. Scaling Algorithms for Unbalanced Transport Problems.” arXiv:1607.05816 [Math].
Courty, Flamary, Tuia, et al. 2016. Optimal Transport for Domain Adaptation.” arXiv:1507.00504 [Cs].
Cuturi. 2013. Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances.” In Advances in Neural Information Processing Systems 26.
Cuturi, and Doucet. 2014. Fast Computation of Wasserstein Barycenters.” In International Conference on Machine Learning.
Flamary, Rémi, Cuturi, Courty, et al. 2018. Wasserstein Discriminant Analysis.” Machine Learning.
Flamary, Remi, Rakotomamonjy, Courty, et al. n.d. “Optimal Transport with Laplacian Regularization.”
Frogner, Zhang, Mobahi, et al. 2015. Learning with a Wasserstein Loss.” In Advances in Neural Information Processing Systems 28.
Genevay, Cuturi, Peyré, et al. 2016. Stochastic Optimization for Large-Scale Optimal Transport.” In Advances in Neural Information Processing Systems 29.
Genevay, Peyré, and Cuturi. 2017. Learning Generative Models with Sinkhorn Divergences.” arXiv:1706.00292 [Stat].
Gillenwater, Kulesza, Fox, et al. 2014. Expectation-Maximization for Learning Determinantal Point Processes.” In Advances in Neural Information Processing Systems 27.
Iyer, and Bilmes. 2015. Submodular Point Processes with Applications to Machine Learning.” In Artificial Intelligence and Statistics.
Knott, and Smith. 1984. On the Optimal Mapping of Distributions.” Journal of Optimization Theory and Applications.
Krishnapur. 2006. Zeros of Random Analytic Functions.” arXiv:math/0607504.
Kulesza, and Taskar. 2011. Learning Determinantal Point Processes.” In Proceedings of the Twenty-Seventh Conference on Uncertainty in Artificial Intelligence. UAI’11.
———. 2012. Determinantal Point Processes for Machine Learning. Foundations and Trends® in Machine Learning 5,2-3.
Lavancier, Møller, and Rubak. 2015. Determinantal Point Process Models and Statistical Inference.” Journal of the Royal Statistical Society: Series B (Statistical Methodology).
Li, Jegelka, and Sra. 2015. Efficient Sampling for k-Determinantal Point Processes.”
Liu, Walder, and Xie. 2022. Determinantal Point Process Likelihoods for Sequential Recommendation.” In Proceedings of the 45th International ACM SIGIR Conference on Research and Development in Information Retrieval. SIGIR ’22.
Lyons. 2003. Determinantal Probability Measures.” Publications Mathématiques de l’Institut Des Hautes Études Scientifiques.
Lyons, and Peres. 2016. Probability on Trees and Networks. Cambridge Series in Statistical and Probabilistic Mathematics.
Mariet. 2016. Learning and enforcing diversity with Determinantal Point Processes.”
McCullagh, and Møller. 2006. The Permanental Process.” Advances in Applied Probability.
Møller, and Waagepetersen. 2007. Modern Statistics for Spatial Point Processes.” Scandinavian Journal of Statistics.
Møller, and Waagepetersen. 2017. Some Recent Developments in Statistics for Spatial Point Patterns.” Annual Review of Statistics and Its Application.
Osogami, Raymond, Goel, et al. 2018. Dynamic Determinantal Point Processes.” In Thirty-Second AAAI Conference on Artificial Intelligence.
Pemantle, and Rivin. 2013. “The Distribution of Zeros of the Derivative of a Random Polynomial.” In Advances in Combinatorics.
Perrot, Courty, Flamary, et al. n.d. “Mapping Estimation for Discrete Optimal Transport.”
Peyré, Cuturi, and Solomon. 2016. Gromov-Wasserstein Averaging of Kernel and Distance Matrices.” In International Conference on Machine Learning.
Qiao, Xu, Bian, et al. 2016. Fast Sampling for Time-Varying Determinantal Point Processes.” ACM Transactions on Knowledge Discovery from Data.
Redko, Courty, Flamary, et al. 2019. Optimal Transport for Multi-Source Domain Adaptation Under Target Shift.” In The 22nd International Conference on Artificial Intelligence and Statistics.
Schmitzer. 2019. Stabilized Sparse Scaling Algorithms for Entropy Regularized Transport Problems.” arXiv:1610.06519 [Cs, Math].
Solomon, de Goes, Peyré, et al. 2015. Convolutional Wasserstein Distances: Efficient Optimal Transportation on Geometric Domains.” ACM Transactions on Graphics.
Soshnikov. 2000. Determinantal Random Point Fields.” Russian Mathematical Surveys.
Torrisi, and Leonardi. 2014. Large Deviations of the Interference in the Ginibre Network Model.” Stochastic Systems.
Xie, Salakhutdinov, Mou, et al. 2017. Deep Determinantal Point Process for Large-Scale Multi-Label Classification.” In.