Total least squares and the generalised SVD

Intuition Beginner

Ordinary least squares assumes your inputs are perfect and only your outputs are noisy. You fit a line, and you measure each miss as a vertical drop from the data point straight down to the line. That vertical drop treats the horizontal coordinate as exact. But in most real experiments both coordinates are measured, and both carry error. A line fitted as if only the vertical coordinate were noisy will be biased, because it never asks the line to move sideways to meet a point that was mismeasured horizontally.

Total least squares fixes this. Instead of the vertical drop, it measures each miss as the shortest distance from the data point to the line — the perpendicular distance. A point can now be off because its input was wrong, its output was wrong, or both. The fitted line is the one that makes the total of these squared perpendicular distances as small as possible. Because the error can live in any direction, this is called the errors-in-variables fit.

The remarkable part is that the recipe for the best perpendicular fit is still a singular value decomposition — the same rotate-stretch-rotate factorisation used everywhere in this chapter. You stack the inputs and outputs side by side into one wide table, factor it, and read the answer off the smallest stretch direction. The smallest stretch direction is the thin axis of the data cloud, and the best line is the one lying along the cloud, perpendicular to that thin axis.

Visual Beginner

The table contrasts the two fits on the single question that separates them: which direction the error is allowed to point.

Fit	Error measured as	Inputs assumed	Best for
Ordinary least squares	vertical drop to the line	exact (noise-free)	only the output is noisy
Total least squares	perpendicular distance to the line	noisy, like the outputs	both input and output noisy

The difference is a right angle. Ordinary least squares drops straight down from each point; total least squares drops along the shortest path, which meets the line at a right angle. When the data points are far from the line, or when the inputs are very noisy, the two fitted lines can tilt noticeably apart.

The geometry is the whole lesson. Ordinary least squares answers "how far down to the line," total least squares answers "how far to the line in any direction." The second is the honest question whenever the horizontal coordinate is itself a measurement.

Worked example Beginner

Fit a line through the origin, $y=xm$, to two data points $(1,1)$ and $(2,1)$, where both coordinates are measured and noisy.

First the ordinary fit, which trusts the $x$ values. It minimises the squared vertical gaps. The slope that does this is the ratio of the cross term to the input energy: $m=(1\cdot 1+2\cdot 1)/(1\cdot 1+2\cdot 2)=3/5=0.6$. So the ordinary line is $y=0.6x$.

Now the total fit, which trusts neither coordinate. Stack the data into a wide table with the inputs in the first column and the outputs in the second:

$$M=\left(\begin{array}{cc}1& 1\\ 2& 1\end{array}\right).$$

The total fit asks for the thin direction of this cloud — the direction in which the two columns vary least together. The stretch factors of $M$ are about $2.62$ and about $0.38$, and the thin direction (the smallest-stretch direction) turns out to point roughly along $(0.53,-0.85)$ in the input-output plane. Reading the slope off that thin direction gives $m\approx 0.62$, a touch steeper than the ordinary $0.6$.

What this tells us: when you stop trusting the $x$ values, the best line tilts. The total fit found a slightly steeper line because it let the points move sideways as well as up and down to meet it. With only two points the shift is small, but with noisy inputs across many points the bias the ordinary fit carries can be large, and the total fit removes it.

Check your understanding Beginner

Formal definition Intermediate+

Let $A\in {\mathbb{R}}^{m\times n}$ with $m>n$ and $b\in {\mathbb{R}}^m$, and consider the overdetermined system $Ax\approx b$. Ordinary least squares, treated in 43.04.01, perturbs only $b$: it solves ${\min }_r\Vert r{\Vert }_2$ subject to $Ax=b-r$, charging error to the right-hand side alone. The total least squares (TLS) problem charges error to both $A$ and $b$. It seeks the smallest perturbation of the augmented data $[A\mid b]$ that makes the perturbed system consistent:

$$\underset{E,r}{\min }\Vert [E\mid r]{\Vert }_F\text{subject to}(A+E)x=b+r\text{ for some }x\in {\mathbb{R}}^n,$$

where $\Vert \cdot {\Vert }_F$ is the Frobenius norm. The minimising $x$, when it exists and is unique, is the TLS solution. The constraint says the perturbed augmented matrix $[A+E\mid b+r]$ has the vector $\left(\genfrac{}{}{0ex}{}{x}{-1}\right)$ in its kernel, hence is rank-deficient. So TLS is the problem of finding the nearest rank-deficient augmented matrix in Frobenius norm, then reading the solution off its kernel.

The SVD solution. Write the SVD (developed in 01.01.12) of the $m\times (n+1)$ augmented matrix as

$$[A\mid b]=\tilde{U}\tilde{\Sigma }{\tilde{V}}^{\mathsf{T}},\tilde{\Sigma }=\mathrm{diag}({\sigma }_1,\dots ,{\sigma }_{n+1}),{\sigma }_1\ge \cdots \ge {\sigma }_{n+1}\ge 0.$$

By the Eckart-Young theorem 01.01.12, the nearest rank-$n$ matrix in Frobenius norm is obtained by zeroing ${\sigma }_{n+1}$, and the kernel of that nearest matrix is spanned by ${\tilde{v}}_{n+1}$, the last right singular vector. Partition ${\tilde{v}}_{n+1}=\left(\genfrac{}{}{0ex}{}{z}{\gamma }\right)$ with $z\in {\mathbb{R}}^n$ and $\gamma \in \mathbb{R}$ its final entry. When $\gamma \ne 0$, the TLS solution is

$$x_{\mathrm{TLS}}=-\frac{1}{\gamma }z.$$

Genericity and the degenerate case. The construction requires $\gamma \ne 0$, and uniqueness requires ${\sigma }_n>{\sigma }_{n+1}$ (a simple smallest singular value of the augmented matrix). Equivalently, the genericity condition is ${\sigma }_{\min }(A)>{\sigma }_{n+1}([A\mid b])$: the smallest singular value of $A$ alone strictly exceeds the smallest singular value of the augmented matrix. When ${\sigma }_n={\sigma }_{n+1}$ the minimiser is non-unique, and when $\gamma =0$ (the last right singular vector is orthogonal to the $b$-coordinate) no finite TLS solution exists — the nearest rank-deficient augmented matrix decouples $b$ from $\mathrm{range}(A+E)$.

The closed form. When the genericity condition holds, the TLS solution admits the closed form

$$x_{\mathrm{TLS}}=(A^{\mathsf{T}}A-{\sigma }_{n+1}^2{I}_n{)}^{-1}{A}^{\mathsf{T}}b.$$

This is the ordinary normal-equations solution with the smallest augmented singular value subtracted from the diagonal of $A^{\mathsf{T}}A$ — a deregularisation: where Tikhonov regularisation adds a positive multiple of $I$ to stabilise, TLS subtracts ${\sigma }_{n+1}^{2}I$, which is why TLS amplifies noise more than ordinary least squares and why $A^{\mathsf{T}}A-{\sigma }_{n+1}^{2}I$ must stay positive definite for the solution to exist.

The generalised SVD. The generalised singular value decomposition (GSVD) factors a matrix pair rather than a single matrix. For $A\in {\mathbb{R}}^{m_A\times n}$ and $B\in {\mathbb{R}}^{m_B\times n}$ sharing $n$ columns, with the stacked matrix $\left(\genfrac{}{}{0ex}{}{A}{B}\right)$ of full column rank, there exist orthogonal $U\in {\mathbb{R}}^{m_A\times m_A}$, $V\in {\mathbb{R}}^{m_B\times m_B}$ and a nonsingular $X\in {\mathbb{R}}^{n\times n}$ with

$$A=U{\Sigma }_A{X}^{-1},B=V{\Sigma }_B{X}^{-1},$$

where ${\Sigma }_A=\mathrm{diag}({\alpha }_1,\dots ,{\alpha }_n)$ and ${\Sigma }_B=\mathrm{diag}({\beta }_1,\dots ,{\beta }_n)$ (rectangular diagonal) carry non-negative entries normalised so that ${\alpha }_i^2+{\beta }_i^2=1$. The ratios ${\gamma }_i={\alpha }_i/{\beta }_i$ are the generalised singular values of the pair $(A,B)$; they are exactly the square roots of the eigenvalues of the pencil $A^{\mathsf{T}}A-\lambda B^{\mathsf{T}}B$, linking the GSVD to the generalised eigenvalue problem cross-referenced in 43.06.10. When $B=I$, the generalised singular values reduce to the ordinary singular values of $A$.

Counterexamples to common slips

• TLS is not ordinary least squares with $b$ perturbed too. Ordinary least squares perturbs $b$ but holds $A$ fixed; TLS perturbs the whole augmented matrix and minimises the joint Frobenius norm of $[E\mid r]$. The two coincide only when $A$ has error-free columns, i.e. when the right model is mixed LS-TLS, not full TLS.
• The TLS solution need not exist. If the last right singular vector of $[A\mid b]$ has a zero in its $b$-coordinate ($\gamma =0$), the formula $x=-z/\gamma$ is undefined and the problem has no finite solution. This is a genuine feature of the perpendicular-distance geometry, not a numerical artefact.
• The closed form subtracts ${\sigma }_{n+1}^{2}I$; it does not add it. Writing $A^{\mathsf{T}}A+{\sigma }_{n+1}^{2}I$ would be Tikhonov-type regularisation, the opposite stabilising operation. TLS deregularises, so it is more, not less, sensitive than ordinary least squares.
• The GSVD's $X$ is not orthogonal in general. Only $U$ and $V$ are orthogonal; $X$ is merely nonsingular. Demanding $X$ orthogonal would force $A$ and $B$ to be simultaneously diagonalisable by the same orthogonal change of basis, which fails for a generic pair.

Key theorem with proof Intermediate+

Theorem (the TLS solution from the smallest singular triple). Let $A\in {\mathbb{R}}^{m\times n}$, $b\in {\mathbb{R}}^m$, $m>n$, and let $[A\mid b]=\tilde{U}\tilde{\Sigma }{\tilde{V}}^{\mathsf{T}}$ be a singular value decomposition with ${\sigma }_1\ge \cdots \ge {\sigma }_{n+1}$. Suppose the genericity condition ${\sigma }_n>{\sigma }_{n+1}$ holds and the last right singular vector ${\tilde{v}}_{n+1}=\left(\genfrac{}{}{0ex}{}{z}{\gamma }\right)$ has $\gamma \ne 0$. Then the total-least-squares problem has the unique solution $x_{\mathrm{TLS}}=-z/\gamma$, the minimal perturbation has Frobenius norm $\Vert [E\mid r]{\Vert }_F={\sigma }_{n+1}$, and $x_{\mathrm{TLS}}$ satisfies the closed form $x_{\mathrm{TLS}}=(A^{\mathsf{T}}A-{\sigma }_{n+1}^{2}I{)}^{-1}{A}^{\mathsf{T}}b$. ^{[Golub, G. H. & Van Loan, C. F. — An analysis of the total least squares problem]}

Proof. The constraint $(A+E)x=b+r$ says the vector $\left(\genfrac{}{}{0ex}{}{x}{-1}\right)$ lies in the kernel of $C:=[A+E\mid b+r]=[A\mid b]+[E\mid r]$. A matrix has a nonzero kernel vector exactly when it is rank-deficient, so the TLS problem is: minimise $\Vert [E\mid r]{\Vert }_F$ over all $[E\mid r]$ for which $[A\mid b]+[E\mid r]$ has rank at most $n$ (one less than its $n+1$ columns), subject to the kernel containing a vector with last entry $-1$.

By the Eckart-Young theorem 01.01.12, among all rank-$n$ matrices the one nearest $[A\mid b]$ in Frobenius norm is

$$C_{\star }=\tilde{U}{\tilde{\Sigma }}_{\star }{\tilde{V}}^{\mathsf{T}},{\tilde{\Sigma }}_{\star }=\mathrm{diag}({\sigma }_1,\dots ,{\sigma }_n,0),$$

obtained by setting ${\sigma }_{n+1}\mapsto 0$, and the minimal distance is $\Vert [A\mid b]-C_{\star }{\Vert }_F={\sigma }_{n+1}$. The genericity condition ${\sigma }_n>{\sigma }_{n+1}$ makes this nearest rank-$n$ matrix unique. Its kernel is one-dimensional, spanned by the right singular vector ${\tilde{v}}_{n+1}$ associated with the zeroed singular value, since $C_{\star }{\tilde{v}}_{n+1}=\tilde{U}{\tilde{\Sigma }}_{\star }{\tilde{V}}^{\mathsf{T}}{\tilde{v}}_{n+1}=\tilde{U}{\tilde{\Sigma }}_{\star }{e}_{n+1}=0$.

A kernel vector usable as a solution must have its last coordinate normalisable to $-1$, which requires $\gamma \ne 0$. Under that hypothesis, scale ${\tilde{v}}_{n+1}=\left(\genfrac{}{}{0ex}{}{z}{\gamma }\right)$ by $-1/\gamma$ to obtain the kernel vector $\left(\genfrac{}{}{0ex}{}{-z/\gamma }{-1}\right)=\left(\genfrac{}{}{0ex}{}{x_{\mathrm{TLS}}}{-1}\right)$. The first $n$ coordinates give $x_{\mathrm{TLS}}=-z/\gamma$, and the constraint is met with $[E\mid r]=C_{\star }-[A\mid b]$ of Frobenius norm ${\sigma }_{n+1}$.

For the closed form, the eigen-relation $[A\mid b{]}^{\mathsf{T}}[A\mid b]{\tilde{v}}_{n+1}={\sigma }_{n+1}^2{\tilde{v}}_{n+1}$ written in block form with ${\tilde{v}}_{n+1}=\left(\genfrac{}{}{0ex}{}{z}{\gamma }\right)$ reads

$$\left(\begin{array}{cc}{A}^{\mathsf{T}}A& A^{\mathsf{T}}b\\ b^{\mathsf{T}}A& b^{\mathsf{T}}b\end{array}\right)\left(\begin{array}{c}z\\ \gamma \end{array}\right)={\sigma }_{n+1}^2\left(\begin{array}{c}z\\ \gamma \end{array}\right).$$

The top block gives $A^{\mathsf{T}}Az+\gamma A^{\mathsf{T}}b={\sigma }_{n+1}^{2}z$, that is $(A^{\mathsf{T}}A-{\sigma }_{n+1}^{2}I)z=-\gamma A^{\mathsf{T}}b$. Dividing by $-\gamma$ and using $x_{\mathrm{TLS}}=-z/\gamma$ yields $(A^{\mathsf{T}}A-{\sigma }_{n+1}^{2}I)x_{\mathrm{TLS}}=A^{\mathsf{T}}b$. The genericity condition ${\sigma }_n>{\sigma }_{n+1}$ forces ${\sigma }_{n+1}<{\sigma }_{\min }(A)$, so the singular values of $A$ all exceed ${\sigma }_{n+1}$, hence $A^{\mathsf{T}}A-{\sigma }_{n+1}^{2}I$ is positive definite and invertible, giving the stated closed form. $\square$

Bridge. This theorem builds toward the unified view of fitting as low-rank approximation, and it appears again in 43.06.10, where the same pencil $A^{\mathsf{T}}A-\lambda B^{\mathsf{T}}B$ reappears as the generalised eigenproblem the GSVD diagonalises. The foundational reason TLS reduces to an SVD is the Eckart-Young theorem of 01.01.12: minimising a Frobenius perturbation subject to a rank drop is exactly the optimal low-rank approximation problem, and the constraint that the kernel carry a vector with last entry $-1$ is what converts the abstract kernel direction into an affine solution $x$. Putting these together, ordinary least squares of 43.04.01 and total least squares are two faces of one optimisation — column-space projection versus nearest-rank-deficient augmentation — and the closed forms differ only by the term $-{\sigma }_{n+1}^{2}I$, which is the central insight that TLS is a deregularised normal-equations solve. The TLS route generalises the single-matrix SVD to the augmented matrix, and the GSVD generalises it again to a matrix pair, so the bridge is the same low-rank-approximation principle widening from one matrix to two.

Exercises Intermediate+

Advanced results Master

Theorem (orthogonal-distance optimality of TLS). Let the rows of $[A\mid b]$ be the data points $p_i\in {\mathbb{R}}^{n+1}$. The TLS fit minimises the sum of squared orthogonal (perpendicular) distances from the points $p_i$ to the hyperplane through the origin with unit normal ${\tilde{v}}_{n+1}$, whereas ordinary least squares minimises the sum of squared distances measured only along the $b$-coordinate axis. Concretely, the orthogonal distance from $p_i$ to the hyperplane $\{p:{\tilde{v}}_{n+1}^{\mathsf{T}}p=0\}$ is $|{\tilde{v}}_{n+1}^{\mathsf{T}}{p}_i|$, and

$$\sum _{i=1}^m|{\tilde{v}}_{n+1}^{\mathsf{T}}{p}_i{|}^2=\Vert [A\mid b]{\tilde{v}}_{n+1}{\Vert }_2^2={\sigma }_{n+1}^2,$$

minimised over unit vectors by the smallest right singular vector. ^{[Van Huffel, S. & Vandewalle, J. — The Total Least Squares Problem: Computational Aspects and Analysis]} The vector ${\tilde{v}}_{n+1}$ is the unit normal that the data cloud is thinnest along; the fitted relation ${\tilde{v}}_{n+1}^{\mathsf{T}}\left(\genfrac{}{}{0ex}{}{a}{\beta }\right)=0$ rearranges, after extracting the $b$-coordinate, into $b=A{x}_{\mathrm{TLS}}$. This is the precise sense in which TLS is orthogonal distance regression: it is principal-component fitting of a hyperplane to the augmented data, the dual of ordinary least squares' axis-aligned residual.

Theorem (the GSVD via the CS decomposition; Paige-Saunders form). Let $A\in {\mathbb{R}}^{m_A\times n}$, $B\in {\mathbb{R}}^{m_B\times n}$ with $\left(\genfrac{}{}{0ex}{}{A}{B}\right)$ of column rank $n$. Form a thin QR (or any orthonormal basis) $\left(\genfrac{}{}{0ex}{}{A}{B}\right)=QR$ with $Q=\left(\genfrac{}{}{0ex}{}{Q_A}{Q_B}\right)$ having orthonormal columns and $R\in {\mathbb{R}}^{n\times n}$ nonsingular. The CS decomposition of the column-orthonormal $Q$ supplies orthogonal $U,V$ and an orthogonal $W$ with

$$Q_A=UC{W}^{\mathsf{T}},Q_B=VS{W}^{\mathsf{T}},C=\mathrm{diag}({\alpha }_i),S=\mathrm{diag}({\beta }_i),C^{\mathsf{T}}C+S^{\mathsf{T}}S=I.$$

Setting $X^{-1}=W^{\mathsf{T}}R$ recovers $A=Q_{A}R=UC(W^{\mathsf{T}}R)=U{\Sigma }_A{X}^{-1}$ and likewise $B=V{\Sigma }_B{X}^{-1}$, with ${\Sigma }_A=C$, ${\Sigma }_B=S$. ^{[Paige, C. C. & Saunders, M. A. — Towards a generalized singular value decomposition]} The CS decomposition guarantees ${\alpha }_i^2+{\beta }_i^2=1$, so the generalised singular values ${\gamma }_i={\alpha }_i/{\beta }_i$ are well-defined whenever ${\beta }_i>0$, with ${\gamma }_i=+\infty$ encoding the directions in $\ker B$. The Paige-Saunders construction needs no rank assumption on $A$ or $B$ individually — only on the stack — which is why it is the numerically stable route, computing the GSVD without ever forming the cross-products $A^{\mathsf{T}}A$ or $B^{\mathsf{T}}B$ that would square the conditioning as in 43.04.01.

Theorem (GSVD diagonalises the symmetric-definite pencil). With the GSVD $A=U{\Sigma }_A{X}^{-1}$, $B=V{\Sigma }_B{X}^{-1}$ and $B$ of full column rank, the columns of $X$ are generalised eigenvectors of the pencil $(A^{\mathsf{T}}A,B^{\mathsf{T}}B)$:

$$A^{\mathsf{T}}A{x}_i={\gamma }_i^2{B}^{\mathsf{T}}B{x}_i,{\gamma }_i^2={\alpha }_i^2/{\beta }_i^2,$$

so $X^{\mathsf{T}}(A^{\mathsf{T}}A)X={\Sigma }_A^{\mathsf{T}}{\Sigma }_A$ and $X^{\mathsf{T}}(B^{\mathsf{T}}B)X={\Sigma }_B^{\mathsf{T}}{\Sigma }_B$ are simultaneously diagonal. ^{[Van Loan, C. F. — Generalizing the singular value decomposition]} This is the constructive, floating-point-stable form of the simultaneous diagonalisation of two quadratic forms whose existence theory the corpus carries in 01.01.19, and it is exactly the symmetric-definite specialisation of the generalised eigenproblem and QZ algorithm of 43.06.10. The GSVD thereby solves constrained and weighted least squares — minimising $\Vert Ax-c{\Vert }_2$ subject to $\Vert Bx{\Vert }_2$ fixed, or the Tikhonov problem ${\min }_x\Vert Ax-c{\Vert }_2^2+{\mu }^2\Vert Bx{\Vert }_2^2$ — by decoupling the two quadratic forms into the GSVD coordinates, where the regularised solution reads off termwise as $x={\sum }_i\frac{{\alpha }_i(u_i^{\mathsf{T}}c)}{{\alpha }_i^2+{\mu }^2{\beta }_i^2}{x}_i$.

Synthesis. The total-least-squares problem and the generalised SVD are one widening of the singular value decomposition, and the foundational reason both reduce to it is the Eckart-Young low-rank principle of 01.01.12: TLS is the nearest-rank-deficient augmentation of a single matrix, while the GSVD is the simultaneous orthogonal reduction of a pair. The central insight is that perpendicular-distance fitting is principal-component analysis of the augmented data — the residual that ordinary least squares of 43.04.01 measures along one axis becomes, in TLS, the thinnest direction of the whole cloud, and this is exactly the smallest singular triple of $[A\mid b]$. Putting these together, the deregularising closed form $x=(A^{\mathsf{T}}A-{\sigma }_{n+1}^{2}I{)}^{-1}{A}^{\mathsf{T}}b$ is dual to Tikhonov regularisation's stabilising $+{\mu }^{2}I$, and the GSVD unifies both by diagonalising the pencil $(A^{\mathsf{T}}A,B^{\mathsf{T}}B)$ — the same pencil whose general (non-definite) case the QZ algorithm of 43.06.10 resolves and whose existence theory 01.01.19 supplies. The bridge is the CS decomposition: it computes the GSVD from an orthonormal basis of the stacked range without forming a single cross-product, which generalises the conditioning lesson of 43.04.01 from one matrix to a pair, so the whole subject is the SVD applied first to an augmented matrix and then to a pencil, with orthogonal transformations protecting the conditioning at every step.

Full proof set Master

Proposition (genericity controls existence and uniqueness of the TLS solution). Let $[A\mid b]$ have singular values ${\sigma }_1\ge \cdots \ge {\sigma }_{n+1}$ and write ${\sigma }_n^{\prime }:={\sigma }_{\min }(A)$. The TLS problem has a unique solution if and only if ${\sigma }_n>{\sigma }_{n+1}$ and the last right singular vector has $\gamma \ne 0$; a sufficient condition for the latter is the strict interlacing ${\sigma }_n^{\prime }>{\sigma }_{n+1}$.

Proof. Uniqueness of the nearest rank-$n$ matrix in Frobenius norm holds exactly when the singular value being zeroed is strictly separated from the one above it, ${\sigma }_n>{\sigma }_{n+1}$ (Eckart-Young uniqueness, 01.01.12); otherwise the minimising rank-$n$ matrix lies in a positive-dimensional family obtained by rotating within the ${\sigma }_n={\sigma }_{n+1}$ singular subspace, and the kernel direction is not unique. Given ${\sigma }_n>{\sigma }_{n+1}$, the kernel of the nearest rank-$n$ matrix is the line $\mathbb{R}{\tilde{v}}_{n+1}$, and a finite TLS solution exists iff this line is transverse to the hyperplane $\{\gamma =0\}$, i.e. iff $\gamma \ne 0$. For the sufficient condition, the singular values of $A$ interlace those of $[A\mid b]$ (a column-bordered matrix), giving ${\sigma }_{i+1}([A\mid b])\le {\sigma }_i(A)\le {\sigma }_i([A\mid b])$; in particular ${\sigma }_{n+1}\le {\sigma }_n^{\prime }={\sigma }_{\min }(A)$. If this interlacing is strict, ${\sigma }_{n+1}<{\sigma }_n^{\prime }$, then ${\sigma }_{n+1}$ is not a singular value of $A$, so ${\tilde{v}}_{n+1}$ cannot have $\gamma =0$: a vector $\left(\genfrac{}{}{0ex}{}{z}{0}\right)$ in the smallest right singular subspace of $[A\mid b]$ would satisfy $\Vert [A\mid b]\left(\genfrac{}{}{0ex}{}{z}{0}\right){\Vert }_2=\Vert Az{\Vert }_2\ge {\sigma }_n^{\prime }\Vert z{\Vert }_2>{\sigma }_{n+1}\Vert z{\Vert }_2$, contradicting that $\left(\genfrac{}{}{0ex}{}{z}{0}\right)$ achieves the minimum ${\sigma }_{n+1}$. Hence $\gamma \ne 0$ and the solution exists uniquely. $\square$

Proposition (the minimal perturbation is explicit and attains ${\sigma }_{n+1}$). Under the genericity condition, the optimal correction is the rank-one outer product $[E\mid r]=-{\sigma }_{n+1}{\tilde{u}}_{n+1}{\tilde{v}}_{n+1}^{\mathsf{T}}$, with $\Vert [E\mid r]{\Vert }_F={\sigma }_{n+1}$, and $[A+E\mid b+r]\left(\genfrac{}{}{0ex}{}{x_{\mathrm{TLS}}}{-1}\right)=0$.

Proof. The nearest rank-$n$ matrix is $C_{\star }={\sum }_{i=1}^n{\sigma }_i{\tilde{u}}_i{\tilde{v}}_i^{\mathsf{T}}=[A\mid b]-{\sigma }_{n+1}{\tilde{u}}_{n+1}{\tilde{v}}_{n+1}^{\mathsf{T}}$, so the correction is $[E\mid r]=C_{\star }-[A\mid b]=-{\sigma }_{n+1}{\tilde{u}}_{n+1}{\tilde{v}}_{n+1}^{\mathsf{T}}$, a rank-one matrix. Its Frobenius norm is ${\sigma }_{n+1}\Vert {\tilde{u}}_{n+1}{\Vert }_2\Vert {\tilde{v}}_{n+1}{\Vert }_2={\sigma }_{n+1}$ since the singular vectors are unit. The kernel relation $C_{\star }{\tilde{v}}_{n+1}=0$ scales, on dividing ${\tilde{v}}_{n+1}=\left(\genfrac{}{}{0ex}{}{z}{\gamma }\right)$ by $-\gamma$, to $C_{\star }\left(\genfrac{}{}{0ex}{}{x_{\mathrm{TLS}}}{-1}\right)=0$, i.e. $[A+E\mid b+r]\left(\genfrac{}{}{0ex}{}{x_{\mathrm{TLS}}}{-1}\right)=0$, which is the consistency constraint $(A+E)x_{\mathrm{TLS}}=b+r$. No smaller correction works, because any $[E\mid r]$ with $\Vert [E\mid r]{\Vert }_F<{\sigma }_{n+1}$ leaves $[A\mid b]+[E\mid r]$ of full column rank $n+1$ by the Eckart-Young distance-to-singularity bound, hence with kernel reduced to the zero vector, hence inconsistent for every $x$. $\square$

Proposition (the GSVD generalised singular values are the pencil eigenvalues). For a pair $(A,B)$ with $\left(\genfrac{}{}{0ex}{}{A}{B}\right)$ of full column rank and $B$ of full column rank, the scalars ${\gamma }_i^2={\alpha }_i^2/{\beta }_i^2$ are exactly the eigenvalues of the symmetric-definite pencil $A^{\mathsf{T}}A-\lambda B^{\mathsf{T}}B$, with the GSVD columns $x_i$ of $X$ as generalised eigenvectors.

Proof. From $A=U{\Sigma }_A{X}^{-1}$, $A^{\mathsf{T}}A=X^{-\mathsf{T}}{\Sigma }_A^{\mathsf{T}}{\Sigma }_A{X}^{-1}=X^{-\mathsf{T}}\mathrm{diag}({\alpha }_i^2)X^{-1}$, and similarly $B^{\mathsf{T}}B=X^{-\mathsf{T}}\mathrm{diag}({\beta }_i^2)X^{-1}$. Multiplying both by $X$ on the right and $X^{\mathsf{T}}$ on the left gives $X^{\mathsf{T}}{A}^{\mathsf{T}}AX=\mathrm{diag}({\alpha }_i^2)$ and $X^{\mathsf{T}}{B}^{\mathsf{T}}BX=\mathrm{diag}({\beta }_i^2)$, simultaneously diagonal. For the $i$-th column $x_i$ of $X$, the relation $A^{\mathsf{T}}A{x}_i={\gamma }_i^2{B}^{\mathsf{T}}B{x}_i$ follows by comparing the $i$-th columns of $A^{\mathsf{T}}AX=X^{-\mathsf{T}}\mathrm{diag}({\alpha }_i^2)$ and $B^{\mathsf{T}}BX=X^{-\mathsf{T}}\mathrm{diag}({\beta }_i^2)$: each equals $X^{-\mathsf{T}}{e}_i$ times ${\alpha }_i^2$ resp. ${\beta }_i^2$, so $A^{\mathsf{T}}A{x}_i={\alpha }_i^2{X}^{-\mathsf{T}}{e}_i=({\alpha }_i^2/{\beta }_i^2){\beta }_i^2{X}^{-\mathsf{T}}{e}_i={\gamma }_i^2{B}^{\mathsf{T}}B{x}_i$. Full column rank of $B$ makes $B^{\mathsf{T}}B$ positive definite, so the pencil is regular and its $n$ finite eigenvalues are precisely the ${\gamma }_i^2$. $\square$

Connections Master

• The entire low-rank machinery this unit rests on — the existence and uniqueness of the SVD, the Eckart-Young best-rank-$k$ approximation theorem that turns TLS into a smallest-singular-triple computation, and the dyadic expansion $A=\sum {\sigma }_i{u}_i{v}_i^{\mathsf{T}}$ — is proved in 01.01.12; this unit specialises that theory to the augmented matrix $[A\mid b]$ and to a matrix pair, neither of which the foundational SVD unit treats.

• The ordinary least-squares problem that TLS reframes — the normal equations, the three solver algorithms, and the conditioning analysis ${\kappa }_2(A^{\mathsf{T}}A)={\kappa }_2(A{)}^2$ — is the subject of 43.04.01, and the deregularising closed form $x_{\mathrm{TLS}}=(A^{\mathsf{T}}A-{\sigma }_{n+1}^{2}I{)}^{-1}{A}^{\mathsf{T}}b$ is exactly that unit's normal-equations solve with the smallest augmented singular value subtracted from the diagonal, making explicit why TLS amplifies noise more than ordinary least squares.

• The GSVD diagonalises the symmetric-definite pencil $(A^{\mathsf{T}}A,B^{\mathsf{T}}B)$, whose existence theory as simultaneous diagonalisation of two quadratic forms is 01.01.19 and whose general, possibly non-definite, numerical resolution by the QZ algorithm is 43.06.10; this unit supplies the SVD-based constructive form that sits between the abstract existence statement and the full pencil algorithm.

Historical & philosophical context Master

The errors-in-variables idea predates its modern numerical form: orthogonal-distance line fitting was studied by Adcock in 1878 and by Pearson in his 1901 paper on lines and planes of closest fit to systems of points, where the principal-axis construction that underlies total least squares first appears in statistics. The numerical-linear-algebra treatment is due to Golub and Van Loan, whose 1980 paper An analysis of the total least squares problem (SIAM Journal on Numerical Analysis 17, 883-893) gave the SVD solution from the smallest singular triple, the closed form, and the genericity and non-existence conditions in the form used here ^{[Golub, G. H. & Van Loan, C. F. — An analysis of the total least squares problem]}. The name total least squares is theirs.

The generalised singular value decomposition was introduced by Van Loan in 1976 as a simultaneous diagonalisation of a matrix pair, and recast by Paige and Saunders in 1981 into the CS-decomposition form that requires no rank assumption on the individual blocks and computes without cross-products ^{[Paige, C. C. & Saunders, M. A. — Towards a generalized singular value decomposition]}. Van Huffel and Vandewalle's 1991 monograph collected the computational theory of total least squares, including its multiple-right-hand-side and degenerate variants, and made the link between the TLS problem and the GSVD of the pair explicit.

Bibliography Master

@book{golub-vanloan-2013-tls,
  author    = {Golub, Gene H. and Van Loan, Charles F.},
  title     = {Matrix Computations},
  edition   = {4th},
  publisher = {Johns Hopkins University Press},
  year      = {2013},
  address   = {Baltimore},
  note      = {Sec. 6.3 (total least squares), Sec. 8.7.3-8.7.4 (the generalized SVD)}
}

@article{golub-vanloan-1980,
  author  = {Golub, Gene H. and Van Loan, Charles F.},
  title   = {An analysis of the total least squares problem},
  journal = {SIAM Journal on Numerical Analysis},
  volume  = {17},
  number  = {6},
  pages   = {883--893},
  year    = {1980}
}

@book{vanhuffel-vandewalle-1991,
  author    = {Van Huffel, Sabine and Vandewalle, Joos},
  title     = {The Total Least Squares Problem: Computational Aspects and Analysis},
  series    = {Frontiers in Applied Mathematics},
  volume    = {9},
  publisher = {Society for Industrial and Applied Mathematics},
  year      = {1991},
  address   = {Philadelphia}
}

@article{paige-saunders-1981,
  author  = {Paige, Christopher C. and Saunders, Michael A.},
  title   = {Towards a generalized singular value decomposition},
  journal = {SIAM Journal on Numerical Analysis},
  volume  = {18},
  number  = {3},
  pages   = {398--405},
  year    = {1981}
}

@article{vanloan-1976,
  author  = {Van Loan, Charles F.},
  title   = {Generalizing the singular value decomposition},
  journal = {SIAM Journal on Numerical Analysis},
  volume  = {13},
  number  = {1},
  pages   = {76--83},
  year    = {1976}
}

@article{pearson-1901,
  author  = {Pearson, Karl},
  title   = {On lines and planes of closest fit to systems of points in space},
  journal = {Philosophical Magazine, Series 6},
  volume  = {2},
  number  = {11},
  pages   = {559--572},
  year    = {1901}
}