Welcome to MathOverflow

Question

0

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()$?

flag	asked Jan 14 2010 at 9:13 andinos 3●1

3

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. – Darsh Ranjan Jan 14 2010 at 9:25

@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'. – Matus Telgarsky Jan 14 2010 at 9:34

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. – sheldon-cooper Jan 14 2010 at 10:02

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. – Andrew Stacey Jan 14 2010 at 10:20

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. – andinos Jan 14 2010 at 21:39

deneme · Accepted Answer · 2010-01-15 21:29:42Z UTC

0

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)$.

answered Jan 15 2010 at 21:29

deneme
16

Matus Telgarsky · Answer 2 · 2010-01-15 10:40:23Z UTC

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.

Get rid of tr() in SVM kernel trick

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

2 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.