An Algebraic and Combinatorial Perspective on Rank-one Tensor Completion
Loading...
URL
Journal Title
Journal ISSN
Volume Title
Perustieteiden korkeakoulu |
Master's thesis
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.
Authors
Date
2018-12-04
Department
Major/Subject
Applied Mathematics
Mcode
SCI3053
Degree programme
Master’s Programme in Mathematics and Operations Research
Language
en
Pages
63
Series
Abstract
We investigate matrix completion and tensor completion from two different ap- proaches. Matrix completion is introduced as a particular instance of the Rank Minimization Problem, and a heuristic for solving this optimization problem is induced by the nuclear norm of a matrix [9]. Minimizing the nuclear norm of matrices agreeing with a set of observed entries yields a reconstruction of low rank. Moreover, we explore some guarantees on the least number of entries that allow exact reconstruction [6]. The same problem is studied using the tools of algebra and combinatorics. A cor- respondence between partial matrices and bipartite graphs allows certain prop- erties of bipartite graphs to characterize completion to rank one [13]. Moreover, a local approach for completion is possible and the finitely completable entries from a partial matrix are computed by a matroid closure [22]. An analogous development is considered for the case of tensor completion. For- mulating an optimization approach for tensor completion leads us to study the rank and nuclear norm for tensors. Computing these quantities, as well as other tensor properties, was found to be an NP-hard problem [10, 28]. However, effi- cient heuristics for tensor completion based on the nuclear norm of the flattenings of a tensor have been proposed in [11, 19, 30, 37, 41]. The algebraic and combinatorial approach is revisited for rank-one tensor com- pletion. A characterization of rank one tensors using minors can be described as the kernel of a parameterization map. Generated by binomials, the kernel reveals connections to toric geometry and other combinatorial objects that are used to describe the conditions for rank-one tensor completion [21].Tässä työssä tarkastellaan kahta eri tapaa matriisien ja tensorien täydentämiseksi. Matriisien täydennys voidaan esittää eräänä matriisin asteen minimointiongelmana, jolle esitellään heuristinen ratkaisumenetelmä matriisin ydinnormin indusoimana [9]. Matriisin ydinnormin minimointi havaittujen matriisialkioiden mukaan tuottaa matalan asteen rekonstruoinnin. Riittäviä ehtoja täydelliseen rekonstruointiin tutkitaan [6]. Samaa ongelmaa tutkitaan algebran ja kombinatoriikan työkaluilla. Osittaisten matriisien ja kaksipuolisten verkkojen välinen yhdenmukaisuus mahdollistaa ensimmäisen kertaluvun täydennyksen karakterisoinnin kaksipuolisten verkkojen ominaisuuksien kautta [13]. Lisäksi, lokaali täydennys on mahdollista, ja äärellisesti täydellistyvät alkiot osittaisesta matriisista voidaan laskea matroidin sulkeuman avulla [22]. Työssä myös tarkastellaan analogisia menetelmiä tensorien täydentämiseksi. Vastaavan optimointiongelman kehittäminen johtaa tensorien kertaluvun sekä ydinnormin tutkimiseen. Näiden sekä muiden tensorien ominaisuuksien laskeminen osoittautuu NP-vaikeaksi [10, 28]. Kuitenkin tehokkaita ydinnormiin ja tensorien litistykseen perustuvia heuristisia menetelmiä tensorien täydennykseen on esitetty [11, 19, 30, 37, 41]. Algebrallisiin ja kombinatorisiin menetelmiin palataan ensimmäisen kertaluvun tensorien täydennyksen yhteydessä. Tällaiset tensorit voidaan karakterisoida.Description
Supervisor
Kubjas, KaieThesis advisor
Kubjas, KaieKeywords
rank minimization, nuclear norm, matrix completion, tensor completion, rank-one completion