If we want to compute Svd of matrix A we can use QR as follows
A=Q*R= Q*U*S*V, where [U,S,V]= qr(R).
However this algorithm requires calculating the Full Q and R matrices. For very large matrices that would be time consuming.
Is there a way to find only the first largest k singular values using QR decomposition? Thus no need to compute full Q?
I know tha I can use other algorithms for computing SVD such as LAN son and Arnoldo which give you the ability to compute largest k singular values. But I wanted to know of this can be accomplished by QR.
Thanks
Mina
Calculating the singular values of the matrix A amounts to calculating the (square roots of the) eigenvalues of the Hermitian matrix AA* or A*A. Typically one would reduce AA* to Hessenberg form H (O(n^3) operations using Householder reduction) and then perform QR on H. If A is real, determining the QR factorisation requires O(n) operations and hence shouldn't be a bottleneck. Nonetheless, it is certainly possible to avoid storing either Q or R in the QR eigenvalue algorithm by simply applying appropriate Givens rotations to H followed by some deflation procedure. This would also allow you to halt the procedure after finding a sufficient number of eigenvalues. I recommend that you look at Golub and Van Loan, Matrix Computations. It describes this procedure in detail (and others for finding the SVD of A).
Calculating the singular values of the matrix A amounts to calculating the (square roots of the) eigenvalues of the Hermitian matrix AA* or A*A. Typically one would reduce AA* to Hessenberg form H (O(n^3) operations using Householder reduction) and then perform QR on H. If A is real, determining the QR factorisation requires O(n) operations and hence shouldn't be a bottleneck. Nonetheless, it is certainly possible to avoid storing either Q or R in the QR eigenvalue algorithm by simply applying appropriate Givens rotations to H followed by some deflation procedure. This would also allow you to halt the procedure after finding a sufficient number of eigenvalues. I recommend that you look at Golub and Van Loan, Matrix Computations. It describes this procedure in detail (and others for finding the SVD of A).
Thank you for your reply,
I am aware for the process but can we use QR algorithm to find a truncated SVD for the largest k singular-values? I am interested in the orthogonal basis corresponding to the largest singular-values.
Thanks
I presume you are trying to solve some ill-conditioned linear algebraic equations using SVD and QR. If this is so, you may wish to consider an alternative approach in which a small parameter (epsilon) is added to the diagonal of the coefficient matrix and then attempting a direct solution of the epsilon modified matrix by QR or any other direct method. The theory behind this is presented in the following publications:
Ojalvo, I.U., “Improved solutions for ill-conditioned algebraic equations by epsilon decomposition, AIAA J., 1991, Vol 29, pp. 2274-2277,
Ojalvo, I.U. & Zhang L-M, “Tutorial: Fundamentals of Ill-Conditioning”, 1993 Modal Analysis (ASTM IMAC), Vol 8, No. 2, pp. 165-176
As to how to choose epsilon, pick something large enough such that ill-conditioning is not a problem, yet small enough such that your results are sufficiently accurate.
If you're interested in the orthogonal basis corresponding to the largest singular-values for a large-scale matrix, the most reasonable thing is to use large-scale SVD algorithms. For instance, the Golub-Kahan-Bidiagonalization approaches (Golub/van Loan: Matrix Computations, 4th edition, Chapter 10.4). I think the way through the QR-factorization won't work in the large scale case, unless A is tall and very very skinny.
- Badges
- Science topic
- Similar topics
- Computer Science and Engineering
- Algorithms