1
$\begingroup$

I apologize in advance if this is an ill-posed question -- I'd appreciate advice on what pieces are missing as much as an answer.

I'm solving a system like $P \approx X Y^T$, where P is a large sparse matrix, and X and Y are a low-rank (rank $k$) factorization of P. I need to solve, for example, for a row of X, $X_u$, given $P_u$ and $Y$. I'm approximating with $X_u = P_u Y (Y^T Y)^{-1}$.

I'm computing a solution for $(Y^T Y)^{-1}$ with a QR decomposition. But the matrix may be rank deficient or very nearly so. If it's nearly so, the solution for $X_u$ can be, for example, quite large -- a "bad" answer in the sense that it's much larger than any other row of $X$.

I'm examining the diagonal of $R$ in the decomposition. If it ends in 0 -- or very small values, less than some $\epsilon$ -- I conclude that $Y^T Y$ was rank deficient ($k$ was too large). This appears to generally work.

But, picking a smallish $\epsilon$ doesn't work in all cases. In some cases I find the diagonal elements are overall quite large, with values towards the end much smaller but not nearly 0 (i.e., not even < 1). I'd like to reject these cases too since they produce "bad" answers.

A single threshold is obviously not a suitable criterion. I'm looking for guidance on how to reliably detect this situation. Or better frame the question.

$\endgroup$
7
  • $\begingroup$ Tough problem. Maybe your application suggests some relevant criteria? How are you computing the QR decomposition? Householder is faster, Givens is a little more accurate. $\endgroup$
    – copper.hat
    Mar 26, 2013 at 9:27
  • $\begingroup$ Thanks @copper.hat. This is in Java and I'm using Commons Math. The implementation (grepcode.com/file/repo1.maven.org/maven2/org.apache.commons/…) uses Householder reflections. The diagonal of R is plainly decreasing, but I'm having a hard time quantifying where it becomes "very small" since no absolute threshold seems sufficient. It feels like there must be some mathematically correct-er approach. $\endgroup$
    – Sean Owen
    Mar 26, 2013 at 11:35
  • $\begingroup$ I think it depends more on the levels of 'noise' in your application? $\endgroup$
    – copper.hat
    Mar 26, 2013 at 18:27
  • $\begingroup$ If so I am not smart enough to see how.. I'm not speaking about quantizing $P$ and rounding small values to 0, but evaluating the diagonal of $R$ in the QR decomposition. $\endgroup$
    – Sean Owen
    Mar 26, 2013 at 23:22
  • $\begingroup$ Sorry, I have no good suggestions. The QR decomposition is 'well-behaved' numerically, so (roughly speaking), rank ambiguities reflect ambiguities in the data. That was all I meant by 'noise' above... $\endgroup$
    – copper.hat
    Mar 27, 2013 at 1:56

0

You must log in to answer this question.

Browse other questions tagged .