A new Algorithm for Overcomplete Tensor Decomposition based on Sums-of-Squares Optimisation

2018/12/13 by Blomenhofer, Alexander Taveira
#65D32 (Primary) #Algebraic Geometry (math.AG) #FOS: Mathematics #Numerical Analysis (math.NA) #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.1812.05565

Abstract

In this thesis, a new class of algorithms based on Sums of Squares Programming is developed. These allow to reduce a degree-d homogeneous polynomial T = ∑_{i = 1}^m ⟨ a_i, X ⟩^d to a quadratic form being close to a rank-1 form via a low-degree reduction polynomial W∈∑ ℝ[X]². W can be thought of as a `weight function' attaining high values on merely one of the components a_i. The component can then be extracted by running an eigenvalue decomposition on the quadratic form ∑_i=1^m W(a_i) ⟨ a_i, X ⟩².

Related

• Polynomial-time Tensor Decompositions with Sum-of-Squares
• Minimizing Polynomials via Sum of Squares over the Gradient Ideal
• Weak Decoupling, Polynomial Folds, and Approximate Optimization over the Sphere
• Eigenvectors of tensors and algorithms for Waring decomposition
• A Faster Interior-Point Method for Sum-of-Squares Optimization