  The low-rank matrix approximation problem is ubiquitous in computational
mathematics. Traditionally, this problem is solved in spectral or Frobenius
norms, where the accuracy of the approximation is related to the rate of
decrease of the singular values of the matrix. However, recent results indicate
that this requirement is not necessary for other norms. In this paper, we
propose a method for solving the low-rank approximation problem in the
Chebyshev norm, which is capable of efficiently constructing accurate
approximations for matrices, whose singular values do not decrease or decrease
slowly.
