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

2023/09/26 by Kozhasov, Khazhgali, Muniz, Alan, Qi, Yang +1 · 2 citations
#Algebraic Geometry (math.AG) #FOS: Mathematics #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.2309.15105

Abstract

We study the algebraic complexity of Euclidean distance minimization from a generic tensor to a variety of rank-one tensors. The Euclidean Distance (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 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.

Cited by

• Nonlinear Rayleigh quotient optimization
• Parke-Taylor varieties

Related

• Maximum relative distance between real rank-two and rank-one tensors
• Uniqueness of Nonnegative Tensor Approximations
• Best approximation on semi-algebraic sets and k-border rank approximation of symmetric tensors
• How hard is the tensor rank?
• On the complexity of finding tensor ranks