For $X$ be a nonempty set, a function $f :X\times X\to\mathbb R$ is called a kernel on $X$ if for all $m\in \mathbb N$ and all $x_1,\cdots,x_m \in X$ $$K_f\equiv\begin{bmatrix} f(x_1,x_1) & \cdots & f(x_1,x_m) \\ \vdots & \ddots & \vdots \\ f(x_m,x_1) & \cdots & f(x_m,x_m) \end{bmatrix}$$ is symmetric positive semi-definite, i.e $$\forall v\in \mathbb R^m, v^TK_fv\ge0$$
I want to prove that $f_n\equiv\frac{1}{\sum_{i=1}^n max(u_i,v_i)}$ is a kernel on $\mathbb {R^+}^n$, so all I need to prove is the correctness for $n=2$. That is,
Prove or disprove that, given $x^{(1)},\cdots,x^{(m)}\in\mathbb R^{+^2}$, $K_{f_2}\in\mathbb R^{m\times m}$ defined by $$[K_{f_2}]_{i,j}\equiv \frac{1}{max(x^{(i)}_1,x^{(j)}_1)+max(x^{(i)}_2,x^{(j)}_2)}$$ is symmetric positive semi-definite.
For $n=1$ we can prove it by using Sylvester's criterion and the fact that swapping rows/columns doesn't change the determinant.
But extending $n$ from $1$ to $2$ I spent a lot of time, all I can get is the result that $g_n\equiv\sum_{i=1}^n\frac{1}{max(u_i,v_i)}$ is a kernel as SPSD+SPSD is also SPSD. Unfortunately, this result is not useful as I attempted to prove $v^TK_fv \ge v^TK_gv \ge 0$ but it is not the case.
On the other hand, I was trying to prove that $\frac{1}{1/k_1+1/k_2}$ is a kernel if $k_1$ and $k_2$ are kernels where $$\frac{1}{1/k_1+1/k_2}(u,v)\equiv \frac{1}{1/k_1(u,v)+1/k_2(u,v)}$$but it turns out that I can neither prove that nor give a counter example.
Any ideas?
I need to tell that I don't know if the statement is correct, it's a part of my research. So any counter example would be very welcome. I believe it as I tried some simulate on Matlab so I post it below. Hope it would help anyone interested.
t = 0;
while t < 10000
fnum = randi(100)+1;
dnum = randi(100)+1;
X = rand(dnum, fnum);
C = kernelMatrix(X);
checkSPSD(C);
t = t+1;
end
function matrix = kernelMatrix(X)
[row, ~] = size(X);
matrix = zeros(row);
for i = 1:row
for j = 1:row
matrix(i, j) = maxinv(func, X(i, 1:end), X(j, 1:end));
end
end
end
function value = maxinv(u,v)
[d,~] = size(u);
value = 0;
for k = 1:d
value = value + max(u(k),v(k));
end
value = 1/value;
end
function checkSPSD(X)
if X ~= X'
error('not sysmetric');
end
es = eig(X);
[d , ~] = size(es);
for i = 1:d
if es(i) < -1e-6
error('not PSD');
end
end
end