A note on error bounds for pseudo skeleton approximations of matrices

A new and improved bound for the Chebyshev norm of the error of a maximal volume pseudo-skeleton matrix approximation is presented. This bound uses all the singular values of the approximated matrix up to the r + 1st where r is the rank of the approximation. It is shown that this bound is in particular useful for the case of matrices with slowly decaying singular values where the approximation rank is of moderate size. In this case the original bounds for the maximal volume approximation are of the form (r + 1)o-r +1 and thus are very large and if o-r +1 = O(1/(r + 1)) do not even indicate convergence. A new approximation based on the truncated singular value decomposition of a maximal volume approximation is analysed. It is demonstrated that this approximation is in some cases asymptotically as a good as the truncated singular value approximation of the original matrix. This new approximation is shown to have similar approximation properties as the maximal r-volume method analysed by Osinsky and Zamarashkin (2018) [4] for the case of symmetric positive definite matrices. (c) 2023 Elsevier Inc. All rights reserved.

Automated summary

A new and improved bound for the Chebyshev norm of the error of a maximal volume pseudo-skeleton matrix approximation is proposed. This bound utilizes all the singular values of the approximated matrix up to the r + 1st rank. It is particularly useful for matrices with slowly decaying singular values and moderate-sized approximation ranks, providing better convergence indication compared to original bounds.