Maximal Volume Matrix Cross Approximation for Image Compression and
  Least Squares Solution
Kenneth Allen Ming-Jun Lai Zhaiming Shen
We study the classic cross approximation of matrices based on the maximal
volume submatrices. Our main results consist of an improvement of a classic
estimate for matrix cross approximation and a greedy approach for finding the
maximal volume submatrices. Indeed, we present a new proof of a classic
estimate of the inequality with an improved constant. Also, we present a family
of greedy maximal volume algorithms which improve the error bound of cross
approximation of a matrix in the Chebyshev norm and also improve the
computational efficiency of classic maximal volume algorithm. The proposed
algorithms are shown to have theoretical guarantees of convergence. Finally, we
present two applications: one is image compression and the other is least
squares approximation of continuous functions. Our numerical results in the end
of the paper demonstrate the effective performances of our approach.