Exact solutions in low-rank approximation with zeros (Q2669183)

The authors consider the problem of finding the best rank \(r\) approximation \(M'\) of a matrix \(M\), with the restriction that \(M'\) has zeroes in some fixed set of entries \(S\subset \{1,\dots,i\}\times\{1,\dots,j\}\). The solution of this structured approximation problem is not an easy consequence of results for the unstructured one, because the low rank matrices that the authors consider live in a special linear section of the corresponding secant variety. The restricted approximation problem applies to the study of non-negative approximation of matrices. The authors show how one can compute the best non-negative rank \(2\) approximation of a \(3\times 3\) matrix by considering a series of restricted approximation problems. The authors use the study of critical points for a distance function \(d_U\) in order to determine the best structured rank \(r\) approximation. For rank \(r=1\), the authors compute the number of critical points (the `Euclidean Distance degree') by a combinatorial reduction to the problem of listing minimal vertex covers of a bipartite graph. For the general case, the authors determine a bound for the dimension of the linear span of rank \(r\) critical points of \(d_U\). The authors also give a result on the unstructured approximation problem, by finding linear relations satisfied by the set of rank \(r\) critical points.