0
$\begingroup$

I designed a kernel function (to be used within SVM) which has the expression $tr(AB)$ in it. For efficient implementation of this, I was wondering if I could write $tr(AB)$ as an inner product: $\phi(A)^T \phi(B)$? What is the function $\phi()$?

$\endgroup$
5
  • 3
    $\begingroup$ I'm not sure I understand your question (it would help if you eliminated or explained your jargon), but the obvious optimization is that you don't explicitly need to compute AB: tr(AB) is the sum of A_{ij}*B_{ji} over all pairs i,j. You can do this with a single pass over your matrices. $\endgroup$ Jan 14, 2010 at 9:25
  • $\begingroup$ @darsh you beat me by 3 minutes! I can explain some of the terminology. Imagine you have data in $\mathbb{R}^d$ (here it seems to be in $\mathbb{R}^{d\times d}$??) but want to work with it in $\mathbb{R}^D$, which you can accomplish by passing everything through a mapping $\Phi$. If $D \gg d$, this can be expensive. But in some cases your algorithm need only compute inner products $\langle \Phi(a), \Phi(b)\rangle$, in which case there may be a functin $k(\cdot,\cdot)$ which computes the same thing but with much less work than the explicit mapping. this is called the 'kernel trick'. $\endgroup$ Jan 14, 2010 at 9:34
  • $\begingroup$ Note that you don't really need the explicit mapping $\phi$. What you want is a kernel $k(A, B)$ which has the property that $k(A, B) = \phi(A)^T \phi(B)$. Generally, you compute the kernel directly, instead of calculating the mapping and computing the dot product -- that's why it's called kernel `trick'. In your case, it seems you want the kernel to be $k(A, B) = tr(AB)$. So it seems you want to know how to compute the trace efficiently, rather than what the mapping is. $\endgroup$
    – user3035
    Jan 14, 2010 at 10:02
  • $\begingroup$ The non-efficiency-related part of this question is basic linear algebra: tr(AB) is an inner product on the space of nxn matrices and so you can find isometric isomorphisms from M_{nxn} to R^{n^2}. Any of these will do for the map phi. I do not know whether or not any of these will improve the efficiency in calculating the trace, but I doubt it. $\endgroup$ Jan 14, 2010 at 10:20
  • $\begingroup$ Sorry for being ambiguous. I know that I can implement $k(A,B)$ directly and avoid needing $\phi()$. But it would be nice if I have $\phi()$ because then, I can use a regular linear SVM on my $\phi()$ mapped vectors. This is much simpler and faster compared to implementing $k(A,B)$ and plugging it into SVM. $\endgroup$
    – andinos
    Jan 14, 2010 at 21:39

2 Answers 2

0
$\begingroup$

Matus is right. But if the matrices $A$, and $B$ have certain properties like being symmetric, or diagonal, then simply just vectorizing the matrices and taking their inner product would be equal to the $tr(AB)$.

$\endgroup$
2
$\begingroup$

If $A,B$ are arbitrary $n\times 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 & 1\end{array}\right)$ and $B = A^T = \left(\begin{array}{cc}1 & -1 \\\\ 1 & 1\end{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 & 0\end{array}\right)$. Set $x = \left(\begin{array}{c} 1 \\\\ -1\end{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)^T\Phi(B)$ where $\Phi$ simply takes its input matrix and outputs it as a column vector.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.