Estimating singular values from QR decomposition

[vibe3]

I have a matrix for which I know its QR decomposition: $A = QR$. I want to estimate the largest and smallest singular values of $A$ ($\sigma_1$ and $\sigma_n$) however in my application it is too expensive to compute the full SVD of $A$.

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
$$\left| \prod_i r_{ii} \right| = \prod_i \sigma_i$$
where $r_{ii}$ are the diagonal entries of $R$. I'm not sure if this implies that the singular values of $R$ are the same as the singular values of $A$. If that's true, it might be possible and less expensive for my application to compute $SVD(R)$ rather than $SVD(A)$.

 

[jasonRF]

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

 

[vibe3]

The problem is that my matrix $A$ is very ill-conditioned, so computing eigenvalues from $A^T A$ 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 $A = QR = U \Sigma V^T$. Then suppose the SVD of $R$ is $R = U_r \Sigma_r V_r^T$.

Because $Q$ is orthogonal, $A = Q U_r \Sigma_r V_r^T$ which implies $U = Q U_r$ and $V = V_r$. This would then mean that $\Sigma = \Sigma_r$ and so the singular values of $R$ and $A$ are the same. Is this correct logic?

 

[rs1n]

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

Did you meant to write that the singular values of A are the square root of the eigenvalues of $A^HA$ ?

 

[rs1n]

The problem is that my matrix $A$ is very ill-conditioned, so computing eigenvalues from $A^T A$ 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 $A = QR = U \Sigma V^T$. Then suppose the SVD of $R$ is $R = U_r \Sigma_r V_r^T$.

Because $Q$ is orthogonal, $A = Q U_r \Sigma_r V_r^T$ which implies $U = Q U_r$ and $V = V_r$. This would then mean that $\Sigma = \Sigma_r$ and so the singular values of $R$ and $A$ are the same. Is this correct logic?

Yes, this is mathematically sound. A and R would have the same singular values.

 

[jasonRF]

Did you meant to write that the singular values of A are the square root of the eigenvalues of $A^HA$ ?

oops. yep.