The classic poorly conditioned matrix is Hilbert's.
a_ij = 1/(i+j+1) (for zero-based matrices)
or
a_ij = 1/(i+j-1) (for one-based matrices such as in R)
This matrix looks quite fine, but the inverse shows up factorial size
values. Here, for instance, is the inverse of H_5:
> solve(1/(matrix(1:5, nrow=5, ncol=5) + t(matrix(1:5, nrow=5, ncol=5)) -
1))
[,1] [,2] [,3] [,4] [,5]
[1,] 25 -300 1050 -1400 630
[2,] -300 4800 -18900 26880 -12600
[3,] 1050 -18900 79380 -117600 56700
[4,] -1400 26880 -117600 179200 -88200
[5,] 630 -12600 56700 -88200 44100
This sounds a bit like what you are describing, but I think that the
earlier comment about lack of orthogonality in ALS versus SVD may be more
to the point.
On Thu, Apr 4, 2013 at 8: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.
>
> Try some simple dummy data like below, without maybe k=10. If it
> completes with error that's a problem!
>
> 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?
> >>> > >
> >>> >
> >>>
> >>
> >>
>
