Error Analysis of the Gram Low-Rank Approximation (and Why it is Not as Unstable as One May Think)

Given [Formula: see text] and its singular value decomposition (SVD) [Formula: see text], the eigenvalue decomposition (EVD) of the Gram matrix [Formula: see text] is [Formula: see text]. When [Formula: see text], it is computationally attractive to compute the truncated SVD of [Formula: see text] from the truncated EVD of [Formula: see text]. This idea has in particular been used to efficiently compress low-rank tensors. In finite precision arithmetic, however, there is a good reason to fear instability from this approach, since the Gram matrix [Formula: see text] has condition number [Formula: see text]. We carry out an error analysis of this approach that uses eigenvector perturbation theory. We first explain that a naive application of standard results from this theory leads to an error bound proportional to [Formula: see text], where [Formula: see text] is the machine precision, [Formula: see text] is the matrix truncated to the target rank [Formula: see text], and [Formula: see text] is its generalized condition number. Importantly, this bound is pessimistic and we prove that we can significantly improve it with a more careful analysis. Specifically, we obtain two improvements: First, we show that the error bound is at most proportional to [Formula: see text], instead of [Formula: see text]. Second, we show that regardless of how large [Formula: see text] is, the error cannot exceed a constant multiple of [Formula: see text]. Hence our final bound is of order [Formula: see text]. Moreover, we also propose the use of iterative refinement to further improve the accuracy in some cases. We illustrate the unusual and attractive behavior of this algorithm with numerical experiments that showcase its effectiveness, despite its partial instability. We believe that our results explain the success that this approach has encountered in large scale tensor computations.