Multidirectional Conjugate Gradients for Scalable Bundle Adjustment

• URL: http://arxiv.org/abs/2110.04015v1
• Date: Fri, 8 Oct 2021 10:21:44 GMT
• Title: Multidirectional Conjugate Gradients for Scalable Bundle Adjustment
• Abstract summary: We propose a technique that accelerates the solution of the normal equation by up to 61%. We enlarge the search space of classical preconditioned conjugate gradients to include multiple search directions. The resulting algorithm requires fewer iterations, leading to a significant speedup of large-scale reconstruction.
• Score: 57.18172547021947
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: We revisit the problem of large-scale bundle adjustment and propose a technique called Multidirectional Conjugate Gradients that accelerates the solution of the normal equation by up to 61%. The key idea is that we enlarge the search space of classical preconditioned conjugate gradients to include multiple search directions. As a consequence, the resulting algorithm requires fewer iterations, leading to a significant speedup of large-scale reconstruction, in particular for denser problems where traditional approaches notoriously struggle. We provide a number of experimental ablation studies revealing the robustness to variations in the hyper-parameters and the speedup as a function of problem density.

Related papers

• Analytical Series Expansion for Efficient Gradient Evaluation in Multi-Qubit Optimal Control [42.97938764966747]
  We present a unifying framework for gradient-based quantum optimal control.<n>For the case of unitary propagators, we derive a series expansion involving time-independent commutators and time-dependent coefficients.<n>The method is particularly suited for simulating optimal control tasks in quantum systems with local interactions.
  arXiv  Detail & Related papers  (2026-07-29T12:50:52Z)
• Decomposed Diffusion Sampler for Accelerating Large-Scale Inverse Problems [64.29491112653905]
  We propose a novel and efficient diffusion sampling strategy that synergistically combines the diffusion sampling and Krylov subspace methods. Specifically, we prove that if tangent space at a denoised sample by Tweedie's formula forms a Krylov subspace, then the CG with the denoised data ensures the data consistency update to remain in the tangent space. Our proposed method achieves more than 80 times faster inference time than the previous state-of-the-art method.
  arXiv  Detail & Related papers  (2023-03-10T07:42:49Z)
• Reweighted Interacting Langevin Diffusions: an Accelerated Sampling Methodfor Optimization [28.25662317591378]
  We propose a new technique to accelerate sampling methods for solving difficult optimization problems. Our method investigates the connection between posterior distribution sampling and optimization with Langevin dynamics.
  arXiv  Detail & Related papers  (2023-01-30T03:48:20Z)
• Revisiting the acceleration phenomenon via high-resolution differential equations [6.53306151979817]
  Nesterov's accelerated gradient descent (NAG) is one of the milestones in the history of first-order algorithms. We investigate NAG for the $mu$-strongly convex function based on the techniques of Lyapunov analysis and phase-space representation. We find that the high-resolution differential equation framework from the implicit-velocity scheme of NAG is perfect and outperforms the gradient-correction scheme.
  arXiv  Detail & Related papers  (2022-12-12T04:36:37Z)
• Improving Diffusion Models for Inverse Problems using Manifold Constraints [55.91148172752894]
  We show that current solvers throw the sample path off the data manifold, and hence the error accumulates. To address this, we propose an additional correction term inspired by the manifold constraint. We show that our method is superior to the previous methods both theoretically and empirically.
  arXiv  Detail & Related papers  (2022-06-02T09:06:10Z)
• Bregman divergence based em algorithm and its application to classical and quantum rate distortion theory [61.12008553173672]
  We address the minimization problem of the Bregman divergence between an exponential subfamily and a mixture subfamily in a Bregman divergence system. We apply this algorithm to rate distortion and its variants including the quantum setting.
  arXiv  Detail & Related papers  (2022-01-07T13:33:28Z)
• Towards Mixed-Precision Quantization of Neural Networks via Constrained Optimization [28.76708310896311]
  We present a principled framework to solve the mixed-precision quantization problem. We show that our method is derived in a principled way and much more computationally efficient.
  arXiv  Detail & Related papers  (2021-10-13T08:09:26Z)
• Achieving fast high-fidelity optimal control of many-body quantum dynamics [0.0]
  We demonstrate the efficiency of a recent exact-gradient optimal control methodology by applying it to a challenging many-body problem. We observe fidelities in the range 0.99-0.9999 with associated minimal process duration estimates. Overall, the comparison suggests significant methodological improvements also for many-body systems in the ideal open-loop setting.
  arXiv  Detail & Related papers  (2020-08-13T18:30:24Z)
• Cogradient Descent for Bilinear Optimization [124.45816011848096]
  We introduce a Cogradient Descent algorithm (CoGD) to address the bilinear problem. We solve one variable by considering its coupling relationship with the other, leading to a synchronous gradient descent. Our algorithm is applied to solve problems with one variable under the sparsity constraint.
  arXiv  Detail & Related papers  (2020-06-16T13:41:54Z)
• Total Deep Variation: A Stable Regularizer for Inverse Problems [71.90933869570914]
  We introduce the data-driven general-purpose total deep variation regularizer. In its core, a convolutional neural network extracts local features on multiple scales and in successive blocks. We achieve state-of-the-art results for numerous imaging tasks.
  arXiv  Detail & Related papers  (2020-06-15T21:54:15Z)
• Stochastic gradient algorithms from ODE splitting perspective [0.0]
  We present a different view on optimization, which goes back to the splitting schemes for approximate solutions of ODE. In this work, we provide a connection between descent approach and gradient first-order splitting scheme for ODE. We consider the special case of splitting, which is inspired by machine learning applications and derive a new upper bound on the global splitting error for it.
  arXiv  Detail & Related papers  (2020-04-19T22:45:32Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.