Re: Weighted Singular Value Decomposition algorithm?

A.G.McDowell wrote:
In article <2dednYtyuKMQtXTUnZ2dnUVZ_smdnZ2d@xxxxxxxxxxxxx>, Patricia
Shanahan <pats@xxxxxxx> writes
I am looking for an algorithm for weighted truncated singular value
decomposition. The normal truncated SVD produces a low rank
approximation to an input matrix that minimizes the sum of squares of
differences between corresponding terms of the original matrix and the
result. Weighted SVD minimizes the weighted sum of squares of
differences, where the weights are specified by a matrix with the same
dimensions as the input.

I have found several articles reporting use of weighted SVD, but have
not found a complete algorithm or implementation.

Is there a better newsgroup for asking about algorithms?

Thanks,

Patricia
A little luck while web-searching, and the idea of using near misses as
a source of keywords for future searches, leads me to "Weighted Low-Rank
Approximations" by Nathan Srebro and Tommi Jaakkola, which I found at
http://people.csail.mit.edu/tommi/papers/SreJaa-icml03.pdf.

Be warned that the paper reports multiple local maxima - it would appear
that weighted SVD is intrinsically less tractable than standard SVD.

Pity about the local maxima. But I really want to try weighting. At a
minimum, you have given me a starting point for searching paper
cross-references, and a couple of names of people who may know the
current state of the art.

Oh - searching on %Programmed by: Ben Marlin, marlin[at]cs[dot]toronto[d
ot]edu
%Description: Weighted SVD EM algorithm implmentation from % 'Weighted Low-Rank Approximations' by Nathan % Srebro and Tommi Jaakola, MIT.
should find what appears to be an implementation in some language with
extensive matrix manipulation features with which I am not familiar..

It is in Matlab.

Thanks,

Patricia
.

Relevant Pages

  • Re: Weighted Singular Value Decomposition algorithm?
    ... The normal truncated SVD produces a low rank ... Weighted SVD minimizes the weighted sum of squares of ... I have found several articles reporting use of weighted SVD, ... not found a complete algorithm or implementation. ...
    (comp.theory)
  • Re: Multilinear regression - techniques and performance
    ... >>>The matrix Xij is rather sparse. ... >> a sparse qr or sparse svd should work. ... >> netlib, lsqr, or similar methods for approximating the best linear least squares ... >I'm surprised that there aren't any high capacity linear regression ...
    (sci.math.num-analysis)
  • Re: Linear least squares using SVD
    ... >instead of using the normal equations". ... SVD would then be applied to the 256x256 linear ... NR is recommending that you solve ... the overdetermined 300,000 by 256 least squares problem with the SVD. ...
    (sci.math.num-analysis)
  • Re: Linear regression vs SVD
    ... least squares minimizes deivations from y, which is not the same as ... the svd. ... Note that in least squares, b=1, which isn't a constraint in ...
    (sci.stat.math)
  • Re: Linear least squares using SVD
    ... > I would like to do a least squares fit and compute the weights of 256 ... we recommend that you always use SVD techniques ... Is NR just recommeding SVD for solving least squared problems over ... NR is saying SVD is the most accurate method, albeit slow. ...
    (sci.math.num-analysis)