Non-linear least squares algorithms such as Gauss-Newton allow me to (locally) minimize a sum of squares of residuals (the output of some non-linear function). I.e. locally solve: $$ \mathbf{x} = \arg\min_{\mathbf{x}^*} \|\mathbf{f}(\mathbf{x}^*)\|^2, $$ where $\mathbf{x}$ is a vector of variables, and $\mathbf{f}()$ is a function that outputs a vector of residuals. Assume there are more residuals than variables, so the problem is well conditioned.

The nice thing about least squares solvers is that they offer second-order convergence, but only require the first (not second) derivative of residuals ($\mathbf{f}(\mathbf{x})$) to be computed.

Is there a similarly effective (e.g. second-order) algorithm for maximizing a sum of squares, i.e.

$$ \mathbf{x} = \arg\max_{\mathbf{x}^*} \|\mathbf{f}(\mathbf{x}^*)\|^2, $$

given only the residuals and their gradient? This is for the case that the residuals are in a finite range (so the cost doesn't zoom off to infinity), and there are no constraints on the variables being optimized.

Note that, while this can be rephrased as $$ \mathbf{x} = \arg\min_{\mathbf{x}^*} -\|\mathbf{f}(\mathbf{x}^*)\|^2, $$ it's not clear to me what the update step would be in this case, since Gauss Newton can only be used to minimize a sum of squares, not a negated sum of squares.

I need this for an image alignment problem: I have a scalar field, e.g. an intensity image, and want to maximize the sum of squares of intensity at a predetermined set of sample points, subject to some affine warp of the sample points. I want to find the affine warp that maximizes the sum of squares of the scalar field at the sample points. Note that I want to find a local solution, i.e. the solution I'd get if I did gradient descent from a particular starting point, but with a more efficient, second order algorithm.

If it's not possible, is there an intuitive explanation as to why not?


1 Answer 1


Least squares costs always have a lower bound: zero. They need not have an upper bound in general.

Gauss-Newton approximates the Hessian of a problem with a positive semi-definite matrix, constructed from the Jacobian. This means it can only model quadratics with a minimum. It drops other higher order terms, that might otherwise change the quadratic model to that with a maximum. If you want to maximize the sum of squares, then you need to include those terms, and hope that you then get a negative semi-definite matrix. However, there is no guarantee you will.

In your particular case, you are maximizing costs over a discrete field (pixel values). Locally, the gradients may imply that the cost will continue increasing the further you move, even if the neighbouring samples do not reflect that - indeed they cannot reflect that, since they are bounded. This is problematic.


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.