# Maximal Volume Matrix Cross Approximation for Image Compression and Least Squares Solution

arXiv: https://arxiv.org/abs/2309.17403 · HTML: https://mlsanity.com/paper/2309.17403/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 5 of its 44 references that are in the map.
- First posted on arXiv 29 Sep 2023.

## Builds on (most cited first, 5 of 5)

- [Optimal CUR Matrix Decompositions](https://mlsanity.com/paper/1405.7910/) (2014)
- [Rapid Robust Principal Component Analysis: CUR Accelerated Inexact Low Rank Estimation](https://mlsanity.com/paper/2010.07422/) (2020)
- [Mode-wise Tensor Decompositions: Multi-dimensional Generalizations of CUR Decompositions](https://mlsanity.com/paper/2103.11037/) (2021)
- [Matrix Completion with Cross-Concentrated Sampling: Bridging Uniform Sampling and CUR Sampling](https://mlsanity.com/paper/2208.09723/) (2022)
- [Orthogonal Rank-One Matrix Pursuit for Low Rank Matrix Completion](https://mlsanity.com/paper/1404.1377/) (2014)

## Abstract (arXiv)

We study the classic matrix cross approximation based on the maximal volume submatrices. Our main results consist of an improvement of the classic estimate for matrix cross approximation and a greedy approach for finding the maximal volume submatrices. More precisely, we present a new proof of the classic estimate of the inequality with an improved constant. Also, we present a family of greedy maximal volume algorithms to improve the computational efficiency of matrix cross approximation. The proposed algorithms are shown to have theoretical guarantees of convergence. Finally, we present two applications: image compression and the least squares approximation of continuous functions. Our numerical results at the end of the paper demonstrate the effective performance of our approach.