Fast and Near-Optimal Matrix Completion via Randomized Basis Pursuit
| dc.creator | Zhu, Zhisu | |
| dc.creator | So, Anthony Man-Cho | |
| dc.creator | Ye, Yinyu | |
| dc.date | 2009-05-11 | |
| dc.date | 2009-05-15 | |
| dc.date.accessioned | 2026-07-07T13:14:52Z | |
| dc.date.available | 2026-07-07T13:14:52Z | |
| dc.description | 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 $r$ $n\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 so-called 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 $r$ $n\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 $Ω(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 polynomial time. By contrast, the SDP-based algorithm can only provide an approximate one in polynomial time. | |
| dc.description | 23 pages. New section (Section 3.3) added | |
| dc.identifier | https://arxiv.org/abs/0905.1546 | |
| dc.identifier | http://arxiv.org/abs/0905.1546 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/230316 | |
| dc.subject | Information Theory | |
| dc.subject | Machine Learning | |
| dc.title | Fast and Near-Optimal Matrix Completion via Randomized Basis Pursuit | |
| dc.type | text |