We develop a theory of Pseudoskeleton approximations, which approximate a matrix using only 𝑟 selected rows and 𝑟 selected columns. We prove that if a matrix admits a rank-𝑟 approximation with error 𝜀, then a Pseudoskeleton constructed from carefully chosen rows and columns achieves comparable accuracy, with explicit bounds depending on matrix size. Our analysis establishes improved lower bounds on the smallest singular values of maximal-volume submatrices of orthonormal matrices, strengthening earlier results.
Practical constructions and numerical evidence demonstrate that Pseudoskeleton approximations though might not match the accuracy of truncated SVD, but Pseudoskeleton approximation is much more interpretable than truncated SVD while using only a small subset of matrix entries, offering significant computational and storage savings for large-scale problems.
