Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
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 '10 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 '10 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. –  user3035 Jan 14 '10 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. –  Loop Space Jan 14 '10 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 '10 at 21:39
add comment

2 Answers 2

up vote 0 down vote accepted

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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