A note on error bounds for pseudo skeleton approximations of matrices

DOI10.1016/J.LAA.2023.03.024zbMATH Open1514.65051arXiv2107.01819MaRDI QIDQ6046077FDOQ6046077

Authors: F. R. De Hoog, Markus Hegland 

Publication date: 15 May 2023

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

Abstract: Due to their importance in both data analysis and numerical algorithms, low rank approximations have recently been widely studied. They enable the handling of very large matrices. Tight error bounds for the computationally efficient Gaussian elimination based methods (skeleton approximations) are available. In practice, these bounds are useful for matrices with singular values which decrease quickly. Using the Chebyshev norm, this paper provides improved bounds for the errors of the matrix elements. These bounds are substantially better in the practically relevant cases where the eigenvalues decrease polynomially. Results are proven for general real rectangular matrices. Even stronger bounds are obtained for symmetric positive definite matrices. A simple example is given, comparing these new bounds to earlier ones.

Full work available at URL: https://arxiv.org/abs/2107.01819

Recommendations

• New accuracy estimates for pseudoskeleton approximations of matrices
• On the existence of a nearly optimal skeleton approximation of a matrix in the Frobenius norm
• Quasioptimality of skeleton approximation of a matrix in the Chebyshev norm
• Publication:4938233
• On error bounds for eigenvalues of a matrix pencil
• Pseudo-skeleton approximations by matrices of maximal volume
• Publication:5751854
• scientific article; zbMATH DE number 6783411
• scientific article; zbMATH DE number 4063280
• scientific article; zbMATH DE number 4033921

zbMATH Keywords

low-rank matrix approximation

Mathematics Subject Classification ID

Numerical methods for low-rank matrix approximation; matrix compression (65F55)

Cites Work

• The maximal-volume concept in approximation by low-rank matrices
• On cross approximation of multi-index arrays
• Quasioptimality of skeleton approximation of a matrix in the Chebyshev norm
• On extremum properties of orthogonal quotients matrices
• Pseudo-skeleton approximations with better accuracy estimates
• On the interlacing property for singular values and eigenvalues
• Rectangular maximum-volume submatrices and their applications
• On the best approximation algorithm by low-rank matrices in Chebyshev's norm

Cited In (5)

• On the existence of a nearly optimal skeleton approximation of a matrix in the Frobenius norm
• Pseudo-skeleton approximations with better accuracy estimates
• Maximal volume matrix cross approximation for image compression and least squares solution
• Quasioptimality of skeleton approximation of a matrix in the Chebyshev norm
• New accuracy estimates for pseudoskeleton approximations of matrices

This page was built for publication: A note on error bounds for pseudo skeleton approximations of matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6046077)