Fast DPP Sampling for Nystr\"om with Application to Kernel Methods
  The Nystr\"om method has long been popular for scaling up kernel methods. Its
theoretical guarantees and empirical performance rely critically on the quality
of the landmarks selected. We study landmark selection for Nystr\"om using
Determinantal Point Processes (DPPs), discrete probability models that allow
tractable generation of diverse samples. We prove that landmarks selected via
DPPs guarantee bounds on approximation errors; subsequently, we analyze
implications for kernel ridge regression. Contrary to prior reservations due to
cubic complexity of DPPsampling, we show that (under certain conditions) Markov
chain DPP sampling requires only linear time in the size of the data. We
present several empirical results that support our theoretical analysis, and
demonstrate the superior performance of DPP-based landmark selection compared
with existing approaches.
