Singular Value Decomposition (SVD)

SVD is the definitive method for extracting the relative rotation and translation (up to scale) between two calibrated cameras from the Essential Matrix. The algorithm involves:

• Enforcing the rank-2 constraint on the estimated matrix via SVD.
• Decomposing the resulting matrix into four possible solutions for rotation and translation.
• Applying the chirality constraint to select the physically valid pose where reconstructed 3D points are in front of both cameras. This process is central to Structure from Motion (SfM) and Visual Odometry (VO) pipelines.

For the Perspective-n-Point (PnP) problem—estimating camera pose from 3D-2D correspondences—SVD underpins efficient linear solutions. The Direct Linear Transform (DLT) formulates pose estimation as a homogeneous linear system, A x = 0. Solving for the camera projection matrix P involves:

• Constructing matrix A from the 2D-3D correspondences.
• Performing SVD on A: A = U Σ V^T.
• The solution for the parameters of P is the column of V corresponding to the smallest singular value in Σ. This provides an initial estimate often refined by non-linear optimization.

SVD provides the closed-form, optimal solution for aligning two sets of 3D points, a problem known as Orthogonal Procrustes Analysis. This is critical in Iterative Closest Point (ICP) and bundle adjustment. The steps are:

1. Compute the centroid of each point set and center them.
2. Construct the covariance matrix H = X * Y^T, where X and Y are the centered point matrices.
3. Perform SVD: H = U Σ V^T.
4. The optimal rotation is R = V * U^T (ensuring a proper rotation, det(R)=1).
5. Solve for translation based on the centroids. This yields the rigid transformation minimizing the least-squares error.

SVD is used to solve for projective transformations from noisy point correspondences. For homography estimation (mapping points between two images of a plane) or fundamental matrix estimation, the problem is formulated as minimizing ||Ah|| or ||Af||=0 subject to a constraint.

• The 8-point algorithm for the fundamental matrix constructs a matrix A from correspondences.
• Solving Af=0 via SVD of A gives the initial estimate for f (reshaped into the 3x3 matrix).
• A subsequent SVD step enforces the rank-2 constraint for the fundamental matrix or the special structure for the essential matrix.

In computer vision data pre-processing, SVD is used for principal component analysis (PCA). By decomposing a data matrix (e.g., a set of aligned facial images or point cloud coordinates), SVD identifies the orthogonal directions of maximum variance (eigenvectors).

• Truncating the SVD by keeping only the top k singular values and vectors provides a low-rank approximation.
• This compresses data, removes noise, and reveals latent structure, which is useful for tasks like eigenfaces, point cloud simplification, and stabilizing estimations by filtering out minor components corresponding to noise.

The singular values produced by SVD directly diagnose the numerical stability of vision estimation problems. The condition number of a matrix—the ratio of its largest to smallest singular value—indicates sensitivity to input noise.

• A high condition number signals an ill-posed problem, such as estimating camera motion from points on a near-degenerate configuration (e.g., a planar scene).
• Engineers monitor singular value spectra to detect such issues in SfM and SLAM systems, triggering fallback strategies or requesting more diverse data to improve the observability of the solution.

Eigenvalue Decomposition is a matrix factorization method that decomposes a square, diagonalizable matrix into its eigenvectors and eigenvalues. It is a special case of SVD applicable only to square matrices. In computer vision, it is used for tasks like Principal Component Analysis (PCA), which reduces data dimensionality. While SVD works on any rectangular matrix, eigenvalue decomposition requires the matrix to be square and often symmetric for stable results.

Linear Least Squares is an optimization method for finding the best-fitting solution to a system of linear equations by minimizing the sum of the squares of the residuals. SVD provides a robust, numerically stable solution to least-squares problems, which are ubiquitous in vision. Key applications include:

• Solving for the Essential Matrix or Homography from point correspondences.
• Performing Procrustes analysis to align 3D point sets.
• The solution is found via the pseudoinverse, which is computed directly from the SVD.

The Pseudoinverse, denoted A⁺, is a generalization of the matrix inverse for non-square or rank-deficient matrices. It provides a least-squares solution to linear systems. The SVD offers the most numerically stable way to compute it: if A = UΣVᵀ, then A⁺ = VΣ⁺Uᵀ, where Σ⁺ is formed by taking the reciprocal of each non-zero singular value. This is critical in vision for solving over-determined systems (e.g., from many feature matches) where no exact solution exists.

Matrix Rank is the number of linearly independent rows or columns, equivalent to the number of non-zero singular values from an SVD. The Null Space is the set of all vectors that, when multiplied by the matrix, yield zero. SVD explicitly reveals these:

• Rank: The count of non-zero singular values (σᵢ).
• Null Space: Spanned by the columns of V corresponding to zero singular values. In pose estimation, a degenerate configuration (e.g., points on a plane) can reduce the rank of the problem matrix, making the solution ambiguous—a fact immediately visible in the SVD.

Orthogonal Matrices are square matrices whose columns and rows are orthonormal vectors, meaning their inverse equals their transpose (QᵀQ = I). In the SVD (A = UΣVᵀ), the matrices U and V are orthogonal. This property is fundamental:

• U provides an orthonormal basis for the column space of A.
• V provides an orthonormal basis for the row space of A. In geometric terms, orthogonal matrices represent rotations and reflections. This makes SVD ideal for decomposing transformations, such as separating rotation from scaling in Procrustes analysis.

Numerical Stability refers to an algorithm's resilience to small errors in input data. Condition Number, computed as the ratio of the largest to smallest singular value (σ_max / σ_min), quantifies a matrix's sensitivity to perturbations. A high condition number indicates an ill-conditioned problem, common in vision with noisy data or near-degenerate scenes. SVD is the gold-standard stable algorithm for solving such systems because it explicitly identifies and can regularize (e.g., via Truncated SVD) the influence of small, error-amplifying singular values.