Two Novel Techniques for Graph Optimization — Cycle Based Formulation and Change of Optimal Values
- Publication Type:
- Thesis
- Issue Date:
- 2020
Open Access
Copyright Clearance Process
- Recently Added
- In Progress
- Open Access
This item is open access.
Graph optimization (GO) is an essential enabling technique widely used in the simultaneous localization and mapping (SLAM), sensor fusion, Lidar based or visual-inertial based navigation systems (VINS). As its name suggests, the graph optimization lies at the intersection of probabilistic inference, sparse linear algebra, and graph theory. In its explicit form, it is a sparse least squares derived from a maximum likelihood estimation (MLE). This thesis contains two fundamental contributions regarding this topic.
A GO can be conventionally represented as a graph with vertices being (unobserved) latent variables, and edges being observed measurements. This vertex-edge paradigm has dominated the GO literature, which in essence solves the problem in the cut space of the graph. In this thesis, we firstly investigate a special GO instance, i.e., pose-graph optimization (PGO), and propose an orthogonal complementary formulation that solves PGO in the cycle space. For sparse graphs, which is typically the case for PGO, the cycle based formulation has a lower dimension of state variables, and takes a form of minimum norm optimization. By exploiting the sparsity by a minimum cycle basis (MCB), the cycle based PGO yields a superior convergence property against its vertex-based counterpart while being cheaper to compute.
The second contribution is the theory on how to forecast the change of optimal values (COOV) in incrementally constructed GO instances. In specific, this thesis develops analytical equations to calculate COOV in case of least squares optimization, and minimum norm optimization. The equation is exactly proved under linear cases, and extends to nonlinear cases via linearizations. We show that COOV bears the same computational complexity as the mutual information (MI) in incremental scenarios, while both COOV and MI well complement one another. As a final contribution, we design several derived applications based on the proposed COOV metric, that demonstrates its effectiveness in outlier detection, cost forecasting, and enhancing the overall robustness in incremental settings. It can be foreseen that numerous applications can be generated based on the two cornerstones in this thesis, and the author would like to leave this part as a future research direction, and open to the community.
Please use this identifier to cite or link to this item: