Section C.6 Unit 6 applied, geometric, and computational interpretation
These solution sketches correspond to the additional applied and computational interpretation exercises at the end of Exercises.
Subsection Candidate table on a rectangle
The gradient is
\begin{equation*}
\nabla f(x,y)=
\begin{bmatrix}
2x-2\\
2y+4
\end{bmatrix}.
\end{equation*}
The interior critical point is
\begin{equation*}
(1,-2),
\end{equation*}
and
\begin{equation*}
f(1,-2)=-5.
\end{equation*}
On \(x=0\text{,}\)
\begin{equation*}
f(0,y)=y^2+4y,
\end{equation*}
so the boundary critical point is \(y=-2\text{,}\) giving \((0,-2)\) and value \(-4\text{.}\)
On \(x=3\text{,}\)
\begin{equation*}
f(3,y)=y^2+4y+3,
\end{equation*}
so the boundary critical point is \(y=-2\text{,}\) giving \((3,-2)\) and value \(-1\text{.}\)
On \(y=-3\text{,}\)
\begin{equation*}
f(x,-3)=x^2-2x-3,
\end{equation*}
so the boundary critical point is \(x=1\text{,}\) giving \((1,-3)\) and value \(-4\text{.}\)
On \(y=1\text{,}\)
\begin{equation*}
f(x,1)=x^2-2x+5,
\end{equation*}
so the boundary critical point is \(x=1\text{,}\) giving \((1,1)\) and value \(4\text{.}\)
The corner values are
\begin{equation*}
f(0,-3)=-3,\qquad
f(3,-3)=0,\qquad
f(0,1)=5,\qquad
f(3,1)=8.
\end{equation*}
Thus the absolute minimum value is
\begin{equation*}
-5
\end{equation*}
at
\begin{equation*}
(1,-2),
\end{equation*}
and the absolute maximum value is
\begin{equation*}
8
\end{equation*}
at
\begin{equation*}
(3,1).
\end{equation*}
Subsection Parallel gradients on a circle
Use
\begin{equation*}
g(x,y)=x^2+y^2.
\end{equation*}
Then
\begin{equation*}
\nabla f=
\begin{bmatrix}
3\\
4
\end{bmatrix},
\qquad
\nabla g=
\begin{bmatrix}
2x\\
2y
\end{bmatrix}.
\end{equation*}
The Lagrange equations are
\begin{equation*}
3=2\lambda x,
\qquad
4=2\lambda y,
\qquad
x^2+y^2=25.
\end{equation*}
The first two equations say that
\begin{equation*}
\begin{bmatrix}
x\\
y
\end{bmatrix}
\end{equation*}
is parallel to
\begin{equation*}
\begin{bmatrix}
3\\
4
\end{bmatrix}.
\end{equation*}
Since
\begin{equation*}
\left\|
\begin{bmatrix}
3\\
4
\end{bmatrix}
\right\|=5,
\end{equation*}
the constrained critical points are
\begin{equation*}
(3,4)
\quad\text{and}\quad
(-3,-4).
\end{equation*}
The function values are
\begin{equation*}
f(3,4)=25,
\qquad
f(-3,-4)=-25.
\end{equation*}
So the absolute maximum is \(25\) at \((3,4)\text{,}\) and the absolute minimum is \(-25\) at \((-3,-4)\text{.}\)
Geometrically, \(\nabla f\) points in the direction of fastest increase of \(f\text{,}\) while \(\nabla g\) is perpendicular to the circle. At the maximum and minimum, these directions are parallel or antiparallel.
Subsection Quadratic form on the unit circle
For
\begin{equation*}
\mathbf{x}=
\begin{bmatrix}
x\\
y
\end{bmatrix},
\end{equation*}
we have
\begin{equation*}
q(\mathbf{x})
=
\mathbf{x}^T
\begin{bmatrix}
5\amp0\\
0\amp2
\end{bmatrix}
\mathbf{x}
=
5x^2+2y^2.
\end{equation*}
On the unit circle,
\begin{equation*}
x^2+y^2=1.
\end{equation*}
The maximum value is \(5\text{,}\) attained at
\begin{equation*}
\mathbf{x}=
\begin{bmatrix}
1\\
0
\end{bmatrix}
\quad\text{and}\quad
\mathbf{x}=
\begin{bmatrix}
-1\\
0
\end{bmatrix}.
\end{equation*}
The minimum value is \(2\text{,}\) attained at
\begin{equation*}
\mathbf{x}=
\begin{bmatrix}
0\\
1
\end{bmatrix}
\quad\text{and}\quad
\mathbf{x}=
\begin{bmatrix}
0\\
-1
\end{bmatrix}.
\end{equation*}
These are the eigenvalues and eigenvectors of \(B\text{:}\) the eigenvalues are \(5\) and \(2\text{,}\) with eigenvector directions \(\mathbf{e}_1\) and \(\mathbf{e}_2\text{.}\)
Subsection Maximum stretch of a matrix
Since \(A\) is symmetric,
\begin{equation*}
A^TA=A^2.
\end{equation*}
Compute
\begin{equation*}
A^TA
=
\begin{bmatrix}
1\amp2\\
2\amp1
\end{bmatrix}
\begin{bmatrix}
1\amp2\\
2\amp1
\end{bmatrix}
=
\begin{bmatrix}
5\amp4\\
4\amp5
\end{bmatrix}.
\end{equation*}
The eigenvectors
\begin{equation*}
\frac{1}{\sqrt2}
\begin{bmatrix}
1\\
1
\end{bmatrix}
\quad\text{and}\quad
\frac{1}{\sqrt2}
\begin{bmatrix}
1\\
-1
\end{bmatrix}
\end{equation*}
have eigenvalues \(9\) and \(1\text{,}\) respectively. Therefore the singular values are
\begin{equation*}
3
\quad\text{and}\quad
1.
\end{equation*}
The largest singular value is \(3\text{,}\) so
\begin{equation*}
\max_{\|\mathbf{x}\|=1}\|A\mathbf{x}\|=3.
\end{equation*}
The most-stretched input direction is
\begin{equation*}
\frac{1}{\sqrt2}
\begin{bmatrix}
1\\
1
\end{bmatrix}.
\end{equation*}
Subsection Reading an SVD
The nonzero singular values are
\begin{equation*}
5
\quad\text{and}\quad
2.
\end{equation*}
The matrix has rank
\begin{equation*}
2.
\end{equation*}
Using
\begin{equation*}
A\mathbf{v}_i=\sigma_i\mathbf{u}_i
\end{equation*}
for positive singular values, and \(A\mathbf{v}_i=\mathbf{0}\) for a null direction,
\begin{equation*}
A\mathbf{v}_1=
5
\begin{bmatrix}
1\\
0
\end{bmatrix}
=
\begin{bmatrix}
5\\
0
\end{bmatrix},
\end{equation*}
\begin{equation*}
A\mathbf{v}_2=
2
\begin{bmatrix}
0\\
1
\end{bmatrix}
=
\begin{bmatrix}
0\\
2
\end{bmatrix},
\end{equation*}
and
\begin{equation*}
A\mathbf{v}_3=\mathbf{0}.
\end{equation*}
The forgotten input direction is
\begin{equation*}
\mathbf{v}_3=
\frac{1}{\sqrt2}
\begin{bmatrix}
1\\
-1\\
0
\end{bmatrix}.
\end{equation*}
The transmitted input directions are
\begin{equation*}
\mathbf{v}_1=
\frac{1}{\sqrt2}
\begin{bmatrix}
1\\
1\\
0
\end{bmatrix}
\end{equation*}
and
\begin{equation*}
\mathbf{v}_2=
\begin{bmatrix}
0\\
0\\
1
\end{bmatrix}.
\end{equation*}
Subsection Fundamental subspaces from an SVD
Since the rank is \(2\text{,}\) the first two right singular vectors form an orthonormal basis for the row space:
\begin{equation*}
\operatorname{row}(A)
=
\operatorname{span}
\left\{
\frac{1}{\sqrt2}
\begin{bmatrix}
1\\
1\\
0
\end{bmatrix},
\begin{bmatrix}
0\\
0\\
1
\end{bmatrix}
\right\}.
\end{equation*}
The remaining right singular vector gives the null space:
\begin{equation*}
\operatorname{null}(A)
=
\operatorname{span}
\left\{
\frac{1}{\sqrt2}
\begin{bmatrix}
1\\
-1\\
0
\end{bmatrix}
\right\}.
\end{equation*}
The first two left singular vectors form an orthonormal basis for the column space:
\begin{equation*}
\operatorname{col}(A)
=
\operatorname{span}
\left\{
\begin{bmatrix}
1\\
0
\end{bmatrix},
\begin{bmatrix}
0\\
1
\end{bmatrix}
\right\}
=
\mathbb R^2.
\end{equation*}
Since \(A\) has two rows and rank \(2\text{,}\)
\begin{equation*}
\operatorname{null}(A^T)=\{\mathbf{0}\}.
\end{equation*}
The dimensions are
\begin{equation*}
\dim(\operatorname{row}(A))=2,
\qquad
\dim(\operatorname{null}(A))=1,
\end{equation*}
and
\begin{equation*}
2+1=3,
\end{equation*}
which agrees with rank-nullity for a \(2\times 3\) matrix. Also,
\begin{equation*}
\dim(\operatorname{col}(A))=2,
\qquad
\dim(\operatorname{null}(A^T))=0,
\end{equation*}
and
\begin{equation*}
2+0=2.
\end{equation*}
Subsection Energy retained
The squared singular values are
\begin{equation*}
100,\ 16,\ 1,\ 0.25.
\end{equation*}
The total squared energy is
\begin{equation*}
100+16+1+0.25=117.25.
\end{equation*}
For \(k=1\text{,}\) the retained energy is
\begin{equation*}
\frac{100}{117.25}\approx 0.853.
\end{equation*}
For \(k=2\text{,}\) the retained energy is
\begin{equation*}
\frac{116}{117.25}\approx 0.989.
\end{equation*}
Thus the smallest \(k\) retaining at least \(95\%\) of the energy is
\begin{equation*}
k=2.
\end{equation*}
The rank-\(2\) reconstruction keeps the directions corresponding to singular values \(10\) and \(4\text{,}\) and discards the smaller directions corresponding to singular values \(1\) and \(0.5\text{.}\)
Subsection Code interpretation: rank-\(k\) reconstruction
The singular values are
\begin{equation*}
3
\quad\text{and}\quad
1.
\end{equation*}
When \(k=1\text{,}\) the reconstruction keeps only the singular value \(3\text{.}\) Since \(A\) is \(2\times 2\text{,}\)
U[:, :1] has shape \(2\times 1\text{,}\) np.diag(s[:1]) has shape \(1\times 1\text{,}\) and Vt[:1, :] has shape \(1\times 2\text{.}\)
Therefore
\begin{equation*}
Ak
\end{equation*}
has shape
\begin{equation*}
2\times 2.
\end{equation*}
The rank of \(Ak\) is \(1\text{.}\) In this example,
\begin{equation*}
Ak=
\begin{bmatrix}
3\amp0\\
0\amp0
\end{bmatrix},
\end{equation*}
so the second input direction is discarded.
Subsection Debugging an SVD slice
For a \(2\times 2\) matrix and \(k=1\text{,}\)
U[:, :1] has shape \(2\times 1\text{,}\) np.diag(s[:1]) has shape \(1\times 1\text{,}\) and Vt[:, :1] has shape \(2\times 1\text{.}\) After the first two factors are multiplied, the result has shape \(2\times 1\text{,}\) which cannot be multiplied on the right by another \(2\times 1\) matrix.
The mathematical mistake is that rows of \(V^T\text{,}\) not columns of \(V^T\text{,}\) are the transposed right singular vectors used in the reconstruction. The rank-\(k\) reconstruction must use the first \(k\) rows of \(V^T\text{.}\)
Subsection Redundant features revisited by singular values
Compute
\begin{equation*}
X
\begin{bmatrix}
1\\
1\\
-1
\end{bmatrix}
=
\begin{bmatrix}
1+2-3\\
2+4-6\\
0+1-1\\
1-1-0
\end{bmatrix}
=
\begin{bmatrix}
0\\
0\\
0\\
0
\end{bmatrix}.
\end{equation*}
Thus
\begin{equation*}
\begin{bmatrix}
1\\
1\\
-1
\end{bmatrix}
\in \operatorname{null}(X).
\end{equation*}
The third column is the sum of the first two columns, so the columns are dependent. The first two columns are not multiples of each other, so
\begin{equation*}
\operatorname{rank}(X)=2.
\end{equation*}
Because \(X\) has three columns but rank \(2\text{,}\) one singular value is zero.
If \(X\mathbf{c}=\mathbf{y}\text{,}\) then
\begin{equation*}
X\left(\mathbf{c}+t
\begin{bmatrix}
1\\
1\\
-1
\end{bmatrix}\right)
=
X\mathbf{c}
+
tX
\begin{bmatrix}
1\\
1\\
-1
\end{bmatrix}
=
\mathbf{y}.
\end{equation*}
So different coefficient vectors can give the same output. This is the same nonuniqueness from Unit 2, now detected by a zero singular value.
Subsection Low-rank update storage
The product \(BC\) has shape
\begin{equation*}
5000\times 3000,
\end{equation*}
so it can be added to \(W\text{.}\) Since the inner dimension is \(8\text{,}\)
\begin{equation*}
\operatorname{rank}(BC)\leq 8.
\end{equation*}
The full matrix \(W\) stores
\begin{equation*}
5000\cdot 3000=15000000
\end{equation*}
numbers. The matrices \(B\) and \(C\) together store
\begin{equation*}
5000\cdot 8+8\cdot 3000
=
40000+24000
=
64000
\end{equation*}
numbers.
The product \(BC\) is called a low-rank update because the change has rank at most \(8\text{,}\) even though it has the same shape as \(W\text{.}\) This does not mean that
\begin{equation*}
W_{\text{new}}=W+BC
\end{equation*}
has low rank. The update has low rank; the whole updated matrix may still have large rank.
