CSS-BA: Gate Guided Column Space Search for Bundle Adjustment¶

Conference: ECCV 2026
Paper: ECCV Official
Area: 3D Vision
Keywords: Bundle Adjustment, Column Space Search, Schur Complement, Low-Parallax Degeneracy, Trust-Region Optimization

TL;DR¶

Addressing severe ill-conditioning and pose/calibration distortion in Schur Levenberg–Marquardt under low-parallax and near-rotational motions, CSS-BA preserves the original BA objective, residuals, and all parameters while restricting each LM update step to a gate-guided, Ritz-basis low-dimensional subspace, achieving robust geometric recovery without artificial priors.

Background & Motivation¶

Bundle adjustment (BA) serves as the indispensable nonlinear least-squares refinement stage in multiview 3D reconstruction, continuing to dictate the final camera pose and geometric calibration accuracy even in cutting-edge neural/foundation reconstruction frameworks (e.g., DUSt3R, MASt3R). The canonical workflow eliminates 3D scene landmarks via the Schur complement and executes Levenberg–Marquardt (LM) damped normal equation steps over camera parameter increments. However, in low-parallax or near-rotational trajectories—such as orbital captures, handheld phone sweeps in PhoneSweep, or distant object orbiting—this classical paradigm suffers from acute numerical vulnerability.

Under near-zero baseline regimes, the sensitivity of image disparity with respect to scene depth $\partial d_{\text{disp}}/\partial Z \approx -fB/Z^2$ vanishes, causing camera translation, landmark depth, and focal length calibration to become hopelessly entangled in the measurement equations. Upon Schur reduction, this coupling manifests as near-null singular directions with infinitesimal eigenvalues in the reduced camera Hessian. Standard Schur-LM routinely drifts along these unconstrained null-space modes: even when reprojection errors decrease to near-zero, the estimated relative poses suffer catastrophic distortions, trajectories fold or collapse, and focal lengths drift by hundreds of percent. Existing acceleration or robustification schemes—such as Power BA, Square Root BA, or heuristic spherical motion priors—either focus exclusively on linear algebra throughput or alter the estimation problem itself by introducing ad-hoc geometric regularization.

This work attacks the root cause from a solver-side update restriction perspective within the classical trust-region framework. The authors argue that neither modifying reprojection residuals nor discarding non-keyframe variables is required; rather, one must prevent LM update steps from wandering into poorly constrained subspaces. Core idea: integrate Column Space Search into the Schur-reduced BA system (Gate-Guided CSS-BA), filtering candidate cameras through view parallax and rotational consistency gating, ranking informative blocks via Schur predicted decrease to construct a compact Lanczos/Ritz subspace basis, and confining each LM update to well-conditioned directions before lifting back to the full camera vector.

Method¶

Overall Architecture¶

CSS-BA operates strictly within the classical Levenberg–Marquardt trust-region framework on the Schur-reduced camera system. Given the current camera parameters $\mathbf{c}$ and 3D point coordinates $\mathbf{p}$, the algorithm first constructs an offline geometry-aware support set $\mathcal{S}$ based on multi-view graph diagnostics. At each LM iteration $t$, the system linearizes residuals and forms the damped Schur-reduced linear system $\tilde{H}_\lambda \Delta \mathbf{c} = -\tilde{\mathbf{g}}_\lambda$. Instead of solving this high-dimensional system directly, CSS scores candidate camera blocks within $\mathcal{S}$ by their local predicted decrease to select a top-$k$ support set $K_t$. A localized Schur operator is then formed, and an $m$-step Lanczos process extracts the dominant Ritz curvature vectors, optionally appended with an orthogonalized gradient complement to build a compact subspace basis $V_t$. Finally, a small projected LM subproblem is solved in this subspace, lifted back to the full camera space, and point updates are recovered via back-substitution. Standard trust-region ratio evaluation then dictates step acceptance and damping parameter updates.

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["Input camera & point parameters (c, p)"] --> B["Geometry-aware support set construction<br/>Determine S via parallax & rotational consistency"]
    B --> C["Linearization & damped Schur reduction<br/>Form Schur system (H̃_λ, g̃_λ)"]
    C --> D["Schur-consistent column space search scoring<br/>Evaluate predicted decrease in S to select top-k Kt"]
    D --> E["Localized operator & Lanczos/Ritz basis generation<br/>Extract Ritz basis VK and append gradient complement vg to form Vt"]
    E --> F["Projected LM subproblem solve & full-vector lifting<br/>Solve Vtᵀ H̃_λ Vt y = -Vtᵀ g̃_λ, Δc = Vt y"]
    F --> G["Back-substitute landmark increment Δp<br/>Trust-region check ρ & damping update"]

Key Designs¶

1. Geometry-Aware Support Set Construction: Pruning Degenerate Cameras via Parallax and Rotational Consistency In low-parallax regimes, blindly involving all camera gradients can introduce severely ill-conditioned update directions. CSS-BA establishes an initial reliable camera set $\mathcal{S}$ before optimization begins. For any camera pair $i, j$, a valid edge $(i, j) \in \mathcal{E}$ is defined if they share at least $|\mathcal{P}_{ij}| \ge \tau_{\text{shared}}$ feature tracks. For each track, ray vectors are constructed to compute the median pairwise parallax $\mathrm{Par}_{ij}$. Filtering neighbors by an edge threshold yields the parallax-filtered neighborhood $\mathcal{N}_E(i) = \{j \in \mathcal{N}(i) \mid \mathrm{Par}_{ij} \ge \tau_{\text{par}}^{\text{edge}}\}$, which provides the camera-level parallax score $\mathrm{Par}_i = \mathrm{median}_{j \in \mathcal{N}_E(i)} \mathrm{Par}_{ij}$. Concurrently, rotational consistency $\mathrm{RA}_i$ is defined as the geodesic distance between camera rotation $R_i$ and the average neighbor rotation $\bar{R}_i$: $$ \mathrm{RA}_i = \arccos\left(\operatorname{clamp}\left(\frac{\mathrm{tr}(R_i^\top \bar{R}_i) - 1}{2}, -1, 1\right)\right) $$ The support set $\mathcal{S}$ comprises cameras satisfying $|\mathcal{N}_E(i)| \ge \tau_{\text{nbr}}$, $\mathrm{RA}_i \le \tau_{\text{ra}}$, and $\mathrm{Par}_i \ge \tau_{\text{par}}^{\text{cam}}$. This gate purely defines candidate blocks for subsequent basis construction; no cameras or observations are dropped from the BA problem.

2. Schur-Consistent Column Space Search Scoring: Adaptive Top-$k$ Selection via Predicted Objective Decrease After defining the geometrically viable pool $\mathcal{S}$, the solver must determine which camera coordinate blocks yield the highest reduction gain at iteration $t$. CSS-BA extends Column Space Search (CSS) to the Schur-reduced camera space. The camera increment vector $\Delta \mathbf{c} \in \mathbb{R}^{n_c}$ is partitioned into $B$ camera blocks with block projectors $P_i \in \mathbb{R}^{n_c \times d_i}$. For each camera $i \in \mathcal{S}$, the solver extracts the local reduced gradient block $\tilde{\mathbf{g}}_{\lambda, i} = P_i^\top \tilde{\mathbf{g}}_\lambda$ and the diagonal Hessian block $\tilde{H}_{\lambda, ii} = P_i^\top \tilde{H}_\lambda P_i$. The single-block predicted decrease under the quadratic model is computed as: $$ s_i = \frac{1}{2} \tilde{\mathbf{g}}{\lambda, i}^\top \tilde{H} $$ Evaluating }^{-1} \tilde{\mathbf{g}}_{\lambda, i$s_i$ requires only inverting small $6 \times 6$ or $9 \times 9$ camera blocks, making scoring computationally negligible. Ranking blocks in descending order of $s_i$ yields the top-$k$ set $K_t \subseteq \mathcal{S}$, where $k = \min(k_{\text{max}}, |\mathcal{S}|)$.

3. Localized Operator & Lanczos/Ritz Basis Generation: Transforming Discrete Support into Smooth Joint Motion Optimizing selected camera blocks independently in coordinate space would break multi-view geometric rigidity. CSS-BA defines the block projector $P_{K_t} = \sum_{i \in K_t} P_i P_i^\top$ and localizes the Schur operator symmetrically: $\tilde{H}_{\lambda, K_t} = P_{K_t} \tilde{H}_\lambda P_{K_t}$. Initializing from the localized negative reduced gradient, an $m$-step Lanczos process generates an orthonormal Krylov basis $Q_m \in \mathbb{R}^{n_c \times m}$ and a tridiagonal matrix $T_m \in \mathbb{R}^{m \times m}$. Selecting the top-$k$ eigenvectors $C_k$ of $T_m$ produces the low-dimensional Ritz basis: $$ V_K = Q_m C_k \in \mathbb{R}^{n_c \times k} $$ $V_K$ encapsulates the dominant curvature modes of the selected support, turning discrete block selections into smooth, coupled camera update directions. To ensure non-support camera gradients are not entirely muted, the solver calculates the complement gradient $z_g = (I - P_{K_t})(-\tilde{\mathbf{g}}_\lambda)$. If $\|z_g\|_2 > \epsilon_g$, it is Gram-Schmidt orthogonalized against $V_K$ and normalized to obtain $v_g$, assembling the full basis $V_t = [V_K, v_g] \in \mathbb{R}^{n_c \times (k+1)}$.

4. Projected LM Subproblem Solve & Full-Vector Lifting: Well-Conditioned Search with Full State Retention With $V_t$ in hand, the camera increment is parameterized as $\Delta \mathbf{c} = V_t \mathbf{y}_t$, where $\mathbf{y}_t \in \mathbb{R}^{r_t}$ is a tiny vector ($r_t \in \{k, k+1\}$, typically $10 \sim 11$). Substituting this into the damped Schur normal equations yields the projected linear system: $$ \left(V_t^\top \tilde{H}\lambda V_t\right) \mathbf{y}_t = -V_t^\top \tilde{\mathbf{g}}\lambda $$ Because $V_t$ spans only well-conditioned curvature directions, the small matrix $V_t^\top \tilde{H}_\lambda V_t$ is numerically well-behaved and easily solved. The full camera update is recovered via $\Delta \mathbf{c} = V_t \mathbf{y}_t$, followed by landmark increment recovery through standard back-substitution $\Delta \mathbf{p} = H_{pp, \lambda}^{-1}(-\mathbf{g}_p - H_{pc} \Delta \mathbf{c})$. Applying manifold updates, the trial step is evaluated using the standard LM trust-region ratio $\rho$, adapting $\lambda$ accordingly. All camera and landmark variables are optimized without loss of measurement support.

Key Experimental Results¶

Main Results¶

Evaluation was conducted on PhoneSweep (a low-parallax near-spherical benchmark with iPhone13Mini and Nexus5X subsets, initialized via GLOMAP without shared intrinsics) and BAL (Bundle Adjustment in the Large, assessing general performance). Baselines include standard unconstrained Schur-LM (Normal-LM) and Power BA (PoBA), with SphericalSfM+BA (using ground-truth shared intrinsics and spherical priors) serving as an idealized reference.

Metrics include relative rotation accuracy (RRA@$\tau$), relative translation accuracy (RTA@$\tau$), AUC@$30^\circ$, and Absolute Focal Error AFE ($|\hat{f} - f_{\text{gt}}|/f_{\text{gt}}$).

Dataset	Solver	RRA@$5^\circ$ ↑	RRA@$15^\circ$ ↑	RRA@$30^\circ$ ↑	RTA@$5^\circ$ ↑	RTA@$15^\circ$ ↑	RTA@$30^\circ$ ↑	AUC@$30^\circ$ ↑	AFE ↓
iPhone13Mini	Normal-LM	17.40	53.49	81.38	6.24	28.73	51.26	13.34	115.56
	PoBA	41.58	73.98	87.62	17.22	52.99	62.13	42.62	169.43
	CSS-BA (Ours)	85.79	86.55	87.82	77.24	86.32	89.68	79.97	158.01
	SphericalSfM (Ref.)	100.00	100.00	100.00	86.65	98.77	99.77	91.45	0.25
Nexus5X	Normal-LM	8.06	44.32	76.29	5.10	21.38	43.32	12.06	265.35
	PoBA	14.15	66.90	88.10	16.14	52.90	75.04	33.01	121.18
	CSS-BA (Ours)	86.32	91.09	95.98	81.12	94.79	98.41	83.78	0.89
	SphericalSfM (Ref.)	100.00	100.00	100.00	83.48	96.56	98.83	90.43	0.97

On standard BAL datasets with well-conditioned motion, objective reduction ratio $r_i = f_i^{\text{final}} / f_i^0$ (lower is better) and logarithmic drop $\Delta_i = \log_{10}(f_i^0 / f_i^{\text{final}})$ (higher is better) were measured:

Family	Problems	Normal-LM (mean $r$ ↓ / $\Delta$ ↑)	PoBA (mean $r$ ↓ / $\Delta$ ↑)	CSS-BA Ours (mean $r$ ↓ / $\Delta$ ↑)	Note
ladybug	20	0.01556 / 1.8713	0.01634 / 1.8604	0.01720 / 1.8089	Abundant parallax; all solvers reach similar minima
trafalgar	14	0.00484 / 2.3542	0.00471 / 2.3383	0.00460 / 2.3400	Internet photo collection; CSS-BA slightly edges baselines
dubrovnik	16	0.00484 / 2.3254	0.00491 / 2.3194	0.00530 / 2.2919	Large-scale city model; consistent convergence across solvers

Ablation Study¶

1. Geometric Gate Ablation (PhoneSweep, GLOMAP Initialization) Examining the stabilizing impact of rotation agreement (RA) and parallax (Par) filters:

Gate Configuration	iPhone13Mini AUC@$30^\circ$ ↑	iPhone13Mini AFE ↓	Nexus5X AUC@$30^\circ$ ↑	Nexus5X AFE ↓	Note
Full gate	79.97	158.01	83.78	0.89	Best accuracy; restores proper calibration on hardest set
No gate	79.98	157.82	79.56	1.06	AUC degrades notably on the degenerate Nexus5X subset
RA only	79.91	157.30	79.65	0.88	Lacks parallax check; minor pose fluctuations
Par only	79.94	158.25	79.61	0.94	Lacks orientation smoothing; slightly inferior to full gate

2. Top-$k$ Sensitivity Analysis Varying the subspace basis dimension $k \in \{4, 6, 8, 10, 12, 16\}$ across three PhoneSweep sequences:

Parameter $k$	N5X/eng (AUC@30 / AFE)	i13/scott (AUC@30 / AFE)	i13/plaza (AUC@30 / AFE)	Observed Behavior
$k=4$	97.747 / 0.503	95.365 / 0.601	94.327 / 0.692	Highly stable even with minimal basis dimension
$k=6$	97.746 / 0.128	95.394 / 0.299	93.872 / 0.586	Significant reduction in focal length error
$k=8$	97.762 / 0.430	95.365 / 0.601	93.426 / 0.576	Consistently high accuracy across sequences
$k=10$ (Default)	97.753 / 0.447	95.363 / 0.601	94.249 / 0.654	Optimal balance between generality and accuracy
$k=12$	97.754 / 0.447	95.365 / 0.601	93.294 / 0.580	Marginal gains plateau beyond $k=10$
$k=16$	97.757 / 0.467	95.391 / 0.379	93.367 / 0.578	Higher dimension offers no further geometric leap

3. Wall-Clock Runtime Breakdown Over 150 iterations on two PhoneSweep sequences, total runtimes were: Normal-LM 6495s, PoBA 1930s, and CSS-BA 13142s. CSS-BA costs $\approx 2.02\times$ Normal-LM and $6.81\times$ PoBA. The overhead stems from Lanczos decompositions and Ritz vector generation, indicating that CSS-BA explicitly trades solver throughput for vital geometric convergence stability in ill-conditioned regimes.

Key Findings¶

Substantial Accuracy Gain in Degeneracy: Under low-parallax PhoneSweep benchmarks, classical LM and PoBA collapse into corrupted trajectory configurations (AUC@$30^\circ$ only $12\% \sim 42\%$). CSS-BA suppresses updates along near-null directions, propelling AUC to $80\% \sim 84\%$ without needing motion priors.
Focal Length Decoupling: On Nexus5X, baseline solvers drift wildly with focal errors exceeding $120\% \sim 265\%$, while CSS-BA restores calibration error down to $0.89\%$, demonstrating that subspace restriction decouples depth/translation/focal ambiguities.
Robust Subspace Hyperparameter: Performance is remarkably invariant across $k \in [6, 16]$, validating that a fixed default $k=10$ generalizes without per-scene manual tuning.

Highlights & Insights¶

Solver-Side Update Subspace Restriction: Rather than modifying the BA cost function, altering residual linearizations, or removing states via keyframe selection, CSS-BA operates purely on the step search subspace of the Schur system. This keeps all parameters and physical observations fully active while preventing solver drift.
Bridging Discrete Support to Continuous Motion: Instead of freezing unselected cameras or updating blocks independently, computing Ritz vectors on the localized Schur operator $\tilde{H}_{\lambda, K_t}$ converts discrete high-gain camera selections into smooth, coupled motion trajectories across the scene.

Limitations & Future Work¶

Increased Computational Overhead: Per-iteration Lanczos iterations and Ritz projection double the execution time relative to classical LM. On well-conditioned large-scale datasets (e.g., BAL), this extra computation provides limited geometric improvement.
Static Gate Thresholds and Basis Dimensions: The gating criteria and basis size ($k=10$) are currently fixed globally. Future work could introduce adaptive subspace sizing and gating relaxation based on instantaneous Schur Hessian condition numbers.

vs Power BA / Variable Projection: While PoBA focuses on approximating the inverse Schur complement via power series to accelerate computation, CSS-BA tackles the geometric vulnerability of Schur-LM null spaces via Lanczos/Ritz subspace design.
vs Keyframe Selection / Double-Window SLAM: Traditional methods discard redundant low-parallax frames to avoid singularity. CSS-BA shows that all views carry valuable geometric constraints; restricting the solver update directions is vastly superior to discarding observations.

Rating¶

Novelty: ⭐⭐⭐⭐☆ Elegant adaptation of Column Space Search and Lanczos/Ritz projection to Schur-reduced bundle adjustment.
Experimental Thoroughness: ⭐⭐⭐⭐☆ Rigorous validation on challenging PhoneSweep benchmarks and standard BAL datasets.
Writing Quality: ⭐⭐⭐⭐⭐ Cohesive theoretical narrative from two-view geometric degeneracy to projected normal equations.
Value: ⭐⭐⭐⭐☆ Highly practical drop-in refinement tool for handheld, drone-orbiting, and low-parallax 3D reconstruction pipelines.

Parameter \(k\)	N5X/eng (AUC@30 / AFE)	i13/scott (AUC@30 / AFE)	i13/plaza (AUC@30 / AFE)	Observed Behavior
\(k=4\)	97.747 / 0.503	95.365 / 0.601	94.327 / 0.692	Highly stable even with minimal basis dimension
\(k=6\)	97.746 / 0.128	95.394 / 0.299	93.872 / 0.586	Significant reduction in focal length error
\(k=8\)	97.762 / 0.430	95.365 / 0.601	93.426 / 0.576	Consistently high accuracy across sequences
\(k=10\) (Default)	97.753 / 0.447	95.363 / 0.601	94.249 / 0.654	Optimal balance between generality and accuracy
\(k=12\)	97.754 / 0.447	95.365 / 0.601	93.294 / 0.580	Marginal gains plateau beyond \(k=10\)
\(k=16\)	97.757 / 0.467	95.391 / 0.379	93.367 / 0.578	Higher dimension offers no further geometric leap