  This paper explores the distance-based relative state estimation problem in
large-scale systems, which is hard to solve effectively due to its
high-dimensionality and non-convexity. In this paper, we alleviate this
inherent hardness to simultaneously achieve scalability and robustness of
inference on this problem. Our idea is launched from a universal geometric
formulation, called \emph{generalized graph realization}, for the
distance-based relative state estimation problem. Based on this formulation, we
introduce two collaborative optimization models, one of which is convex and
thus globally solvable, and the other enables fast searching on non-convex
landscapes to refine the solution offered by the convex one. Importantly, both
models enjoy \emph{multiconvex} and \emph{decomposable} structures, allowing
efficient and safe solutions using \emph{block coordinate descent} that enjoys
scalability and a distributed nature. The proposed algorithms collaborate to
demonstrate superior or comparable solution precision to the current
centralized convex relaxation-based methods, which are known for their high
optimality. Distinctly, the proposed methods demonstrate scalability beyond the
reach of previous convex relaxation-based methods. We also demonstrate that the
combination of the two proposed algorithms achieves a more robust pipeline than
deploying the local search method alone in a continuous-time scenario.
