Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Estimating singular values from QR decomposition

  1. Oct 24, 2015 #1
    I have a matrix for which I know its QR decomposition: [itex]A = QR[/itex]. I want to estimate the largest and smallest singular values of [itex]A[/itex] ([itex]\sigma_1[/itex] and [itex]\sigma_n[/itex]) however in my application it is too expensive to compute the full SVD of [itex]A[/itex].

    Is it possible to estimate the largest/smallest singular values from the QR decomposition? The only result I've been able to find so far is
    [tex]
    \left| \prod_i r_{ii} \right| = \prod_i \sigma_i
    [/tex]
    where [itex]r_{ii}[/itex] are the diagonal entries of [itex]R[/itex]. I'm not sure if this implies that the singular values of [itex]R[/itex] are the same as the singular values of [itex]A[/itex]. If thats true, it might be possible and less expensive for my application to compute [itex]SVD(R)[/itex] rather than [itex]SVD(A)[/itex].
     
  2. jcsd
  3. Oct 24, 2015 #2

    jasonRF

    User Avatar
    Science Advisor
    Gold Member

    The singular values of ##A## are the nonzero eigenvalues of ## A^H A ## or ## A A^H ##. The largest eigenvalue of a matrix can usually be computed using the power method with just a few iterations. The smallest eigenvalue of a full-rank matrix is the largest eigenvalue of the inverse, so again the power method can work; if you have hte QR the inverse is cheap to compute. If not full rank ... I'm not sure what clever methods there are.

    jason
     
  4. Oct 24, 2015 #3
    The problem is that my matrix [itex]A[/itex] is very ill-conditioned, so computing eigenvalues from [itex]A^T A[/itex] is unreliable (hence the reason I'm computing the QR decomposition instead). I'm looking for a numerically stable way to estimate the singular values from the QR decomposition for ill-conditioned matrices.

    Suppose we have [itex]A = QR = U \Sigma V^T[/itex]. Then suppose the SVD of [itex]R[/itex] is [itex]R = U_r \Sigma_r V_r^T[/itex].

    Because [itex]Q[/itex] is orthogonal, [itex]A = Q U_r \Sigma_r V_r^T[/itex] which implies [itex]U = Q U_r[/itex] and [itex]V = V_r[/itex]. This would then mean that [itex]\Sigma = \Sigma_r[/itex] and so the singular values of [itex]R[/itex] and [itex]A[/itex] are the same. Is this correct logic?
     
    Last edited: Oct 24, 2015
  5. Nov 4, 2015 #4
    Did you meant to write that the singular values of A are the square root of the eigenvalues of [itex] A^HA [/itex] ?
     
  6. Nov 4, 2015 #5
    Yes, this is mathematically sound. A and R would have the same singular values.
     
  7. Nov 4, 2015 #6

    jasonRF

    User Avatar
    Science Advisor
    Gold Member

    oops. yep.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Estimating singular values from QR decomposition
Loading...