2026-07-25T20:49:40Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8358 2024-03-06T10:42:02Z ddc:004 open_access

Matrix Completion and Related Problems via Strong Duality Balcan, Maria-Florina Liang, Yingyu Woodruff, David P. Zhang, Hongyang Non-Convex Optimization Strong Duality Matrix Completion Robust PCA Sample Complexity This work studies the strong duality of non-convex matrix factorization problems: we show that under certain dual conditions, these problems and its dual have the same optimum. This has been well understood for convex optimization, but little was known for non-convex problems. We propose a novel analytical framework and show that under certain dual conditions, the optimal solution of the matrix factorization program is the same as its bi-dual and thus the global optimality of the non-convex program can be achieved by solving its bi-dual which is convex. These dual conditions are satisfied by a wide class of matrix factorization problems, although matrix factorization problems are hard to solve in full generality. This analytical framework may be of independent interest to non-convex optimization more broadly. We apply our framework to two prototypical matrix factorization problems: matrix completion and robust Principal Component Analysis (PCA). These are examples of efficiently recovering a hidden matrix given limited reliable observations of it. Our framework shows that exact recoverability and strong duality hold with nearly-optimal sample complexity guarantees for matrix completion and robust PCA. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Maria-Florina Balcan and Yingyu Liang and David P. Woodruff and Hongyang Zhang 2018 Is Part Of LIPIcs, Volume 94, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2018.5 urn:nbn:de:0030-drops-83583 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.5 eng https://creativecommons.org/licenses/by/3.0/legalcode