  In this paper, we attempt to solve a long-lasting open question for
non-positive definite (non-PD) kernels in machine learning community: can a
given non-PD kernel be decomposed into the difference of two PD kernels (termed
as positive decomposition)? We cast this question as a distribution view by
introducing the \emph{signed measure}, which transforms positive decomposition
to measure decomposition: a series of non-PD kernels can be associated with the
linear combination of specific finite Borel measures. In this manner, our
distribution-based framework provides a sufficient and necessary condition to
answer this open question. Specifically, this solution is also computationally
implementable in practice to scale non-PD kernels in large sample cases, which
allows us to devise the first random features algorithm to obtain an unbiased
estimator. Experimental results on several benchmark datasets verify the
effectiveness of our algorithm over the existing methods.
