# Orthonormal bases on Reproducing Kernel Hilbert Spaces

Recall that a Hilbert space $\mathcal{H}$ is a reproducing kernel Hilbert space (RKHS) if the elements of $\mathcal{H}$ are functions on a certain set $X$ and for any $a\in X$, the linear functional $f\mapsto f(a)$ is bounded on $\mathcal{H}$. By Riesz Representation Theorem, there exists an element $K_a\in\mathcal{H}$ such that $$f(a) = \langle f, K_a\rangle\ \text{ for all } \ f\in\mathcal{H}.$$ The function $K(x,y) = K_y(x) = \langle K_y, K_x\rangle$ defined on $X\times X$ is called the reproducing kernel function of $\mathcal{H}$.

It is well known and easy to show that for any orthonormal basis $\{e_m\}_{m=1}^{\infty}$ for $\mathcal{H}$, we have the formula $$K(x,y) = \sum_{m=1}^{\infty}e_m(x)\overline{e_m(y)},\tag{Eqn 1}$$ where the convergence is pointwise on $X\times X$.

My question concerns the converse of the above statement.

Question: if $\{g_m\}_{m=1}^{\infty}$ is a sequence of functions in $\mathcal{H}$ such that $$K(x,y) = \sum_{m=1}^{\infty}g_m(x)\overline{g_m(y)}\tag{Eqn 2}$$ for all $x,y\in X$. Is the sequence $\{g_m\}_{m=1}^{\infty}$ an orthonormal basis for $\mathcal{H}$?

The answer to this question is clearly negative since equation (Eqn 1) can be re-written as $$K(x,y) = \frac{e_1(x)}{\sqrt{2}}\overline{\frac{e_1(y)}{\sqrt{2}}}+\frac{e_1(x)}{\sqrt{2}}\overline{\frac{e_1(y)}{\sqrt{2}}}+\sum_{m=2}^{\infty}e_m(x)\overline{e_m(y)}$$ and clearly $\{e_1/\sqrt{2}, e_1/\sqrt{2}, e_2, \ldots\}$ is not an orthonormal basis for $\mathcal{H}$. So the following additional condition should be added: the sequence $\{g_m\}_{m=1}^{\infty}$ is linearly independent.

The following proof suggests that the answer is affirmative. (For those who are familiar with the proof of the Moore-Aronszajn's Theorem in the theory of RKHS, the proof here looks similar.) Assume that we have (Eqn 2) and the sequence $\{g_m\}_{m=1}^{\infty}$ is linearly independent. Let $\mathcal M$ be the linear space spanned by the functions $\{g_m\}_{m=1}^{\infty}$. Define a sesquilinear form on $\mathcal M$ as \begin{align*} \left\langle\sum_{\text{finite sum}}a_jg_j, \sum_{\text{finite sum}}b_kg_k\right\rangle_{\mathcal M} = \sum_{\text{finite sum}} a_j\overline{b}_j. \end{align*} Since $\{g_m\}_{m=1}^{\infty}$ is a linearly independent set, the above definition is well-defined. Note that $\{g_m\}_{m=1}^{\infty}$ is an orthonormal set in $\langle,\rangle_{\mathcal M}$. For any $f\in\mathcal M$ and $x\in X$, we have \begin{align*} f(x) = \sum_{\text{finite sum}}\langle f,g_m\rangle_{\mathcal M}\,g_m(x). \end{align*} Cauchy-Schwarz's inequality gives \begin{align*} |f(x)| & \leq \Big(\sum_{\text{finite sum}}|\langle f,g_m\rangle_{\mathcal M}|^2\Big)^{1/2}\Big(\sum_{\text{finite sum}}|g_m(x)|^2\Big)^{1/2} \leq \|f\|_{\mathcal M}\sqrt{K(x,x)}. \end{align*} Let $\widetilde{\mathcal M}$ be the Hilbert space completion of $\mathcal M$. The standard argument shows that $\widetilde{\mathcal M}$ is a RKHS of functions on $X$. What is the kernel of $\widetilde{\mathcal M}$? Since $\{g_m\}_{m=1}^{\infty}$ is an orthonormal set and its span is dense in $\widetilde{\mathcal M}$, it is an orthonormal basis for $\widetilde{\mathcal M}$. The kernel of $\widetilde{\mathcal M}$ then can be computed as $$\sum_{m=1}^{\infty}g_m(x)\bar{g}_m(y),$$ which is the same as $K(x,y)$. Therefore, $\widetilde{\mathcal M}$ is the same as $\mathcal H$ (they consist of the same functions and the inner products on the two spaces are equal). Consequently, $\{g_m\}_{m=1}^{\infty}$ is an orthonormal basis for $\mathcal{H}$. This completes the proof.

Counterexample: On the other hand, there are counterexamples that provide a negative answer to the question in the infinite dimensional case.

What part of the above proof is incorrect? I have checked but could not figure out what went wrong.

Thank you.

• Could you describe briefly one of these counterexamples? – Chris Ramsey Jan 23 '16 at 19:43
• @ChrisRamsey: Together with Theorem 3.12 in Vern Paulsen's lecture note at www.math.uh.edu/~vern/rkhs.pdf, if the conclusion were correct, then any linearly independent Parseval frame would be an orthonormal basis. However this seems to be incorrect. For example, take E to be the orthogonal complement of v = (1, 1/2, 1/3, ...) in l^2 and take g_m = P(e_m), where P is the orthogonal projection onto E. Then {g_m} is a linearly independent Parseval frame for E but it is not an orthonormal basis. – T. Le Jan 23 '16 at 19:59
• This sentence worries me: "The standard argument shows that $\widetilde{\mathcal{M}}$ is a RKHS of functions on $X$". Can you look at that more carefully? I am not convinced that the completion $\widetilde{\mathcal{M}}$ can be identified with a space of functions on $X$. You have shown that the map $f \mapsto f(x)$ is continuous with respect to the $\mathcal{M}$ norm, so this map extends to the completion, and every element $\tilde{f}$ of the completion is associated with a well-defined function on $X$. But I do not see why this association has to be 1-1. – Nate Eldredge Jan 23 '16 at 20:38
• By "standard argument", I meant the usual argument that one might find when proving that any positive definite kernel K(x,y) gives rise to an RKHS whose kernel is K(x,y) (Moore-Aronszajn Theorem). Such argument can be found in Vern Paulsen's note, page 14, at www.math.uh.edu/~vern/rkhs.pdf or in the proof of Theorem 2.23 on page 19 in Agler-McCarthy's book "Pick Interpolation and Hilbert Function Spaces". @NateEldredge: can you explain what you mean and why you need the association to be 1-1 for $\widetilde{\mathcal{M}}$ to be RKHS? – T. Le Jan 23 '16 at 23:02
• @NateEldredge: I think you are right! I was unable to verify that the map from $\widetilde{\mathcal{M}}$ to $\mathbb{R}^{X}$ (or $\mathbb{C}^{X}$ for the complex case) is injective. In other words, if $h\in\widetilde{\mathcal{M}}$ and $h(x)=0$ for all $x\in X$, then it cannot be verified that $\|h\|=0$ (in fact, this may not be true). On the other hand, in the "standard proofs" of Moore-Aronszajn Theorem, injectivity can be verified (even though in all the proofs that I know of, it was not mentioned or verified!!). Could you please put part of your comments in an answer so I can vote for it? – T. Le Jan 24 '16 at 1:13

The error is in this line:

The standard argument shows that $\widetilde{\mathcal{M}}$ is an RKHS of functions on $X$.

In fact, this is not generally true. The completion $\widetilde{\mathcal{M}}$ may not be naturally identified with a space of functions on $X$.

The "obvious" way that one would try to prove this is as follows. Consider an element $\phi \in \widetilde{\mathcal{M}}$. Since $\mathcal{M}$ is dense in its completion, there is a sequence $\{f_n\} \subset \mathcal{M}$ such that $f_n \to \phi$ in $\widetilde{\mathcal{M}}$-norm, which is an extension of the $\mathcal{M}$-norm. In particular, $\{f_n\}$ is $\mathcal{M}$-norm Cauchy. Because of your inequality $|f(x)| \le \|f\|_{\mathcal{M}} \sqrt{K(x,x)}$ (*), we have that $\{f_n(x)\}$ is Cauchy in $\mathbb{R}$ for each $x$. So $\{f_n(x)\}$ converges to a number which we may call $f_\phi(x)$; that is, $f_n \to f_\phi$ pointwise. It is also easy to show that $f_{\phi}$ does not depend on the choice of sequence $f_n \to \phi$, so the linear map $\phi \mapsto f_\phi$ of $\widetilde{\mathcal{M}}$ into $\mathbb{R}^X$ is well defined. Let's call this map $T$.

So the "obvious" thing to do is to look at the image of $T$, which is of course a function space, and make it a Hilbert space by pushing forward the $\widetilde{\mathcal{M}}$-norm. If this works, then the same inequality (*) will show that the evaluation map is continuous in this norm, and we have ourselves an RKHS.

The problem is that $T$ might fail to be injective. In other words, we could have a nonzero $\phi$ for which $f_\phi = 0$. In that case, pushing forward the norm will not work; it will not be well defined on the image of $T$.

This is exactly what happens in the counterexample you discuss in the comments. As you suggest, consider $\ell^2$ as an RKHS on $X = \mathbb{N} = \{1,2,\dots\}$, with its usual orthonormal basis $\{e_n\}$, and let $v = \sum_n \frac{1}{n} e_n$. Let $H = \{v\}^\perp$ with the same $\ell^2$ inner product; being a closed subspace of $\ell^2$, $H$ is an RKHS.

Let $P : \ell^2 \to H$ be the orthogonal projection and let $g_n = P e_n$. The $g_n$ are linearly independent; if $0 = a_1 g_1 + \dots + a_n g_n = P(a_1 e_1 + \dots + a_n e_n)$ then $a_1 e_1 + \dots + a_n e_n$ is a scalar multiple of $v$, which is only possible if all $a_i$ are 0.

Following your construction, let $\mathcal{M} \subset H$ be the linear span of $\{g_n\}$ and let $\langle\cdot, \cdot\rangle_{\mathcal{M}}$ be the inner product on $\mathcal{M}$ which makes the $\{g_n\}$ orthonormal.

Set $h_m = \sum_{n=1}^m \frac{1}{n} g_n$. Clearly the sequence $\{h_m\}$ is Cauchy in $\mathcal{M}$, so it converges in the completion $\widetilde{\mathcal{M}}$ to some $\phi$. It is also clear that $\|\phi\|_\widetilde{\mathcal{M}}^2 = \frac{\pi^2}{6}$ so in particular $\phi \ne 0$.

But on the other hand, we have $h_m = \sum_{n=1}^m \frac{1}{n} P e_n = P\left(\sum_{n=1}^m \frac{1}{n} e_n\right)$. By continuity of $P$, we have $h_m \to Pv = 0$ in $\ell^2$, and thus also pointwise. So $f_\phi = 0$.

This is basically an example of a somewhat paradoxical fact that's bitten me before. Let $X,Y$ be Banach spaces, and suppose $E \subset X$ is dense. It's well known that every bounded operator $T : E \to Y$ has a unique bounded extension $\tilde{T} : X \to Y$. But it's possible that $T$ is injective while $\tilde{T}$ is not. Indeed, we've just constructed an example, by letting $E = \mathcal{M}$, $X = \widetilde{\mathcal{M}}$, $Y = \ell^2$, and $T : E \to Y$ the inclusion map.

• Nice answer. Just a remark related to your last point: we get particularly striking examples if X is the full group Cstar algebra of a non-amenable discrete group (like $F_2$), E is the dense subalgebra generated by point masses, and Y is the reduced group Cstar algebra. Then the "identity map" from E to Y is continuous and injective with dense range, but the unique continuous extension to a map $X \to Y$ is not injective – Yemon Choi Jan 24 '16 at 3:25
• Thank you for your answer! On the other hand, I believe that the map $T$ is injective and hence the Question has an affirmative answer if we assume a stronger condition than just linear independence: for any sequence $\{c_m\}$ in $\ell^2$, if $\sum_{m=1}^{\infty}c_mg_m(x) = 0$ for all $x\in X$, then $c_1=c_2=\cdots = 0$ (note that the convergence of the series is automatic by Cauchy-Schwarz's inequality). I think there is a name for this condition but I'm not sure what it is. – T. Le Jan 24 '16 at 3:46
• @T.Le: Yes, that's true, because the map $S : \ell^2 \to \widetilde{\mathcal{M}}$ which maps $\{c_m\}$ to $\sum_m c_m g_m$ is an isometric isomorphism. Your condition is that $TS$ is injective, which means that $T$ must be as well. – Nate Eldredge Jan 24 '16 at 3:59