BTW, my initialization of X and Y is simply random:
X = rand(m,k);
Y = rand(k,n);
On Thu, Apr 4, 2013 at 3:51 PM, Koobas <koobas@gmail.com> wrote:
> 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 roundoff. 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 nonweighted
>>>>>> 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
>>>>>> >>> > illconditionedness of matrices  like a principled
choice of
>>>>>> >>> > threshold above which you say it's illconditioned,
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
illconditioned, or
>>>>>> is there
>>>>>> >>> > more
>>>>>> >>> > > to it?
>>>>>> >>> > >
>>>>>> >>> >
>>>>>> >>>
>>>>>> >>
>>>>>> >>
>>>>>>
>>>>>
>>>>>
>>>>
>>>
>>
>
