k-Determinantal Point Processes for Fixed-Size Subset Selection

k-Determinantal Point Processes for Fixed-Size Subset Selection (k-DPPs) is a probabilistic diverse subset selection model and exact polynomial-time inference framework introduced by Kulesza and Taskar (2011) that conditions a standard L-ensemble Determinantal Point Process on the event that the selected subset Y subseteq {1, ..., N} has exact fixed cardinality |Y| = k. Given an N x N positive semidefinite similarity and quality kernel L = sum_{n=1}^N lambda_n v_n v_n^T, a k-DPP assigns probability P_L^k(Y) = det(L_Y) / e_k(lambda_1, ..., lambda_N) to every k-subset Y (Equation 5 & Proposition 3.1, Equation 10), where the normalization constant sum_{|Y'|=k} det(L_{Y'}) equals the k-th elementary symmetric polynomial e_k(lambda_1, ..., lambda_N) = sum_{|J|=k} prod_{n in J} lambda_n of the eigenvalues of L. Algorithm 2 computes all intermediate polynomials e_l^n = e_l(lambda_1, ..., lambda_n) in O(N k) time via the Newton-Pascal recurrence e_l^n = e_l^{n-1} + lambda_n e_{l-1}^{n-1} (Equation 12), and Algorithm 1 decomposes P_L^k into a mixture of rank-k elementary projection DPPs (Equation 8), first sampling an eigenvector index subset J of size k in O(N k) time with sequential marginal probabilities lambda_n e_{l-1}^{n-1} / e_l^n and then sampling k items Y from the projection DPP spanned by {v_n}_{n in J} in O(N k^2) time via iterative Gram-Schmidt orthogonal projection.