A fast method to minimize L_∞ error norm for geometric vision problems

Minimizing L_∞ error norm for some geometric vision problems provides global optimization using the well-developed algorithm called SOCP (second order cone programming). Because the error norm belongs to quasi-convex functions, bisection method is utilized to attain the global optimum. It tests the feasibility of the intersection of all the second order cones due to measurements, repeatedly adjusting the global error level. The computation time increases according to the size of measurement data since the number of second order cones for the feasibility test inflates correspondingly. We observe in this paper that not all the data need be included for the feasibility test because we minimize the maximum of the errors; we may use only a subset of the measurements to obtain the optimal estimate, and therefore we obtain a decreased computation time. In addition, by using L_∞ image error instead of L₂ Euclidean distance, we show that the problem is still a quasi-convex problem and can be solved by bisection method but with linear programming (LP). Our algorithm and experimental results are provided.