Optimal transport between determinantal point processes and application to fast simulation

Decreusefond, Laurent; Moroz, Guillaume

doi:10.15559/21-VMSTA180

Modern Stochastics: Theory and Applications

Optimal transport between determinantal point processes and application to fast simulation

Volume 8, Issue 2 (2021), pp. 209–237

Laurent Decreusefond ¹

Guillaume Moroz ¹

https://doi.org/10.15559/21-VMSTA180

Pub. online: 2 June 2021 Type: Research Article

Open Access

¹ Supported by grant ANR-17-CE40-0017 of the French National Research Agency (ANR project ASPAG). The authors are indebted to the anonymous referees for their very insightful remarks which helped them to improve this paper.

Received
1 November 2020

Revised
1 April 2021

Accepted
10 May 2021

Published
2 June 2021

Abstract

Two optimal transport problems between determinantal point processes (DPP for short) are investigated. It is shown how to estimate the Kantorovitch–Rubinstein and Wasserstein-2 distances between distributions of DPP. These results are applied to evaluate the accuracy of a fast but approximate simulation algorithm of the Ginibre point process restricted to a circle. One can now simulate in a reasonable amount of time more than ten thousands points.

References

[1]

Anari, N., Gharan, S.O., Rezaei, A.: Monte Carlo Markov chain algorithms for sampling strongly Rayleigh distributions and determinantal point processes. In: 29th Annual Conference on Learning Theory, vol. 49, pp. 103–115 (2016). http://proceedings.mlr.press/v49/anari16.html

[2]

Barbour, A.D., Brown, T.C.: The Stein-Chen method, point processes and compensators. Ann. Probab. 20(3), 1504–1527 (1992). MR1175275

[3]

Barbour, A.D., Maansson, M.: Compound Poisson process approximation. Ann. Probab. 30(3), 1492–1537 (2002). 00027. MR1920275. https://doi.org/10.1214/aop/1029867135

[4]

Bardenet, R., Hardy, A.: Monte Carlo with determinantal point processes. Ann. Appl. Probab. 30(1), 368–417 (2020). MR4068314. https://doi.org/10.1214/19-AAP1504

[5]

Burden, R.L., Faires, J.D.: Numerical Analysis. Cengage Learning, Boston, MA (2016)

[6]

Camilier, I., Decreusefond, L.: Quasi-invariance and integration by parts for determinantal and permanental point processes. J. Funct. Anal. 259, 268–300 (2010). MR2610387. https://doi.org/10.1016/j.jfa.2010.01.007

[7]

Daley, D.J., Vere-Jones, D.: An Introduction to the Theory of Point Processes. Vol. I: Elementary theory and methods, 2nd edn. Probability and its Applications (New York), p. 469. Springer (2003). MR1950431

[8]

Decreusefond, L.: Wasserstein distance on configurations space. Potential Anal. 28(3), 283–300 (2008). MR2386101. https://doi.org/10.1007/s11118-008-9077-5

[9]

Decreusefond, L., Vasseur, A.: Stein’s method and Papangelou intensity for Poisson or Cox process approximation. Working paper or preprint (2018). https://hal.archives-ouvertes.fr/hal-01832212

[10]

Decreusefond, L., Flint, I., Vergne, A.: A note on the simulation of the Ginibre point process. J. Appl. Probab. 52(04), 1003–1012 (2015). 1310.0800v2. MR3439168. https://doi.org/10.1239/jap/1450802749

[11]

Decreusefond, L., Joulin, A., Savy, N.: Upper bounds on Rubinstein distances on configuration spaces and applications. Commun. Stoch. Anal. 4(3), 377–399 (2010). MR2677197. https://doi.org/10.31390/cosa.4.3.05

[12]

Dudley, R.M.: Real Analysis and Probability vol. 74. Cambridge University Press (2002). MR1932358. https://doi.org/10.1017/CBO9780511755347

[13]

Fenzl, M., Lambert, G.: Precise Deviations for Disk Counting Statistics of Invariant Determinantal Processes. Int. Math. Res. Not. (2021). https://doi.org/10.1093/imrn/rnaa341

[14]

Gillenwater, J.: Approximate inference for determinantal point processes. PhD thesis, University of Pennsylvania (2014). MR3321917

[15]

Goldman, A.: The Palm measure and the Voronoi tessellation for the Ginibre process. Ann. Appl. Probab. 20(1), 90–128 (2010). math/0610243. MR2582643. https://doi.org/10.1214/09-AAP620

[16]

Gomez, J.-S., Vasseur, A., Vergne, A., Martins, P., Decreusefond, L., Wei, C.: A Case Study on Regularity in Cellular Network Deployment. Wirel. Commun. Lett. (2015)

[17]

Haimi, A., Hedenmalm, H.: The polyanalytic Ginibre ensembles. J. Stat. Phys. 153(1), 10–47 (2013). MR3100813. https://doi.org/10.1007/s10955-013-0813-x

[18]

Hough, J.B., Krishnapur, M., Peres, Y., Virág, B.: Determinantal processes and independence. Probab. Surv. 3, 206–229 (2006). MR2216966. https://doi.org/10.1214/154957806000000078

[19]

Hough, J.B., Krishnapur, M., Peres, Y., Virág, B.: Zeros of Gaussian Analytic Functions and Determinantal Point Processes. University Lecture Series, vol. 51, p. 154. American Mathematical Society, Providence, RI (2009). MR2552864. https://doi.org/10.1090/ulect/051

[20]

Kallenberg, O.: Random Measures, 3rd edn. Academic Press (1983). MR0818219

[21]

Kulesza, A., Taskar, B.: Determinantal point processes for machine learning. Found. Trends Mach. Learn. 5(2–3), 123–286 (2012). https://doi.org/10.1561/2200000044

[22]

Lavancier, F., Møller, J., Rubak, E.: Determinantal point process models and statistical inference. J. R. Stat. Soc., Ser. B, Stat. Methodol. 77(4), 853–877 (2015). MR3382600. https://doi.org/10.1111/rssb.12096

[23]

Lindvall, T.: On Strassen’s Theorem on Stochastic Domination. Electron. Commun. Probab. 4, 51–59 (1999). MR1711599. https://doi.org/10.1214/ECP.v4-1005

[24]

Macchi, O.: The coincidence approach to stochastic point processes. Adv. Appl. Probab. 7, 83–122 (1975). MR0380979. https://doi.org/10.2307/1425855

[25]

McCann, R., Guillen, N.: Five Lectures on Optimal Transportation: Gemetry, Regularity and Applications. CRM Proceedings and Lecture Notes, vol. 56. American Mathematical Society, Providence, Rhode Island (2013). MR3060502. https://doi.org/10.1090/crmp/056/06

[26]

Moroz, G.: Determinantal Point Process. Zenodo (2020). https://doi.org/10.5281/zenodo.4088585

[27]

Olver, S., Nadakuditi, R.R., Trogdon, T.: Sampling unitary ensembles. Random Matrices: Theory Appl. 4(1), 1550002 (2015). MR3334666. https://doi.org/10.1142/S2010326315500021

[28]

Rezaei, A., Gharan, S.O.: A polynomial time MCMC method for sampling from continuous determinantal point processes. In: Proceedings of the 36th International Conference on Machine Learning, vol. 97, pp. 5438–5447 (2019). http://proceedings.mlr.press/v97/rezaei19a.html.

[29]

Röckner, M., Schied, A.: Rademacher’s theorem on configuration spaces and applications. J. Funct. Anal. 169(2), 325–356 (1999). MR1730565. https://doi.org/10.1006/jfan.1999.3474

[30]

Shirai, T., Takahashi, Y.: Random point fields associated with certain Fredholm determinants i: fermion, Poisson and boson point processes. J. Funct. Anal. 205(2), 414–463 (2003). MR2018415. https://doi.org/10.1016/S0022-1236(03)00171-X

[31]

Tremblay, N., Barthelme, P.-O., Amblard, S.: Optimized Algorithms to Sample Determinantal Point Processes. arXiv e-prints, 1802–08471 (2018). 1802.08471.

[32]

Villani, C.: Topics in Optimal Transportation. Graduate Studies in Mathematics, vol. 58. American Mathematical Society, Providence, RI (2003). MR1964483. https://doi.org/10.1090/gsm/058

[33]

Villani, C.: Optimal Transport, Old and New. Lectures Notes in Mathematics. Springer Verlag, New York (2007). MR2459454. https://doi.org/10.1007/978-3-540-71050-9

Full article

Open access article under the CC BY license.

Metrics

since March 2018

561

Article info
views

655

Full article
views

373

PDF
downloads

130

XML
downloads

RSS

Authors

Abstract

References

Export citation

Copy and paste formatted citation

Download citation in file