3
$\begingroup$

Let $x \in \mathbb{R}^n$ and $k$ is RBF kernel

$$k(x, x') := \exp \left(-\frac{\|x-x'\|^2}{2\sigma^2}\right)$$

and let $\mathbf{K}$ be the following $n \times n$ covariance matrix

$$\mathbf{K} = \begin{bmatrix} 1 & k(x_1, x_2) & \dots & k(x_1, x_n)\\ k(x_2, x_1) & 1 & \dots & k(x_2, x_n)\\ \vdots & \vdots & \ddots & \vdots \\ k(x_n, x_1) & k(x_n, x_2) & \dots & 1\\ \end{bmatrix}$$

In practice, the sum of the entries of matrix $\mathbf{K}^{-1}$ is small. How can I find the minimum upper bound for it?

Specifically, when $\mathbf{1} = [1, ... , 1] \in \mathbb{R}^n$, I am looking for $M$ such that

$$\mathbf{1} \mathbf{K}^{-1} \mathbf{1}^{T} \leq M$$

Note: A similar question has been asked here, but unfortunately it is not answered. Moreover, another similar question has been asked here, but the value of the entries are not determined.

Thank you in advance for your help!

$\endgroup$
7
  • 1
    $\begingroup$ What's known for $n=2$ or $n=3$? $\endgroup$ Sep 2, 2021 at 21:05
  • $\begingroup$ @LevBorisov $n$ is a finite number. Let's say $n=1000$ $\endgroup$ Sep 3, 2021 at 12:32
  • $\begingroup$ and you want the bound to be uniform over $x\in \mathbb{R}^n$? $\endgroup$ Sep 6, 2021 at 9:33
  • $\begingroup$ @FedorPetrov If you are talking about $M$. I think it is obvious that $M \in \mathbb{R}$. Because the left side ($\mathbf{1} \mathbf{K}^{-1} \mathbf{1}^{T}$) is a read number $\endgroup$ Sep 6, 2021 at 14:51
  • $\begingroup$ I mean, should the same real constant $M$ work for all $n$ and all $x_1,\ldots,x_n$? $\endgroup$ Sep 6, 2021 at 15:15

1 Answer 1

0
$\begingroup$

I am writing here some tests I did. I wait it is useful.

Note that $$\mathbf{1}^T \mathbf{K}^{-1} \mathbf{1} =(\mathbf{K}^{-1} \mathbf{1})^T\mathbf{K}(\mathbf{K}^{-1} \mathbf{1})=\mathbf{y}^T\mathbf{K}\mathbf{y}=\|\mathbf{K}^{\frac{1}{2}}\mathbf{y}\|^2=\sum_{i=1}^ny_i=\mathbf{y}^T\mathbf{1}\leq n\|\mathbf{y}\|,$$ in which $\mathbf{1}$ is written as a column, $\mathbf{K}\mathbf{y}=\mathbf{1}$ and $\mathbf{K}^{\frac{1}{2}}$ is the positive square root of $\mathbf{K}.$ It follows that $$\|\mathbf{K}^{\frac{1}{2}}\mathbf{y}\|^2=\|\mathbf{K}^{-\frac{1}{2}}\mathbf{1}\|^2\leq \|\mathbf{K}^{-\frac{1}{2}}\|^2\|\mathbf{1}\|^2=n\|\mathbf{K}^{-\frac{1}{2}}\|^2=n\frac{1}{\lambda_{min}(\mathbf{K})}.$$

You can see the equality $\mathbf{K}\mathbf{y}=\mathbf{1}$ as an interpolation problem $$g(x_j)=1, \qquad j=1,\,2,\,\ldots,\,n,$$ to find the function $$g(x)=\sum_{i=1}^ny_iK(x_i,x),$$ in the reproducing kernel space $\mathcal{H}_K$. It follows that (please see equation (10) in this text) $$1=g(x_j)=\langle g,K(x_j,\cdot)\rangle\leq \|g\|\|K(x_j,\cdot)\|=\left(\mathbf{y}^T\mathbf{K}\mathbf{y}\right)\sqrt{K(x_j,x_j)}.$$

You can find more results on reproducing kernels searching for "\(g(x)=\langle g,K^x\rangle \) " on SearchOnMath, for instance.

Remark: If you have some bound on $\min_{i\neq j}|x_i-x_j|$ then Gershgorin circle theorem can helps.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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