On Thu, Apr 4, 2013 at 2:23 PM, Sean Owen <[email protected]> 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 <[email protected]> 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 <[email protected]> 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 < > [email protected]>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 <[email protected]> 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 <[email protected]> wrote: > >>> > > So, the problem is that the kxk matrix is ill-conditioned, or is > there > >>> > more > >>> > > to it? > >>> > > > >>> > > >>> > >> > >> >
