An algebraic and combinatorial perspective on rank-one tensor completion

Thumbnail Image

Files

master_Rendon_Jaramillo_Mateo_2018.pdf (520.58 KB)

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 approaches. 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 correspondence between partial matrices and bipartite graphs allows certain properties 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. Formulating 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, efficient 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 completion. 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, Kaie

Thesis advisor

Kubjas, Kaie

Keywords

rank minimization, nuclear norm, matrix completion, tensor completion, rank-one completion

Other note

Citation

Permanent link to this item

https://urn.fi/URN:NBN:fi:aalto-201812075902

Collections

[dipl] Perustieteiden korkeakoulu / SCI