# Minimum upper bound for sum of the entries of the inverse covariance matrix

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.

• What's known for $n=2$ or $n=3$? Sep 2, 2021 at 21:05
• @LevBorisov $n$ is a finite number. Let's say $n=1000$ Sep 3, 2021 at 12:32
• and you want the bound to be uniform over $x\in \mathbb{R}^n$? Sep 6, 2021 at 9:33
• @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 Sep 6, 2021 at 14:51
• I mean, should the same real constant $M$ work for all $n$ and all $x_1,\ldots,x_n$? Sep 6, 2021 at 15:15

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.