Timeline for Is there a way to simplify block Cholesky decomposition if you already have decomposed the submatrices along the leading diagonal?
Current License: CC BY-SA 2.5
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 26, 2013 at 16:09 | comment | added | Memming | Technical report moved to: ipg.epfl.ch/~seeger/lapmalmainweb/papers/cholupdate.shtml | |
| Jul 9, 2010 at 0:57 | comment | added | Matthew Gretton | If you could ask your numerical linear algebraists about the problem when they get back in the country it would be greatly appreciated. Even if the answer is a definite 'C cannot help' it would at least allow me to put the problem to bed and force me to take a new approach. Thanks again for all you help, I look forward to hearing what your num lin algs have to say. | |
| Jul 9, 2010 at 0:55 | comment | added | Matthew Gretton | Excellent! Glad I've managed to communicate the problem. Probably should have given the machine learning context earlier. Still, got there in the end. Thanks for sticking with it! As you say pre-computation of B is impossible as you need both training sets X and Y. Whereas you can precompute A and C as soon as you have the appropriate training sets. | |
| Jul 8, 2010 at 16:54 | comment | added | Jack Schmidt | Thanks! That exactly answered my earlier question. I would phrase your problem as A,C fixed, B changes, just because A,C came (possibly hours) before B was around, and so pre-computation is completely sensible for A,C and impossible for B. I personally still think C cannot help (well, your stability argument has halfway changed my mind), but I'll definitely ask around once people get back. Our numerical linear algebraists are all out of the country right now, but will be back soon enough. | |
| Jul 8, 2010 at 1:05 | comment | added | Matthew Gretton | So in answer to your question, I do not need C^1/2 for anything else necessarily but will have it for free. In the case that you give certainly knowledge of A^1/2 and C^1/2 does not help but in thinking about the problem for the machine learning viewpoint, I would expect the X trained data (A^1/2) and the Y trained data (C^1/2) to be relevant in the trained data for (X+Y). I hoped this would be reflected in the Matrix Algebra. | |
| Jul 8, 2010 at 0:54 | comment | added | Matthew Gretton | It might help if I give some more detail relating to how A,B, and C are formed. In the context of machine learning I am trying to solve the problem of combining two sets of trained data to create a new one. Given two sets of training samples X, Y and covariance function k we form the block matrices as follows A = k(X,X), B = k(X,Y), C = k(Y,Y). Where give k, A and C should be positive definite. Now if we have trained the algorithm on X and Y before hand we will already have A^1/2 and C^1/2. | |
| Jul 7, 2010 at 19:11 | comment | added | Jack Schmidt | Summer is a slow time; so far none around. However, I am doubtful it would help much in your case to compute C^{1/2} (do you need it for anything else?). Imagine A=1, C=0. Then Q = -B*B is an arbitrary (negative) definite symmetric matrix, completely unrelated to A and C. How can knowing A^{1/2}=1 and C^{1/2}=0 possibly help to find the (imaginary) Cholesky decomposition of the arbitrary matrix Q? | |
| Jul 7, 2010 at 18:08 | vote | accept | Matthew Gretton | ||
| Jul 7, 2010 at 18:08 | |||||
| Jul 5, 2010 at 22:19 | comment | added | Matthew Gretton | I'm still hopeful. I have a gut feeling that the computation of C^{-1/2} must in some way give some relevant information and should therefore be able to speed up the calculation. Do you know any Matrix Algebra wizs who would be able to verify one way or the other? Thanks again. | |
| Jul 5, 2010 at 22:15 | comment | added | Matthew Gretton | Hi. I've got a bit of time to respond to your answer properly. With respect to your first paragraph, as a result of the way the training works given two sets of training samples you want to combine, A,B, and C are fixed. So as you point out we are updating the decomposition of A, and again as you say, the best way to do this is to do the update in one go (calc Q^{-1/2} using cholesky decomposition). So the one question remaining is whether there is any way I can use C^{-1/2} in any way to speed up the calculation of Q^{-1/2}. | |
| Jul 2, 2010 at 13:01 | comment | added | Matthew Gretton | Hey. Thanks for the reply. Sadly it's looking like I can't use C^{-1/2} to help be out in the decomposition of Q. Perhaps some kind of approximation to Q^{1/2} using C^{-1/2} as a starting point. I'll have a think... Should have time over the weekend to look over the links you supplied in more detail. I'll reply in more detail then. Thanks again for the detailed reply. | |
| Jul 1, 2010 at 19:39 | history | answered | Jack Schmidt | CC BY-SA 2.5 |