1
$\begingroup$

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
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.