yep -- this seems to be fixing it: private boolean isPositiveDefinite = true;
On Thu, Mar 6, 2014 at 12:53 PM, Dmitriy Lyubimov <[email protected]> wrote: > 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 => {} >>> > >>>> > } >>> > >>>> > >>> > >>>> >>> > >>> >>> > >>> >>> > >> >>> > > >>> > >>> >> >> >
