Kernels and Fourier Transform

[Manzil Zaheer]

In one of the slides you have mentioned, "Simple trick for checking Mercer’s condition: Compute the Fourier transform of the kernel and check that it is nonnegative". I have some questions:

1. With respect to which variable do we take fourier transform? I guess x, anyways it should not matter as its symmetric

2. How do we prove this?

3. Infact how do you even guarantee it is real in the first place so that an order is defined? For functions having symmetry its fine like the Laplacian or Gaussian RBF, but for example in case of linear kernel, the Fourier transform is imaginary at origin

[Manzil Zaheer]

Kindly help and guide me, as I seem to be lost.

[Krikamol Muandet]

Hi Manzil,

Some of my answers below. As I am not an expert, please correct me if I am wrong.

On 11 February 2013 22:34, Manzil Zaheer <manzil...@gmail.com> wrote:

Kindly help and guide me, as I seem to be lost.

On Monday, February 11, 2013 4:32:01 PM UTC-5, Manzil Zaheer wrote:

In one of the slides you have mentioned, "Simple trick for checking Mercer’s condition: Compute the Fourier transform of the kernel and check that it is nonnegative". I have some questions:

1. With respect to which variable do we take fourier transform? I guess x, anyways it should not matter as its symmetric

I guess this trick works only for translation-invariant kernels, i.e., k(x,y) = g(x-y) for some positive semidefinite function g. In which case, there is only one variable, i.e., x-y, and you should take fourier transform with respect to this variable. I think there is also a way to check this for other types of kernels such as dot product kernels, e.g., k(x,y) = g(x^T. y), but I believe things get more complicate.

 

2. How do we prove this?

What do you mean by this?

 

3. Infact how do you even guarantee it is real in the first place so that an order is defined? For functions having symmetry its fine like the Laplacian or Gaussian RBF, but for example in case of linear kernel, the Fourier transform is imaginary at origin

If I understand correctly, you get a Fourier transform, which is a real-valued function, whose domain can be complex. So in principle you should be able to check non-negativity of the function.

Btw, I don't think you need to do a Fourior transform to prove that a linear kernel satisfies Mercer condition.

 

Krik

--
http://alex.smola.org/teaching/cmu2013-10-701 (course website)
http://www.youtube.com/playlist?list=PLZSO_6-bSqHQmMKwWVvYwKreGu4b4kMU9 (YouTube playlist)
---
You received this message because you are subscribed to the Google Groups "10-701 Spring 2013 CMU" group.
To unsubscribe from this group and stop receiving emails from it, send an email to 10-701-spring-201...@googlegroups.com.
To post to this group, send email to 10-701-spri...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

--

Krikamol Muandet
PhD Student                                                   
Max Planck Institute for Intelligent Systems            
Spemannstrasse 38, 72076 Tübingen, Germany      
Telephone: +49-(0)7071 601 554
http://www.kyb.mpg.de/~krikamol

[Krikamol Muandet]

btw, Laplacian and Gaussian kernels are both translation-invariant since they depend only on x-y.

Krik

[Manzil Zaheer]

Thanks Krik very much for the suggestions.

Sorry for not being more clear and specific about point 2, but I meant how do we prove that if for a function Fourier transform is non-negative then it satisfies Mercer's theorem.

Unless I understood your statement incorrectly, Fourier transform is not a real valued function. Au contraire, typically Fourier Transform of a function will always be complex, unless the function itself is real and even. Infact it is easy to prove it: since generally any function can be written as a sum of an even and an odd function, unless the odd part is zero everywhere the Fourier transform will be complex.

So I still have my doubt how the Fourier transform is guaranteed to be real? if not then which ordering is used?

Thanking you,

Manzil

On Monday, February 11, 2013 5:44:16 PM UTC-5, Krik wrote:

btw, Laplacian and Gaussian kernels are both translation-invariant since they depend only on x-y.

Krik

On 11 February 2013 23:42, Krikamol Muandet <krik...@gmail.com> wrote:

Hi Manzil,

Some of my answers below. As I am not an expert, please correct me if I am wrong.

On 11 February 2013 22:34, Manzil Zaheer <manzil...@gmail.com> wrote:

Kindly help and guide me, as I seem to be lost.

On Monday, February 11, 2013 4:32:01 PM UTC-5, Manzil Zaheer wrote:

In one of the slides you have mentioned, "Simple trick for checking Mercer’s condition: Compute the Fourier transform of the kernel and check that it is nonnegative". I have some questions:

1. With respect to which variable do we take fourier transform? I guess x, anyways it should not matter as its symmetric

I guess this trick works only for translation-invariant kernels, i.e., k(x,y) = g(x-y) for some positive semidefinite function g. In which case, there is only one variable, i.e., x-y, and you should take fourier transform with respect to this variable. I think there is also a way to check this for other types of kernels such as dot product kernels, e.g., k(x,y) = g(x^T. y), but I believe things get more complicate.

 

2. How do we prove this?

What do you mean by this?

 

3. Infact how do you even guarantee it is real in the first place so that an order is defined? For functions having symmetry its fine like the Laplacian or Gaussian RBF, but for example in case of linear kernel, the Fourier transform is imaginary at origin

If I understand correctly, you get a Fourier transform, which is a real-valued function, whose domain can be complex. So in principle you should be able to check non-negativity of the function.

Btw, I don't think you need to do a Fourior transform to prove that a linear kernel satisfies Mercer condition.

 

Krik

--
http://alex.smola.org/teaching/cmu2013-10-701 (course website)
http://www.youtube.com/playlist?list=PLZSO_6-bSqHQmMKwWVvYwKreGu4b4kMU9 (YouTube playlist)
---
You received this message because you are subscribed to the Google Groups "10-701 Spring 2013 CMU" group.

To unsubscribe from this group and stop receiving emails from it, send an email to 10-701-spring-2013-cmu+unsub...@googlegroups.com.

To post to this group, send email to 10-701-spri...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

--

Krikamol Muandet
PhD Student                                                   
Max Planck Institute for Intelligent Systems            
Spemannstrasse 38, 72076 Tübingen, Germany      
Telephone: +49-(0)7071 601 554
http://www.kyb.mpg.de/~krikamol

[Krikamol Muandet]

Hi Manzil,

Thank you very much for your clarification. You are indeed correct. I was wrong when I said that it is a real-valued function. I will think about your third question more thoroughly.

For the second question, I attached a simple derivation for translation-invariant kernel, which guarantee to satisfy Mercer's condition if the Fourier transform is nonnegative.

Best,

Krik

To unsubscribe from this group and stop receiving emails from it, send an email to 10-701-spring-201...@googlegroups.com.

To post to this group, send email to 10-701-spri...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

[Alex Smola]

hi manzil,

ok, i think krik and i skipped a few steps in the reasoning (they're straightforward, though):

a) since k(x-x') = k(x'-x) due to symmetry, the fourier transform has to be real.

b) to see backwards part of the argument, simply use the fact that for the reverse fourier transform you get

\int \exp(i<w,x>) \exp(-i<w,x') \kappa(\omega)

and by now we know that \kappa(\omega) must be real. if \kappa(\omega) were negative at some point, we could simply pick the corresponding frequency and get a negative value for the term in mercer's theorem since there we have to satisfy

\int f(x) f(x') k(x,x')

and we could simply pick f(x) = \cos(<w,x>) (or \sin(<w,x>) for that matter). due to the expansion property you'd get a negative value. 

cheers,

alex

--

                            ''~``

                           ( o o )

+----------------------.oooO--(_)--Oooo.---------------------------+

| Prof. Alexander J. Smola             http://alex.smola.org       |

| 5000 Forbes Ave                      phone: (+1) 408-759-1044    |

| Gates Hillman Center 8002            Carnegie Mellon University  |

| Pittsburgh 15213 PA    (   )   Oooo. Machine Learning Department |

+-------------------------\ (----(   )-----------------------------+                          

                          \_)    ) /

                                (_/