File Download
There are no files associated with this item.
Supplementary
-
Citations:
- Scopus: 0
- Appears in Collections:
Conference Paper: Recovery guarantee of weighted low-rank approximation via alternating minimization
Title | Recovery guarantee of weighted low-rank approximation via alternating minimization |
---|---|
Authors | |
Issue Date | 2016 |
Citation | 33rd International Conference on Machine Learning, ICML 2016, 2016, v. 5, p. 3504-3526 How to Cite? |
Abstract | Many applications require recovering a ground truth low-rank matrix from noisy observations of the entries, which in practice is typically formulated as a weighted low-rank approximation problem and solved by non-convex optimization heuristics such as alternating minimization. In this paper, we provide provable recovery guarantee of weighted low-rank via a simple alternating minimization algorithm. In particular, for a natural class of matrices and weights and without any assumption on the noise, we bound the spectral norm of the difference between the recovered matrix and the ground truth, by the spectral norm of the weighted noise plus an additive error term that decreases exponentially with the number of rounds of alternating minimization, from either initialization by SVD or, more importantly, random initialization. These provide the first theoretical results for weighted low-rank approximation via alternating minimization with non- binary deterministic weights, significantly generalizing those for matrix completion, the special case with binary weights, since our assumptions are similar or weaker than those made in existing works. Furthermore, this is achieved by a very simple algorithm that improves the vanilla alternating minimization with a simple clipping step.copyright |
Persistent Identifier | http://hdl.handle.net/10722/341196 |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Li, Yuanzhi | - |
dc.contributor.author | Liang, Yingyu | - |
dc.contributor.author | Risteski, Andrej | - |
dc.date.accessioned | 2024-03-13T08:40:56Z | - |
dc.date.available | 2024-03-13T08:40:56Z | - |
dc.date.issued | 2016 | - |
dc.identifier.citation | 33rd International Conference on Machine Learning, ICML 2016, 2016, v. 5, p. 3504-3526 | - |
dc.identifier.uri | http://hdl.handle.net/10722/341196 | - |
dc.description.abstract | Many applications require recovering a ground truth low-rank matrix from noisy observations of the entries, which in practice is typically formulated as a weighted low-rank approximation problem and solved by non-convex optimization heuristics such as alternating minimization. In this paper, we provide provable recovery guarantee of weighted low-rank via a simple alternating minimization algorithm. In particular, for a natural class of matrices and weights and without any assumption on the noise, we bound the spectral norm of the difference between the recovered matrix and the ground truth, by the spectral norm of the weighted noise plus an additive error term that decreases exponentially with the number of rounds of alternating minimization, from either initialization by SVD or, more importantly, random initialization. These provide the first theoretical results for weighted low-rank approximation via alternating minimization with non- binary deterministic weights, significantly generalizing those for matrix completion, the special case with binary weights, since our assumptions are similar or weaker than those made in existing works. Furthermore, this is achieved by a very simple algorithm that improves the vanilla alternating minimization with a simple clipping step.copyright | - |
dc.language | eng | - |
dc.relation.ispartof | 33rd International Conference on Machine Learning, ICML 2016 | - |
dc.title | Recovery guarantee of weighted low-rank approximation via alternating minimization | - |
dc.type | Conference_Paper | - |
dc.description.nature | link_to_subscribed_fulltext | - |
dc.identifier.scopus | eid_2-s2.0-84998881881 | - |
dc.identifier.volume | 5 | - |
dc.identifier.spage | 3504 | - |
dc.identifier.epage | 3526 | - |