Computational complexity in algebraic regression

10/08/2019
by   Oliver Gäfvert, et al.
0

We analyze the complexity of fitting a variety, coming from a class of varieties, to a configuration of points in C^n. The complexity measure, called the algebraic complexity, computes the Euclidean Distance Degree (EDdegree) of a certain variety called the hypothesis variety as the number of points in the configuration increases. For the problem of fitting an (n-1)-sphere to a configuration of m points in C^n, we give a closed formula of the algebraic complexity of the hypothesis variety as m grows for the case of n=1. For the case n>1 we conjecture a generalization of this formula supported by numerical experiments.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset