by **Julien Langou** » Thu Mar 10, 2005 11:04 pm

James Demmel wrote

[-- Mon Mar 7 00:02:09 EST 2005 --]

When you solve a rank deficient least squares problem with the SVD,

it works as follows:

(1) compute the SVD, and set the singular values smaller than a user supplied

threshold to zero;

(2) compute the minimum norm solution of the resulting exactly rank deficient problem

So depending on the threshold, you might get very different answers.

Furthermore, if the threshold is chosen very close to a true singular value,

roundoff might cause the computed singular value to be slightly greater

than the threshold (and so kept unchanged) or slightly less than the threshold

(and so zeroed out).

So the threshold should ideally be chosen as follows:

(1) at least a small multiple of macheps*norm(A), where macheps = machine epsilon

is the roundoff error, because there is this much uncertainty in any

computed singular value

(2) at least equal to the inherent uncertainty in the input data, which

only the user can know. For example, if the data is only good to

6 decimal digits, the threshold should be at least 1e-6 * norm(A).

(3) in a "gap" in the spectrum, i.e. far from any true singular value,

so roundoff won't change the computed rank. This is hard to

tell until the routine has actually computed the singular values.

So differences in roundoff and thresholds could cause different

implementations of the routine to get very different answers.

Typically the routines report rank and the singular values themselves,

so you can check to see what happened.

Jim Demmel