Low-Rank Matrix Approximation in the Infinity Norm

Abstract

The low-rank matrix approximation problem with respect to the entry-wise ${\ell }_{\infty }$-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 ${\max }_{i,j}|M_{ij}-X_{ij}|$. 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.

12 pages, 3 tables

References in corpus (1)

• Algorithms for ${\ell }_p$ Low Rank Approximation

Cited by in corpus (7)

• On the distance to low-rank matrices in the maximum norm
• Simple and practical algorithms for ${\ell }_p$-norm low-rank approximation
• Entrywise tensor-train approximation of large tensors via random embeddings
• Optimal approximation of a large matrix by a sum of projected linear mappings on prescribed subspaces
• Quasioptimal alternating projections and their use in low-rank approximation of matrices and tensors
• When big data actually are low-rank, or entrywise approximation of certain function-generated matrices
• Impact of spatial coarsening on Parareal convergence for the linear advection equation