on the "uniqueness" of Singular value decomposition (answer to the blog question)

[Subbarao Kambhampati <rao@asu.edu>]

There is a question on the blog as to whether SVD is guaranteed to be unique for a given matrix. 

dt= df * ff * tf'

It is easy to see that  ff is unique--since it is just the square roots of eigen values of dt*dt' (or dt'*dt). 

The question is about df and tf' .  Their "uniqueness" depends on whether or not the singular values are all distinct (which in turn 
depends on whether the eigen values of dt*dt' are distinct)
(Recall  that a square matrix can have repeated eigen values--which happens when its characteristic equation has a factor--say
(x - l)^k   --so we have k roots at l, and the eigen value l is said to have multiplicity  k )

When the singular values are all distinct, then df and tf' are unique *upto* the sign of the vectors (that is, their magnitude is unique, but sign can be either positive or negative--but the signs of df and tf' have to be consistent).

When the singular values are degenerate, then df and tf' are no longer unique. 

The lack of uniqueness doesn't however affect any of the low-rank approximation properties of SVD we cared about in doing LSI.

Rao

ps: Here is a longer technical description on SVD uniqueness: http://informatik.unibas.ch/lehre/hs09/cs253/slides/svd09.pdf