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!

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ What's known for $n=2$ or $n=3$? $\endgroup$
    – Lev Borisov
    Commented Sep 2, 2021 at 21:05
  • $\begingroup$ @LevBorisov $n$ is a finite number. Let's say $n=1000$ $\endgroup$
    – Maryam Bahrami
    Commented Sep 3, 2021 at 12:32
  • $\begingroup$ and you want the bound to be uniform over $x\in \mathbb{R}^n$? $\endgroup$
    – Fedor Petrov
    Commented 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$
    – Maryam Bahrami
    Commented Sep 6, 2021 at 14:51
  • 1
    $\begingroup$ You probably need some hypothesis on the xi, e.g., (a) bounded (something like ||x|| = 1) and (b) deterministic (for example, if the xi are all equal, the matrix K has no inverse). The reason for the bounded condition is that if you take, for example $x_1 = N, x_2 = N^2$, etc., your K is close to the identity and the sum is close to n... $\endgroup$
    – Derek
    Commented Mar 25, 2022 at 14:01

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .