seek advice on optimization of Gram matrix

su_jionglong@hotmail.com · science forum beginner Joined: 20 Jun 2006 Posts: 2

Suppose I have a kernel function:

k(x_i,x_j)=exp(-|x_i-x_j|^2), where x_i, x_j belongs to [0,1]

Now suppose I have n points: x_1, x_2, ...,x_n belonging to [0,1].

I obtain the Gram matrix, K =

[ k(x_1,x_1) k(x_1,x_2) ... k(x_1,x_n) ]
[ k(x_2,x_1) k(x_2,x_2) ... k(x_2,x_n) ]
[ : : ... : ]
[ k(x_n,x_1) k(x_n,x_2) ... k(x_n,x_n) ]

which is a n-by-n positive definite matrix.

This is the problem I need to solve:

Where should we place x_1, x_2, ..., x_n on the interval [0,1] so that trace(inverse of K) is minimized?

*********************************************************

I have run some trials using matlab and found the trend:

The points should be placed as far apart as possible.

This is to say, if I have 3 points, my strategy should be

x_1=0, x_2=0.5, x_3=1

if I have n points, my strategy should be

x_1=0, x_2=1/(n-1), x_3=2/(n-1), ..., x_n=(n-1)/(n-1)=1.

QUESTION: I am unable to prove mathematically this is indeed the case. Has anyone seen this before? Any help/advice is very much appreciated!

Regards

Maarten Bergvelt · science forum beginner Joined: 23 May 2005 Posts: 22

Dear Su,

First thing, when two of the x_i are equal, your matrix is not positive
definite, since it is singular.

Second thing, do you have an expression for the charateristic
polynomial of K? Or even better, the eigenvalues of K?

Regards

su_jionglong@hotmail.com a écrit :

GM · science forum beginner Joined: 23 Jun 2006 Posts: 1

Dear Su,

First thing, when two of the x_i are equal, your matrix is not positive
definite, since it is singular.

Second thing, do you have an expression for the charateristic
polynomial of K? Or even better, the eigenvalues of K?

Regards

su_jionglong@hotmail.com a écrit :

Google