The rank is one of the major characteristics of a matrix. In practice, the rank is not clear cut due to measurement errors and/or noise. Thus, determining the numerical rank of a matrix is an important problem. Many applications require numerical rank, for example, filtering noise in image processing. Basically, the problem of determining numerical rank is to separate small singular values from large ones, which can be difficult when the gap between small and large may not be obvious. There are software packages that compute numerical rank, for example, SPQR from SuiteSparseQR. In this paper, based on SPQR, the authors propose a package SPQR_RANK, which is an improvement of SPQR in that it returns an indicator of the correctness of the computed numerical rank and uses implicit sparse representation of a null space to reduce the memory requirement. It is also an extension to SPQR in that it produces linear least squares solutions, an orthonormal basis for the numerical null space of a matrix, and the complete orthogonal decomposition (COD) of a matrix.
The key to the indicator in the package is the estimates of the bounds for the errors between the estimated singular values si and the exact singular values . The error bounds used in the package are based on the following equation (page 7:21, equation (18)):
As pointed out by the authors, the &agr; in the equation is some singular value, not necessarily the ith singular value used in the package. This discrepancy may cause underestimates or overestimates. Another discrepancy appears on page 7:8, where the authors claim that the computed numerical rank is the exact numerical rank of A + E, where A is the data matrix and the size of the error E is , where is the machine precision. In numerical analysis, the error E, called backward error, depends on the algorithm in addition to the finite precision arithmetic. A backward error analysis is necessary for an upper bound of the size of E. Nevertheless, the package is a practical tool rather than a theoretical work. It is reported in the paper that the package works well despite the discrepancies.
The user should be cautious when the gap between the small singular values and the large ones is not obvious, and the differences between the upper bounds and lower bounds returned by the package are big.
This package is useful for sparse matrices that are too large for more accurate methods such as the singular value decomposition (SVD) method or SPQR_COD in the package.
