Abstract
dc:description.abstractOver a series of four articles and an introduction, a "method of pseudo-moments" is developed which gives polynomial-time tensor rank decompositions for a variety of tensor component models. Algorithms given fall into two general classes: those falling back on convex optimization, which develop the theory of polynomial-time algorithms, as well as those constructed through spectral and matrix polynomial methods, which illustrate the possibility of realizing the aforementioned polynomial-time algorithm ideas in runtimes practical for real-life inputs. Tensor component models covered include those featuring random, worst-case, generic, or smoothed inputs, as well as cases featuring overcomplete and undercomplete rank. All models are capable of tolerating substantial noise in tensor inputs, measured in spectral norm.
Degree
thesis:*- Name thesis:degree_name
- Ph. D., Computer Science
- Level thesis:degree_level
- Doctor of Philosophy
- Discipline thesis:degree_discipline
- Computer Science
- Year dc:date.issued
- 2019
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Shi, Jonathan
- Chair dc:contributor.chair
-
- Steurer, David
- Committee members dc:contributor.committeemember
-
- Kleinberg, Robert David
- Sridharan, Karthik
Rights
dc:rights- Statement dc:rights
-
- Attribution-ShareAlike 4.0 International
- Licence dc:rights.uri
- Language dc:language.iso
- en
Identifiers
dc:identifier.*- Dc Identifier Bibid
- 13119655
- Dc Identifier Other
-
ProQuest Submission ID: 11675
ProQuest Publication ID: 22615444