Mo logo [home] [lexicon] [problems] [tests] [courses] [auxiliaries] [notes] [staff] german flag
Mathematics-Online course: Linear Algebra - Normal Forms - Singular Value Decomposition

Pseudo-Inverse

[previous page] [next page] [table of contents][page overview]
By means of the singular value decomposition $ USV^*$ of an $ m\times n$ matrix $ A$, the solution of the minimization problem $ \Vert Ax-b\Vert _2\to\min$ can be expressed in the form

$\displaystyle x = A^+b,\quad A^+ = VS^+U^*, $

where $ A^+$ is the so-called pseudo-inverse of $ A$ (Moore-Penrose inverse), and $ S^+$ is an $ n\times m$ diagonal matrix of the form

$\displaystyle S^+ =\operatorname{diag}(1/s_1,\ldots,1/s_k,0,\ldots,0)\, , $

containing the inverse values of the singular ones.
Since the $ 2$ -norm is invariant under unitary transformations, we can multiply $ Ax-b$ from the left by $ U^*$ . With

$\displaystyle c=U^* b,\quad y=V^* x, $

we obtain the equivalent minimization problem

$\displaystyle \Vert Sy-c\Vert _2 = \left\Vert \left( \begin{array}{c} s_1y_1-... ...k \\ -c_{k+1} \\ \vdots \\ -c_m \end{array} \right) \right\Vert _2 \to\min. $

We find the minimum by solving the first $ k$ equations:

$\displaystyle y_i=c_i/s_i,\ i=1:k\, . $

Since $ V$ is unitary, we have $ \Vert x\Vert _2 = \Vert y\Vert _2$ . Hence, for the solution of minimal norm

$\displaystyle y_{k+1}=\cdots=y_n=0\, . $

Summarizing, it follows that

\begin{displaymath} y = S^+c,\quad s^+_{i,j} = \begin{cases} 1/s_i & \text{for}\ i=j\le k; \\ 0& \text{otherwise.} \end{cases} \end{displaymath}

We solve the least squares problem for

$\displaystyle A = \left(\begin{array}{rrr} 2 & -4 & 5 \\ 6 & 0 & 3 \\ 2 & -... ...quad b = \left(\begin{array}{r} 1 \\ 3 \\ -1 \\ 3 \end{array}\right)\, . $

In order to compute the singular value decomposition, we first determine the eigenvalues and eigenvectors of

$\displaystyle A^{\operatorname t}A = \left(\begin{array}{rrr} 80 & -16 & 56 \\ -16 & 32 & -40 \\ 56 & -40 & 68 \end{array}\right) $

and obtain

$\displaystyle s_1^2 = 144,\, s_2^2 = 36,\, s_3^2=0,\quad V = \frac{1}{3} \lef... ...{array}{rrr} 2 & 2 & -1 \\ -1 & 2 & 2 \\ 2 & -1 & 2 \end{array}\right)\, . $

This implies

$\displaystyle S = \left(\begin{array}{rrr} 12 & 0 & 0 \\ 0 & 6 & 0 \\ 0 & 0... ... & 0 \\ 6 & 3 & 0 \\ 6 & -3 & 0 \\ 6 & 3 & 0 \end{array}\right) = US\, . $

We obtain the first two columns of $ U$ by dividing the respective columns of $ AV$ by the corresponding singular values. (The resulting vectors must have norm 1.) We find the other columns (not uniquely determined) by completing the first two columns to an orthonormal basis:

$\displaystyle U = \frac{1}{2} \left(\begin{array}{rrrr} 1 & -1 & -1 & 1 \\ 1 & 1 & -1 & -1 \\ 1 & -1 & 1 & -1 \\ 1 & 1 & 1 & 1 \end{array}\right). $

Thus, the pseudo-inverse (Moore-Penrose inverse) is

$\displaystyle A^+ = V \left(\begin{array}{cccc} \frac{1}{12} & 0 & 0 & 0 \\ ... ...} -2 & 6 & -2 & 6 \\ -5 & 3 & -5 & 3 \\ 4 & 0 & 4 & 0 \end{array}\right), $

and

$\displaystyle x = A^+b = \frac{1}{4}\left(\begin{array}{c} 2 \\ 1 \\ 0\end{array}\right) $

is the solution of minimal norm.
  automatically generated 4/21/2005