Publication:2099276

DOI10.1016/J.JCO.2022.101698zbMATH Open1498.11111arXiv2109.04772OpenAlexW4289597569MaRDI QIDQ2099276FDOQ2099276

Paria Abbasi, Andreas Klingler, Tim Netzer, Sander Gribling

Publication date: 23 November 2022

Published in: Journal of Complexity (Search for Journal in Brave)

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 $mathbbC$ 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 $varepsilon$-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.

Full work available at URL: https://arxiv.org/abs/2109.04772

zbMATH Keywords

semidefinite programmingapproximationsums of squaresPythagoras number

Mathematics Subject Classification ID

Semidefinite programming (90C22) Sums of squares and representations by other particular quadratic forms (11E25) Fields related with sums of squares (formally real fields, Pythagorean fields, etc.) (12D15)

Cites Work

• The Pythagoras number of some affine algebras and local algebras.
• Sum of squares length of real forms
• Zur Darstellung definiter Funktionen als Summe von Quadraten. (To the representation of definite functions as the sum of squares)
• Title not available (Why is that?)
• Title not available (Why is that?)

This page was built for publication: Approximate Pythagoras numbers on \(\ast\)-algebras over \(\mathbb{C}\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2099276)