Fast Determinantal Point Process Sampling with Application to Clustering
Determinantal Point Process (DPP) has gained much popularity for modeling sets of diverse items. The gist of DPP is that the probability of choosing a particular set of items is proportional to the determinant of a positive definite matrix that defines the similarity of those items. However, computing the determinant requires time cubic in the number of items, and is hence impractical for large sets. In this paper, we address this problem by constructing a rapidly mixing Markov chain, from which we can acquire a sample from the given DPP in sub-cubic time. In addition, we show that this framework can be extended to sampling from cardinalityconstrained DPPs. As an application, we show how our sampling algorithm can be used to provide a fast heuristic for determining the number of clusters, resulting in better clustering. There are some crucial errors in the proofs of the theorem which invalidate the theoretical claims of this paper. Please consult the appendix for more details.
This paper provides an efficient sampling algorithm 
      for DPPs. Though their algorithm is not explicitely better than the 
      standard sampling algorithm for DPPs, in practice their algorithm 
      outperforms the standard algorithm. They also consider real world and 
      synthetic applications involving clustering, there they use the DPPs to 
      give a hueristic for sampling. I thnk the application of Markov 
      chain mixing techniques to sampling DPPs is nice, and the faster sampling 
      algorithm could be useful in many applications. Overall the paper also 
      seems well written. However, I am not fully convinced on the 
      application of DPPs for clustering. Though DPPs seem to model diversity in 
      many real world applications, it is not intuitive that the DPPs are in 
      general a better model for clustering. Moreover, even using DPPs there are 
      no guarantees for clustering and the procedure seems hueristic. In that 
      context, it is not clear why the DPPs will necessarily offer a better 
      solution for clustering. I think this should be clarified better in the 
      paper. Also, are there some other applications where one might want to 
      sample from a DPP? A recent relevant paper at UAI this year, is 
      "Determinantal Clustering Processes - A Nonparametric Bayesian Approach to 
      Kernel Based Semi-Supervised Clustering". Though not exactly the same 
      problem, the paper is closely related to this one. * Edits after 
      the author rebuttal period and discussions I feel that the paper is 
      well written, though only incremental in my opinion. The main cons are 
      that the application of the sampling algorithm to k-means seems very 
      heuristic, and hence I will stick to my score of 6 (i.e borderline 
      accept). I think the paper can be significantly improved, if the authors 
      could point out some other applications of DPP sampling, where their 
      algorithms will imply significant improvement in running 
      time.