Abstract
Maximum Aposteriori (MAP) inference in Markov Random Fields (MRFs) is a fundamental yet computationally taxing problem in computer vision and machine learning. This paper presents Spectral relaxation to Quadratic Programming (SQP), a novel framework that transforms the discrete MAP optimization problem into a continuous Rayleigh quotient maximization. By leveraging eigenvalue decomposition, SQP provides a mathematically principled, computationally efficient algorithm that offers tighter optimality bounds than previous relaxation techniques. Unlike specialized solvers, SQP is applicable to arbitrary graph topologies and clique potentials, achieving linear time complexity relative to the number of edges.
Introduction
Markov Random Fields are indispensable for modeling spatial dependencies in tasks ranging from image restoration to object recognition. The core challenge lies in finding the MAP solution—the most probable configuration of variables given observed data. However, for most non-trivial graph structures, this optimization is NP-hard.
Existing methodologies often face significant limitations. Belief Propagation (BP) is efficient but frequently fails to converge on loopy graphs. Graph Cuts provide global optimality but are restricted to submodular potentials. Linear and quadratic relaxations often result in non-convex problems that remain difficult to solve. SQP addresses these gaps by providing a spectral solution that is both scalable and robust to "frustrated" or non-submodular potentials.
The Spectral Relaxation Approach
The authors propose a three-step transformation to solve the MAP problem:
- IQP Formulation: The discrete MAP problem is first reformulated as an Integer Quadratic Program (IQP).
-
The Spectral Shift: To avoid the NP-hardness of standard Quadratic Program (QP) relaxations, the objective is relaxed into a Rayleigh quotient form: $$\max \epsilon_S(x) = \frac{x^T W x + V^T x}{x^T x + \beta}$$ subject to affine constraints ($Cx=1$).
-
The Eigen-Solution: This formulation allows for a closed-form solution where the optimal $x$ is the leading eigenvector of a specifically constructed matrix ($P_C W' P_C$).
A critical component of this method is the $\beta$ parameter. Acting as a regularizer, $\beta$ encourages "flatter" solutions that facilitate the mapping of continuous results back to the discrete domain. The authors demonstrate that under conditions like diagonal dominance, the discrete IQP and continuous QP share the same global optimum, justifying the relaxation strategy.
Experimental Evaluation
The algorithm was evaluated using synthetic benchmarks consisting of randomly generated MRFs. These tests varied node counts ($n=20$ to $50$), label sets ($k=10$ to $20$), and edge densities ($p_{edge}$ from 0.1 to 1.0). These controlled environments allowed for a rigorous comparison between SQP and established baselines, including L2QP, BP, and Iterative Conditional Modes (ICM).
Key Results
- Theoretical Superiority: SQP consistently provides tighter data-dependent lower bounds compared to competing relaxation methods like CQP and L2QP.
- Computational Efficiency: With a complexity of $O(\text{edges} \cdot \text{labels}^2)$, the algorithm scales effectively for large-scale vision tasks by utilizing sparse matrix-vector products.
- Robust Performance: In empirical tests, SQP matched or outperformed L2QP and significantly surpassed local search methods like ICM and standard BP in terms of final solution energy. Its performance remained stable even in the presence of arbitrary or non-submodular potentials.
Discussion and Conclusion
While SQP represents a significant advancement, some challenges remain. Mapping the continuous spectral solution back to discrete labels currently relies on discretization heuristics, such as Relaxation Labeling. Additionally, while heuristics exist for estimating the optimal $\beta$, further refinement could improve performance on specific datasets.
Despite these limitations, SQP offers a powerful alternative for MAP inference. By turning a "hard" optimization problem into a well-understood linear algebra problem, it provides a scalable and principled tool for the computer vision community. Future work may explore tighter conditions for the non-negativity of spectral solutions and the application of SQP to high-level tasks like 3D reconstruction and graph matching.
Summary updated