TSSOS: A Moment-SOS hierarchy that exploits term sparsity
Not on the map. Why?
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.
Key facts. Cited by 14 papers in the map (data through 7 Oct 2026). First posted on arXiv 18 Dec 2019.
Builds on
No reference list yet.
Built on by
Citing papers per year: 2021: 3; 2022: 5; 2023: 2; 2024: 2; 2025: 2.
14 papers.
Sort:
- 2021Certifiably Optimal Outlier-Robust Geometric Perception: Semidefinite Relaxations and Scalable Global Optimizationcited by 21
- 2021Optimal Pose and Shape Estimation for Category-level 3D Object Perceptioncited by 15
- 2022Estimation Contracts for Outlier-Robust Geometric Perceptioncited by 11
- 2021An Inexact Projected Gradient Method with Rounding and Lifting by Nonlinear Programming for Solving Rank-One Semidefinite Relaxation of Polynomial Optimizationcited by 10
- 2022Fairness in Forecasting of Observations of Linear Dynamical Systemscited by 4
- 2022Quantum open system identification via global optimization: Optimally accurate Markovian models of open systems from time-series datacited by 3
- 2025Neural Sum-of-Squares: Certifying the Nonnegativity of Polynomials with Transformerscited by 2
- 2023Joint Problems in Learning Multiple Dynamical Systemscited by 1
- 2024Verifying Properties of Binary Neural Networks Using Sparse Polynomial Optimizationcited by 1
- 2024Interventional Causal Structure Discovery over Graphical Models with Convergence and Optimality Guaranteescited by 1
- 2025Data-Driven Safety Verification using Barrier Certificates and Matrix Zonotopescited by 1
- 2022Sparse Polynomial Optimization: Theory and Practicecited by 0
- 2025Neural Sum-of-Squares: Certifying the Nonnegativity of Polynomials with Transformers15 Oct 2025
- 2025Data-Driven Safety Verification using Barrier Certificates and Matrix Zonotopes1 Apr 2025
- 2024Interventional Causal Structure Discovery over Graphical Models with Convergence and Optimality Guarantees9 Aug 2024
- 2024Verifying Properties of Binary Neural Networks Using Sparse Polynomial Optimization27 May 2024
- 2023Joint Problems in Learning Multiple Dynamical Systems3 Nov 2023
- 2023GloptiNets: Scalable Non-Convex Optimization with Certificates26 Jun 2023
- 2022Tractable hierarchies of convex relaxations for polynomial optimization on the nonnegative orthant13 Sep 2022
- 2022Fairness in Forecasting of Observations of Linear Dynamical Systems12 Sep 2022
- 2022Sparse Polynomial Optimization: Theory and Practice23 Aug 2022
- 2022Estimation Contracts for Outlier-Robust Geometric Perception22 Aug 2022
- 2022Quantum open system identification via global optimization: Optimally accurate Markovian models of open systems from time-series data31 Mar 2022
- 2021Certifiably Optimal Outlier-Robust Geometric Perception: Semidefinite Relaxations and Scalable Global Optimization7 Sep 2021
- 2021Certifiably Optimal Outlier-Robust Geometric Perception: Semidefinite Relaxations and Scalable Global Optimizationcited by 21
- 2021Optimal Pose and Shape Estimation for Category-level 3D Object Perceptioncited by 15
- 2022Estimation Contracts for Outlier-Robust Geometric Perceptioncited by 11
- 2021An Inexact Projected Gradient Method with Rounding and Lifting by Nonlinear Programming for Solving Rank-One Semidefinite Relaxation of Polynomial Optimizationcited by 10
- 2022Fairness in Forecasting of Observations of Linear Dynamical Systemscited by 4
- 2022Quantum open system identification via global optimization: Optimally accurate Markovian models of open systems from time-series datacited by 3
- 2025Neural Sum-of-Squares: Certifying the Nonnegativity of Polynomials with Transformerscited by 2
- 2023Joint Problems in Learning Multiple Dynamical Systemscited by 1
- 2024Verifying Properties of Binary Neural Networks Using Sparse Polynomial Optimizationcited by 1
- 2024Interventional Causal Structure Discovery over Graphical Models with Convergence and Optimality Guaranteescited by 1
- 2025Data-Driven Safety Verification using Barrier Certificates and Matrix Zonotopescited by 1
- 2022Sparse Polynomial Optimization: Theory and Practicecited by 0
12 most cited of 14 All 14 (JSON)
- 2025Neural Sum-of-Squares: Certifying the Nonnegativity of Polynomials with Transformers15 Oct 2025
- 2025Data-Driven Safety Verification using Barrier Certificates and Matrix Zonotopes1 Apr 2025
- 2024Interventional Causal Structure Discovery over Graphical Models with Convergence and Optimality Guarantees9 Aug 2024
- 2024Verifying Properties of Binary Neural Networks Using Sparse Polynomial Optimization27 May 2024
- 2023Joint Problems in Learning Multiple Dynamical Systems3 Nov 2023
- 2023GloptiNets: Scalable Non-Convex Optimization with Certificates26 Jun 2023
- 2022Tractable hierarchies of convex relaxations for polynomial optimization on the nonnegative orthant13 Sep 2022
- 2022Fairness in Forecasting of Observations of Linear Dynamical Systems12 Sep 2022
- 2022Sparse Polynomial Optimization: Theory and Practice23 Aug 2022
- 2022Estimation Contracts for Outlier-Robust Geometric Perception22 Aug 2022
- 2022Quantum open system identification via global optimization: Optimally accurate Markovian models of open systems from time-series data31 Mar 2022
- 2021Certifiably Optimal Outlier-Robust Geometric Perception: Semidefinite Relaxations and Scalable Global Optimization7 Sep 2021
12 newest of 14 All 14 (JSON)