mahout-user mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Ted Dunning <ted.dunn...@gmail.com>
Subject Re: Using SVD-conditioned matrix
Date Sun, 16 Sep 2012 20:00:24 GMT
I should point out that for vectors in the space spanned by columns of A,
U_k U_k' is an identity mapping. For any vector x in the null space of
columns of A, U_k U_k x = 0.

You can view every vector u as the sum of a component in span A and an
orthogonal component in null A

     u = u_A + u_/A

If you shove u through U_k U_k' you get this:

     U_k U_k' u = U_k U_k' (u_A + u_/A) = U_k U_k' (u_A) + 0 = u_A

This is another way of showing that U_k U_k' projects a vector into span A.

On Sun, Sep 16, 2012 at 12:55 PM, Ted Dunning <ted.dunning@gmail.com> wrote:

> U_k ' U_k = I
>
> U_k U_k ' != I
>
>
> On Sun, Sep 16, 2012 at 12:54 PM, Sean Owen <srowen@gmail.com> wrote:
>
>> I have a feeling this is a dumb question. But in...
>>
>>  u_k = U_k U_k' u
>>
>> U is orthonormal, so Uk is orthonormal. So U_k U_k' is the identity.
>> So what does this actually say?
>>
>> It's surely on the right track of somehthing, since I find the same
>> expression in that original SVD paper, "Incremental Singular Value
>> Decomposition Algorithms for Highly Scalable Recommender Systems". But
>> it has some serious typos in its notation. (Try to figure out Figure
>> 1.) And it proceeds in its analysis by basically saying that the
>> projection is Uk' times the new vector, so, I never understood this
>> expression.
>>
>> On Sun, Sep 16, 2012 at 7:13 PM, Ted Dunning <ted.dunning@gmail.com>
>> wrote:
>> > A is in there implicitly.
>> >
>> > U_k provides a basis of the row space and V_k provides a basis of the
>> > column space of A.  A itself has a representation in either of these
>> > depending on whether you think of it as rows or columns.
>> >
>> > The original question (possibly misphrased and not in so many words)
>> asked
>> > for a way to project any vector into the space spanned by A.  What space
>> > this is depends on whether we have a new column vector (with n rows x 1
>> > column) or a new row vector (with 1 row x m columns).  In either case,
>> the
>> > way to compute this is to project the vector onto the basis of interest
>> > (U_k for column vectors, V_k for row vectors) and then reconstruct that
>> > projection in the original space.
>> >
>> > This is not usually a practical operation when we are working with
>> sparse
>> > vectors because the projected vector is not usually sparse.  Thus it is
>> > usually better to stop before projecting back into the original space.
>> >
>> > On Sun, Sep 16, 2012 at 10:26 AM, Sean Owen <srowen@gmail.com> wrote:
>> >
>> >> I don't quite get these formulations -- shouldn't Ak be in there
>> >> somewhere? you have a new row of that (well, some piece of some new
>> >> row of Ak), and need a new row of Uk. Or: surely the expression
>> >> depends on V?
>> >>
>> >> On Sun, Sep 16, 2012 at 5:33 PM, Ted Dunning <ted.dunning@gmail.com>
>> >> wrote:
>> >> > And if you want the reduced rank representation of A, you have it
>> already
>> >> > with
>> >> >
>> >> >     A_k = U_k S_k V_k'
>> >> >
>> >> > Assume that A is n x m in size.  This means that U_k is n x k and
>> V_k is
>> >> m
>> >> > x k
>> >> >
>> >> > The rank reduced projection of an n x 1 column vector is
>> >> >
>> >> >     u_k = U_k U_k' u
>> >> >
>> >> > Beware that v_k is probably not sparse even if v is sparse.
>> >> >
>> >> > Similarly, the rank reduced projection of a 1 x m row vector is
>> >> >
>> >> >     v_k = v V_k V_k'
>> >> >
>> >> > A similar sparsity warning applies to v_k.  This is why it is usually
>> >> > preferable to just work in the reduced space directly.
>> >>
>>
>
>

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