mahout-user mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Koobas <koo...@gmail.com>
Subject Re: Detecting rank-deficiency, or worse, via QR decomposition
Date Thu, 04 Apr 2013 19:51:19 GMT
It's done in one iteration.
This is the R from QR factorization:

    5.0663    5.8122    4.9704    4.3987    6.3400    4.5970    5.0334
4.2581    3.3808    5.3250
         0    2.4036    1.1722    2.3296    1.6580    0.4575    1.1706
2.1040    1.6738    1.4839
         0         0    1.5085    0.0966    1.2581    0.5236    0.4712
-0.0411    0.3143    0.5957
         0         0         0    1.8682    0.1834   -0.3244   -0.0073
0.3817    1.1673    0.4783
         0         0         0         0    1.9569    0.8666    0.3201
-0.4167    0.0732    0.3114
         0         0         0         0         0    1.3520    0.2326
-0.1156   -0.2793    0.0103
         0         0         0         0         0         0    1.1689
0.3151    0.0590    0.0435
         0         0         0         0         0         0         0
1.6296   -0.3494   -0.0024
         0         0         0         0         0         0
0         0    1.4307    0.1803
         0         0         0         0         0         0
0         0         0    1.1404



On Thu, Apr 4, 2013 at 3:46 PM, Koobas <koobas@gmail.com> wrote:

> Sorry, the image was off.
> This is more like it:
>
> [image: Inline image 1]
>
>
> On Thu, Apr 4, 2013 at 3:38 PM, Koobas <koobas@gmail.com> wrote:
>
>> k was 10
>>
>>
>> On Thu, Apr 4, 2013 at 3:37 PM, Koobas <koobas@gmail.com> wrote:
>>
>>> No major problems:
>>>
>>> A =
>>>
>>>      1     4     3     0     0
>>>      0     0     3     0     0
>>>      0     4     0     3     2
>>>      5     0     2     0     3
>>>      0     0     0     5     0
>>>      2     4     0     0     0
>>>
>>>
>>> XY =
>>>
>>>     0.9605    3.4671    2.4266    0.0542    0.1976
>>>     0.1638    0.0900    2.2520   -0.0241    0.0057
>>>     0.3024    3.4562    0.0997    2.6573    1.3113
>>>     4.2061    0.1756    1.7800    0.0045    2.4648
>>>    -0.1467    0.1345   -0.0401    4.0637    0.2787
>>>     1.5208    3.3953    0.2292    0.0489    0.3508
>>>
>>>
>>> RMSE =
>>>
>>>     0.4084
>>>
>>> [image: Inline image 1]
>>>
>>>
>>> On Thu, Apr 4, 2013 at 3:04 PM, Koobas <koobas@gmail.com> wrote:
>>>
>>>>
>>>>
>>>>
>>>> On Thu, Apr 4, 2013 at 2:23 PM, Sean Owen <srowen@gmail.com> wrote:
>>>>
>>>>> Does it complete without problems? It may complete without error but
>>>>> the result may be garbage. The matrix that's inverted is not going to
>>>>> be singular due to round-off. Even if it's not you may find that the
>>>>> resulting vectors are infinite or very large. In particular I at least
>>>>> had to make the singularity threshold a lot larger than
>>>>> Double.MIN_VALUE in the QR decomposition.
>>>>>
>>>>> No, not at all, it completes very nicely.
>>>> I print the residual and also plot eyeball the plot of the matrix.
>>>> It does the job.
>>>>
>>>>
>>>>> Try some simple dummy data like below, without maybe k=10. If it
>>>>> completes with error that's a problem!
>>>>>
>>>>
>>>> Okay, let me try it....
>>>>
>>>>>
>>>>> 0,0,1
>>>>> 0,1,4
>>>>> 0,2,3
>>>>> 1,2,3
>>>>> 2,1,4
>>>>> 2,3,3
>>>>> 2,4,2
>>>>> 3,0,5
>>>>> 3,2,2
>>>>> 3,4,3
>>>>> 4,3,5
>>>>> 5,0,2
>>>>> 5,1,4
>>>>>
>>>>> On Thu, Apr 4, 2013 at 7:05 PM, Koobas <koobas@gmail.com> wrote:
>>>>> > I took Movie Lens 100K data without ratings and ran non-weighted
ALS
>>>>> in
>>>>> > Matlab.
>>>>> > I set number of features k=2000, which is larger than the input
>>>>> matrix
>>>>> > (1000 x 1700).
>>>>> > I used QR to do the inversion.
>>>>> > It runs without problems.
>>>>> > Can you share your data?
>>>>> >
>>>>> >
>>>>> >
>>>>> > On Thu, Apr 4, 2013 at 1:10 PM, Koobas <koobas@gmail.com>
wrote:
>>>>> >
>>>>> >> Just to throw another bit.
>>>>> >> Just like Ted was saying.
>>>>> >> If you take the largest singular value over the smallest singular
>>>>> value,
>>>>> >> you get your condition number.
>>>>> >> If it turns out to be 10^16, then you're loosing all the digits
of
>>>>> double
>>>>> >> precision accuracy,
>>>>> >> meaning that your solver is nothing more than a random number
>>>>> generator.
>>>>> >>
>>>>> >>
>>>>> >>
>>>>> >>
>>>>> >> On Thu, Apr 4, 2013 at 12:21 PM, Dan Filimon <
>>>>> dangeorge.filimon@gmail.com>wrote:
>>>>> >>
>>>>> >>> For what it's worth, here's what I remember from my Numerical
>>>>> Analysis
>>>>> >>> course.
>>>>> >>>
>>>>> >>> The thing we were taught to use to figure out whether the
matrix
>>>>> is ill
>>>>> >>> conditioned is the condition number of a matrix (k(A) =
norm(A) *
>>>>> >>> norm(A^-1)). Here's a nice explanation of it [1].
>>>>> >>>
>>>>> >>> Suppose you want to solve Ax = b. How much worse results
will you
>>>>> get
>>>>> >>> using
>>>>> >>> A if you're not really solving Ax = b but A(x + delta) =
b +
>>>>> epsilon (x is
>>>>> >>> still a solution for Ax = b).
>>>>> >>> So, by perturbing the b vector by epsilon, how much worse
is delta
>>>>> going
>>>>> >>> to
>>>>> >>> be? There's a short proof [1, page 4] but the inequality
you get
>>>>> is:
>>>>> >>>
>>>>> >>> norm(delta) / norm(x) <= k(A) * norm(epsilon) / norm(b)
>>>>> >>>
>>>>> >>> The rule of thumb is that if m = log10(k(A)), you lose m
digits of
>>>>> >>> accuracy. So, equivalently, if m' = log2(k(A)) you lose
m' bits of
>>>>> >>> accuracy.
>>>>> >>> Since floats are 32bits, you can decide that say, at most
2 bits
>>>>> may be
>>>>> >>> lost, therefore any k(A) > 4 is not acceptable.
>>>>> >>>
>>>>> >>> Anyway there are lots of possible norms and you need to
look at
>>>>> ways of
>>>>> >>> actually interpreting the condition number but from what
I learned
>>>>> this is
>>>>> >>> probably the thing you want to be looking at.
>>>>> >>>
>>>>> >>> Good luck!
>>>>> >>>
>>>>> >>> [1] http://www.math.ufl.edu/~kees/ConditionNumber.pdf
>>>>> >>> [2] http://www.rejonesconsulting.com/CS210_lect07.pdf
>>>>> >>>
>>>>> >>>
>>>>> >>> On Thu, Apr 4, 2013 at 5:26 PM, Sean Owen <srowen@gmail.com>
>>>>> wrote:
>>>>> >>>
>>>>> >>> > I think that's what I'm saying, yes. Small rows X shouldn't
>>>>> become
>>>>> >>> > large rows of A -- and similarly small changes in X
shouldn't
>>>>> mean
>>>>> >>> > large changes in A. Not quite the same thing but both
are
>>>>> relevant. I
>>>>> >>> > see that this is just the ratio of largest and smallest
singular
>>>>> >>> > values. Is there established procedure for evaluating
the
>>>>> >>> > ill-conditioned-ness of matrices -- like a principled
choice of
>>>>> >>> > threshold above which you say it's ill-conditioned,
based on k,
>>>>> etc.?
>>>>> >>> >
>>>>> >>> > On Thu, Apr 4, 2013 at 3:19 PM, Koobas <koobas@gmail.com>
wrote:
>>>>> >>> > > So, the problem is that the kxk matrix is ill-conditioned,
or
>>>>> is there
>>>>> >>> > more
>>>>> >>> > > to it?
>>>>> >>> > >
>>>>> >>> >
>>>>> >>>
>>>>> >>
>>>>> >>
>>>>>
>>>>
>>>>
>>>
>>
>

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