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

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Sep 2023.

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

- [On the Geometry and Optimization of Polynomial Convolutional Networks](https://mlsanity.com/paper/2410.00722/) (2024)
- [Algebraic Complexity and Neurovariety of Linear Convolutional Networks](https://mlsanity.com/paper/2401.16613/) (2024)
- [A Framework for Reducing the Complexity of Geometric Vision Problems and its Application to Two-View Triangulation with Approximation Bounds](https://mlsanity.com/paper/2503.08142/) (2025)

## Abstract (arXiv)

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.