0

Low-Rank Matrix Approximation in the Infinity Norm

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}|$.

Open
Year
2017
ArXiv
arxiv.org/abs/1706.00078
Hosting
Abstract onlyARXIV-DEFAULT

Cite

Notes

Only stored in your browser.

Attribution

Abstract & full text
arxiv.org/abs/1706.00078ARXIV-DEFAULT
TL;DR
Semantic Scholar
Attribution policy →

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.