2
$\begingroup$

Suppose you have two PSD kernels $k(x,y)$ and $k'(x,y)$. Let $\mathcal{H}_k(\mathcal{D})$ and $\mathcal{H}_{k'}(\mathcal{D})$ be the corresponding RKHS's.

Now, if we know that for all $f \in \mathcal{H}_k(\mathcal{D})$ if $||f||_{k'}$ is bounded (here $||.||_k$ denotes the norm w.r.t kernel $k$), then $\mathcal{H}_{k'}(\mathcal{D}) = \mathcal{H}_k(\mathcal{D})$.

However, now suppose $k'(x,y)$ is created from a randomized algorithm and we can prove that with probability $1 - \delta$, $(1 - \epsilon) k(x,y) \leq k'(x,y) \leq (1 + \epsilon) k(x,y)$ for all $x,y$, for a fixed $\epsilon$.

In this case, can we conclude that with probability $1 - \delta$, $\mathcal{H}_{k'}(\mathcal{D}) = \mathcal{H}_k(\mathcal{D})$. I am not even sure whether such a statement is theoretically sound.

$\endgroup$
2
$\begingroup$

If I understand your question correctly, you are asking if $k'\le ck$ for a constant $c\ge1$ implies that $\mathcal{H}_{k'}\subset \mathcal{H}_{k}$. Now Theorem 3.11 in V.I. Paulsen, M. Raghupathi, An Introduction to the Theory of RKHS, Cambidge Univ. Press 2016 says the following: $f\in \mathcal{H}_{k'}$ with norm $\le1$ iff $(x,y)\mapsto k'(x,y) - f(x)\overline{f(y)}$ is a kernel function. I think this implies the claim.

If your set of inequalities holds for $k'=k'_\omega$ for $\omega $ in a measurable subset of the underlying probability space of probability $\ge 1-\delta$, then on this subset $\mathcal{H}_{k'_\omega} = \mathcal{H}_{k}$. In this sense the equality of RHKS (which might or might not be an event) occurs with probability $\ge 1-\delta$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.