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.
> >>
>
