What is the inverse of the covariance matrix generated by the exponential covariance function? I'm trying to analytically find the inverse of the covariance matrix generated by the exponential covariance function (also known as Ornstein-Uhlenbeck kernel) in $\mathbb{R}$, that is
$K_{ij} = k(x_i, x_j) = \exp(-\frac{|x_i - x_j|}{\theta})$
Where $x_i \in \mathbb{R}$ and that $K$ is an $n\times n$ matrix.
Here is what I've thought about doing:
Since $K$ is a covariance matrix, I know it is positive semidefinite and so is $K^{-1}$. We can do a singular value decomposition on $K = UDU^*$ and $K^{-1} = VCV^*$ where $U, V$ are unitary matrices and $D, C$ are diagonal matrices.
But that I haven't been able to develop the idea further.
What would be right approach to get an analytical expression for $K^{-1}$?
 A: I'll keep a $\sigma$ out front for completeness. Okay so assume $C(x,x') = \sigma^2 \exp(-|x-x'|/T)$, and $x \in \mathbb{R}$. (a more complicated but similar approach works for $x \in \mathbb{R}^n$ too)
The kernel associates a function $\hat{e}(x')$  with $e(x)$ via,
1) $e(x) = \int_{x_1}^{x_2} dx' C(x,x')\hat{e}(x')$.
Notice, if $\phi(x) = \sigma^2 \exp(-|x|/T)$ then two things:
2) $\partial_x \phi(x) = -\frac{1}{T}sign(x)\phi(x)$ and
3) $\partial_x^2 \phi(x) = -\frac{1}{T^2}\phi(x) - \frac{2\sigma^2}{T}\delta(x)$
therefore plugging this in,
4) $\partial_x e(x) = \frac{1}{-T}\int_{x_1}^{x_2} dx' sign(x-x')C(x,x')\hat{e}(x')$
and,
5) $\partial_x^2 e(x) = \frac{1}{T^2} - \frac{2 \sigma^2}{T} \hat{e}(x)$
using 1) and 4) shows that at $x=x_1$ and $x = x_2$ that $\partial_x e(x)$ and $e(x)$ are not independent.
6) $\partial_x e(x_1) = \frac{1}{T} e(x_1)$ and likewise for $x_2$. 
Eq 5) then gives,
7) $\hat{e}(x) = \frac{1}{2\sigma^2 T} e(x) - \frac{T}{2\sigma^2} \partial_x^2 e(x)$
$C^{-1}(x,x')$ has domain of definition thus satifying relations 6) and accosiates via eq 7). Taking the integral representation,
8) $\hat{e}(x) = \int_{x_1}^{x_2} dx' C^{-1}(x,x')e(x')$
it then follows that,
$C^{-1}(x,x') = \frac{1}{2\sigma} (\frac{1}{T} \delta(x-x') - T \delta^{(2)}(x-x'))$
where we use $\int dx' \delta^{(n)}(x') f(x') = (-1)^n \partial_x^n f(x)$.
A: We first write the kernel in the following form: 
$$exp(-||x-y||)=exp(\min\{x,y\})exp(-\max\{x,y\})=:p(\min\{x,y\})q(\max\{x,y\})$$
Then the inverse matrix is a symmetric tridiagonal matrix with entries:
$$[K^{-1}]_{i,i}=\frac{p(x_{i+1})q(x_{i-1})-p(x_{i-1})q(x_{i+1})}{[p(x_{i+1})q(x_{i})-p(x_{i})q(x_{i+1})][p(x_{i})q(x_{i-1})-p(x_{i-1})q(x_{i})]} $$
$$[K^{-1}]_{i,i-1}=[K^{-1}]_{i-1,i}=\frac{-1}{p(x_{i})q(x_{i-1})-p(x_{i-1})q(x_{i})} $$
which is  easier and more general.
you can refer to the following paper for details: https://ldingaa.github.io/files/ScalableSK.pdf
