Approximate Pythagoras numbers on ⁎-algebras over C

Paria Abbasi, Sander Gribling, Andreas Klingler, Tim Netzer

Research output: Contribution to journalArticleScientificpeer-review

Abstract

The Pythagoras number of a sum of squares is the shortest length among its sums of squares representations. In many algebras, for example real polynomial algebras in two or more variables, there exists no upper bound on the Pythagoras number for all sums of squares. In this paper, we study how Pythagoras numbers in ⁎-algebras over C behave with respect to small perturbations of elements. More precisely, the approximate Pythagoras number of an element is the smallest Pythagoras number among all elements in its ε-ball. We show that these approximate Pythagoras numbers are often significantly smaller than their exact versions, and allow for (almost) dimension-independent upper bounds. Our results use low-rank approximations for Gram matrices of sums of squares and estimates for the operator norm of the Gram map.

Original languageEnglish
Article number101698
Number of pages12
JournalJournal of Complexity
Volume74
DOIs
Publication statusPublished - Feb 2023
Externally publishedYes

Keywords

  • Pythgoras number
  • Sums of squares
  • approximation
  • Semidefinite programming

Fingerprint

Dive into the research topics of 'Approximate Pythagoras numbers on ⁎-algebras over C'. Together they form a unique fingerprint.

Cite this