Suppose I have a collection of polynomials with multiple variables (more polynomials than variables, say), and I'm given noisy versions the values of these polynomials at a certain unknown point. I would like to solve for this point in a stable manner. What is known about this problem?

Certainly, the notion of stability should depend on the degree of the polynomials. I am particularly interested in case where the degree is 2 and the field is real, but I'm open to results involving higher degrees and algebraically closed fields.

UPDATE: Following Misha's suggestion, I'll describe one way to estimate the desired point. Take $m>n$ and let $F\colon\mathbb{R}^n\rightarrow\mathbb{R}^m$ be a polynomial mapping. I am given $y=F(x)+e$ for some noise vector $e\in\mathbb{R}^m$ of small norm, and my task is to estimate $x$. Here, we might find the closest point $\hat{y}$ in the image $F(\mathbb{R}^n)$ to $y$, and then solve the system $F(\hat{x})=\hat{y}$ for $\hat{x}$. But what can be said about the quality of this estimator? For example, how is $\|\hat{x}-x\|$ related to $\|e\|$? Is there a Holder-type relationship in terms of the degree of $F$?

  • 1
    $\begingroup$ You should specify what you mean by "stable manner", especially if the solution set is unbounded. Or, maybe, you are interested in the case when $F: R^n\to R^n$ is your polynomial vector-function and there are only finitely many solutions? In the latter case, the key words are "regular value". $\endgroup$
    – Misha
    Commented Apr 20, 2013 at 4:00
  • $\begingroup$ Ah, good point. I'm actually thinking about the over-determined regime (i.e., more polynomials than variables), so you could say there are no "solutions." $\endgroup$ Commented Apr 20, 2013 at 4:11
  • $\begingroup$ @Dustin: Yes, I would. Maybe in this case, you are looking at stability of the nearest-point projection of $0\in R^m$ to the image $F(R^n)=S$ of $F: R^n\to R^m$ (as in the linear case)? Then things become interesting. In the case when $m=n+1$, you may require $S$ to be convex (and $0$ be on the "concave side"). For $m>n+1$, I do not have good suggestions, my guess is that you would need some positivity properties for the shape operator of $S$. In any case, you should revise the question to ask what you mean to ask. $\endgroup$
    – Misha
    Commented Apr 20, 2013 at 15:33

1 Answer 1


Clearly if $F$ is not injective, then as $||e||$ goes to $0$, $||\hat{x}-x||$ can approach a constant, or alternately $\hat{x}$ can be undefined.

But if $F$ is injective, and the Jacobian of $F$ is of full rank at $x$, then $||\hat{x}-x||=O(x)$. This is because $\hat{x}$ certainly converges to $x$ as $e$ goes to $0$, and then we have an estimate $||F(\hat{x}) - F(x) ||= \Theta( ||\hat{x}-x||) $ by Taylor series. But $||F(\hat{x})-F(x)|| < 2e$ for trivial reasons.

If the Jacobian is not of full rank we can still get a Holder-type bound by the same method.

In this regard a polynomial is not appreciably different from a general smooth function. Indeed, for $e$ small this is an entirely local question, and locally polynomials do not behave much differently from general smooth functions. It is apparent that it does not matter so much that your function is a polynomial, but rather which sort of polynomial it is - is it injective? Is its Jacobian injective?

There might be some weird cases where $\hat{x}$ need not converge to $x$ because it diverges to $\infty$ instead. One could place a condition to deal with that, except I'm guessing in whatever estimation application this has that won't be a problem.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.