Article · Mathematics of Computation · December 12, 2025

On the minimal algebraic complexity of the rank-one approximation problem for general inner products

Khazhgali Kozhasov, Alan Muniz, Yang Qi, Luca Sodomaco

Abstract

We study the algebraic complexity of Euclidean Distance (ED) minimization from a generic tensor to a variety of rank-one tensors. The ED degree of the Segre-Veronese variety counts the number of complex critical points of this optimization problem. We regard this invariant as a function of inner products. We prove that Frobenius inner product is a local minimum of the ED degree, and conjecture that it is a global minimum. We prove our conjecture in the case of matrices and symmetric binary and 3 × 3 × 3 3\times 3\times 3 tensors. We discuss the above optimization problem for other algebraic varieties, classifying all possible values of the ED degree. Our approach combines tools from Singularity Theory, Morse Theory, and Algebraic Geometry.

Polynomial and algebraic computationTensor decomposition and applicationsAlgebraic Geometry and Number TheoryEuclidean distance degreerank-one tensorsSegre-Veronese varieties

On the minimal algebraic complexity of the rank-one approximation problem for general inner products

Abstract

More by Khazhgali Kozhasov