Generalized weiszfeld algorithms for lq optimization

Abstract

In many computer vision applications, a desired model of some type is computed by minimizing a cost function based on several measurements. Typically, one may compute the model that minimizes the L2 cost, that is the sum of squares of measurement errors with respect to the model. The simplicity of L2 methods is well appreciated, but they suffer from a drawback when it comes to robustness against outliers; even a single outlier may change the L2 solution drastically. This thesis is primarily focused on the development of simple and robust Lq optimization methods, for q ranging from 1 to 2 (excluding 2), for problems in the area of computer vision. The proposed Lq optimization methods minimize the sum of the q-th power of errors and give more robust results than least squares methods in the presence of outliers. We particularly consider two classes of problems: Firstly, Lq-closest-point problems, where we seek a point for which the sum of the q-th power of distances from a given set of measurements is the minimum. Secondly, Lq non-linear parameter estimation problems, where parameters of a model are estimated by minimizing the sum of the q-th power of distances to a given set of points. The proposed Lq-closest-point algorithms are inspired by the Weiszfeld algorithm, a classic algorithm for finding the L1 mean of a set of points in a Euclidean space. The proposed Lq-closest-point algorithms inherit all the properties of the Weiszfeld algorithm, such as provable convergence to the global Lq minimum, analytical updates, simple to understand and easy to code. We specifically propose the following algorithms: First of all, we propose a generalization of the Weiszfeld algorithm to find the Lq mean of a set of points in a Euclidean space. We refer to this as the Lq Weiszfeld algorithm. We then propose a generalization of the Lq Weiszfeld algorithm to find the Lq mean of a set of points on a Riemannian manifold of non-negative sectional curvature and apply it to rotation averaging and Symmetric Positive-Definite matrices averaging problems. In addition to the proof of convergence, we relax the bounds on maximum distance between points on manifold to ensure convergence. Furthermore, we propose a generalization of the Lq Weiszfeld algorithm to find the Lq-closest-point to a set of affine subspaces, possibly of different dimensions, in a Euclidean space and apply it to the triangulation problem. In addition to the closest-point problems, we propose an algorithm to find an Lq solution of a non-linear parameter estimation problem, specifically the bundle adjustment problem. An advantage of the proposed algorithm is that an efficient least squares optimization method, namely the Levenberg-Marquardt method, is used to find a robust solution to the problem, even an Lq solution. In all the cases, our experimental results confirm the fact that in the presence of outliers the proposed Lq algorithms give superior results than least squares algorithms.