Hm I think it is a valid bug in Cholesky decomposition. I don't seem to see that isPositiveDefinite is initialized to true, anywhere (default valuel in java is false). So if degenerate case is detected, it is assigned to false but never otherwise.
Are you ok with me fixing this? On Thu, Mar 6, 2014 at 12:45 PM, Dmitriy Lyubimov <[email protected]> wrote: > Hm. I still seem to have trouble, this time with isPositiveDefinite which > returns false although i seem to have a fairly nice traingular L' (which > is printed here as R). Clearly algorithm has finished all elements without > encountering a degenerative condition yet reported failure to assert > positive-definite-ness : > > > > > 2243 [ScalaTest-run-running-MathSuite] DEBUG > org.apache.mahout.sparkbindings.drm.decompositions.DQR$ - R= > { > 0 => > {0:4.186193378864822,1:-0.3357736566246455,2:0.8607534898896447,3:-4.33523362179746} > 1 => {1:9.134979322863726,2:1.4522423059617362,3:-0.315879931815721} > 2 => {2:0.8986806052211012,3:-0.03911349897105256} > 3 => {3:0.02316192361205758} > } > > for the input of A > > val inCoreA = dense( > (1, 2, 3, 4), > (2, 3, 4, 5), > (3, -4, 5, 6), > (4, 5, 6, 7), > (8, 6, 7, 8) > ) > > > and A'A as > 2242 [ScalaTest-run-running-MathSuite] DEBUG > org.apache.mahout.sparkbindings.drm.decompositions.DQR$ - A'A= > { > 0 => > {0:17.524215005251673,1:-1.405613458159321,2:3.603280560210819,3:-18.148126283400686} > 1 => > {0:-1.405613458159321,1:83.5605911776309,2:12.977185089995727,3:-1.4298994001311764} > 2 => > {0:3.603280560210819,1:12.977185089995727,2:3.6575311157828283,3:-4.225452212963807} > 3 => > {0:-18.148126283400686,1:-1.4298994001311764,2:-4.225452212963807,3:18.896097027394198} > } > > > > > On Thu, Mar 6, 2014 at 12:28 PM, Ted Dunning <[email protected]>wrote: > >> It may be a knowledge gap, but it seems to have been well filled by >> accurate inference. >> >> A'A is always semi-positive-definite. >> >> And I think you are correct that only rank deficiency can cause y'y = 0 >> >> >> On Thu, Mar 6, 2014 at 10:45 AM, Dmitriy Lyubimov <[email protected]> >> wrote: >> >> > I guess A'A is always semi-positive-definite since x'(A'A)x = >> (x'A')(Ax) = >> > y'y >=0. >> > >> > I also intuitively think that y'y = 0 when x != 0 in this case if and >> only >> > if A'A is rank-deficient, i.e. it is sufficient to test for rank >> deficiency >> > of A'A product to figure if QR is going less non-zero column than one >> > desires. (Yes i have a knowledge gap here :) >> > >> > >> > On Wed, Mar 5, 2014 at 7:17 PM, Dmitriy Lyubimov <[email protected]> >> > wrote: >> > >> > > Still though, it seems this code is too sensitive to the error margin. >> > > >> > > Even when i change the input so that the case is not degenerate, i >> still >> > > get second norm of difference on Q of ~1e-5 between Cholesky and QR >> even >> > > on 3 x 4 input which is large-ish imo, >> > > >> > > >> > > On Wed, Mar 5, 2014 at 7:05 PM, Dmitriy Lyubimov <[email protected] >> > >wrote: >> > > >> > >> oh, ok. So input is indeed still deficient. ok . >> > >> >> > >> >> > >> On Wed, Mar 5, 2014 at 7:04 PM, Dmitriy Lyubimov <[email protected] >> > >wrote: >> > >> >> > >>> well the positive definite test is failing starting with row 2. I >> > >>> stepped thru it. But i am at loss why. >> > >>> >> > >>> >> > >>> On Wed, Mar 5, 2014 at 6:55 PM, Andrew Musselman < >> > >>> [email protected]> wrote: >> > >>> >> > >>>> Just noticed it looks like some kind of rounding error since rows >> "2" >> > >>>> and >> > >>>> "3" in rControl have very small values in their elements. >> > >>>> >> > >>>> >> > >>>> On Wed, Mar 5, 2014 at 6:48 PM, Dmitriy Lyubimov < >> [email protected]> >> > >>>> wrote: >> > >>>> >> > >>>> > Hi, >> > >>>> > >> > >>>> > I am trying to put in Cholesky-based distributed thin QR and >> having >> > >>>> > troubles again (even with in-core). What am i doing wrong? I am >> > >>>> inclined to >> > >>>> > think there's definitely a bug in our Cholesky implementation, at >> > this >> > >>>> > point. >> > >>>> > >> > >>>> > Here is the test code -- obviously results are different via >> > >>>> Householder QR >> > >>>> > and via Cholesky. Note that two rows of L' (R) matrix match the >> > result >> > >>>> > exactly, and it looks like L is just loosing two of its columns >> > >>>> somehow. >> > >>>> > >> > >>>> > Could somebody perhaps review the CholeskyDecomposition in >> Mahout? >> > >>>> Because >> > >>>> > of this, tests in spark - QR and spark -SSVD are failing. >> > >>>> > >> > >>>> > here's the code for in-core only and output: >> > >>>> > >> > >>>> > ----------------- >> > >>>> > >> > >>>> > val inCoreA = dense( >> > >>>> > (1, 2, 3, 40), >> > >>>> > (2, 3, 4, 50), >> > >>>> > (3, 4, 5, 60), >> > >>>> > (4, 5, 6, 70), >> > >>>> > (5, 6, 7, 80) >> > >>>> > ) >> > >>>> > >> > >>>> > val (qControl, rControl) = qr(inCoreA) >> > >>>> > >> > >>>> > printf("qControl=\n%s\n", qControl) >> > >>>> > printf("rControl=\n%s\n", rControl) >> > >>>> > >> > >>>> > // Validate with Cholesky >> > >>>> > val ch = chol(inCoreA.t %*% inCoreA) >> > >>>> > val rControl2 = (ch.getL cloned).t >> > >>>> > val qControl2 = ch.solveRight(inCoreA) >> > >>>> > >> > >>>> > printf("qControl2=\n%s\n", qControl2) >> > >>>> > printf("rControl2=\n%s\n", rControl2) >> > >>>> > >> > >>>> > >> > >>>> > >> > >>>> > qControl= >> > >>>> > { >> > >>>> > 0 => >> > >>>> > >> > >>>> > >> > >>>> >> > >> {0:0.13483997249264842,1:0.7627700713964736,2:0.09950371902099892,3:-0.30053573339989126} >> > >>>> > 1 => >> > >>>> > >> > >>>> > >> > >>>> >> > >> {0:0.26967994498529685,1:0.4767312946227957,2:0.19900743804199783,3:0.34749444174362476} >> > >>>> > 2 => >> > >>>> > >> > >>>> > >> > >>>> >> > >> {0:0.40451991747794525,1:0.1906925178491178,2:0.39801487608399566,3:0.22070592921554588} >> > >>>> > 3 => >> > >>>> > >> > >>>> > >> > >>>> >> > >> {0:0.5393598899705937,1:-0.09534625892456007,2:0.39801487608399566,3:0.6949888834872495} >> > >>>> > 4 => >> > >>>> > >> > >>>> > >> > >>>> >> > >> {0:0.6741998624632421,1:-0.3813850356982384,2:0.7960297521679913,3:-0.5071540501123155} >> > >>>> > } >> > >>>> > rControl= >> > >>>> > { >> > >>>> > 0 => >> > >>>> > >> > >>>> > >> > >>>> >> > >> {0:7.416198487095663,1:9.43879807448539,2:11.461397661875116,3:134.83997249264843} >> > >>>> > 1 => >> > >>>> {1:0.9534625892455925,2:1.906925178491185,3:28.603877677367773} >> > >>>> > 2 => {2:2.2315206618374916E-15,3:4.1360462167918654E-14} >> > >>>> > 3 => {3:1.8726762404185252E-15} >> > >>>> > } >> > >>>> > L: >> > >>>> > { >> > >>>> > 0 => {0:7.416198487095663} >> > >>>> > 1 => {0:9.43879807448539,1:0.953462589245576} >> > >>>> > 2 => {0:11.461397661875116,1:1.9069251784911967} >> > >>>> > 3 => {0:134.83997249264843,1:28.603877677367997} >> > >>>> > } >> > >>>> > qControl2= >> > >>>> > { >> > >>>> > 0 => {0:0.13483997249264842,1:0.7627700713964867} >> > >>>> > 1 => {0:0.26967994498529685,1:0.4767312946228039} >> > >>>> > 2 => {0:0.40451991747794525,1:0.19069251784912108} >> > >>>> > 3 => {0:0.5393598899705937,1:-0.09534625892456171} >> > >>>> > 4 => {0:0.674199862463242,1:-0.38138503569824406} >> > >>>> > } >> > >>>> > rControl2= >> > >>>> > { >> > >>>> > 0 => >> > >>>> > >> > >>>> > >> > >>>> >> > >> {0:7.416198487095663,1:9.43879807448539,2:11.461397661875116,3:134.83997249264843} >> > >>>> > 1 => >> > >>>> {1:0.953462589245576,2:1.9069251784911967,3:28.603877677367997} >> > >>>> > 2 => {} >> > >>>> > 3 => {} >> > >>>> > } >> > >>>> > >> > >>>> >> > >>> >> > >>> >> > >> >> > > >> > >> > >
