Determinantal point processes



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

References

Agueh, Martial, and Guillaume Carlier. 2011. Barycenters in the Wasserstein Space.” SIAM Journal on Mathematical Analysis 43 (2): 904–24.
Alaya, Mokhtar Z., Maxime Berar, Gilles Gasso, and Alain Rakotomamonjy. 2019. Screening Sinkhorn Algorithm for Regularized Optimal Transport.” Advances in Neural Information Processing Systems 32.
Altschuler, Jason, Jonathan Niles-Weed, and Philippe Rigollet. n.d. “Near-Linear Time Approximation Algorithms for Optimal Transport via Sinkhorn Iteration,” 11.
Belhadji, Ayoub, R. Bardenet, and Pierre Chainais. 2019. Kernel Quadrature with DPPs.” In NeurIPS 2019 - Thirty-Third Conference on Neural Information Processing Systems. Vancouver, Canada.
Ben Hough, J., Manjunath Krishnapur, Yuval Peres, and Bálint Virág. 2006. Determinantal Processes and Independence.” Probability Surveys 3 (0): 206–29.
Ben Hough, John, Manjunath Krishnapur, Yuval Peres, and Bálint Virág. 2009. Zeros of Gaussian Analytic Functions and Determinantal Point Processes. University Lecture Series, v. 51. Providence, R.I: American Mathematical Soc.
Benamou, Jean-David, Guillaume Carlier, Marco Cuturi, Luca Nenna, and Gabriel Peyré. 2014. Iterative Bregman Projections for Regularized Transportation Problems.” arXiv:1412.5154 [Math], December.
Blondel, Mathieu, Vivien Seguy, and Antoine Rolet. 2018. Smooth and Sparse Optimal Transport.” In AISTATS 2018.
Bonneel, Nicolas. n.d. “Displacement Interpolation Using Lagrangian Mass Transport,” 11.
Borodin, Alexei. 2009. Determinantal Point Processes.” In Oxford Handbook of Random Matrix Theory.
Chizat, Lenaic, Gabriel Peyré, Bernhard Schmitzer, and François-Xavier Vialard. 2017. Scaling Algorithms for Unbalanced Transport Problems.” arXiv:1607.05816 [Math], May.
Courty, Nicolas, Rémi Flamary, Devis Tuia, and Alain Rakotomamonjy. 2016. Optimal Transport for Domain Adaptation.” arXiv:1507.00504 [Cs], June.
Cuturi, Marco. 2013. Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances.” In Advances in Neural Information Processing Systems 26.
Cuturi, Marco, and Arnaud Doucet. 2014. Fast Computation of Wasserstein Barycenters.” In International Conference on Machine Learning, 685–93. PMLR.
Flamary, Rémi, Marco Cuturi, Nicolas Courty, and Alain Rakotomamonjy. 2018. Wasserstein Discriminant Analysis.” Machine Learning 107 (12): 1923–45.
Flamary, Remi, Alain Rakotomamonjy, Nicolas Courty, and Devis Tuia. n.d. “Optimal Transport with Laplacian Regularization,” 10.
Frogner, Charlie, Chiyuan Zhang, Hossein Mobahi, Mauricio Araya, and Tomaso A Poggio. 2015. Learning with a Wasserstein Loss.” In Advances in Neural Information Processing Systems 28, edited by C. Cortes, N. D. Lawrence, D. D. Lee, M. Sugiyama, and R. Garnett, 2053–61. Curran Associates, Inc.
Genevay, Aude, Marco Cuturi, Gabriel Peyré, and Francis Bach. 2016. Stochastic Optimization for Large-Scale Optimal Transport.” In Advances in Neural Information Processing Systems 29, edited by D. D. Lee, M. Sugiyama, U. V. Luxburg, I. Guyon, and R. Garnett, 3432–40. Curran Associates, Inc.
Genevay, Aude, Gabriel Peyré, and Marco Cuturi. 2017. Learning Generative Models with Sinkhorn Divergences.” arXiv:1706.00292 [Stat], October.
Gillenwater, Jennifer A, Alex Kulesza, Emily Fox, and Ben Taskar. 2014. Expectation-Maximization for Learning Determinantal Point Processes.” In Advances in Neural Information Processing Systems 27, edited by Z. Ghahramani, M. Welling, C. Cortes, N. D. Lawrence, and K. Q. Weinberger, 3149–57. Curran Associates, Inc.
Iyer, Rishabh, and Jeffrey Bilmes. 2015. Submodular Point Processes with Applications to Machine Learning.” In Artificial Intelligence and Statistics, 388–97.
Knott, M., and C. S. Smith. 1984. On the Optimal Mapping of Distributions.” Journal of Optimization Theory and Applications 43 (1): 39–49.
Krishnapur, Manjunath. 2006. Zeros of Random Analytic Functions.” arXiv:math/0607504, July.
Kulesza, Alex, and Ben Taskar. 2011. Learning Determinantal Point Processes.” In Proceedings of the Twenty-Seventh Conference on Uncertainty in Artificial Intelligence, 419–27. UAI’11. Arlington, Virginia, United States: AUAI Press.
———. 2012. Determinantal Point Processes for Machine Learning. Vol. 5. Foundations and Trends® in Machine Learning 5,2-3. Boston, Mass.: Now Foundations and Trends.
Lavancier, Frédéric, Jesper Møller, and Ege Rubak. 2015. Determinantal Point Process Models and Statistical Inference.” Journal of the Royal Statistical Society: Series B (Statistical Methodology) 77 (4): 853–77.
Lyons, Russell. 2003. Determinantal Probability Measures.” Publications Mathématiques de l’Institut Des Hautes Études Scientifiques 98 (1): 167–212.
Lyons, Russell, and Y. Peres. 2016. Probability on Trees and Networks. Cambridge Series in Statistical and Probabilistic Mathematics. New York NY: Cambridge University Press.
McCullagh, Peter, and Jesper Møller. 2006. The Permanental Process.” Advances in Applied Probability 38 (4): 873–88.
Møller, Jesper, and Rasmus Waagepetersen. 2017. Some Recent Developments in Statistics for Spatial Point Patterns.” Annual Review of Statistics and Its Application 4 (1): 317–42.
Møller, Jesper, and Rasmus Plenge Waagepetersen. 2007. Modern Statistics for Spatial Point Processes.” Scandinavian Journal of Statistics 34 (4): 643–84.
Osogami, Takayuki, Rudy Raymond, Akshay Goel, Tomoyuki Shirai, and Takanori Maehara. 2018. Dynamic Determinantal Point Processes.” In Thirty-Second AAAI Conference on Artificial Intelligence.
Pemantle, Robin, and Igor Rivin. 2013. “The Distribution of Zeros of the Derivative of a Random Polynomial.” In Advances in Combinatorics, edited by Ilias S. Kotsireas and Eugene V. Zima, 259–73. Springer Berlin Heidelberg.
Perrot, Michaël, Nicolas Courty, Rémi Flamary, and Amaury Habrard. n.d. “Mapping Estimation for Discrete Optimal Transport,” 9.
Peyré, Gabriel, Marco Cuturi, and Justin Solomon. 2016. Gromov-Wasserstein Averaging of Kernel and Distance Matrices.” In International Conference on Machine Learning, 2664–72. PMLR.
Qiao, Maoying, Richard Yi Da Xu, Wei Bian, and Dacheng Tao. 2016. Fast Sampling for Time-Varying Determinantal Point Processes.” ACM Transactions on Knowledge Discovery from Data 11 (1): 8:1–24.
Redko, Ievgen, Nicolas Courty, Rémi Flamary, and Devis Tuia. 2019. Optimal Transport for Multi-Source Domain Adaptation Under Target Shift.” In The 22nd International Conference on Artificial Intelligence and Statistics, 849–58. PMLR.
Schmitzer, Bernhard. 2019. Stabilized Sparse Scaling Algorithms for Entropy Regularized Transport Problems.” arXiv:1610.06519 [Cs, Math], February.
Solomon, Justin, Fernando de Goes, Gabriel Peyré, Marco Cuturi, Adrian Butscher, Andy Nguyen, Tao Du, and Leonidas Guibas. 2015. Convolutional Wasserstein Distances: Efficient Optimal Transportation on Geometric Domains.” ACM Transactions on Graphics 34 (4): 66:1–11.
Soshnikov, A. 2000. Determinantal Random Point Fields.” Russian Mathematical Surveys 55 (5): 923.
Torrisi, Giovanni Luca, and Emilio Leonardi. 2014. Large Deviations of the Interference in the Ginibre Network Model.” Stochastic Systems 4 (1): 173–205.
Xie, Pengtao, Ruslan Salakhutdinov, Luntian Mou, and Eric P. Xing. 2017. Deep Determinantal Point Process for Large-Scale Multi-Label Classification.” In, 473–82. IEEE.

No comments yet. Why not leave one?

GitHub-flavored Markdown & a sane subset of HTML is supported.