On the distance to low-rank matrices in the maximum norm (Q6204176)

Given an \(m\times n\) real matrix \(A\), the author considers upper bounds for the quantity \[d_r(X)=\inf\{\|X-Y\|_{max}: rank(Y)=r\},\] where the maximum norm is defined as the maximum of the entries in modulus. Two upper bounds are given for \(d_r(X)\), where the underlying matrices that are not full rank and whose column and row spaces are incoherent. The proofs make use of Johnson-Lindenstrauss lemma and the Hanson-Wright inequality. Numerical experiments are included. As remarked by the author, this is the first extensive numerical study of low-rank matrix approximation in the maximum norm.