Nystrom Approximation for Large-Scale Determinantal Processes
Raja Hafiz Affandi, Alex Kulesza, Emily B. Fox, Ben Taskar

Citation
Raja Hafiz Affandi, Alex Kulesza, Emily B. Fox, Ben Taskar. "Nystrom Approximation for Large-Scale Determinantal Processes". AISTATS 2013, April, 2013.

Abstract
Determinantal point processes (DPPs) are appealing models for subset selection problems where diversity is desired. They offer surprisingly efficient inference, including sampling in O(N^3) time and O(N^2) space, where N is the number of base items. However, in some applications, N may grow so large that sampling from a DPP becomes computationally infeasible. This is especially true in settings where the DPP kernel matrix cannot be represented by a linear decomposition of low-dimensional feature vectors. In these cases, the PIs propose applying the Nystrom approximation to project the kernel matrix into a low-dimensional space. While theoretical guarantees for the Nystrom approximation in terms of standard matrix norms have been previously established, the PIs are concerned with probabilistic measures, like total variation distance between the DPP and its Nystrom approximation,that behave quite differently. In this paper the PIs derive new error bounds for the Nystrom-approximated DPP and present empirical results to corroborate them. The PIs then demonstrate the Nystrom-approximated DPP by applying it to a motion capture summarization task.

Electronic downloads

Internal. This publication has been marked by the author for TerraSwarm-only distribution, so electronic downloads are not available without logging in.

Citation formats

• HTML

  Raja Hafiz Affandi, Alex Kulesza, Emily B. Fox, Ben Taskar.
  <a
  href="http://www.terraswarm.org/pubs/53.html"
  >Nystrom Approximation for Large-Scale Determinantal
  Processes</a>, AISTATS 2013, April, 2013.

• Plain text

  Raja Hafiz Affandi, Alex Kulesza, Emily B. Fox, Ben Taskar.
  "Nystrom Approximation for Large-Scale Determinantal
  Processes". AISTATS 2013, April, 2013.

• BibTeX

  @inproceedings{AffandiKuleszaFoxTaskar13_NystromApproximationForLargeScaleDeterminantalProcesses,
      author = {Raja Hafiz Affandi and Alex Kulesza and Emily B.
                Fox and Ben Taskar},
      title = {Nystrom Approximation for Large-Scale
                Determinantal Processes},
      booktitle = {AISTATS 2013},
      month = {April},
      year = {2013},
      abstract = {Determinantal point processes (DPPs) are appealing
                models for subset selection problems where
                diversity is desired. They offer surprisingly
                efficient inference, including sampling in O(N^3)
                time and O(N^2) space, where N is the number of
                base items. However, in some applications, N may
                grow so large that sampling from a DPP becomes
                computationally infeasible. This is especially
                true in settings where the DPP kernel matrix
                cannot be represented by a linear decomposition of
                low-dimensional feature vectors. In these cases,
                the PIs propose applying the Nystrom approximation
                to project the kernel matrix into a
                low-dimensional space. While theoretical
                guarantees for the Nystrom approximation in terms
                of standard matrix norms have been previously
                established, the PIs are concerned with
                probabilistic measures, like total variation
                distance between the DPP and its Nystrom
                approximation,that behave quite differently. In
                this paper the PIs derive new error bounds for the
                Nystrom-approximated DPP and present empirical
                results to corroborate them. The PIs then
                demonstrate the Nystrom-approximated DPP by
                applying it to a motion capture summarization task.},
      URL = {http://terraswarm.org/pubs/53.html}
  }
  

Posted by Mila MacBain on 26 Apr 2013.