Large 3D reconstruction jobs refine millions of camera poses and 3D points so that projected points line up with where they were observed in photos. This problem, bundle adjustment, is now solved across many GPUs or machines by splitting the observations among them. Every such solver assumes the dataset is fixed. In practice data arrives continuously: new images, new observations of old points, and bad matches that get removed. Warm-starting the solution after an update is cheap. What is expensive is rebuilding the solver's internal structure. That structure is the "reduced camera system", the camera-only linear system left after the 3D points are algebraically eliminated, together with the preconditioner derived from it. A preconditioner is a cheap approximate inverse that lets an iterative solver converge in few steps.
This note proposes to maintain that preconditioner incrementally and in a distributed way. The key observation is that eliminating one 3D point from the camera–point graph is exactly a star–mesh transform: the point, a hub node, is removed and every pair of cameras that saw it becomes linked. Dynamic graph maintenance has good tools for patching star–mesh cliques locally when nodes come and go. We reuse them so that each streamed update touches only the cliques it actually changes, and each machine refreshes only the cliques of the points it owns.
Core Claim
Consider streaming distributed bundle adjustment with a warm-started solution. The dominant per-update cost is rebuilding the reduced camera system and its preconditioner, not re-converging the solution. A sparsified, partition-local Schur-complement preconditioner can be updated with bounded recourse and refreshed only where the linearization has moved. Here recourse means the number of camera–camera blocks rewritten per update. On streamed versions of BAL and 1DSfM, we expect this preconditioner to reach the same reprojection-error tolerance per update as a full rebuild, with far less maintenance time and communication. We also expect it to need clearly fewer distributed conjugate-gradient rounds than the trivially dynamic block-Jacobi preconditioner.
Concretely, eliminating point $j$ contributes to the camera system the term $-E_j C_j^{-1} E_j^\top$. Here $E_j$ stacks the Jacobian cross-blocks between point $j$ and the cameras observing it, and $C_j$ is the point's own $3\times 3$ Hessian block. This term is a dense clique over the $\ell_j$ cameras in the point's track. Following the deterministic top-$t$ sparsification in Graph-based Nearest Neighbors with Dynamic Updates via Random Walks, each clique is reduced to its $t$ heaviest camera–camera blocks per camera. The dropped off-diagonal mass is folded back onto the diagonal so the preconditioner stays positive definite and dominates the exact system. An inserted or deleted observation of point $j$ then changes only $O(\ell_j t)$ blocks, all computed by the machine that owns point $j$.
Relation to Prior Work
Three groups of papers motivate the idea. Static distributed bundle adjustment solvers all partition an offline dataset once and rebuild from scratch when it changes. MegBA does exact distributed Schur elimination and distributed preconditioned conjugate gradient over GPUs. DBA-BSMC partitions the reduced camera system by 3D points and compresses it. D-ADMM BA enforces consensus with the alternating direction method of multipliers. DABA decouples cameras and points by majorization–minimization and uses decentralized Nesterov acceleration. None of the four maintains state across data updates. We borrow MegBA's distributed conjugate-gradient loop and DBA-BSMC's point-ownership partitioning, and add the maintenance layer.
ICE-BA shows that incremental reuse pays off. It reports 2.45 ms versus 26.8 ms per local bundle adjustment on EuRoC. However, it is centralized, and it preserves sparsity by splitting feature tracks into sub-tracks, which changes the optimization problem. We leave the problem exact and approximate only the preconditioner, so the converged answer does not depend on the sparsification.
Dynamic Effective Resistances and Approximate Schur Complement on Separable Graphs maintains approximate Schur complements dynamically, but only for centralized scalar Laplacians on graphs with small separators. Camera covisibility graphs from internet photo collections are not such graphs. We give up its worst-case guarantees in exchange for block-structured, distributed, empirically bounded updates.
Two papers constrain the design. The networked linear-solver literature treats "dynamic" as changing communication links over a fixed equation system; see Distributed Linear Equations Over Random Networks. That paper also shows that inconsistent systems degrade to sublinear convergence under first-order methods, which is a reason to prefer preconditioned second-order steps here. DiSCO warns that a preconditioner built from one node's data breaks down under non-identically distributed partitions. Spatially partitioned scenes are exactly that case. This is why each partition builds its preconditioner from its own points, rather than borrowing one master's.
Research Program
The system has three parts.
The first part is the preconditioner structure. Each machine owns a set of points and keeps their sparsified cliques. It sums these into its share of a sparse camera–camera matrix. Blocks for cameras that are owned elsewhere are aggregated with one sparse all-reduce. Each machine applies the preconditioner by solving its own camera block with a sparse Cholesky factor, which is updated by low-rank modifications when cliques change. Couplings between partitions are dropped, so the preconditioner is partition-block-diagonal. A coarse level built by incremental coarsening in the style of Adapting to Evolving Graphs is an optional extension, to be added only if cross-partition coupling proves to limit convergence.
The second part is a change-driven refresh policy. The preconditioner depends on the current linearization, so it would normally be rebuilt every Levenberg–Marquardt iteration. We instead mark a point's clique stale when its observations change, or when the Jacobian blocks of its point or cameras drift by more than a relative threshold $\tau$ since the last refresh. Only stale cliques are recomputed. This mirrors FreshVamana's policy of letting deleted nodes linger until a background pass repairs them, described in The DiskANN library. Recourse is logged per update.
The third part is analysis. We will bound the condition number of the preconditioned system in terms of the dropped clique mass and the lag $\tau$, and check the bound empirically against measured conjugate-gradient iteration counts.
Baselines
The naive reference is cold rebuild. After each update batch, MegBA re-partitions and re-solves from the previous camera poses, rebuilding the reduced camera system and its preconditioner in full. It runs on the same GPUs, with the same Levenberg–Marquardt and conjugate-gradient tolerances.
The strongest Schur-based competitor is warm-started MegBA. The solution carries over, but the reduced camera system and preconditioner are still rebuilt at every Levenberg–Marquardt step, as in the static library. On static data MegBA reports a 41.45x speedup over Ceres on BAL Final-13682. It also solved an 80-million-observation synthetic problem in 216 seconds on 8 GPUs, where DeepLM and RootBA ran out of memory.
The strongest competitor overall is warm-started DABA. It has no Schur complement to maintain, so it absorbs streaming for free. It reports speedups of up to 953.7x over Ceres and 174.6x over DeepLM on the largest static datasets, and the lowest reprojection errors among decentralized methods. There is no reported result on Lacuna for any distributed bundle adjustment method on a streaming workload, so all streaming numbers will be produced here.
Three ablations isolate the key ingredient. The first is block-Jacobi: a camera-diagonal preconditioner that is trivially dynamic. The second is a stale preconditioner that is never refreshed after the first build. The third is full refresh of our sparsified preconditioner at every step, which isolates the value of the refresh policy.
All methods get identical data streams, GPU count, and a matched budget for tuning step sizes and thresholds on a held-out BAL subset. Beating the field means two things. First, reaching within 1% of the batch-optimal reprojection error after each update in less wall-clock time and fewer communicated bytes than warm-started MegBA and warm-started DABA, on at least the three largest streamed datasets. Second, needing at least 2x fewer conjugate-gradient rounds than block-Jacobi. If that second margin is not met, the maintenance machinery is not worth its cost.
Why not just…?
Why not just warm-start a static solver and rebuild its internals? Warm-starting fixes the solution but not the rebuild cost, which grows with every camera and observation rather than with the size of the update. Evidence from nearby problems suggests local maintenance wins by an order of magnitude. Incremental coarsening was 10–20x faster than recomputation (Adapting to Evolving Graphs), and ICE-BA's reuse gave a 10x speedup. The warm-started MegBA baseline measures this cost directly for our setting.
Why not just use DABA, which has no Schur complement to maintain? This is the real threat. If first-order decentralized updates re-converge after a local change in few rounds, the preconditioner is unnecessary. Our bet is that the change from a new camera spreads through long camera–point chains slowly under first-order steps. That is the regime where Distributed Linear Equations Over Random Networks finds first-order methods slow on inconsistent systems. The rounds-to-tolerance comparison against warm-started DABA settles this. We will report honestly the stream regimes, such as small incremental batches, where DABA wins.
Why not just use block-Jacobi, which is already trivially dynamic? It costs nothing to maintain, but it ignores coupling between cameras. The per-update comparison of conjugate-gradient rounds and communicated bytes decides whether sparsified cliques earn their maintenance cost.
Why not just tombstone removed observations or keep a stale preconditioner? Leaving a stale preconditioner in place avoids all maintenance. Our stale-preconditioner ablation measures how fast iteration counts grow over time, analogous to the tombstone degradation that SPatch avoided with 2.5–3x faster queries (Graph-based Nearest Neighbors with Dynamic Updates via Random Walks).
Proposed Experiments
We build streams from BAL (Venice, Final, Trafalgar, and the other subsets with more than 700 cameras) and from 1DSfM. Cameras are inserted in covisibility breadth-first order, in batches of 1, 10, and 100 cameras. Deletions are interleaved: 5% of observations are removed as simulated outlier rejections, and a sweep removes up to 30% of cameras. A MegBA-style synthetic generator scales the stream to tens of millions of observations.
The metrics are measured per update. They are time and communicated bytes to reach within 1% of the batch optimum, conjugate-gradient rounds per Levenberg–Marquardt step, preconditioner maintenance time, recourse, and peak memory. We also measure final reprojection error against a full static solve at the end of the stream.
There are three decisive checks. The first is that recourse per update stays roughly flat as the scene grows, while rebuild cost grows. The second is that measured conjugate-gradient iterations track the predicted dependence on dropped clique mass and $\tau$. The third is the head-to-head against warm-started DABA across batch sizes, which determines whether the method is useful or only a finding about when first-order methods suffice.
References
- Graph-based Nearest Neighbors with Dynamic Updates via Random Walks
- MegBA: A GPU-Based Distributed Library for Large-Scale Bundle Adjustment
- Distributed bundle adjustment with block-based sparse matrix compression for super large scale datasets
- Distributed Bundle Adjustment
- Decentralization and Acceleration Enables Large-Scale Bundle Adjustment
- ICE-BA: Incremental, Consistent and Efficient Bundle Adjustment for Visual-Inertial SLAM
- Dynamic Effective Resistances and Approximate Schur Complement on Separable Graphs
- Distributed Linear Equations Over Random Networks
- DiSCO: Distributed Optimization for Self-Concordant Empirical Loss
- Adapting to Evolving Graphs: A Scalable Framework for Dynamic Coarsening
- The DiskANN library: Graph-Based Indices for Fast, Fresh and Filtered Vector Search