An Algebraic and Combinatorial Perspective on Rank-one Tensor Completion

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.