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

Question

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!

Answer 1

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.