PaperlayerView exact revision on arXiv

Source-linked AI summary

Eigendecomposition-free Training of Deep Networks with Zero Eigenvalue-based Losses

Zheng Dang, Kwang Moo Yi, Yinlin Hu, Fei Wang, Pascal Fua, Mathieu Salzmann

arXiv:1803.08071v2cs.CV

TL;DR

Differentiating eigendecompositions can cause training instabilities when eigenvalue order changes and the corresponding eigenvector switches. This paper introduces an eigendecomposition-free loss and reports state-of-the-art results on keypoint matching and PnP outlier rejection.

  • Problem

    Eigenvalue-order changes can switch the target eigenvector during training, causing numerical instabilities that may prevent convergence.

    Source: §3 · p. 5

  • Method

    The authors derive a loss that operates directly on the matrix to train networks using eigenvectors corresponding to zero eigenvalues, without explicit SVD or eigendecomposition.

    Source: §1 · p. 2, §4 · p. 5

  • Results

    The method achieves state-of-the-art results on real-image keypoint matching and PnP outlier rejection, while standard TensorFlow decompositions either fail to converge or perform significantly worse.

    Source: §1 · p. 3, §6 · p. 14

  • Takeaways & Limitations

    The approach handles vector switching and repeated eigenvalues within an end-to-end learning formalism, unlike a prior workaround that delays eigenvector-based loss until after initial training.

    Source: §4 · p. 5, §3 · p. 5

    In plane fitting, SVD- or Eigh-based methods converge; in more complex cases, they do not always converge.

    Source: §5.1 · p. 11

Abstract

from arXiv · show

Many classical Computer Vision problems, such as essential matrix computation and pose estimation from 3D to 2D correspondences, can be solved by finding the eigenvector corresponding to the smallest, or zero, eigenvalue of a matrix representing a linear system. Incorporating this in deep learning frameworks would allow us to explicitly encode known notions of geometry, instead of having the network implicitly learn them from data. However, performing eigendecomposition within a network requires the ability to differentiate this operation. Unfortunately, while theoretically doable, this introduces numerical instability in the optimization process in practice. In this paper, we introduce an eigendecomposition-free approach to training a deep network whose loss depends on the eigenvector corresponding to a zero eigenvalue of a matrix predicted by the network. We demonstrate on several tasks, including keypoint matching and 3D pose estimation, that our approach is much more robust than explicit differentiation of the eigendecomposition, It has better convergence properties and yields state-of-the-art results on both tasks.

1 Introduction

Classical vision tasks can use eigenvectors to encode geometric constraints, but integrating this approach into deep networks is hindered by unstable differentiation. The paper introduces an eigendecomposition-free loss and reports state-of-the-art results on keypoint matching and PnP pose estimation.

1 Introduction

  • Embedding geometric methods in deep networks can explicitly encode known geometry rather than require networks to relearn it, potentially allowing learning from smaller training sets.The introduction gives keypoint detection and matching with global correspondence consistency as an example.Source: §1 · pp. 1–2
  • A prior approach uses network-predicted inlier weights to form an auxiliary matrix whose smallest eigenvector is the sought-for Essential Matrix.The network is trained to bring the matrix-derived eigenvector close to the ground-truth one.Source: §1 · p. 2
  • Differentiating SVD or eigendecomposition can be unstable because the smallest-eigenvalue vector may switch abruptly, while gradient computation divides by differences between eigenvalues that may be zero.The paper notes that a proposed solution for the zero denominator does not resolve the eigenvector-switching issue.Source: §1 · p. 2
  • The loss depends on the eigenvector corresponding to a zero eigenvalue without explicitly performing SVD or eigendecomposition, and remains differentiable and robust to noise.The paper states that imperfect image measurements, which mean the eigenvalue is not strictly zero, do not affect the computation.Source: §1 · pp. 2–3
  • The proposed approach achieves state-of-the-art results on keypoint matching and PnP pose estimation, while standard TensorFlow decomposition implementations either fail to converge or perform significantly worse.The evaluations train networks for globally consistent keypoint correspondences and for outlier removal in pose estimation.Source: §1 · p. 3

2 Motivation

In the toy outlier-rejection example, reducing the outlier’s weight changes which eigenvector is smallest. That switch can cause a large gradient jump, and in more complex settings the instability can prevent convergence.

2 Motivation

  • When optimization reduces the outlier’s weight, the smallest-eigenvalue eigenvector switches from esub to enoise, causing a large jump in the gradient vector.Initially, with all weights set to one, esub is the smallest-eigenvalue vector; enoise is the plane normal.Source: §2 · p. 3
  • Although this instability does not prevent eventual convergence in the toy example, the authors found that it can prevent convergence in more complex situations.The paper notes that the issue had also been observed for learning keypoint correspondences.Source: §2 · p. 3
  • The prior keypoint method first uses a classification loss, then adds the eigenvector-based geometric loss once the network is sufficiently close to the correct solution to avoid switching.This ordering is intended to ensure eigenvector switching no longer occurs when geometry-based loss optimization begins.Source: §2 · p. 3

3 Related Work

Prior work brings geometric operations into deep networks, but the paper identifies a lack of widely accepted deep-learning methods for many linear-system vision problems. It focuses on single eigenvectors, where changing eigenvalue order can destabilize training.

3 Related Work

  • Deep-learning methods have incorporated spatial transformations and Cholesky differentiation, but widely accepted deep-learning solutions remain limited for geometric problems reducible to least-squares linear systems.The paper focuses on essential-matrix computation and 3D pose estimation from 3D-to-2D correspondences.Source: §3 · p. 4
  • For essential-matrix estimation, prior work includes classical outlier-rejection methods and a deep-learning approach that embeds geometric constraints.Other deep approaches directly estimate rotation and translation without prior geometric knowledge [19, 20].Source: §3 · p. 4
  • For PnP, DSAC uses a stochastic derivative approximation, and the paper describes it as limited to grid configurations and known scenes.The proposed method instead has an analytical form without stochastic sampling.Source: §3 · p. 4
  • When two eigenvalues are equal (σi = σj), the denominator in the eigendecomposition-derivative expression becomes 0, creating numerical instabilities; the same issue applies to singular value decomposition.Source: §3 · p. 5
  • Prior eigendecomposition-free spectral-clustering work assumes constant matrix rank and uses all nonzero eigenvalues, unlike this paper’s focus on a single eigenvalue whose order can change during training.The paper says such switching can cause instabilities that prevent convergence; the earlier keypoint approach delays its eigenvector loss until switching is avoided.Source: §3 · p. 5

4 Our Approach

The approach replaces explicit SVD or eigendecomposition with a loss that operates directly on the matrix and supports end-to-end learning with zero-eigenvalue targets. It covers both networks that output a matrix and those that predict weights used to construct one.

4 Our Approach

  • The proposed loss operates directly on the matrix, avoiding explicit SVD or eigendecomposition and the associated vector-switching and repeated-eigenvalue difficulties.It is intended for end-to-end optimization of eigenvectors corresponding to zero eigenvalues.Source: §4 · p. 5

4.1 Generic Scenario

  • The generic loss uses the ground-truth eigenvector and the positive-semidefinite matrix AθᵀAθ to target a zero minimum eigenvalue.The loss alone admits the trivial global solution Aθ = 0, so the formulation adds a term that maximizes projection along directions orthogonal to the target vector.Source: §4.1 · pp. 6–7
  • The loss is fully differentiable without an eigendecomposition at each optimization step, avoiding eigenvector switching and non-unique-eigenvalue problems.The approach also discusses extending the strategy to multiple zero eigenvalues.Source: §4.1 · p. 7

4.2 Learning to Predict Weights

  • For weight-prediction networks, the matrix commonly takes the form XT WX, with W diagonal and its entries equal to the predicted weights.This formulation covers the paper's applications, where the network predicts one weight per input element.Source: §4.2 · p. 7

Outlier Rejection with 3D Points.

  • The 3D-point outlier-rejection example directly optimizes point weights using the weighted covariance matrix, whose smallest eigenvector gives the noise direction.The points are mean-centered before forming the covariance matrix.Source: Outlier Rejection with 3D Points · p. 7

Keypoint Matching with the Essential Matrix.

3D-to-2D Correspondences for Pose Estimation.

For 3D-to-2D correspondences, the network predicts weights used by a weighted DLT solution to estimate calibrated-camera pose. A generalized Procrustes step refines the pose only during validation and testing.

3D-to-2D Correspondences for Pose Estimation.

  • The PnP task estimates calibrated-camera rotation and translation from known 3D points and corresponding 2D image points.The network receives the sparse correspondences and predicts one weight per correspondence.Source: 3D-to-2D Correspondences for Pose… · p. 8
  • Weighted DLT constructs X from the correspondences, and the smallest-eigenvalue eigenvector of XT WX encodes the pose targeted by the PnP loss.The network is trained to predict correspondence weights that recover the ground-truth pose.Source: 3D-to-2D Correspondences for Pose… · p. 9
  • Generalized Procrustes refinement makes the DLT result a valid rotation matrix, but is used only for validation model selection and testing, not training.The DLT solution does not preserve rotation-matrix orthogonality or determinant 1.Source: 3D-to-2D Correspondences for Pose… · p. 9

5 Experiments

Experiments cover plane fitting, keypoint matching, and PnP, comparing convergence and performance against decomposition-based and other baselines. Results highlight the proposed method’s convergence behavior and robustness to outliers.

5.1 Plane Fitting

  • In plane fitting, our method converges gradually without overly large gradients; SVD and Eigh show slow loss reduction until an eigenvector switch, and take millions of iterations with vanilla gradient descent.Across tested learning rates from 10^-5 to 1, none produced faster convergence for SVD or Eigh with vanilla gradient descent.Source: Figure 2 · p. 10, §5.1 · pp. 10–11
  • With multiple plane-fitting outliers, our method correctly classifies inliers and outliers, whereas the SVD baseline discards many inliers and accepts outliers.Both approaches still converge in this setting.Source: Figure 3 · p. 11, §5.1 · p. 11
  • The plane-fitting baseline’s convergence in the toy example does not always extend to the more complex cases evaluated below.The paper notes that SVD- or Eigh-based methods converge in this example, but not always in the subsequent cases.Source: §5.1 · p. 11

5.2 Keypoint Matching

  • On keypoint matching, our method performs roughly on par with and outperforms the other baselines; “Essential Only” severely underperforms and often fails.The method also identifies inliers automatically during training, unlike ’s workaround based on a user-selected decision boundary.Source: Figure 4 · p. 12, §5.2 · p. 12
  • In qualitative keypoint-matching comparisons, our false-positive inliers are close to correct correspondences, while RANSAC’s are substantially wrong.The comparisons use image pairs from the dataset of and SUN3D.Source: §5.2 · p. 12, Figure 5 · p. 13

5.3 PnP

  • Our method significantly outperforms the compared PnP methods, especially as outliers increase, while REPPnP is the least affected competing method.REPPnP is on par with our method when outlier counts are small, but falls behind beyond a threshold.Source: §5.3 · p. 13
  • For PnP, our method maintains near-zero rotation and translation error with up to 130 outliers (65%), while compared methods perform significantly worse as outliers increase.Other methods may perform well on rotation or translation, but not both.Source: Figure 6 · p. 14

6 Conclusion

The paper reports state-of-the-art results for keypoint matching and PnP outlier rejection, with its loss avoiding eigendecomposition instabilities and converging faster. It proposes investigating additional tasks, including homography estimation.

6 Conclusion

  • The approach achieves state-of-the-art results on real-image keypoint matching and PnP outlier rejection.Its loss avoids the numerical instabilities of analytical eigendecomposition differentiation and converges to the correct solution much faster.Source: §6 · p. 14
  • The authors identify homography estimation as a task for future investigation.They also hope the approach will help integrate traditional Computer Vision knowledge into Deep Learning.Source: §6 · p. 14
  • For PnP, the proposed loss converges nicely, while the explicit eigendecomposition-based loss does not converge to anything meaningful.The comparison is shown in the loss evolution for the PnP problem.Source: Figure 7 · p. 15

1 Appendix

The appendix provides additional results for plane fitting, keypoint matching, and PnP, including learning curves, per-sequence comparisons, and real-image pose results. The PnP model is evaluated on real images without fine-tuning after synthetic-data training.

1 Appendix

  • The appendix supplies additional details for the results reported in Section 5 of the main paper.It covers plane fitting, keypoint matching, and PnP.Source: §1 · p. 18

1.1 Plane Fitting

  • Across the tested learning rates, the proposed approach converges and finds the correct plane-fitting inliers, whereas SVD/Eigh can fail to converge or misclassify points.With Adam, SVD/Eigh converge only with an eigenvector switch; with gradient descent, learning fails.Source: §1.1 · p. 18, Figure 8 · p. 20, Figure 9 · p. 21

1.2 Keypoint Matching

  • On SUN3D and Strecha individual sequences, across error thresholds 5, 10, and 20, our method performs essentially on par with state-of-the-art method without pre-training with a different loss.Source: §1.2 · p. 18, Figure 10 · p. 22, Figure 11 · p. 23

1.3 PnP

  • Without fine-tuning, a model trained only on synthetic data yields much lower PnP errors than all baselines on four real image pairs.Its 3D-point reprojections also align more closely with ground-truth locations than EPnP+RANSAC, the best-performing baseline described as on par with OPnP and P3P+RANSAC.Source: §1.3 · pp. 18–19, Table 1 · p. 19, Table 2 · p. 19

Related papers

Loading 1803.08071v2…