## Extended L-ensembles: a new representation for determinantal point processes.(English)Zbl 1527.60038

Determinantal point processes are by now perhaps the most famous example of repulsive point processes. A key aspect of determinantal point processes is that “diversity” is defined relative to a notion of similarity represented by a positive-definite kernel. For instance, if the items are vectors in $$\mathbb{R}^d$$, similarity may be defined via the squared-exponential (Gaussian) kernel: $$k(x, y)=\exp\left(-\| x - y\|^2\right)$$, where $$x$$ and $$y$$ are two items, and similarity is a decreasing function of distance. The class of determinantal point processess can be separated into two subclasses: $$L$$-ensembles and the rest. By definition, an $$L$$-ensemble based on the $$n\times n$$ kernel matrix $$\mathbf{L} = [k(x_i, x_j)]_{i,j}$$ is a distribution over random subsets $$\chi$$ such that $$P(\chi = X)\propto \det\mathbf{L}_X$$, where $$\mathbf{L}_X$$ is the principal submatrix of $$\mathbf{L}$$ indexed by $$X$$. If two or more points in $$X$$ are very similar (in the sense of the kernel function), then the matrix $$\mathbf{L}_X$$ has rows that are nearly collinear and the determinant is small. This in turns makes it unlikely that such a set $$\chi$$ will be selected by the $$L$$-ensemble. $$L$$-ensembles are thus highly intuitive, and it is easy to design a determinantal point process appropriate for a particular situation, since one only needs to pick an appropriate kernel. Unfortunately, not all determinantal point processes are $$L$$-ensembles. The main contribution of this paper is to provide a unifying framework to write handy, explicit joint distributions for all varying and fixed-size determinantal point processes and thus to fill in the holes of the current theory. To this end, the authors introduce extended $$L$$-ensembles, a novel way of representing the class of determinantal point processes. The authors show that all determinantal point processes are extended $$L$$-ensembles, and vice versa. The paper is organized as follows. Section 1 contains definitions, preliminaries and all of the results are classical [S. Barthelmé et al., Bernoulli 25, No. 4B, 3555–3589 (2019; Zbl 1428.62095)]. Section 2 defines extended $$L$$-ensembles while Section 3 gives some of their major properties. As a theoretical application, Section 4 shows how extended $$L$$-ensembles arise in perturbative limits of determinantal point processes. As a practical application, Section 5 shows that some interesting extended $$L$$-ensembles can be constructed via conditionally (semi)-definite positive functions. The authors chose to focus on discrete determinantal point processes, for simplicity. The continuous case is a straightforward generalisation of discrete results, which the authors sketch in the concluding remarks in Section 6.

### MSC:

 60G55 Point processes (e.g., Poisson, Cox, Hawkes processes) 65D05 Numerical interpolation

### Keywords:

determinantal point process; $$L$$-ensemble

Zbl 1428.62095
Full Text:

### References:

 [1] ANARI, N., VINZANT, C., LIU, K. and VUONG, T.-D. (2021). Log-concave polynomials IV: Approximate exchange, tight mixing times, and near-optimal sampling of forests. In STOC ’21—Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing 408-420. ACM, New York. · Zbl 07765181 · doi:10.1145/3406325.3451091 [2] AVENA, L. and GAUDILLIERE, A. (2013). On some random forests with determinantal roots. ArXiv preprint. Available at arXiv:1310.1723. · Zbl 1397.05161 [3] AVENA, L. and GAUDILLIÈRE, A. (2018). Two applications of random spanning forests. J. Theoret. Probab. 31 1975-2004. · Zbl 1397.05161 · doi:10.1007/s10959-017-0771-3 [4] Bardenet, R. and Hardy, A. (2020). Monte Carlo with determinantal point processes. Ann. Appl. Probab. 30 368-417. · Zbl 1491.65007 [5] BARTHELMÉ, S., AMBLARD, P.-O. and TREMBLAY, N. (2019). Asymptotic equivalence of fixed-size and varying-size determinantal point processes. Bernoulli 25 3555-3589. · Zbl 1428.62095 · doi:10.3150/18-bej1102 [6] BARTHELMÉ, S., TREMBLAY, N., USEVICH, K. and AMBLARD, P.-O. (2023). Determinantal point processes in the flat limit. Bernoulli. To appear. Availiable at arXiv:2107.07213. · Zbl 1535.60081 [7] BARTHELMÉ, S. and USEVICH, K. (2021). Spectral properties of kernel matrices in the flat limit. SIAM J. Matrix Anal. Appl. 42 17-57. · Zbl 1458.15012 · doi:10.1137/19M129677X [8] BELHADJI, A., BARDENET, R. and CHAINAIS, P. (2020). A determinantal point process for column subset selection. J. Mach. Learn. Res. 21 Paper No. 197. · Zbl 1536.68029 [9] BISCIO, C. A. N. and LAVANCIER, F. (2016). Quantifying repulsiveness of determinantal point processes. Bernoulli 22 2001-2028. · Zbl 1343.60058 · doi:10.3150/15-BEJ718 [10] BORODIN, A. and RAINS, E. M. (2005). Eynard-Mehta theorem, Schur process, and their Pfaffian analogs. J. Stat. Phys. 121 291-317. · Zbl 1127.82017 · doi:10.1007/s10955-005-7583-z [11] BURTON, R. and PEMANTLE, R. (1993). Local characteristics, entropy and limit theorems for spanning trees and domino tilings via transfer-impedances. Ann. Probab. 21 1329-1371. · Zbl 0785.60007 [12] CHEN, X.-H., DEMPSTER, A. P. and LIU, J. S. (1994). Weighted finite population sampling to maximize entropy. Biometrika 81 457-469. · Zbl 0816.62008 · doi:10.1093/biomet/81.3.457 [13] COEURJOLLY, J.-F., MAZOYER, A. and AMBLARD, P.-O. (2021). Monte Carlo integration of non-differentiable functions on ${[0,1]^{\iota }}, \iota =1,\dots ,d$, using a single determinantal point pattern defined on ${[0,1]^d}$. Electron. J. Stat. 15 6228-6280. · Zbl 1483.60072 · doi:10.1214/21-ejs1929 [14] DEREZIŃSKI, M. and MAHONEY, M. W. (2021). Determinantal point processes in randomized numerical linear algebra. Notices Amer. Math. Soc. 68 34-45. · Zbl 1454.60063 · doi:10.1090/noti2202 [15] FANUEL, M., SCHREURS, J. and SUYKENS, J. A. (2020). Determinantal point processes implicitly regularize semi-parametric regression problems. ArXiv preprint. Available at arXiv:2011.06964. · Zbl 07589189 [16] GAUTIER, G. (2020). On sampling determinantal point processes. Ph.D. thesis, Ecole Centrale de Lille. [17] Horn, R. A. and Johnson, C. R. (1990). Matrix Analysis. Cambridge Univ. Press, Cambridge. · Zbl 0704.15002 [18] HOUGH, J. B., KRISHNAPUR, M., PERES, Y. and VIRÁG, B. (2006). Determinantal processes and independence. Probab. Surv. 3 206-229. · Zbl 1189.60101 · doi:10.1214/154957806000000078 [19] KLEIN, D. J. and RANDIĆ, M. (1993). Resistance distance. J. Math. Chem. 12 81-95. · doi:10.1007/BF01164627 [20] KULESZA, A. and TASKAR, B. (2011). k-DPPs: Fixed-size determinantal point processes. In Proceedings of the 28th International Conference on Machine Learning (ICML-11) 1193-1200. [21] KULESZA, A., TASKAR, B. et al. (2012). Determinantal point processes for machine learning. Found. Trends Mach. Learn. 5 123-286. · Zbl 1278.68240 [22] Macchi, O. (1975). The coincidence approach to stochastic point processes. Adv. in Appl. Probab. 7 83-122. · Zbl 0366.60081 · doi:10.2307/1425855 [23] MICCHELLI, C. A. (1986). Interpolation of scattered data: Distance matrices and conditionally positive definite functions. Constr. Approx. 2 11-22. · Zbl 0625.41005 · doi:10.1007/BF01893414 [24] TREMBLAY, N., BARTHELME, S. and AMBLARD, P.-O. (2018). Optimized algorithms to sample determinantal point processes. Available at arXiv:1802.08471 [cs, Stat]. [25] TREMBLAY, N., BARTHELMÉ, S. and AMBLARD, P.-O. (2019). Determinantal point processes for coresets. J. Mach. Learn. Res. 20 Paper No. 168. · Zbl 1446.62351 [26] WENDLAND, H. (2005). Scattered Data Approximation. Cambridge Monographs on Applied and Computational Mathematics 17. Cambridge Univ. Press, Cambridge · Zbl 1075.65021 · doi:10.1017/CBO9780511617539
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.