Criterion for Determining the Numerical Rank.

The GUPTRI algorithm makes use of the SVD for determining the numerical rank. Let $A = U \Sigma V^{\ast}$ be the SVD of an $n \times n$ $A$, where $U$ and $V$ are unitary and $\Sigma = {\rm diag}(\sigma_1,\ldots,\sigma_n)$ with $0 \leq \sigma_1 \leq \cdots \leq \sigma_n$.

Given a tolerance $\epsilon$, the numerical rank of the matrix is the largest $k$ such that $\sigma_{n-k+1} > \epsilon \cdot \sigma_n$. This definition does not ensure that the rank is stable in the sense that a small perturbation relative to $\epsilon$ could cause the matrix to change rank. The rank is sensitive to perturbations if $\sigma_{n-k+1}$ is only slightly larger than $\sigma_{n-k}$. Given a constant $gap$, the requirement that $k$ should be chosen as the largest number such that $\sigma_{n-k+1} > \epsilon \cdot \sigma_n$ and $\sigma_{n-k+1} > gap \cdot \sigma_{n-k}$ is added [121,122]. In practice, $\sigma_{n-k+1} > \epsilon \Vert A\Vert _F$ is used; i.e., $\Vert A\Vert _2$ is replaced by $\Vert A \Vert _F$. If the gap criterion fails, $\sigma_{n-k}$ is also treated as zero. This process is repeated until the gap criterion is satisfied. If this is not possible, the numerical rank is not defined for the tolerance parameters $\epsilon$ and $gap$.