zbMATH — the first resource for mathematics

Fast and near-optimal matrix completion via randomized basis pursuit. (English) Zbl 1269.15031
Ji, Lizhen (ed.) et al., Fifth international congress of Chinese mathematicians. Proceedings of the ICCM ’10, Beijing, China, December 17–22, 2010. Part 2. Providence, RI: American Mathematical Society (AMS); Somerville, MA: International Press (ISBN 978-0-8218-7587-2/pbk; 978-0-8218-7555-1/set). AMS/IP Studies in Advanced Mathematics 51, pt.2, 859-881 (2012).
Summary: Motivated by the philosophy and phenomenal success of compressed sensing, the problem of reconstructing a matrix from a sampling of its entries has attracted much attention recently. Such a problem can be viewed as an information-theoretic variant of the well-studied matrix completion problem, and the main objective is to design an efficient algorithm that can reconstruct a matrix by inspecting only a small number of its entries. Although this is an impossible task in general, Candès and co-authors have recently shown that under a so-called incoherence assumption, a rank \(rn\times n\) matrix can be reconstructed using semidefinite programming (SDP) after one inspects \(O(nr\log^6n)\) of its entries.
In this paper we propose an alternative approach that is much more efficient and can reconstruct a larger class of matrices by inspecting a significantly smaller number of the entries. Specifically, we first introduce a class of matrices, which we call stable matrices, and show that it includes all those that satisfy the incoherence assumption. Then, we propose a randomized basis pursuit (RBP) algorithm and show that it can reconstruct a stable rank \(rn\times n\) matrix after inspecting \(O(nr \log n)\) of its entries. Our sampling bound is only a logarithmic factor away from the information-theoretic limit and is essentially optimal. Moreover, the runtime of the RBP algorithm is bounded by \(O(nr^2\log n+n^2r)\), which compares very favorably with the \(\Omega(n^4r^2 \log^{12}n)\) runtime of the SDP-based algorithm. Perhaps more importantly, our algorithm will provide an exact reconstruction of the input matrix in strongly polynomial time if the matrix entries are rational. By contrast, the SDP-based algorithm can only provide an approximate one in polynomial time.
For the entire collection see [Zbl 1235.00046].

15A83 Matrix completion problems
65F30 Other matrix algorithms (MSC2010)
68Q25 Analysis of algorithms and problem complexity
68W20 Randomized algorithms
PDF BibTeX Cite
Full Text: arXiv