Deterministic algorithms for matrix completion (Q2925527)

Let \(Y\) be a real \(n\times n\) matrix for which we only know the entries at a set \(S\) of positions. The objective of the matrix completion problem is to find a matrix \(X\) lying within a restricted class (for example, \(X\) may be restricted by the rank or trace norm) such that \(X\) is close to \(Y\) in a suitable sense. In typical applications we predict preferences in movies from a knowledge of past viewing choices (the Netflix challenge) or predict unknown values from partial experimental data (see, for example [\textit{N. Srebro} and \textit{A. Shraibman}, Lect. Notes Comput. Sci. 3559, 545--560 (2005; Zbl 1137.68563)]). Since the appearance of the latter paper there have been various analyses of the completion problem under the assumption that \(S\) is a randomly chosen set of positions.NEWLINENEWLINEIn the current paper, the authors consider the case where we are allowed to choose \(S\) (before knowing the values of the corresponding entries of \(Y\)). They propose choosing a \(d\)-regular expander graph \(G\) on the set\(\left\{ 1,\dots,n\right\} \) and then taking \(S\) as the set of edges of \(G\). The largest eigenvalue of the adjacency matrix of \(G\) is equal to \(d\); let \(\lambda\) be the maximum in absolute value of the remaining eigenvalues. For a suitable choice of \(G\) (for example, if \(G\) is a Ramanujan expander), it is possible to choose \(G\) so that \(\lambda=O(\sqrt{d})\). In this case, the authors prove that it is possible to find \(X\) such that the Frobenius norm \(\left\| Y-X\right\| \;\) is bounded by \(O(nd^{-1/4}\gamma_{2}(Y))\), where \(\gamma_{2}(Y)\) denotes the \(\gamma_{2}\)-norm (the result stated in the paper is more precise). Further results and conjectures are included.