Back to search

Cornell University

Tensor rank decompositions via the pseudo-moment method

Abstract

dc:description.abstract

Over 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
Language dc:language.iso
en

Identifiers

dc:identifier.*
Dc Identifier Bibid
13119655
Dc Identifier Other
ProQuest Submission ID: 11675
ProQuest Publication ID: 22615444

Chain of custody

source
Harvested from
Cornell University
Base URL
ecommons.cornell.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Shi, Jonathan. Tensor rank decompositions via the pseudo-moment method. Doctor of Philosophy thesis, 2019. https://hdl.handle.net/1813/69989