If $A,B$ are arbitrary $ntimes n$ matrices, by definition of trace, $textrm{tr}(AB) = sum_{i,j} A_{ij}B_{ji}$. This is $O(n^2)$, but just reading the entries of $A$ is $Omega(n^2)$. Without any special structure on $A,B$, you probably can't do better.
If $A,B$ are (column) vectors, you probably mean the outer product $textrm{tr}(AB^T) = sum_i A_i B_i$.
Edit: andinos clarified to say he wants to know about the implicit mapping of the kernel function. Well I have bad news: It does not exist!! The proof works by showing there exist matrices $A,B$ such that the corresponding kernel matrix is not positive semi-definite. To finish, apply Mercer's theorem.
In particular, set $A = left(begin{array}{cc}1 & 1 \\ -1 & 1end{array}right)$ and $B = A^T = left(begin{array}{cc}1 & -1 \\ 1 & 1end{array}right)$. Therefore $textrm{tr}(AB) = textrm{tr}(AA^T) = 4$, and $textrm{tr}(BA)$ is identical. On the other hand, $textrm{tr}(AA) = textrm{tr}(BB) = 0$. therefore, the kernel matrix $K$ is $left(begin{array}{cc}0 & 4 \\ 4 & 0end{array}right)$. Set $x = left(begin{array}{c} 1 \\ -1end{array}right)$, and observe that $x^T K x = -8 < 0$, and therefore $K$ is not PSD, so the kernel $k(A,B) = textrm{tr}(AB)$ is not PSD.
On the other hand! If you had instead defined your kernel to be $k'(A,B) = textrm{tr}(AB^T)$, notice that $k'(A,B) = sum_{i,j}A_{ij}B_{ij} = Phi(A)^TPhi(B)$ where $Phi$ simply takes its input matrix and outputs it as a column vector.
No comments:
Post a Comment