mahout-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Dmitriy Lyubimov <dlie...@gmail.com>
Subject Re: Cholesky troubles again.
Date Thu, 06 Mar 2014 20:45:48 GMT
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 <ted.dunning@gmail.com> 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 <dlieu.7@gmail.com>
> 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 <dlieu.7@gmail.com>
> > 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 <dlieu.7@gmail.com
> > >wrote:
> > >
> > >> oh, ok. So input is indeed still deficient. ok .
> > >>
> > >>
> > >> On Wed, Mar 5, 2014 at 7:04 PM, Dmitriy Lyubimov <dlieu.7@gmail.com
> > >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 <
> > >>> andrew.musselman@gmail.com> 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 <dlieu.7@gmail.com
> >
> > >>>> 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  => {}
> > >>>> > }
> > >>>> >
> > >>>>
> > >>>
> > >>>
> > >>
> > >
> >
>

Mime
  • Unnamed multipart/alternative (inline, None, 0 bytes)
View raw message