File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Non-convex matrix completion and related problems via strong duality

TitleNon-convex matrix completion and related problems via strong duality
Authors
KeywordsMatrix completion
Matrix factorization
Non-convex optimization
Robust principal component analysis
Sample complexity
Strong duality
Issue Date2019
Citation
Journal of Machine Learning Research, 2019, v. 20 How to Cite?
AbstractThis work studies the strong duality of non-convex matrix factorization problems: we show that under certain dual conditions, these problems and the 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 prove that under certain dual conditions, the optimal solution of the matrix factorization program is the same as that of 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 is 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. These are examples of efficiently recovering a hidden matrix given limited reliable observations. Our framework shows that exact recoverability and strong duality hold with nearly-optimal sample complexity for the two problems.
Persistent Identifierhttp://hdl.handle.net/10722/341255
ISSN
2023 Impact Factor: 4.3
2023 SCImago Journal Rankings: 2.796

 

DC FieldValueLanguage
dc.contributor.authorBalcan, Maria Florina-
dc.contributor.authorLiang, Yingyu-
dc.contributor.authorSong, Zhao-
dc.contributor.authorWoodruff, David P.-
dc.contributor.authorZhang, Hongyang-
dc.date.accessioned2024-03-13T08:41:23Z-
dc.date.available2024-03-13T08:41:23Z-
dc.date.issued2019-
dc.identifier.citationJournal of Machine Learning Research, 2019, v. 20-
dc.identifier.issn1532-4435-
dc.identifier.urihttp://hdl.handle.net/10722/341255-
dc.description.abstractThis work studies the strong duality of non-convex matrix factorization problems: we show that under certain dual conditions, these problems and the 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 prove that under certain dual conditions, the optimal solution of the matrix factorization program is the same as that of 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 is 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. These are examples of efficiently recovering a hidden matrix given limited reliable observations. Our framework shows that exact recoverability and strong duality hold with nearly-optimal sample complexity for the two problems.-
dc.languageeng-
dc.relation.ispartofJournal of Machine Learning Research-
dc.subjectMatrix completion-
dc.subjectMatrix factorization-
dc.subjectNon-convex optimization-
dc.subjectRobust principal component analysis-
dc.subjectSample complexity-
dc.subjectStrong duality-
dc.titleNon-convex matrix completion and related problems via strong duality-
dc.typeArticle-
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.scopuseid_2-s2.0-85072624374-
dc.identifier.volume20-
dc.identifier.eissn1533-7928-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats