  We study dual volume sampling, a method for selecting k columns from an n x m
short and wide matrix (n <= k <= m) such that the probability of selection is
proportional to the volume spanned by the rows of the induced submatrix. This
method was proposed by Avron and Boutsidis (2013), who showed it to be a
promising method for column subset selection and its multiple applications.
However, its wider adoption has been hampered by the lack of polynomial time
sampling algorithms. We remove this hindrance by developing an exact
(randomized) polynomial time sampling algorithm as well as its derandomization.
Thereafter, we study dual volume sampling via the theory of real stable
polynomials and prove that its distribution satisfies the "Strong Rayleigh"
property. This result has numerous consequences, including a provably
fast-mixing Markov chain sampler that makes dual volume sampling much more
attractive to practitioners. This sampler is closely related to classical
algorithms for popular experimental design methods that are to date lacking
theoretical analysis but are known to empirically work well.
