Deterministic algorithms for matrix completion
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.
- A simpler approach to matrix completion
- Exact matrix completion via convex optimization
- Expander graphs and their applications
- scientific article; zbMATH DE number 4032351 (Why is no real title available?)
- Matrix completion from noisy entries
- Nuclear-norm penalization and optimal rates for noisy low-rank matrix completion
- Ramanujan graphs
- The Power of Convex Relaxation: Near-Optimal Matrix Completion
- Twice-Ramanujan sparsifiers
- Sparse random tensors: concentration, regularization and applications
- Long time dynamics for interacting oscillators on graphs
- A divide-and-conquer algorithm for binary matrix completion
- Deterministic tensor completion with hypergraph expanders
- Spectral gap in random bipartite biregular graphs and applications
- Nonconvex deterministic matrix completion by projected gradient descent methods
This page was built for publication: Deterministic algorithms for matrix completion
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2925527)
