mahout-user mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Sean Owen <sro...@gmail.com>
Subject Re: Using SVD-conditioned matrix
Date Sun, 16 Sep 2012 19:54:00 GMT
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
View raw message