PaperlayerView exact revision on arXiv

Source-linked AI summary

No Cones, No Duals: A Fast and Scalable Solver for NRSfM

Suryansh Kumar

arXiv:2610.34403v1cs.CV

TL;DR

Shape-space NRSfM methods achieve strong reconstruction results, but conventional SDP rotation correction and ADMM shape recovery can limit scalability. This paper replaces those solver components with factor-side rotation estimation and an unrolled spectral-proximal shape solver; across benchmarks, it reports substantial speedups with competitive reconstruction accuracy.

  • Problem

    Shape-space NRSfM relies on costly SDP-based Euclidean correction and ADMM shape recovery, which become bottlenecks as sequences lengthen or point tracks grow denser.

    Source: §1 · pp. 1–2

  • Method

    The solver optimizes small per-sequence factors for rotation recovery and uses an unrolled spectral-proximal method for low-rank shape recovery.

    Source: §1 · p. 3, §3.2 · p. 5

  • Results

    Across sparse and dense benchmarks, the solver achieves substantial runtime gains while retaining competitive reconstruction accuracy.

    Source: §1 · p. 3

  • Takeaways & Limitations

    The solver is category-agnostic, requires no external training data, and is presented as a practical tool for 3D reconstruction.

    Source: §1 · p. 3, §11.3 · p. 17

    The method assumes classical orthographic tracked-point NRSfM with reliable 2D tracks, known visibility masks for missing data, and mean-centered measurements.

    Source: §5 · p. 8

Abstract

from arXiv · show

Non-rigid structure from motion (NRSfM) aims to recover camera motion and time-varying 3D shape from tracked 2D image measurements. Recent high-performing methods show that shape-space factorization remains highly effective for this task. These methods often use costly solvers for two key steps. First, a semidefinite programming (SDP) cone solver to perform Euclidean correction. Next, an alternating direction method of multipliers (ADMM) solver to recover the low-rank shape. These steps often scale poorly to long sequences and dense point tracks. We propose a fast, scalable NRSfM solver that avoids these costly steps. For rotation estimation, we introduce a differentiable Euclidean correction that directly optimizes small factors for each sequence. A row-polar projection then maps each estimated camera block to the closest row-orthonormal matrix. For shape estimation, we introduce an unrolled spectral-proximal solver. It combines reprojection-gradient steps with weighted singular-value shrinkage in the reshuffled shape domain. This solver further uses FISTA-style restart and continuation. The spectral shrinkage operator itself is classical, but we embed it in a fixed differentiable solver, while preserving NRSfM's geometric constraints. The proposed approach is category-agnostic, requires no external training data, and maps naturally to modern accelerator-friendly linear algebra primitives. Across sparse, dense, noisy, missing-data, and long-sequence benchmarks, our solver achieves substantial speedups with competitive reconstruction accuracy, including 7x-1000x runtime improvements on dense sequences with 28,887 tracked points.

1. Introduction

Shape-space NRSfM can achieve strong reconstruction accuracy, but its conventional rotation and shape solvers impose costly computation. The paper replaces those solver components while retaining the orthographic camera constraints and low-rank shape structure.

1. Introduction

  • Across sparse and dense benchmarks, the solver offers a better accuracy-runtime tradeoff and large speedups on dense sequences while remaining competitive in accuracy.Figure 1 compares accuracy and runtime on CMU MoCap and dense sequences with 28,887 tracks.Source: Figure 1 · p. 1, §1 · p. 3
  • NRSfM must recover camera motion and deforming 3D shape from 2D tracks, where many plausible decompositions can explain the same observations.This paper focuses on the classical orthographic setting, with row-orthonormal camera blocks and a low-rank shape space.Source: §1 · p. 1
  • Recent shape-space methods can outperform trajectory-space methods in reconstruction accuracy, but their SDP-based Euclidean correction and ADMM shape recovery become costly for long videos or dense tracks.SDP cone solvers are difficult to parallelize efficiently, while ADMM adds auxiliary variables, dual updates, and large subproblem solves.Source: §1 · p. 2
  • The proposed solver replaces SDP rotation recovery with per-sequence factor optimization and row-polar projection, and replaces ADMM shape recovery with an unrolled spectral-proximal loop.The paper presents the pathway—not a new low-rank prior or shrinkage operator—as its central contribution.Source: §1 · pp. 2–3

2. Preliminaries

  • In the orthographic factorization W ≈ RS, camera blocks have orthonormal rows, while the reshuffled shape matrix has rank bounded by the shape-space dimension.The Euclidean-correction formulation uses positive-semidefinite, low-rank Gram matrices; the shape stage commonly uses spectral penalties and ADMM-style updates.Source: §2 · p. 3

3. Proposed Approach

The proposed approach estimates rotations without a cone solver, then recovers low-rank shape without ADMM dual variables or large shape-subproblem solves. Its fixed unrolled spectral-proximal updates combine reprojection gradients, weighted shrinkage, and restart and continuation safeguards.

3. Proposed Approach

  • The two-stage solver recovers camera rotations without an SDP cone program, then estimates shape without ADMM dual variables or large shape-subproblem solves.Its design targets the two computational bottlenecks identified for shape-space NRSfM.Source: §3 · p. 4

3.1. Rotation Estimation

  • Per-sequence factor variables enforce positive semidefiniteness and rank at most three by construction, avoiding direct optimization over Gram matrices.The factors are optimized using measurement-space orthonormality residuals and scale and trace regularizers; the selected camera blocks are mapped to the closest row-orthonormal matrices by row-polar projection.Source: §3.1 · p. 4

3.2. Shape Estimation

  • Shape recovery combines a reprojection-gradient step with weighted singular-value shrinkage on the reshuffled shape matrix, followed by FISTA-style momentum.A monotone restart resets the momentum when the objective increases; a fixed iteration count yields predictable runtime.Source: §3.2 · pp. 4–5
  • Continuation strengthens low-rank shrinkage early and relaxes it later, while preserved leading modes and capped shrinkage help protect meaningful deformation modes.The continuation and safeguard parameters are fixed across experiments unless otherwise stated.Source: §3.2 · p. 5
  • The fixed-depth shape solver uses feed-forward gradient and spectral-shrinkage operations instead of ADMM split variables, dual updates, and large linear solves.Its layers use matrix multiplication, masking, reshaping, SVD, scalar shrinkage, and FISTA-style skip or restart.Source: §3.2 · p. 5

4. Experiment and Results

Across the evaluated benchmarks, the solver targets a favorable accuracy-runtime tradeoff, with substantial speedups on dense tracks and competitive reconstruction accuracy. Experiments assess rotation and shape stages, benchmark performance, and robustness to missing and noisy data.

4. Experiment and Results

  • Experiments used 160 fixed unrolling steps for shape recovery, although the objective stabilized earlier on most sequences.Runtimes are indicative scaling trends; where same-hardware reruns were unavailable, reported baseline runtimes were used.Source: §4 · pp. 5–6

4.1. Dataset and Results

  • Rotation estimation achieves accuracy better or close to state-of-the-art shape-space methods while using considerably less computation time.On the 1,102-frame Drink sequence, OPM and TSM [57] runtimes increase substantially, while the proposed solver’s increase is modest.Source: §4.1 · pp. 6–7, Table 2 · p. 6
  • With rotations fixed, shape estimation is consistently faster and remains competitive in e3d across the benchmark.The comparison uses the best K from previous methods; on the more-than-1,000-frame Drink sequence, the solver uses significantly less compute time.Source: §4.1 · p. 7, Table 3 · p. 7
  • On the NRSfM challenge benchmark, reconstruction is best or near-best for Articulated, Balloon, and Tearing, and favorably accurate for Paper and Stretch.The RMSE values in Table 4 are in millimeters and averaged over six camera trajectories; weaker cases involve challenging deformation and camera configurations.Source: §4.1 · p. 7, Table 4 · p. 7
  • 7×–1000× faster than OPM and TSM [57] on dense sequences, the solver demonstrates scalability on tracks with 28,887 feature points.The dense benchmark includes four synthetic face sequences; the comparison uses CSF2 initialization for TSM because its default initialization breaks down.Source: §4.1 · pp. 7–8, Table 5 · p. 7
  • On H3WB’s one-circle camera-motion setting, the solver achieves the best e3d on several actions and remains competitive on the rest.Additional H3WB results are reported in the supplementary material.Source: §4.1 · p. 8, Table 6 · p. 8

4.2. Ablations

  • The rotation-loss ablation supports the usefulness of its orthonormality, scale, and trace terms; on missing trajectories, the method performs comparably with state-of-the-art approaches.The missing-data experiment randomly removes 30% of a trajectory from W.Source: §4.2 · p. 8, Figure 5 · p. 8, Figure 4 · p. 8
  • On noisy trajectories, the solver is reported robust without noise-specific tuning and stable compared with state-of-the-art approaches.Methods were run ten times for each noise standard deviation, and their mean e3d was plotted.Source: §4.2 · p. 8, Figure 6 · p. 8

5. Limitations and Closing Remarks

The solver is scoped to classical orthographic NRSfM with tracked points, reliable tracks, known visibility masks, and mean-centered measurements. It omits several specialized priors, which can improve accuracy when they match the data.

Limitations

  • The method assumes classical orthographic NRSfM, reliable 2D tracks, known visibility masks for missing data, and mean-centered measurements.Its shape stage does not use image-grid smoothness, explicit camera-trajectory or temporal deformation priors, or category-level training.Source: §5 · p. 8
  • Specialized methods can be more accurate when their additional priors match the data, such as smooth dense surfaces or challenging camera motion.Perspective cameras and lightweight spatial or temporal priors are identified as future directions.Source: §5 · p. 8

Closing Remarks

  • The closing argument is that accurate shape-space NRSfM can replace Gram-matrix cone optimization and ADMM with differentiable correction and an unrolled spectral-proximal solver.The paper presents this as a way to retain NRSfM factorization while making computation simple, scalable, and accelerator-friendly.Source: §5 · p. 8

Abstract

The supplement reports additional comparisons, long-sequence and noisy-data experiments, ablations, and theoretical analyses. Its results include favorable trajectory-space and H3WB comparisons and row-orthonormality residuals near 10^-7.

Abstract

  • The supplement adds benchmark comparisons, deep-learning comparisons on long CMU sequences, rotation-transfer and noisy-data results, solver-complexity analysis, and a Lipschitz-continuity proof.It also includes a step-by-step derivation and additional qualitative results.Source: Abstract · p. 12

6.1. Comparison with trajectory-space approaches

  • Our approach more often outperforms trajectory-space methods on CMU MoCap and performs well across Dense Face sequences, where trajectory methods struggle with high-frequency details.Trajectory-space methods can be faster by using fixed temporal bases, but may fail to model high-frequency details.Source: §6.1 · p. 12, Table 7 · p. 12, Table 8 · p. 12

6.2. More results on H3WB dataset

  • For H3WB, our approach achieves better e3d in most Fixed-type camera cases and accuracy favorably close to the state of the art for Multi-circle-type motion.The comparisons are shown in Tables 9 and 10.Source: §6.2 · p. 12, Table 9 · p. 12, Table 10 · p. 13

6.3. Orthonormality residuals

  • 10^-7 residuals show that recovered camera blocks satisfy the orthographic row-orthonormality constraint to high numerical precision, including sequences without ground-truth rotations.Figure 7 reports frame-wise residuals and sequence-level mean and maximum values; the projection uses Newton-Schulz inverse-square-root iterations.Source: §6.3 · p. 13, Figure 7 · p. 13

7. Comparison with deep-learning approaches on long-sequence CMU MoCap Dataset.

The solver is evaluated on the unseen test set of a large CMU Motion Capture dataset. It works well on these large sequences without a dataset-driven object prior, extending the reported scope of factorization approaches.

7. Comparison with deep-learning approaches on long-sequence CMU MoCap Dataset

  • The CMU Motion Capture dataset contains 144 subjects, 31 keypoints, and more than 10,000 frames.The train/test division follows [29].Source: §7 · p. 13
  • The comparison uses the unseen test set because the approach does not rely on category-specific training.Source: §7 · p. 13
  • The solver works well on large sequences without learning a dataset-driven object prior, stretching factorization's previously smaller-sequence scope.Source: §7 · p. 13

8. Additional Ablation Study

The additional experiments test the proposed rotation estimates within existing methods and examine performance under noise. The reported rotation integrations usually improve reconstruction, while noise-level results follow a similar e3d variation trend.

Additional rotation results

  • The proposed rotation estimates improve other methods' 3D reconstruction results in most cases when integrated into their shape-recovery pipelines.Source: §8 · p. 13
  • When e3d differences are not improvements, they are on the order of 10^-3, while compute-time improvement can still be significant.The runtime comparison is referenced to Table 2.Source: §8 · p. 13

Additional results on noisy data sequence

  • On Pickup and Stretch, e3d varies similarly to other state-of-the-art methods across noise levels in W; the authors infer robustness to noise.They describe the approach as well-suited to practical applications in soft robotics and vision-based automation.Source: §8 · p. 13, Figure 8 · p. 13

9. Detailed Pipeline

The pipeline estimates camera rotations through factor-side Euclidean correction, then recovers shape with an unrolled spectral-proximal solver.

9. Detailed Pipeline

  • The rotation stage estimates the block-orthographic camera matrix using factor-side Euclidean correction.The detailed pipeline description identifies this as the rotation stage described in Section 3.1.Source: §9 · p. 13
  • The shape stage initializes from the estimated camera matrix and applies repeated spectral-proximal updates to recover shape.Each layer uses a reprojection-gradient step, reshuffling, weighted singular-value shrinkage, inverse reshaping, FISTA-style restart, and continuation.Source: §9 · p. 14
  • The pipeline replaces SDP rotation solvers and ADMM shape updates with matrix multiplications, SVD-based shrinkage, and small row-polar projections.Table 11 reports e3d on large CMU MOCAP unseen categories, with Brown shown as second-best.Source: §9 · p. 14, Table 11 · p. 14

10. Why the row–polar projection is the closest 2 × 3 row–orthonormal matrix?

The row-polar projection is justified as the Frobenius-closest row-orthonormal camera block. The section derives its optimality and explains its use in rotation estimation.

10. Why the row–polar projection is the closest 2 × 3 row–orthonormal matrix?

  • The projection seeks the closest row-orthonormal 2 × 3 matrix to a given camera-block estimate.The target matrices lie in St(2, 3), whose rows are orthonormal.Source: §10 · p. 14

10.1. Equivalent trace maximization

  • Minimizing the Frobenius objective is equivalent to maximizing a linear trace functional over row-orthonormal matrices.The SVD reduces that maximization to a solution attaining σ1 + σ2.Source: §10.1 · p. 14, §10.2 · p. 15

10.2. SVD reduction and solution form

  • The SVD reduction yields a unique maximizer when the input has full row rank and distinct positive singular values.Rank-1 or isotropic inputs admit a low-dimensional family of maximizers.Source: §10.2 · p. 15

10.3. Equivalence to the row polar factor

  • For full row rank, the row-polar factor is the unique Frobenius-closest row-orthonormal matrix; for rank-deficient inputs, it remains a canonical choice among minimizers.The polar factor is row-orthonormal by construction.Source: §10.3 · p. 15

10.4. Usage in our rotation estimation

  • Rotation estimation projects each synthesized 2 × 3 block onto the row-orthonormal camera constraint using the row-polar factor.The projection is differentiable almost everywhere and is non-smooth only when the input block is rank-deficient.Source: §10.4 · p. 15

11. Complexity Analysis

The proposed solver replaces SDP and ADMM optimization-heavy steps with basic linear algebra primitives. Its complexity analysis reports faster rotation and shape stages and practical runtimes on typical benchmarks.

11.1. Rotation Estimation

  • Rotation estimation reduces theoretical runtime from O(K^6) per sequence to O(FK^2), with memory falling from O(K^4) to O(FK).The method uses learnable corrective factors and row-polar projections instead of SDP cone solves.Source: §11.1 · p. 16

11.2. Shape Estimation

  • The shape solver removes ADMM’s linear system and dual variable, and typically converges in Nk ≈40-60 layers.Its layers use GEMM and SVD; FISTA acceleration and continuation add only O(FP) bookkeeping.Source: §11.2 · p. 17
  • ADMM and the proposed shape solver require SVDs of the same shape matrix, but ADMM adds O((3F)^3P) linear solves per iteration.The paper reports that this makes ADMM 1–2 orders of magnitude slower and that the unrolled solver reaches identical objective values with less runtime and memory overhead on dense datasets.Source: §11.2 · pp. 16–17

11.3. Discussion

  • Typical benchmarks run in a few seconds on an NVIDIA A6000 GPU or Apple M3 processor, versus several minutes for SDP/ADMM pipelines.The stated setting is F ≈300, P ≈30−100, and K ≤13.Source: §11.3 · p. 17

12. Lipschitz properties: Re-projection term

The section analyzes the reprojection objective used by the shape solver, establishing an affine gradient and a global Lipschitz bound. Under orthography, the bound supports step sizes up to one for proximal-gradient iterations.

12. Lipschitz properties: Re-projection term

  • The objective combines a reprojection term with a nonsmooth regularizer that promotes low-rank structure across frames.The reprojection term enforces consistency between estimated 3D structure and observed 2D points.Source: §12 · p. 17

12.1. Preliminaries and notations

  • The analysis expresses reprojection and visibility masking as a composite linear operator and its adjoint.The measurement mask is applied by Hadamard masking, and the camera operator maps shape through R.Source: §12.1 · p. 17

12.2. Differentiability and the gradient of f

  • The smooth reprojection term is globally C1, with an affine gradient given by ∇f(S) = A∗A(S) − A∗B.The gradient follows from the operator form of the least-squares objective.Source: §12.2 · pp. 17–18

12.3. Lipschitz continuity of the gradient (L– smoothness)

  • The gradient is globally Lipschitz, and under orthography its Lipschitz constant can be taken as L = 1.The bound uses the orthonormal rows of the blockwise camera matrix.Source: §12.3 · p. 18

12.4. On Lipschitz continuity of f itself

  • The objective itself is Lipschitz on bounded sets, with a constant that depends linearly on the radius.The paper identifies Lipschitz continuity of the gradient, rather than of the objective on an unbounded domain, as the relevant algorithmic property.Source: §12.4 · p. 18

12.5. Consequences (step sizes and descent)

  • Under orthography, choosing α ≤1 satisfies the step-size condition for monotonic decrease in proximal-gradient and FISTA-with-restart iterations.The section states the general condition as α ∈(0, 1/L].Source: §12.5 · p. 18

13. Additional Discussion and Results

Additional analyses examine pose impact, rank and shrinkage sensitivity, runtime, and qualitative results. They also describe accuracy tradeoffs and the possible cost of coordinate-descent refinement.

Sequence-wise accuracy tradeoffs

  • Coordinate-descent refinement may improve accuracy on some sequences, especially with imperfect initial cameras, but adds an outer loop and runtime.The solver instead retains a sequential rotation-then-shape design; competing priors benefit on some more difficult sequences.Source: §13 · p. 19

Stage-wise runtime accounting

  • Runtime accounting separates rotation correction and row-polar projection from the fixed-depth shape solver, with total time equal to their sum.Longer, denser, and challenging sequences incur higher cost, while total runtime remains within a practical range.Source: Table 14 · p. 19, §13 · p. 19

Sensitivity to the shape-space rank K

  • Across K values from 10 to 13, the solver remains stable and shows no monotonic advantage from increasing rank.Nearby rank values slightly improve reported error in several cases.Source: §13 · p. 19, Table 15 · p. 19

Sensitivity to continuation and spectral safeguards

  • Continuation rate η has the strongest effect: η = 1.10 consistently degrades accuracy, while η ∈{1.02, 1.05} is more stable.Preserving two modes can weaken low-rank regularization, especially on Drink; caps of 0.95–0.99 are more reliable than 0.90.Source: §13 · pp. 19–20
  • The fixed main-paper defaults give stable results without aggressive per-sequence tuning.Some η = 1.02 settings yield slightly lower errors, while the defaults provide a stable accuracy-runtime tradeoff.Source: §13 · p. 20

Pose-impact diagnostic using GT rotations

  • Replacing estimated rotations with ground-truth rotations changes e3d by only 8 × 10−4 on Drink, 3 × 10−3 on Pickup, 0 on Yoga, and 10−4 on Stretch.The authors report that ground-truth rotations do not by themselves guarantee ground-truth shape recovery.Source: §13 · p. 20, Table 19 · p. 20

Qualitative evaluation on real dense sequences

  • Qualitative evaluations include real dense videos with coherent 3D structure and additional results across H3WB, NRSfM challenge, CMU Mocap, and Dense Face data.The real dense sequences have no ground-truth 3D shape.Source: §13 · p. 20, Figure 10 · p. 20, Figure 11 · p. 21

Related papers

Loading 2610.34403v1…