Low-rank matrix approximation in the infinity norm (Q2273885)

The authors investigate the \(\ell_\infty\) LRA problem: ``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}|\).'' They are mostly concerned with the case \(r = 1\). Their main results are: 1) if the sign pattern of \(X\) is known, then the decision version of rank-one \(\ell_\infty\) LRA can be solved in polynomial time by finding a solution to a system of linear inequalities; 2) the rank-one \(\ell_\infty\) LRA is NP-complete. The authors also propose a simple heuristic algorithm.