  Determinantal point processes (DPPs) have attracted significant attention in
machine learning for their ability to model subsets drawn from a large item
collection. Recent work shows that nonsymmetric DPP (NDPP) kernels have
significant advantages over symmetric kernels in terms of modeling power and
predictive performance. However, for an item collection of size $M$, existing
NDPP learning and inference algorithms require memory quadratic in $M$ and
runtime cubic (for learning) or quadratic (for inference) in $M$, making them
impractical for many typical subset selection tasks. In this work, we develop a
learning algorithm with space and time requirements linear in $M$ by
introducing a new NDPP kernel decomposition. We also derive a linear-complexity
NDPP maximum a posteriori (MAP) inference algorithm that applies not only to
our new kernel but also to that of prior work. Through evaluation on real-world
datasets, we show that our algorithms scale significantly better, and can match
the predictive performance of prior work.
