An Extended Sparse Linear System for Exact Marginal Inference on Factor Graphs

Factor graphs are fundamental to large-scale estimation in robotics and computer vision, but their underlying normal equations incur significant computational costs. To overcome this, we introduce an Extended Sparse Linear System (ESLS) that seamlessly integrates state variables with auxiliary measurements. This framework fundamentally restructures the normal equations via algebraic-topological isomorphism and structured marginalization, achieving intrinsic computational optimization. The ESLS features a skew-symmetric block-structured matrix that is isomorphic to the factor graph topology, ensuring that algebraic marginalization directly implements graphical inference. We prove that classical normal equations are a special case of ESLS marginalization through Schur complements. Moreover, we characterize novel theoretical properties of the ESLS, derive closed-form self- and cross-information updates, and formalize how information flows to adjacent graph elements during Schur complement operations. Overall, the ESLS establishes a unified and computationally efficient algebraic foundation for large-scale inference, bridging graphical models and numerical linear algebra in a principled way.