SJSU Singular Matrix Database

### Accuracy of calculated singular values and calculated numerical rank

Due to computer arithmetic calculated singular values may be different from the exact singular values of A. Therefore quantities, such as the condition number, the gap, and the numerical rank that are calculated from the singular values may not be exact. For example, if the tolerance used to define the numerical rank is close to a singular value of A then small changes in A could potentially change the calculated rank. Consequently, if the tolerance is in the middle of a cluster of almost equal singular values and potential errors in A are sufficiently large, the numerical rank would not be well defined for that tolerance. On the other hand if the tolerance is near the middle of a large gap in the singular values and if potential errors in A are small, then the numerical rank is well defined for that tolerance. The numerical rank is meaningful if, for example,

• the tolerance defining the numerical rank is not too small (tolerance ≥ the Matlab default tolerance of max(m,n) * eps(norm(A)) appears to be satisfactory),
• the tolerance is within a sufficiently large gap in the singular values and
• the errors in A are sufficiently small, for example, the errors are due to computer arithmetic.

If the errors in A are due to computer arithmetic there are bounds for the errors in the calculated singular values:

• If the singular values are calculated using Matlab's routine svd and if eps represents the spacing between floating point numbers (approximately 2.2 x 10-16) then for a general matrix A the ith calculated singular value si differs from the true singular value si* by at most
| si - si*| ≤ p(m,n) eps norm(A)
where p(m,n) is a "modestly growing" function of m and n, eps indicates relative machine precision and the norm is the Euclidean norm. Therefore large singular values are computed to high relative accuracy and small ones may not be (see Section 4.9 of the LAPACK User's Guide). For this reasons in our plots of singular value spectrums singular values below the horizontal line drawn at max(m,n) * eps(norm(A)) may have little relative accuracy.
• If the singular values are calculated by spnrank, svds_err or normest_err then the errors in the calculated singular values are potentially larger since
• there is a stopping tolerance in the iterations used to calculate the singular values and
• in spnrank the iterative method is applied to a factorization of a matrix, which may introduce additional errors.
For this reason, error bounds on the calculated singular values are provided when spnrank, svds_err or normest_err are used. These error bounds are pictured in the plot of the partial singular value spectrum on the web page containing matrix details and also are a field, Problem.svals_err, when a problem is downloaded from the database. The error bounds guarantee that
| si - (an exact singular value of A+E) | ≤ Problem.svals_err(i)
where
|| E || ≤ q(m,n) eps norm(A)                                 (eqn 1)
and q(m,n) is a lower order polynomial in m and n. If one characterizes the error in A using norms, (eqn 1) is the best one can expect of a floating point computation involving matrices. The bound does not guarantee the exact singular value is the ith singular value but this is usually the case. The calculation of these bounds is based on Theorem 5.5 in Applied Numerical Linear Algebra by James Demmel.