AI

General, Nested, and Constrained Wiberg Minimization

Abstract

Wiberg matrix factorization breaks a matrix Y into low-rank factors U and V by solving for V in closed form given U, linearizing V (U) about U, and iteratively minimizing ||Y − UV (U)||_2 with respect to U only. This approach factors the matrix while effectively removing V from the minimization. Recently Eriksson and van den Hengel extended this approach to L1, minimizing ||Y − UV (U)||_1. We generalize their approach beyond factorization to minimize ||Y − f(U, V )||_1 for more general functions f(U, V ) that are nonlinear in each of two sets of variables. We demonstrate the idea with a practical Wiberg algorithm for L1 bundle adjustment. One Wiberg minimization can be nested inside another, effectively removing two of three sets of variables from a minimization. We demonstrate this idea with a nested Wiberg algorithm for L1 projective bundle adjustment, solving for camera matrices, points, and projective depths. Wiberg minimization also generalizes to handle nonlinear constraints, and we demonstrate this idea with Constrained Wiberg Minimization for Multiple Instance Learning (CWM-MIL), which removes one set of variables from the constrained optimization. Our experiments emphasize isolating the effect of Wiberg by comparing against the algorithm it modifies, successive linear programming.