Re: questions about ichol

[Juan Pablo Carbajal]

On Sun, May 8, 2016 at 7:37 PM, siko1056 <address@hidden> wrote:
> Hi Juan,
>
> In Germany we enjoyed a long sunny Holiday weekend, thus sorry for my
> delayed reply.
>
>
> Juan Pablo Carbajal-2 wrote
>> 1. Is there a reason for it to work only with sparse matrices?
>
> Yes, the implemented algorithm is according to the book by Yousef Saad
> http://www-users.cs.umn.edu/~saad/books.html (Chap. 10) with some
> modifications described in Eduardo Fernández GSoC blog
> http://edu159-gsoc2014.blogspot.de/ . And they really only make sense with
> sparse matrices and large dimensions. For each other case, a dense
> Cholesky-Factorization is more economical.
>
>
> Juan Pablo Carbajal-2 wrote
>> 2. I can get it to work with the "ict" option and "droptol" > 1e-10. I
>> always get
>> error: ichol: negative pivot encountered
>> error: called from
>>     ichol at line 242 column 9
>> (I guess the actual value of droptol might be different for different
>> matrices)
>>
>> For example, the following fails. the matrix is clearly positive
>> definite (algouth some eigvals might be really small, but even if I
>> regularize...)
>>
>> t = linspace (0,1,1e3).';
>> k = sparse (exp (-(t-t.').^2/0.1^2));
>> Ui = ichol(k,struct("type","ict","droptol",1e-9,"shape","upper"));
>>
>> Ui =
>> ichol(k+1e-6*eye(size(k)),struct("type","ict","droptol",1e-9,"shape","upper"));
>> # remove small eigs
>
> Here I have to disagree. Your matrix is not positive definite, see for
> example
> https://en.wikipedia.org/wiki/Positive-definite_matrix#Characterizations (4.
> Its leading principal minors are all positive.)
>
>>> t = linspace (0,1,1e3).';
>>> k = sparse (exp (-(repmat (t,1,1e3) - repmat (t.',1e3,1)).^2/0.1^2));
>>> cond(k)
> ans =    1.5316e+21
>
>>> full(k(1:5,1:5))
> ans =
>
>    1.00000   0.99990   0.99960   0.99910   0.99840
>    0.99990   1.00000   0.99990   0.99960   0.99910
>    0.99960   0.99990   1.00000   0.99990   0.99960
>    0.99910   0.99960   0.99990   1.00000   0.99990
>    0.99840   0.99910   0.99960   0.99990   1.00000
>
>>> eig(k(1:5,1:5))
> ans =
>
>    2.6878e-16
>    1.9309e-11
>    2.8099e-07
>    2.0026e-03
>    4.9980e+00
>
> Your matrix is symmetric, strictly positive, no value is smaller or equal to
> zero, but it is not diagonal dominant (enough) for positive
> semidefiniteness. A principal minor check quickly reveals, that there are
> negative eigenvalues, and the matrix condition estimation is not very
> promising.
>
> The same with your Tikhonov regularization.
>
>>> k = k + 1e-6*speye (size (k));
>>> cond(k)
> ans =    1.7339e+08
>
>>> full(k(1:5,1:5))
> ans =
>
>    1.00000   0.99990   0.99960   0.99910   0.99840
>    0.99990   1.00000   0.99990   0.99960   0.99910
>    0.99960   0.99990   1.00000   0.99990   0.99960
>    0.99910   0.99960   0.99990   1.00000   0.99990
>    0.99840   0.99910   0.99960   0.99990   1.00000
>
>>> eig(k(1:5,1:5))
> ans =
>
>    1.0000e-06
>    1.0000e-06
>    1.2810e-06
>    2.0036e-03
>    4.9980e+00
>
> Better but not "enough".
>
> Maybe you tell me what you are going to archive with your computation, to
> find a better approach, but I doubt ichol was the right tool for archiving
> it.
>
> HTH, Kai
>
>
>
>
> --
> View this message in context: 
> http://octave.1599824.n4.nabble.com/questions-about-ichol-tp4676730p4676836.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

Hi Kai,

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 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.