Definition

SVD null-space estimation is the standard technique for finding a geometric entity that is defined only up to scale from a set of homogeneous linear constraints. Given a coefficient matrix $A$ assembled from measurements, it returns the unit vector $x$ that minimises $\|Ax\|$ subject to $\|x\| = 1$.

The input is $A$ — any coefficient matrix whose rows encode linear constraints on an unknown vector $x$ meaningful only up to a global scale. The output is the unit vector $x^\star$ that best satisfies those constraints in the least-squares sense. In computer vision $A$ is called the design matrix or DLT matrix; the pattern of stacking one constraint per correspondence and extracting the smallest right-singular vector appears identically in fundamental-matrix estimation, homography estimation, and camera calibration.

Mathematical Description

The homogeneous system and its least-squares solution

A geometric entity described by $n$ parameters but defined only up to scale has $n - 1$ effective degrees of freedom. Each measurement contributes one linear equation; stacking $m \geq n - 1$ constraints yields

$Ax = 0, \qquad A \in \mathbb{R}^{m \times n},$

which has no non-trivial solution unless $A$ is exactly rank-deficient. Under measurement noise $A$ has full column rank, and the exact equation is replaced by the constrained minimisation $x^\star = \arg\min_{\|x\|=1} \|Ax\|^2$. Expanding via the SVD $A = U\Sigma V^\top$ with $\sigma_1 \geq \cdots \geq \sigma_n \geq 0$,

$\|Ax\|^2 = \|\Sigma V^\top x\|^2 = \sum_{i=1}^n \sigma_i^2 (v_i^\top x)^2.$

Subject to $\|x\| = 1$, this weighted sum of squared projections is minimised by placing all weight on the smallest term — $x^\star = v_n$ — giving minimum value $\sigma_n^2$. This is the Rayleigh-quotient argument applied to $A^\top A$, whose eigenvalues are $\sigma_i^2$ and eigenvectors the columns of $V$.

Rank deficiency and the residual interpretation

An exact solution to $Ax = 0$ exists if and only if $\sigma_n = 0$: the system is rank-deficient and $v_n$ lies exactly in the null space. When $\sigma_n > 0$, no exact solution exists and $\sigma_n$ is the minimum achievable residual $\|Ax^\star\|$. The ratio $\sigma_{n-1}/\sigma_n$ measures how clearly the solution direction is separated: a large ratio indicates a well-determined unique solution; a ratio near 1 indicates near-degeneracy.

For the eight-point fundamental-matrix estimator, $A$ is the $m \times 9$ design matrix from $m \geq 8$ correspondences, each row $(u u',\, u v',\, u,\, v u',\, v v',\, v,\, u',\, v',\, 1)$; the nine-vector $\mathbf{f} = v_9$ reshapes to $F$ satisfying $\mathbf{u}'^T F \mathbf{u} = 0$. The stacking follows from the bilinear epipolar constraint $x'_\lambda Q_{\lambda\mu} x_\mu = 0$ that Longuet-Higgins derived in 1981, where each correspondence supplies one equation in the nine entries of the essential matrix. For the homography DLT the same structure applies with a $2m \times 9$ matrix; for Zhang's planar calibration the stacked system $Vb = 0$ is a $2n \times 6$ matrix whose smallest right-singular vector encodes the image of the absolute conic.

Rank enforcement by truncating the spectrum

The null-space step produces an unconstrained solution. Many geometric entities carry an additional rank constraint, enforced by a second SVD applied to the recovered matrix. The fundamental matrix must have rank 2, yet the linear solution $\hat{F}$ generically has rank 3. The closest rank-2 matrix in Frobenius norm is obtained by computing $\hat{F} = U \operatorname{diag}(r, s, t) V^\top$ and setting $F' = U \operatorname{diag}(r, s, 0) V^\top$ — zeroing the smallest singular value. This projection is optimal in Frobenius norm but not in geometric (Sampson) error; iterative refinement is needed for calibration-grade accuracy.

Numerical Concerns

Conditioning of the design matrix. The fundamental-matrix design matrix has entries ranging from $O(1)$ to $O(u_{\max}^2) \approx O(10^6)$ for $\sim$1000-pixel coordinates, making the condition number of $A^\top A$ of order $10^{11}$–$10^{13}$ on un-normalised data. At such conditioning, 64-bit floating point retains only a few significant digits in the smallest singular vector. The fix — dlt-normalisation — translates each point set to zero centroid and scales isotropically to unit mean distance, dropping the condition number by roughly $10^8$ and bringing all design-matrix entries to $O(1)$.

The singular-value gap as a degeneracy indicator. A ratio $\sigma_{n-1}/\sigma_n$ near 1 means two or more directions of $V$ compete for the null space — the solution is numerically unreliable and geometrically degenerate. For the eight-point algorithm this corresponds to degenerate correspondence configurations such as collinear or coplanar points; for Zhang's $Vb = 0$ system, parallel-plane views contribute linearly dependent rows.

Exact vs overdetermined systems. With exactly $n - 1$ consistent constraints, $\sigma_n = 0$ and $v_n$ is the unique null vector. With $m > n - 1$ constraints the system is overdetermined, $\sigma_n > 0$, and $v_n$ is the least-squares null vector. The eight-point algorithm is most stable from roughly ten correspondences onward.

Sensitivity to outliers. The null-space step minimises a global least-squares objective over all rows of $A$; a single grossly mismatched correspondence corrupts the entire fit by inflating the residual in a direction unrelated to the true null vector. The method has no intrinsic outlier rejection — in practice RANSAC wraps it: sample a minimal subset, compute $v_n$, count inliers, repeat, then re-estimate from the inlier set.

Precision. Applying SVD directly to $A$ is numerically preferable to forming $A^\top A$ and computing its eigendecomposition, since squaring the matrix squares the condition number. Even after normalisation, the smallest singular value and its right-singular vector should be computed in 64-bit double precision.

Where it appears

The SVD null-space step is the shared computational core of every homogeneous linear estimator in the atlas; dlt-normalisation describes the preconditioning that must precede it.

• longuet-higgins-eight-point — the 1981 origin: eight correspondences determine the nine entries of the essential matrix up to scale via SVD of the $8 \times 9$ design matrix.
• fundamental-matrix-eight-point — Hartley's normalised extension; SVD of the $m \times 9$ matrix yields $\hat{\mathbf{f}} = v_9$, followed by a second SVD enforcing rank 2.
• gao-dual-homography-stitching — fits one homography per correspondence cluster, each solved by SVD null-space estimation from its cluster's DLT design matrix.
• homography — the projective planar mapping; the $2m \times 9$ DLT matrix assembles two rows per correspondence and the nine-vector $h = v_9$ reshapes to the $3 \times 3$ homography.

References

1. H. C. Longuet-Higgins. A computer algorithm for reconstructing a scene from two projections. Nature, 293:133–135, 1981.
2. R. I. Hartley. In Defense of the Eight-Point Algorithm. IEEE Transactions on Pattern Analysis and Machine Intelligence, 19(6):580–593, 1997.
3. Z. Zhang. A Flexible New Technique for Camera Calibration. IEEE Transactions on Pattern Analysis and Machine Intelligence, 22(11):1330–1334, 2000.
4. J. Gao, S. J. Kim, M. S. Brown. Constructing Image Panoramas Using Dual-Homography Warping. IEEE CVPR, 2011.
5. R. Hartley, A. Zisserman. Multiple View Geometry in Computer Vision, 2nd ed. Cambridge University Press, 2004.