# TSSOS: A Moment-SOS hierarchy that exploits term sparsity

arXiv: https://arxiv.org/abs/1912.08899 · HTML: https://mlsanity.com/paper/1912.08899/

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Dec 2019.

## Built on by (most cited first, 14 of 14)

- [Certifiably Optimal Outlier-Robust Geometric Perception: Semidefinite Relaxations and Scalable Global Optimization](https://mlsanity.com/paper/2109.03349/) (2021)
- [Optimal Pose and Shape Estimation for Category-level 3D Object Perception](https://mlsanity.com/paper/2104.08383/) (2021)
- [Estimation Contracts for Outlier-Robust Geometric Perception](https://mlsanity.com/paper/2208.10521/) (2022)
- [An Inexact Projected Gradient Method with Rounding and Lifting by Nonlinear Programming for Solving Rank-One Semidefinite Relaxation of Polynomial Optimization](https://mlsanity.com/paper/2105.14033/) (2021)
- [Fairness in Forecasting of Observations of Linear Dynamical Systems](https://mlsanity.com/paper/2209.05274/) (2022)
- [Quantum open system identification via global optimization: Optimally accurate Markovian models of open systems from time-series data](https://mlsanity.com/paper/2203.17164/) (2022)
- [Neural Sum-of-Squares: Certifying the Nonnegativity of Polynomials with Transformers](https://mlsanity.com/paper/2510.13444/) (2025)
- [Joint Problems in Learning Multiple Dynamical Systems](https://mlsanity.com/paper/2311.02181/) (2023)
- [Verifying Properties of Binary Neural Networks Using Sparse Polynomial Optimization](https://mlsanity.com/paper/2405.17049/) (2024)
- [Interventional Causal Structure Discovery over Graphical Models with Convergence and Optimality Guarantees](https://mlsanity.com/paper/2408.04819/) (2024)
- [Data-Driven Safety Verification using Barrier Certificates and Matrix Zonotopes](https://mlsanity.com/paper/2504.01007/) (2025)
- [Sparse Polynomial Optimization: Theory and Practice](https://mlsanity.com/paper/2208.11158/) (2022)
- [Tractable hierarchies of convex relaxations for polynomial optimization on the nonnegative orthant](https://mlsanity.com/paper/2209.06175/) (2022)
- [GloptiNets: Scalable Non-Convex Optimization with Certificates](https://mlsanity.com/paper/2306.14932/) (2023)

## Abstract (arXiv)

This paper is concerned with polynomial optimization problems. We show how to exploit term (or monomial) sparsity of the input polynomials to obtain a new converging hierarchy of semidefinite programming relaxations. The novelty (and distinguishing feature) of such relaxations is to involve block-diagonal matrices obtained in an iterative procedure performing completion of the connected components of certain adjacency graphs. The graphs are related to the terms arising in the original data and not to the links between variables. Our theoretical framework is then applied to compute lower bounds for polynomial optimization problems either randomly generated or coming from the networked systems literature.