1
$\begingroup$

I am a CS student and currently trying to work on a paper. My math skills are not too good, please dont blame me for that :D

The paper constructs a kernel matrix $ K_t $ at time t that has the following design:

$K_t$ is a square kernel matrix. The vector $ \varphi $ represents the RBFs of a new point $x_n$, to all existing points in the matrix. ($ \varphi= (RBF(x_n, x_1),...,RBF(x_n, x_{n-1}))^T$ . K looks like:

$ K_{t} = \begin{bmatrix} K_{t-1} & \varphi\\ \varphi^T & 1 \end{bmatrix} $

This matrix $K_t$ gets decomposed into $K_t = V \Sigma V^T$ where V are the eigenvectors and $\Sigma$ are the eigenvalues put into a diagonal matrix. This is done to do calculations whether if a new data point is important or not. Therefore a recalculation of all eigenvectors has to be done every time a new data point arrives.

Therefore a low-rank update formula for the eigendecomposition is provided that does not really work for me and I dont know why:

$ K_t+\varphi\varphi^T = \left. \begin{matrix} \begin{bmatrix} V && \frac{p}{\left \| p \right \|} \end{bmatrix} \end{matrix} \right. {\Sigma}' { \begin{matrix} \begin{bmatrix} V && \frac{p}{\left \| p \right \|} \end{bmatrix} \end{matrix} }^T$

$p = (I-VV^T)\varphi$

$ \Sigma^{'} = \begin{matrix} \begin{bmatrix} \Sigma && V^T\varphi \\ \varphi^TV && \left \| p \right \| \end{bmatrix} \end{matrix}$

The formula at all is not too difficult, even if I can not understand the proof at the moment (should be from Brand, M. (2006), `Fast low-rank modications of the thin singular value decomposition', Linear Algebra and Its Applications).

The problem is, when I am trying to calculate this in an example, I do not get the expected result. To focus on the part $\begin{matrix} \begin{bmatrix} V && \frac{p}{\left \| p \right \|} \end{bmatrix} \end{matrix} $ which should give the new eigenvectors. This would imply that I have the old eigenvectors V and the new ones are that p part (which is a projection of $\varphi$ to the eigenspace?). But in my calculations of course the eigenvectors change completely when I add the vector $\varphi$ to the matrix K. Let me show what I mean:

The initialization of $K_2$ with two points gives:

$ K_{2} = \begin{bmatrix} 1 & 0.0173\\ 0.0173 & 1 \end{bmatrix} \\ $ The eigenvectors of this matrix $K_2$ are: $ V = \begin{bmatrix} 0.707 & -0.707 \\ 0.707 & 0.707 \end{bmatrix} $

Now if a new point $x_3$ arrives $K_3$ could look like: $ K_{3} = \begin{bmatrix} 1 & 0.0173 & 0.895 \\ 0.0173 & 1 & 0.053 \\ 0.895 & 0.053 & 1 \end{bmatrix} $

If the whole decomposition of $K_3$ (without using the update mechanism) is done, the top 2 eigenvectors should be: $V_{2} = \begin{bmatrix} 0.705 & 0.706 \\ 0.055 & 0.028 \\ 0.706 & -0.707 \end{bmatrix}$

The update formula gives something completely different. The mess starts with the p part where $VV^T$ gives the identity matrix. So identity matrix - identity matrix gives a zero matrix.

$ (I - \begin{bmatrix} 0.707 & -0.707 \\ 0.707 & 0.707 \end{bmatrix} * \begin{bmatrix} 0.707 & -0.707 \\ 0.707 & 0.707 \end{bmatrix}^T) = 0 $

Why is that? What I am doing wrong or misunderstanding?

The formula and complete problem comes from "Stream Clustering: efficient kernel-based approximation using importance sampling" by Radha Chitta, Jin & Jain 2016, where they try to cluster only important points in a data stream, based on statistical leverage scores. As the calculation of important points is done with the help of the eigendecomposition, the kernel matrix and its eigendecomposition have to be calculated every time a data point arrives. Therefore they wanted to have a fast way of updating the eigenvectors, which is the formula that I am referring to.

$\endgroup$
  • $\begingroup$ Hi there, if you clarify the details of what exactly your algorithm is supposed to do, maybe link to some papers with explanations, and write out more steps of your example, it might make people more willing and able to help you :) $\endgroup$ – user3658307 Jun 11 '17 at 1:17
  • $\begingroup$ Hi, thank you for your good hint. I tried to give a bit more information and updated some parts. It is really hard to break the problem down into the necessary parts without writing too much. $\endgroup$ – C. Clarke Jun 11 '17 at 18:15

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.