Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
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 '10 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 '10 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 '10 at 0:47
add comment

1 Answer

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

share|improve this answer
    
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 '10 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 '10 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 '10 at 13:02
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.