# Low-Rank Matrix Approximation in the Infinity Norm

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 May 2017.

## Built on by (most cited first, 5 of 5)

- [Critical Points and Convergence Analysis of Generative Deep Linear Networks Trained with Bures-Wasserstein Loss](https://mlsanity.com/paper/2303.03027/) (2023)
- [When big data actually are low-rank, or entrywise approximation of certain function-generated matrices](https://mlsanity.com/paper/2407.03250/) (2024)
- [Understanding Learning Invariance in Deep Linear Networks](https://mlsanity.com/paper/2506.13714/) (2025)
- [Discrete Optimization of Min-Max Violation and its Applications Across Computational Sciences](https://mlsanity.com/paper/2508.13437/) (2025)
- [On the Complexity of Low-Rank Matrix Signing and Entrywise Power Matrix Factorization](https://mlsanity.com/paper/2607.04875/) (2026)

## Abstract (arXiv)

The low-rank matrix approximation problem with respect to the entry-wise ℓ∞-norm is the following: given a matrix M and a factorization rank r, find a matrix X whose rank is at most r and that minimizes maxi,j |Mij - Xij|. In this paper, we prove that the decision variant of this problem for r=1 is NP-complete using a reduction from the problem `not all equal 3SAT'. We also analyze several cases when the problem can be solved in polynomial time, and propose a simple practical heuristic algorithm which we apply on the problem of the recovery of a quantized low-rank matrix.