Bilinear Factorization via Augmented Lagrange Multipliers (BALM)

We present a unified approach to solve different bilinear factorization problems in Computer Vision in the presence of missing data in the measurements. The problem is formulated as a constrained optimization where one of the factors is constrained to lie on a specific manifold. To achieve this, we introduce an equivalent reformulation of the bilinear factorization problem. This reformulation decouples the core bilinear aspect from the manifold specificity. We then tackle the resulting constrained optimization problem with a Bilinear factorization via Augmented Lagrange Multipliers (BALM). The mechanics of our algorithm are such that only a projector onto the manifold constraint is needed. That is the strength and the novelty of our approach: this framework can handle seamlessly different computer vision problems.
This is the problem we optimise:

$\text{minimize } \left\| Y - S M \right\|^2 \\ \\\text{subject to } M_i \in {\mathcal M}, \quad i = 1, \ldots, f,$

where $Y$ is a matrix that contains the measurement data (e.g. image point trajectories in SfM or pixel intensity variations in Photometric Stereo). The matrices $M$ and $S$ are the bilinear components to estimate. The matrix $M$ is formed as:

$M = \begin{bmatrix} M_1 & \cdots & M_i & \cdots & M_f \end{bmatrix} \in {\mathbb R}^{r \times m}, \quad M_i \in {\mathbb R}^{r \times p}.$

Each of the sub-matrices $M_i$ lies on a specific manifold ${\mathcal M}$ (i.e. its values are not arbitrary but constrained). When dealing with SfM the manifolds are usually Stiefel while with Photometric Stereo they are mostly spherical.

Now a video showing the resilience of BALM to missing data in structure from motion and photometric stereo problems:

Check the pdf here.