Welcome to MathOverflow

Question

2

1

Hi All

My question is about the well known and well studied singular value decomposition (SVD). What I am working on right now requires performing an SVD repeatedly on a slowly varying matrix. Since I don't need an exact decomposition at every iteration, I was wondering whether there are any statistical estimations of the SVD. I found a paper on estimating the maximal eigenvalue of a matrix with non-negative values using Markov chains (http://www.maik.ru/full/rusmath/97/5/rusmath5_97p46full.pdf). Are there any more general statistical estimation techniques?

Thanks

flag	asked Dec 27 2010 at 3:37 Bernard 63●3

	How does your matrix vary? There are updating algorithms for SVD (which are much cheaper than generating an SVD ab initio per iteration), but without knowing how your matrix changes, I wouldn't know if they're applicable. – J. M. Dec 27 2010 at 3:50
	@ J.M.: The matrix is an error matrix that varies in a complex way. There is dependence on other variables, so I can't model how the variation goes. I can say that the change is small, so can you refer me to the SVD update algorithms you had in mind? Thanks – Bernard Dec 27 2010 at 13:04
	What I had in mind was intended for "low rank" updates; if you are unable to write your "perturbation" in terms of a simple matrix, then you certainly can't use any of those updating methods. This is an interesting problem... – J. M. Dec 28 2010 at 0:47

Igor Rivin · Answer 1 · 2010-12-27 03:55:15Z UTC

1

The question does not seem to be completely well-defined: Is your matrix dense? Sparse? Do you need the singular vectors or just the singular values? Do you need ALL the singular values or just the top few? What do you mean by "statistical estiamtion techniques", and why are these relevant? If your matrix is "slowly varying", then perturbation theory should be your friend: look up the formulas in Kato's "Perturbation theory" (p. 79, if memory serves), and apply them to $A^t A.$ Now, I have no idea how much faster this is then computing the SVD from scratch -- this depends on your problem structure (see the questions at the beginning of this answeer...)

answered Dec 27 2010 at 3:55

Igor Rivin
31.3k●3●37●71

Let me rephrase the question. Given an mxn matrix A, I need to compute the largest k singular values and vectors (U, $\Sigma$ and V). Are there any available randomized techniques that can estimate these values and vectors, whose computational complexity is better than the deterministic technique of SVD? I found this paper: cims.nyu.edu/~tygert/randsurvey.pdf. It shows 2 algorithms that can estimate the SVD but indirectly. It does so by first performing a randomized interpolative decomposition (ID). Does anyone know of a randomized technique that estimates SVD directly? – Bernard Dec 27 2010 at 5:15

1

@Ben: I presume you've seen dx.doi.org/10.1093/comjnl/30.3.268 and dx.doi.org/10.1109/TPAMI.1982.4767324 and did not find them suitable? – J. M. Dec 27 2010 at 6:08

@ J.M.: The randomization techniques I referred to show that they are more efficient than the SVD power algorithm mentioned in the papers you suggested. – Bernard Dec 27 2010 at 13:02

Statistical estimation of singular values and vectors

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.