Re: questions about ichol

[Juan Pablo Carbajal]

On Sun, May 8, 2016 at 11:30 PM, siko1056 <address@hidden> wrote:
> Hi Juan,
>
>
> Juan Pablo Carbajal-2 wrote
>> The squared exponential function is one of the archetypes positive
>> definite kernels
>> https://en.wikipedia.org/wiki/Covariance_function#Parametric_families_of_covariance_functions
>> So maybe your are working with a different definition of positive
>> definite
>
> No, we are working with the same definition of positive definite, and
> numerically in double precision it is not. Also Matlab fails on your data,
> so I assumed with more background information to find a better solution.
>
>
> Juan Pablo Carbajal-2 wrote
>> or the method you are using just can handle small
>> eigenvalues, which was the point I was trying to rise.
>>
>> The incomplete Cholesky factorization has been used for positive
>> kernels and that is how I ended in your algorithm[1], but it seems the
>> implementation is not general enough.
>>
>>
>> [1] Fine, S. and Scheinberg, K. (2002). Efficient SVM Training Using
>> Low-Rank Kernel Representations. Journal of Machine Learning Research,
>> 2(2):243–264.
>
> After reading some of [1] I got stuck with the sentence of Figure 6 and 7
> using a variant of incomplete Cholesky factorization "input dim 10". As I am
> not a domain expert, does it mean an input
>
> d = 10; t=linspace(0,1,d) ?
>
Kai thanks for looking at it. Polynomial kernels are calculated from
scalar products in this case the kernel is

K =@(x,y) (x.' * y + c) .^5

with x and y 10-by-1 arrays and c a constant (probably 0). The
dimension is in the size of the inputs x and y not on how many of
them. In my example I was using the squared exponential in d=1
for higher dimension you would need

K =@(x,y) exp ( - (x-y).' * M * (x-y))

with M a scalar product operator, e.g. M = eyes(d), in other words it
is the exponential of a quadratic form.


> In this case, I assume there are already better approaches available for
> larger problem dimensions. Using your data with a full Cholesky
> factorization, up to dimension d=40, I had no problems. Using a higher
> dimension d quickly results in numerical difficulties, including the claim
> of non-positive definitness.
I guess here you meant the size of the matrix (i.e. number of inputs)
and not their dimension.
Yes, chol is ok, but for large problmes the n^3 makes it unfeasible
and we need aproximations that run faster.
inversion based on ichol ICT is claimed to be n^2

>
> Additionally in [1] they used an incomplete Cholesky factoriztation with
> symmetric pivoting, which is not implemented in ichol. Try the dense
> Cholesky factorization with chol(k, "vector") to get this permutation.
>
Will try.
Thx

> Kai
>
>
>
> --
> View this message in context: 
> http://octave.1599824.n4.nabble.com/questions-about-ichol-tp4676730p4676848.html
> Sent from the Octave - General mailing list archive at Nabble.com.
>
> _______________________________________________
> Help-octave mailing list
> address@hidden
> https://lists.gnu.org/mailman/listinfo/help-octave