M6-T6 — Rank and Condition Number

Learning objectives

After this lesson, you should be able to:

• Compute numerical rank by thresholding singular values and choose a sensible tolerance.
• Define the condition number from singular values and state the error-amplification bound it gives for Ax = b.
• Distinguish rank deficiency from ill conditioning, and exactly singular from nearly singular.
• Use the singular value spectrum to detect degenerate or weakly observable directions in robot measurements.

Introduction and motivation

A scan matcher inside a long, straight corridor gets many LiDAR returns, yet all the wall points constrain only the lateral position and heading: sliding along the corridor changes nothing. Mathematically the Gauss-Newton matrix JᵀJ is nearly singular. The solver does not crash; it returns a confident-looking but arbitrary position along the corridor. The singular values reveal it immediately, and a robot that checks them can warn, switch sensors or fuse odometry instead.

The intuition

The singular values are the semi-axes of the ellipse into which the matrix maps the unit sphere. If the ellipse is fat in every direction, the matrix preserves information in every direction. If one axis is very short, inputs along that axis are squashed almost to nothing, so reversing the map (solving) amplifies noise enormously along it. If the axis is exactly zero, information is lost entirely and the rank drops.

Geometric and physical interpretation

Geometric view. cond(A) = σ₁/σᵣ is the aspect ratio of the image ellipse: a circle (cond = 1, an orthogonal matrix up to scale) is perfectly conditioned; a needle is nearly singular. Physical view. Each singular value is the sensitivity of the output to the input along one axis. For a LiDAR Gauss-Newton matrix, σᵢ² is the information (inverse variance) the scan carries about direction vᵢ; a near-zero value means nothing in the data constrains that motion.

The mathematics

σ₁ ≥ … ≥ σₙ

the singular values of A.

ε

machine precision, about 2.2 × 10⁻¹⁶ for double precision.

τ

the rank tolerance: singular values below τ are treated as zero.

cond(A)

the condition number σ₁/σₙ (for a full-rank square matrix).

Numerical rank

rank_τ(A) = #{ i : σᵢ > τ },      τ = max(m, n) · ε · σ₁   (default)

What it means. The number of singular values larger than a tolerance. The default scales with the largest singular value and the matrix size, so it adapts to units. In robotics, set τ from the sensor noise instead, since noise is usually far bigger than machine precision.

Condition number and error amplification

cond(A) = σ₁ / σₙ        ‖δx‖/‖x‖ ≤ cond(A) · ‖δb‖/‖b‖

What it means. A relative error in b is magnified by at most cond(A) in the solution x of Ax = b. A condition number of 10⁶ means that 1e-6 relative sensor noise can destroy all accuracy; digits lost ≈ log₁₀ cond.

Rank deficiency versus ill conditioning

exactly singular: σₙ = 0        ill conditioned: σₙ ≪ σ₁ but > 0

What it means. Rank deficiency loses information completely (no unique solution, infinitely many). Ill conditioning keeps it technically but buries it in noise. In floating point and with noisy data you cannot tell them apart, so treat both by regularisation or by truncating the spectrum.

Rank = number of singular values above a noise-based tolerance. Condition number = σmax/σmin = noise amplification. Always look at the whole spectrum, not just the determinant.

Step-by-step derivation: the error bound and the degenerate direction

Error amplification. Let A x = b and a perturbed right-hand side b + δb produce x + δx, so A δx = δb.

1. Using the SVD, δx = A⁻¹ δb = V Σ⁻¹ Uᵀ δb, so ‖δx‖ ≤ ‖δb‖/σₙ (the largest entry of Σ⁻¹ is 1/σₙ).
2. Also b = A x gives ‖b‖ ≤ σ₁‖x‖, i.e. 1/‖x‖ ≤ σ₁/‖b‖.
3. Multiply the two: ‖δx‖/‖x‖ ≤ (σ₁/σₙ) ‖δb‖/‖b‖ = cond(A) ‖δb‖/‖b‖.

The bound is attained when b lies along u₁ and δb along uₙ: the worst noise is the one aligned with the weakest direction.

Choosing the tolerance. Rounding perturbs each entry by about ε times its size, so the computed singular values have absolute errors of roughly ε σ₁ (times a modest factor depending on size). A singular value below that cannot be told from zero: this is the origin of τ = max(m, n) ε σ₁. With measurement noise of size η ≫ ε on the entries, the same argument gives a much larger tolerance of about η √(max(m,n)).

Degenerate direction in a scan. Suppose a corridor scan gives the Gauss-Newton matrix JᵀJ = diag(40, 0, 20) for the motion parameters (y across the corridor, x along it, θ) — the zero marks the along-corridor translation (see the example). Its eigenvectors are the coordinate axes, and the eigenvector with eigenvalue ≈ 0 is the direction the data cannot observe. The covariance of the estimate is (JᵀJ)⁻¹, which has an infinite entry in that direction; in practice, a very large one.

Squaring the problem. Since σᵢ(AᵀA) = σᵢ(A)², cond(AᵀA) = cond(A)². A matrix with cond = 10⁹ is still well handled by an SVD or QR, but its normal equations have cond = 10¹⁸, beyond double precision.

A worked example: spotting a degenerate LiDAR corridor

A scan matcher in a long, straight corridor produces (for the motion parameters (Δy across, Δx along, Δθ)) the Gauss-Newton matrix H = JᵀJ = diag(40, 0, 20) in exact arithmetic, but with noise diag(40, 10⁻⁹, 20) in practice.

• Eigenvalues. H is diagonal and symmetric, so its eigenvalues are 40, 20 and 10⁻⁹ (the singular values of H itself; those of J are their square roots 6.32, 4.47 and 3.2 × 10⁻⁵).
• Numerical rank. With tolerance τ = 3 × 10⁻¹⁶ × 40 = 1.2 × 10⁻¹⁴ the third eigenvalue 10⁻⁹ is still above the tolerance, so a naive rank test says “rank 3”. A noise-based tolerance (say 10⁻³ relative to the largest) correctly gives rank 2.
• Condition number. cond(H) = 40/10⁻⁹ = 4 × 10¹⁰; solving for the update amplifies noise on the weak direction by this factor; for J alone the figure is the square root, 2 × 10⁵.
• Interpretation. The weak eigenvector is the second axis, Δx, the along-corridor translation, and the other two eigenvalues are fine. The robot can trust lateral position and heading but must take its along-corridor position from odometry, an IMU or a different landmark.

A small exact case. A = [[1, 1], [1, 1.0001]]: singular values 2.00005 and 0.0000499975 (the smaller is 5 × 10⁻⁵), so cond ≈ 4 × 10⁴. Solving A x = (2, 2) gives (2, 0), but b = (2, 2.0001) gives (1, 1): a 5 × 10⁻⁵ relative change in b moves x by 71 % — noise amplified by about the condition number.

Robotics application

LiDAR and point-cloud registration. Check the eigenvalues of JᵀJ (or of the point-to-plane normal matrix) before trusting a scan match: one small eigenvalue marks a degenerate geometry (corridor, flat wall, open field). See LiDAR point clouds for SLAM and scan registration.

Feature-based SLAM and UAV navigation. The rank of the observation Jacobian decides whether the state is observable; a drop in the smallest singular value predicts drift before it appears. See fault detection and landmark-based mapping.

Manipulators. The smallest singular value of the Jacobian measures distance to a singularity; the condition number is the arm's dexterity index (Module 8).

IMU and GPS calibration. A calibration design matrix whose condition number is large means the calibration motions did not excite every parameter. Add rotations until the spectrum is flat. See extrinsic calibration.

Engineering implications and limitations

Practical rules

• Never use the determinant to test singularity. It depends on the units and size of the matrix: a scaled identity 1e-3·I(10) has determinant 1e-30 but is perfectly conditioned. Use the condition number.
• Set the tolerance from the noise, not from ε. The default max(m, n)·ε·σ₁ only accounts for rounding. Real measurement noise is 10⁸ times larger.
• Normalise units before looking at the spectrum. A Jacobian mixing metres and radians has artificial singular value ratios; scale columns (or whiten with the measurement covariance) first.
• Report digits lost. Roughly log₁₀(cond) significant digits are lost. A condition number above about 10⁸ in double precision leaves less than eight accurate digits.
• Monitor online. In estimation, track the smallest eigenvalue of the information matrix as an observability or degeneracy indicator and raise a flag below a threshold.
• Respond with regularisation or sensor fusion, not just a warning. Add a prior along the weak direction (Tikhonov, previous pose, odometry) or switch estimator mode.

Limits

A good condition number says the linear problem is stable, not that the model is right. Nonlinear systems have local conditioning that changes with the state, and a well-conditioned Jacobian at the wrong linearisation point is still misleading.

Common misconceptions

Engineering takeaways

1. Numerical rank is the count of singular values above a tolerance; choose the tolerance from the noise level.
2. cond(A) = σ₁/σₙ bounds how much relative input error is amplified in the solution of Ax = b; log₁₀ cond digits are lost.
3. Rank deficiency (σ = 0) loses information; ill conditioning (σ ≪ σ₁) buries it in noise; in practice treat both the same way.
4. The determinant is not a singularity test; the singular value spectrum is.
5. Near-zero eigenvalues of JᵀJ reveal degenerate geometry, such as a featureless corridor, so the robot can fuse another sensor.

References and further reading

Primary papers and authoritative documentation.

• MIT 18.06SC Linear Algebra (OCW): lecture on the condition number and numerical rank
• Boyd and Vandenberghe, Introduction to Applied Linear Algebra (VMLS): conditioning and least squares; the site did not load when we last checked
• Mathematics for Machine Learning: matrix decompositions and conditioning
• UCSD ECE276A: Sensing and Estimation in Robotics: observability and degenerate directions in scan registration

Knowledge check

Three conceptual questions. Write an answer, then reveal the explanation. Your answers stay in your browser.

What’s next

When rank is deficient or the system is underdetermined there are many (or approximately many) solutions. The pseudoinverse uses the SVD to pick the most sensible one, the shortest, and also solves least squares in the same stroke.

Related content

Nothing below is required to finish this lesson.

• Before
  M6-T5: Singular Value Decomposition

  Write any matrix as rotation, stretch and rotation, and read the geometry from the singular values.