Section 6.8 Unit 6 highlights
Subsection Mathematical quick reference
Absolute extrema.
Extreme value theorem. A continuous real-valued function on a nonempty closed bounded subset of \(\mathbb R^n\) attains an absolute maximum and an absolute minimum.
Candidate procedure. Find interior critical points, examine interior points where differentiability fails, and optimize on every boundary piece. Include endpoints, corners, and intersections of boundary pieces. Compare the function values at all candidates. When a boundary is parametrized by \(\mathbf r(t)\text{,}\) optimize \(f(\mathbf r(t))\) over its parameter domain.
Lagrange multipliers.
One equality constraint. At a constrained local extremum of \(f\) on \(g(\mathbf x)=k\text{,}\) with \(f,g\) continuously differentiable nearby and \(\nabla g\neq\mathbf0\text{,}\) there is a scalar \(\lambda\) such that
\begin{equation*}
\nabla f(\mathbf x)=\lambda\nabla g(\mathbf x),\qquad g(\mathbf x)=k.
\end{equation*}
Several equality constraints. For \(g_i(\mathbf x)=k_i\text{,}\) \(i=1,\ldots,s\text{,}\) with continuously differentiable functions and independent constraint gradients at the extremum,
\begin{equation*}
\nabla f(\mathbf x)=\sum_{i=1}^s\lambda_i\nabla g_i(\mathbf x),\qquad g_i(\mathbf x)=k_i\quad(i=1,\ldots,s).
\end{equation*}
Lagrangian. Package both the gradient equation and all constraints as
\begin{equation*}
L(\mathbf x,\boldsymbol\lambda)=f(\mathbf x)-\sum_{i=1}^s\lambda_i\bigl(g_i(\mathbf x)-k_i\bigr),\qquad \nabla_{\mathbf x}L=\mathbf0,\quad L_{\lambda_i}=0.
\end{equation*}
Use the conditions. Solve the system for feasible candidates and compare objective values. Examine separately any points where constraint gradients fail the hypotheses, and any additional boundary restrictions. The multiplier equations are necessary under these hypotheses, not sufficient for an extremum.
Quadratic forms and maximum stretch.
Unit-sphere extrema. For a real symmetric \(B\text{,}\)
\begin{equation*}
\min_{\|\mathbf x\|=1}\mathbf x^TB\mathbf x=\lambda_{\min}(B),\qquad \max_{\|\mathbf x\|=1}\mathbf x^TB\mathbf x=\lambda_{\max}(B).
\end{equation*}
Unit eigenvectors for the extreme eigenvalues attain the extrema.
Matrix stretch. For \(A\in\mathbb R^{m\times n}\text{,}\)
\begin{equation*}
\|A\mathbf x\|^2=\mathbf x^TA^TA\mathbf x,\qquad \max_{\|\mathbf x\|=1}\|A\mathbf x\|=\sqrt{\lambda_{\max}(A^TA)}=\sigma_1.
\end{equation*}
The positive singular values are square roots of the positive eigenvalues of \(A^TA\text{.}\)
Principal directions and orthogonal reconstruction.
Centering and covariance. For \(X\in\mathbb R^{n\times d}\) with data rows \(\mathbf x_i^T\text{,}\) let \(\boldsymbol\mu=\frac1n\sum_i\mathbf x_i\) and let \(Z\) have rows \((\mathbf x_i-\boldsymbol\mu)^T\text{.}\) This book uses
\begin{equation*}
C=\frac1nZ^TZ.
\end{equation*}
The symmetric matrix \(C\) has nonnegative eigenvalues.
Principal directions. Choose orthonormal eigenvectors \(\mathbf v_1,\ldots,\mathbf v_d\) of \(C\text{,}\) ordered by \(\lambda_1\geq\cdots\geq\lambda_d\geq0\text{.}\) The first direction maximizes \(\mathbf v^TC\mathbf v\) over unit vectors; each later direction maximizes it subject to orthogonality to earlier directions.
Scores and reconstruction. Put \(V_k=[\mathbf v_1\ \cdots\ \mathbf v_k]\text{.}\) Then
\begin{equation*}
T_k=ZV_k,\qquad \widehat Z=T_kV_k^T=ZV_kV_k^T,\qquad R=Z-\widehat Z,\quad RV_k=0.
\end{equation*}
Rows of \(\widehat Z\) are projections onto the chosen subspace. Add the mean vector to recover approximations in the original coordinates.
Captured variation. When total variation is positive, the fraction retained by the first \(k\) directions is
\begin{equation*}
\frac{\lambda_1+\cdots+\lambda_k}{\lambda_1+\cdots+\lambda_d}.
\end{equation*}
Maximizing the sum of squared scores is equivalent to minimizing the sum of squared reconstruction residuals. A repeated eigenvalue permits different orthonormal choices within its eigenspace.
Singular value decomposition.
Full SVD. Every real \(m\times n\) matrix has a factorization
\begin{equation*}
A=U\Sigma V^T,\qquad U\in\mathbb R^{m\times m},\quad\Sigma\in\mathbb R^{m\times n},\quad V\in\mathbb R^{n\times n},
\end{equation*}
with \(U,V\) orthogonal and rectangular diagonal \(\Sigma\text{.}\) For \(p=\min(m,n)\text{,}\) its diagonal entries satisfy \(\sigma_1\geq\cdots\geq\sigma_p\geq0\text{.}\)
Construction and action. Choose an orthonormal eigenvector basis of \(A^TA\) for the columns of \(V\text{.}\) For each positive singular value, set \(\mathbf u_i=A\mathbf v_i/\sigma_i\text{;}\) complete these to an orthonormal basis of \(\mathbb R^m\text{.}\) If \(r=\operatorname{rank}(A)\text{,}\) then
\begin{equation*}
A\mathbf v_i=\sigma_i\mathbf u_i\ (1\leq i\leq r),\qquad A\mathbf v_i=\mathbf0\ (r\lt i\leq n),
\end{equation*}
\begin{equation*}
A=\sum_{i=1}^r\sigma_i\mathbf u_i\mathbf v_i^T.
\end{equation*}
Do not divide by a zero singular value.
Fundamental subspaces. In a full SVD,
\begin{equation*}
\operatorname{col}(A)=\operatorname{span}\{\mathbf u_1,\ldots,\mathbf u_r\},\qquad \operatorname{null}(A^T)=\operatorname{span}\{\mathbf u_{r+1},\ldots,\mathbf u_m\},
\end{equation*}
\begin{equation*}
\operatorname{row}(A)=\operatorname{span}\{\mathbf v_1,\ldots,\mathbf v_r\},\qquad \operatorname{null}(A)=\operatorname{span}\{\mathbf v_{r+1},\ldots,\mathbf v_n\}.
\end{equation*}
Empty lists give the zero subspace. The number of positive singular values is the rank.
PCA from an SVD. For centered \(Z=U\Sigma V^T\text{,}\)
\begin{equation*}
C=V\left(\frac1n\Sigma^T\Sigma\right)V^T,\qquad T=ZV=U\Sigma.
\end{equation*}
Thus principal directions are right singular vectors, and corresponding covariance eigenvalues are \(\sigma_i^2/n\text{,}\) with additional zeros when needed.
Subsection Common mistakes
Ignoring boundaries or constraint equations; treating every multiplier solution as an extremum; failing to compare objective values; applying the multiplier theorem when constraint gradients are dependent; or requiring the objective gradient to be parallel to every constraint gradient separately.
Dropping the unit-length condition in a quadratic-form extremum; forgetting to center before forming covariance; selecting the smallest eigenvalue for the first principal direction; confusing a direction, a score, and a reconstructed vector; dividing by a zero singular value; interchanging left and right singular vectors; or using an incomplete set of singular vectors to describe a null space.
Subsection Connections
Unit 1 supplies vectors and matrix actions. Unit 2 supplies rank and fundamental spaces. Unit 3 supplies gradients, level sets, and closed bounded regions. Unit 4 supplies orthogonal projection. Unit 5 supplies symmetric diagonalization and quadratic forms. Unit 7 extends orthogonality and projection to polynomial spaces.
