3
$\begingroup$

This problem arises from my research in computer vision, specifically projective homography:

I have $n$ unknown variables, represented by an $n\times 1$ vector $\mathbf{x}$. There is a system of $n$ equations of the form $\mathbf{x}^{T}\mathbf{A_i}\mathbf{x} + \mathbf{b_i}^{T}\mathbf{x} + c_i = 0$, where $\mathbf{A_i}$ is an $n\times n$ symmetric matrix, $\mathbf{b_i}$ is an $n\times 1$ vector and $c_i$ is a scalar for $i=1\ldots n$, that $\mathbf{x}$ has to satisfy.

It is also known that every entry of the solution $\mathbf{x}$ is small, i.e. comparatively smaller than their respective coefficients.

Is there a closed-form or iterative method to solve for $\mathbf{x}$?

1 Answers 1

2

Newton's method converges fast, when it converges. In Newton's method, you start from an initial estimate $\bf x$, and solve a linear equation for $\bf h$ to get the next iterate $\bf x+h$. In this case this seems to give $ {\bf x}^T({\bf A}_i{\bf x}+{\bf b}_i)+(2{\bf A}_i{\bf x}+{\bf b}_i)^T{\bf h}+c_i=0 $ for $i=1$ to $n$. It is obtained by dropping the term which is quadratic in ${\bf h}$.