8
$\begingroup$

I have the following question:

Suppose I have two matrices $X, Y$ both of size $m\times p$ and a random i.i.d Gaussian matrix $G$ of size $m \times k$, $m\gg p>k$.

Is there a fast way to compute $\exp(-XY^T)G$? Perhaps by using the fact that both $X$ and $Y$ are much smaller than $XY^T$? Here, $\exp(\cdot)$ means entry-wise exponent (i.e. of $\textbf{each}$ entry of the matrix). Clearly, without the exponent, it's easy and can be done simply by $X(Y^TG)$, but the problem is that the element-wise exponent is no longer low rank.

The motivation for the question is multiplying a kernel of the form

$D_{ij}=\exp(-d_{ij})$ or $D_{ij}=\exp(-d_{ij}^2)$

with $d_{ij}=\Vert x_i-y_j \Vert$ and $x_i, y_i \in \mathbb{R}^p$ by a random matrix efficiently.

An approximated solution is also fine.

$\endgroup$
  • 5
    $\begingroup$ I find the question clear (I don't have any ideas myself unfortunately), but the fact that the exponential is component-wise I think is going to mislead a lot of people - $\exp(A)$ is a very standard notation for matrix exponential, especially in the theory of ODEs and PDEs. Could you maybe rephrase the title a bit? $\endgroup$ – Kirill Nov 16 '15 at 19:50
  • $\begingroup$ Define fast? Do you mean in a vectorized way without looping over the whole matrix $-XY^T$? $\endgroup$ – nluigi Nov 17 '15 at 17:24
  • $\begingroup$ Computational complexity lower than $\mathbb{O}(m^2k)$. $\endgroup$ – Gil Nov 17 '15 at 21:54
  • 1
    $\begingroup$ NIPS'16 paper that might be relevant papers.nips.cc/paper/6246-orthogonal-random-features $\endgroup$ – Memming Feb 21 '17 at 13:50
  • 1
    $\begingroup$ I looked into the paper, it is very helpful. Thanks! @Memming $\endgroup$ – Gil Feb 28 '17 at 12:15
1
$\begingroup$

If approximations suffice, maybe we could begin by developing the $\exp$ operator as follows: $$ \exp(Z) = \sum\limits_{k=0}^{\infty} \frac{Z^k}{k!} = 1+Z+\frac{Z^2}{2} + \frac{Z^3}{6} + \frac{Z^4}{24} + ... $$ Note that the power terms follow your element-wise notation and refer to the Hadamard powers, slightly abusing the standard conventions.

This gives possibilities for re-writing the expression: $$ \begin{align} \exp{(-XY^T)}G &= \Big(I-XY^T+\frac{(XY^T)^2}{2} - \frac{(XY^T)^3}{6} + \frac{(XY^T)^4}{24} - ...\Big)G \\ &=G-XY^TG+\frac{(XY^T)^2G}{2} - \frac{(XY^T)^3G}{6} + \frac{(XY^T)^4G}{24} - ... \end{align} $$ where $I$ is an appropriately sized identity matrix. If one could live with a first order approximations, then: $$ \begin{align} \exp{(-XY^T)}G &= G-XY^TG+ O(max(|XY^T|)^2)\\ &\approx G-XY^TG = G-X(Y^TG) \end{align} $$ resulting in an easier operation. For higher order approximations, you would like to work out the solution for the Hadamard power, which is probably a bit harder or I haven't seen an immediate solution yet.

$\endgroup$
  • $\begingroup$ Good idea. Small detail: that $O(n^2)$ should be something like $O((\|X\|\|Y\|)^2)$ instead. $\endgroup$ – Federico Poloni Dec 24 '17 at 9:47
  • $\begingroup$ @FedericoPoloni, I agree. If you could introduce a more appropriate notation than using the norms of matrices, I would be happy to update. $\endgroup$ – Tolga Birdal Dec 24 '17 at 10:03
  • $\begingroup$ Well, using norms looks appropriate enough to me, but if you prefer you can write it as $O(\max(|XY^T|)^2)$. $\endgroup$ – Federico Poloni Dec 24 '17 at 10:07
  • $\begingroup$ ok, updated it. $\endgroup$ – Tolga Birdal Dec 30 '17 at 10:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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