= Solution
{c}
For the <linear least-squares problem> <objective function>, direct expansion with $d=y-x$ gives
$$
f(y)=\frac12\|Ax-b+Ad\|^2
=f(x)+(Ax-b)^TAd+\frac12\|Ad\|^2.
$$
Its <gradient> is $\nabla f(x)=A^T(Ax-b)$, so the middle term equals $\nabla f(x)^Td$.
Use the supplied thin <singular value decomposition> $A=USV^T$. Since $U^TU=I_n$, the <linear map> $w\mapsto Uw$ preserves the <Euclidean norm>. The square <matrix> $V$ is an <orthogonal matrix>, so $\|V^Td\|=\|d\|$. Consequently
$$
\|Ad\|^2=\|SV^Td\|^2
=\sum_{i=1}^n s_{i,i}^2(V^Td)_i^2
\geq s_{\min}^2\sum_{i=1}^n(V^Td)_i^2
=s_{\min}^2\|d\|^2.
$$
Substitution into the expansion proves
$$
\boxed{f(y)\geq f(x)+\nabla f(x)^T(y-x)+\frac{s_{\min}^2}{2}\|y-x\|^2.}
$$
Thus $f$ is a <strongly convex function> with modulus $\gamma=s_{\min}^2>0$. This modulus is sharp: choose $d=Ve_i$ for an index attaining the smallest <singular value>. The <Hessian matrix> is $A^TA=VS^2V^T$, so the same conclusion says that its smallest <eigenvalue> is $s_{\min}^2$.
Back to article page
