Least upper bound of truncation error of low-rank matrix approximation algorithm using QR decomposition with pivoting

Low-rank approximation by QR decomposition with pivoting (pivoted QR) is known to be less accurate than singular value decomposition (SVD); however, the calculation amount is smaller than that of SVD. The least upper bound of the ratio of the truncation error, defined by $$\Vert A-BC\Vert _2$$ , using pivoted QR to that using SVD is proved to be $$\sqrt{\frac{4^k-1}{3}(n-k)+1}$$ for $$A\in {\mathbb {R}}^{m\times n}$$ $$(m\ge n)$$ , approximated as a product of $$B\in {\mathbb {R}}^{m\times k}$$ and $$C\in {\mathbb {R}}^{k\times n}$$ in this study.