Secrets of Matrix Factorization: Approximations, Numerics, Manifold Optimization and Random Restarts.

Je Hyeong Hong, Andrew W FitzgibbonICCV 2015 · OpenReview

Abstract

Matrix factorization (or low-rank matrix completion) with missing data is a key computation in many computer vision and machine learning tasks, and is also related to a broader class of nonlinear optimization problems such as bundle adjustment. The problem has received much attention recently, with renewed interest in variable-projection approaches, yielding dramatic improvements in reliability and speed. However, on a wide class of problems, no one approach dominates, and because the various approaches have been derived in a multitude of different ways, it has been difficult to unify them. This paper provides a unified derivation of a number of recent approaches, so that similarities and differences are easily observed. We also present a simple meta-algorithm which wraps any existing algorithm, yielding 100% success rate on many standard datasets. Given 100% success, the focus of evaluation must turn to speed, as 100% success is trivially achieved if we do not care about speed. Again our unification allows a number of generic improvements applicable to all members of the family to be isolated, yielding a unified algorithm that outperforms our re-implementation of existing algorithms, which in some cases already outperform the original authors' publicly available codes.

Introduction

Low-rank matrix factorization—finding two smaller matrices $U$ and $V$ whose product approximates a large, incomplete matrix $M$—is essential for tasks like Structure from Motion (SfM) and recommender systems. Despite its importance, the problem remains challenging due to two primary factors:

  1. Non-convexity: The error landscape is full of local optima. Finding the true global minimum is notoriously difficult when data is missing.
  2. Algorithmic Fragmentation: Researchers have proposed many approaches (Variable Projection, Wiberg, Manifold Optimization), but they are often derived using different notations, making fair comparisons nearly impossible.

This paper addresses these issues by providing a unified mathematical framework, a robust meta-algorithm for global optimization, and numerical implementation "secrets" that significantly boost performance.

Unified Mathematical Framework

A core contribution of this work is the re-derivation of several popular algorithms (like VarPro and the Wiberg algorithm) using a single, consistent notation. This allows the authors to show that many "different" algorithms are actually variations of the same Gauss-Newton framework, differing primarily in how they approximate the Hessian matrix.

Unified derivation of Jacobian, Gradient, and Hessian for various algorithms.

By isolating these components, generic improvements can be applied across the entire family of algorithms. This unified approach led to the development of the "DRW" family of solvers, which outperform existing implementations.

The RUSSO Meta-Algorithm

To overcome the problem of local optima, the authors introduce RUSSO ("Restart $X$ Until Seen Same Optimum"). Instead of running an algorithm once, it is executed from different random starting points until the same best-so-far value is encountered twice. This simple heuristic dramatically increases the probability of finding the global optimum. On five out of 13 benchmarks, RUSSO reached the best-known optimum nearly 100% of the time.

Numerical Implementation "Secrets"

The authors identify specific implementation choices that significantly impact performance:

  • QR vs. Cholesky: Using QR factorization for matrix inversion is more stable and accurate than the standard Cholesky decomposition.
  • Block Coalescing: By recognizing patterns in missing data (where multiple columns share the same "mask"), redundant computations are avoided, leading to massive speedups.
  • Profile-guided Optimization: Moving bottleneck operations into C++ (via MEX files) provides a 2-3x speed boost over pure MATLAB implementations.

Datasets and Evaluation

The study utilizes 13 standard and challenging benchmarks, including Rigid SfM (Dinosaur), Non-rigid SfM (Giraffe, UM boy), Photometric Stereo (Face, Sculpture), and Recommender Systems (Jester, Netflix). The authors argue that wall-clock time is the only meaningful metric for evaluation, as iteration counts can be misleading if individual iterations are computationally expensive.

Key Insights and Results

A critical insight is the "Good Enough" trap: a solution with an error value just 0.06% higher than the global optimum can result in a qualitatively "broken" 3D reconstruction, such as points appearing behind the camera.

Visualizing the 'Good Enough' Trap: Global vs. Local Optima

Key results include:

  • Speed: The new implementations are 5x to 15x faster than previous state-of-the-art codes.
  • Optimization Impact: Hand-optimizing existing publicly available code resulted in a 2-3x speedup without changing the underlying mathematics.

Conclusion and Future Work

This work provides a unified perspective on matrix factorization, demonstrating that numerical implementation and global search strategies are as important as the underlying optimization algorithm. While the focus was on medium-scale problems using the $L_2$ norm, future work will extend these insights to massive-scale data and robust norms like $L_1$.

Summary updated

Abstract

Matrix factorization (or low-rank matrix completion) with missing data is a key computation in many computer vision and machine learning tasks, and is also related to a broader class of nonlinear optimization problems such as bundle adjustment. The problem has received much attention recently, with renewed interest in variable-projection approaches, yielding dramatic improvements in reliability and speed. However, on a wide class of problems, no one approach dominates, and because the various approaches have been derived in a multitude of different ways, it has been difficult to unify them. This paper provides a unified derivation of a number of recent approaches, so that similarities and differences are easily observed. We also present a simple meta-algorithm which wraps any existing algorithm, yielding 100% success rate on many standard datasets. Given 100% success, the focus of evaluation must turn to speed, as 100% success is trivially achieved if we do not care about speed. Again our unification allows a number of generic improvements applicable to all members of the family to be isolated, yielding a unified algorithm that outperforms our re-implementation of existing algorithms, which in some cases already outperform the original authors' publicly available codes.
BibTeX
@inproceedings{hong2015secrets,
  author = {Je Hyeong Hong and Andrew W Fitzgibbon},
  title = {{Secrets of Matrix Factorization: Approximations, Numerics, Manifold Optimization and Random Restarts.}},
  booktitle = {ICCV},
  year = {2015},
  url = {https://openreview.net/forum?id=AoYxq27DdBwh},
}
Figure