Vi studerar dubbelvolymprovtagning, en metod för att välja k kolumner från en n × m kort och bred matris (n ≤ k ≤ m) så att sannolikheten för urvalet är proportionell mot den volym som spänns av raderna i den inducerade submatrisen. Denna metod föreslogs av Avron och Boutsidis (2013), som visade att det är en lovande metod för kolumn delmängd urval och dess flera tillämpningar. Emellertid har dess bredare antagande hindrats av bristen på polynomiska tidsprovtagningsalgoritmer. Vi tar bort detta hinder genom att utveckla en exakt (randomized) polynom tid provtagning algoritm samt dess derandomization. Därefter studerar vi dubbelvolymprovtagning via teorin om verkliga stabila polynom och bevisar att dess fördelning uppfyller "Strong Rayleigh" egenskapen. Detta resultat har många konsekvenser, bland annat en bevisligen snabbblandande Markov-kedjeprovtagare som gör dubbelvolymprovtagning mycket mer attraktiv för utövare. Denna provtagare är nära relaterad till klassiska algoritmer för populära experimentella designmetoder som hittills saknar teoretisk analys men som är kända för att empiriskt fungera väl.
Några andra polynom-tid provtagningsmetoder och deras koppling till teorin om Markov kedjor ansågs i REF.
Polynomial Time Algorithms for Dual Volume Sampling
{'venue': 'NIPS', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}