Google Research

General, Nested, and Constrained Wiberg Minimization

  • Dennis Strelow
  • Qifan Wang
  • Luo Si
  • Anders Eriksson
IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, vol. 38 (2016), pp. 1803-1815

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.

Research Areas

Learn more about how we do research

We maintain a portfolio of research projects, providing individuals and teams the freedom to emphasize specific types of work