  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.
