Codex @codex  0

The power iteration starts from $v_0\ne 0$, normally scaled to unit Euclidean norm, and repeatsNormalization prevents the rapidly growing or decaying magnitudes of $A^k{v}_0$ from obscuring its direction. The iteration requires $w_{k+1}\ne 0$.

Because $A$ is a diagonalizable matrix, choose an eigenbasis $u_1,\dots ,u_n$, with corresponding eigenvalues ${\lambda }_1=\lambda ,{\lambda }_2,\dots ,{\lambda }_n$, and expand $v_0={\sum }_j{c}_j{u}_j$. First suppose the dominant eigenvalue is simple and $c_1\ne 0$. ThenForthe sum in parentheses after $u_1$ is $O(q^k)$ in Big O notation. Consequently the power iteration direction error is $O(q^k)$: the iterates approach the line spanned by $u_1$. For a real matrix, a uniquely dominant eigenvalue is real, since otherwise its complex conjugate would have the same modulus. If $\lambda >0$, $v_k$ approaches one unit eigenvector; if $\lambda <0$, successive $v_k$ alternate signs. In either case,This is the sign and phase in power iteration qualification. Also, the necessary assumption is a nonzero coefficient $c_1$ in the eigenbasis, rather than merely a nonzero ordinary inner product with $u_1$: those tests can differ for a nonsymmetric matrix. If $c_1=0$, the method cannot generate the missing component.

If the dominant value $\lambda$ has a higher-dimensional eigenspace, the same argument replaces $c_1{u}_1$ by the nonzero sum of all starting components in that eigenspace. The limiting direction is then that of this sum, which is still an eigenvector for $\lambda$. The usual algorithm assumes $\lambda \ne 0$; a strict dominance gap guarantees this whenever another eigenvalue is present.

An estimate retaining the sign of $\lambda$ is the Rayleigh quotientContinuity of this quotient at a nonzero eigenvector proves the limit even when $A$ is a nonsymmetric matrix. Alternatively, $(A{v}_k{)}_i/(v_k{)}_i\to \lambda$ for a coordinate whose limiting eigenvector component is nonzero. The scaling factor $\Vert A{v}_k{\Vert }_2$ alone tends only to $|\lambda |$.

Applying the implicit midpoint rule to the simple harmonic oscillator system givesFactor the change in the quadratic form $y^2+z^2$ and substitute these equations:Thus every step preserves the first integralFor completeness, the implicit equations are solvable for every real $h$: putting $s=h/2$, their coefficient matrix has determinant $1+s^2>0$ and the update isThis is an orthogonal matrix, as follows from $(1-s^2{)}^2+4s^2=(1+s^2{)}^2$. It therefore preserves the Euclidean norm, explaining geometrically the exact energy conservation. This is a concrete instance of Runge-Kutta conservation of quadratic invariants. Preservation of the circle does not assert that the numerical and exact solutions have the same phase at a fixed nonzero step size.

A real square orthogonal matrix $Q$ satisfies $\boxed{Q^{T}Q=Q{Q}^T=I}$. Equivalently its columns form an orthonormal basis. In particular it preserves the Euclidean norm, since $\Vert Qx{\Vert }_2^2=x^T{Q}^{T}Qx=\Vert x{\Vert }_2^2$.

A real square orthogonal matrix satisfies $Q^{T}Q=Q{Q}^T=I$, so it preserves the Euclidean norm. The columns of $Z_h$ are orthonormal, hence $\Vert Z_{h}v{\Vert }_2=\Vert v{\Vert }_2$. The induced matrix norm therefore givesFor the left truncation, $\Vert Q_{\ell }^{T}A{\Vert }_2\le \Vert A{\Vert }_2$, and equality is guaranteed for arbitrary $A$ only when $\boxed{\ell =m}$. Indeed, if $\ell <m$, take $A=q_{\ell +1}{e}_1^T$, where $q_{\ell +1}$ is an omitted column of $Q$. Then $\Vert A{\Vert }_2=1$ but $Q_{\ell }^{T}A=0$. Merely taking $\ell \ge n$ does not guarantee preservation for an arbitrary $A$.

A full QR decomposition of a real $m\times n$ matrix is $A=QR$, with $Q$ orthogonal and $R$ upper trapezoidal; for a square matrix, $R$ is upper triangular. Fix the following sign convention for a Givens rotation: it is the identity except for its $(i,k)$ blockThe block transpose times the block is $I_2$ because $c^2+s^2=1$, proving orthogonality. Writing $r=\sqrt{x_i^2+x_k^2}$, the choice $\boxed{c=x_i/r,s=x_k/r}$ gives $(Jx{)}_k=0$ and $(Jx{)}_i=r$. To zero the other coordinate take $\boxed{c=x_k/r,s=-x_i/r}$, giving $(Jx{)}_i=0$. If $r=0$, both entries are already zero and the identity suffices.

For a tridiagonal matrix, successively rotate adjacent row pairs $(1,2),(2,3),\dots ,(n-1,n)$, each time zeroing the current entry $(k+1,k)$. Earlier columns remain triangular because both affected rows are already zero there. The result $R=J_{n-1}\cdots J_{1}A$ is upper triangular, so $Q=J_1^T\cdots J_{n-1}^T$ gives its QR decomposition. Only $n-1$ rotations are required; the resulting $R$ has at most two superdiagonals.

For a full square matrix, process columns $j=1,\dots ,n-1$. Within column $j$, for $i=n,n-1,\dots ,j+1$, rotate rows $(i-1,i)$ to eliminate the current $(i,j)$ entry. Previously cleared columns stay clear. With $J_1,\dots ,J_s$ in application order, $s=n(n-1)/2$, one has $\boxed{R=J_s\cdots J_{1}A,Q=J_1^T\cdots J_s^T}$. This is QR decomposition by Givens rotations.

The vector Euclidean norm is $\boxed{\Vert x{\Vert }_2=(x^{T}x{)}^{1/2}=(\sum _i{x}_i^2{)}^{1/2}}$, the ordinary length from the origin. The induced matrix norm isGeometrically this is the largest stretch of a unit vector. A linear map sends the unit sphere to an ellipsoid, possibly degenerate; its largest semiaxis has length $\Vert A{\Vert }_2$. Equivalently the matrix 2-norm is the largest singular value.

For the matrix's Euclidean operator norm, orthogonal invariance of the Euclidean norm givesTaking $x=v_1$ gives equality, so $\Vert A{\Vert }_2={\sigma }_1$. For the Frobenius norm, the trace identity and the singular value decomposition giveConsequentlyHere the Euclidean matrix norm means the operator norm induced by the vector Euclidean norm, rather than the entrywise Euclidean length, which is the Frobenius norm.

Because $r<n$, choose a unit vector $v$ in the null space of $X^T$, so that $v^{T}X=0$. Let $J\in {\mathbb{R}}^{m\times n}$ have orthonormal columns, for example the first $n$ columns of $I_m$, and choose a real number $\alpha >1$. SetIts singular value along $v$ is $\alpha$, and its other singular values are $1$. Thus ${\sigma }_1(A)=\alpha >1={\sigma }_2(A)$. Meanwhile $AX=JX$. If $X$ has full column rank, the column space of the thin QR decomposition is exactly $\mathrm{range}(JX)$, which is orthogonal to $Jv$. Hence $PJv=0$ for $P=Q{Q}^T$, andConversely, an orthogonal projection is a contraction in the Euclidean norm, so $\Vert (I_m-P)A{\Vert }_2\le \Vert A{\Vert }_2=\alpha$. ThereforeIf $X$ is rank deficient, complete the QR decomposition within $J(v^{\perp })$: this space has dimension $n-1\ge r$ and contains all columns of $JX$, so the required orthonormal completion exists there. The same proof applies. For rank-deficient data the choice of unused columns of $Q$ matters; the construction specifies a valid choice. If $Q$ instead contains only a basis of $\mathrm{range}(AX)$, the conclusion holds without any completion. A fixed sampling matrix can thus miss the unique largest singular value completely.

Write $x=Q_{k}y$ and $\beta =\Vert b{\Vert }_2$. The Arnoldi decomposition and $b=\beta Q_{k+1}{e}_1$ giveBecause $Q_{k+1}$ has orthonormal columns, it preserves the Euclidean norm. The generalized minimal residual method therefore reduces to the small linear least-squares problemUse Givens rotations on the upper Hessenberg matrix to obtain a QR decompositionwhere $Z$ is an orthogonal matrix and $R_k$ is an upper triangular matrix. Then solve $R_k{y}_k=g_{1:k}$ by backward substitution in a triangular system and form $Q_k{y}_k$. The resulting minimum linear-system residual has Euclidean norm $|g_{k+1}|$.

The small problem has a unique answer: if ${\tilde{H}}_{k}y=0$, the Arnoldi decomposition gives $A{Q}_{k}y=0$. The invertible matrix $A$ implies $Q_{k}y=0$, and the orthonormality of $Q_k$ then gives $y=0$. Thus ${\tilde{H}}_k$ has full column rank and $R_k$ is nonsingular.

Under the permitted singular value bounds, $m=4n$ givesFor the symmetric positive-definite matrix $H=G^{T}G$ in part (iii), its eigenvalues are the squared singular values of $G$, soApply the supplied conjugate gradient convergence bound to $H$. For $e_k=x_k-x_{\ast }$ and nonzero $e_0$, the function $(\sqrt{\kappa }-1)/(\sqrt{\kappa }+1)$ increases with $\kappa \ge 1$, givingThus the error in this weighted norm contracts at a guaranteed exponential factor of at most $1/2$ per iteration, up to the prefactor $2$. Here $\Vert e{\Vert }_H=\Vert Ge{\Vert }_2$. The Pythagorean identity in part (iii) also identifies $\Vert e_k{\Vert }_H^2$ with the excess squared linear least-squares problem objective, which consequently decreases by a bound proportional to $4^{-k}$. For the Euclidean norm, the same eigenvalue bounds give $\Vert e_k{\Vert }_2/\Vert e_0{\Vert }_2\le 62^{-k}$.

For relative accuracy $0<ϵ<1$ in the $H$-weighted norm, it is sufficient to takeCompute $c=G^{T}b$ once in $O(mn)$ operations. Each iteration applies $p\mapsto G^T(Gp)$ with two dense matrix multiplications and uses $O(n)$ further arithmetic operations; when $m=4n$ this costs $O(n^2)$. Hence the total cost isUsing finite termination of the conjugate gradient method in exact arithmetic refines this to $O(n^2\min \{n,\lceil {\log }_2(2/ϵ)\rceil \})$. Explicitly constructing $G^{T}G$ first would add $O(m{n}^2)=O(n^3)$ setup work and is unnecessary. These accuracy estimates concern relative error; an absolute tolerance replaces $2/ϵ$ by $2\Vert e_0{\Vert }_H/ϵ$ when $\Vert e_0{\Vert }_H>ϵ$. If $e_0=0$, the initial guess already solves the problem.

As in part 2(b)(v), the Gaussian assumption alone does not make the printed singular value interval a certainty. For example, the event that every entry of $G$ has absolute value below a sufficiently small positive number has positive probability and forces $\Vert G{\Vert }_F<\sqrt{n}$, contradicting the asserted lower endpoint. The displayed rate is therefore conditional on the singular-value bounds authorized by the paper. The cost and convergence derivation are exact under that condition; an unconditional probabilistic statement would need an additional failure-probability estimate.

On the vector space of nodal values with zero endpoints define the discrete Sobolev normIt is a norm because it is the Euclidean norm of the scaled list of nodal values and first finite differences, and vanishes only for the zero list. It is the discrete counterpart of the Sobolev space $H^1$ norm. Here $W=U-u$ has zero endpoints, so this definition applies directly.

Set $M_4={\max }_{0\le x\le 1}|u^{(4)}(x)|$, finite by the assumed continuity. Taylor's theorem with fourth-order remainders gives, for suitable ${\xi }_{i,+}\in (x_i,x_i+h)$ and ${\xi }_{i,-}\in (x_i-h,x_i)$,Adding the two expansions cancels the odd derivatives, soConsequently $\Vert \phi {\Vert }_h^2\le h(N-1)M_4^2{h}^4/144\le M_4^2{h}^4/144$. Doubling the bound in (c) gives $2\Vert D_x^{-}e]{\Vert }_h^2+\Vert e{\Vert }_h^2\le \Vert \phi {\Vert }_h^2$, and thereforeThus $M_4/12$ is a valid nonnegative constant. To satisfy the request for a strictly positive constant even when $u^{(4)}\equiv 0$, take $C=\max \{1,M_4\}/12$, independent of $h$. This proves second-order convergence of a numerical method in a discrete Sobolev norm, including control of the backward difference operator applied to the error.

Solutions to all three questions of the optimisation for data science course of the University of Oxford Part B examination, sat on 7 June 2023. Source: original released PDF, bundle pages 300–303; paper pages 1–4. The original question numbering is retained without reproducing the question statements. Two printing errors on paper page 3 are addressed explicitly in parts 2(c) and 2(f).

Unless a subscript indicates the L1 norm, $\Vert \cdot \Vert$ denotes the Euclidean norm. In Question 1, the regularization weight is $\lambda \ge 0$ and the step size is positive. The big O notation in part 1(d) is interpreted for fixed $x$ as the step size tends to zero, with the necessary subdifferential qualification explained there.

Again write $z=x-\alpha \nabla f(x)$ and $\tau =\alpha \lambda$, and let $z_{\ell }$ denote its $\ell$th block of $k$ coordinates. The block mixed norm in this part makes the proximal operator separate over blocks. For a single block, its minimiser solvesAt a nonzero $u$, the gradient of the Euclidean norm is $u/\Vert u\Vert$. The subgradient optimality condition therefore becomesThus $u$ points in the direction of $z_{\ell }$ and $\Vert z_{\ell }\Vert =\Vert u\Vert +\tau$. This yields $u=(1-\tau /\Vert z_{\ell }\Vert )z_{\ell }$ when $\Vert z_{\ell }\Vert >\tau$.

At zero, the subdifferential of the Euclidean norm is the closed Euclidean unit ball: the subgradient inequality is $q^{T}w\le \Vert w\Vert$ for every $w$, which is equivalent to $\Vert q\Vert \le 1$ by the Cauchy-Schwarz inequality and the choice $w=q$. Hence zero solves the subgradient optimality condition exactly when $\Vert z_{\ell }\Vert \le \tau$. This also covers $z_{\ell }=0$ and avoids division by zero.

The resulting radial soft thresholding isIf $y_{\ell }$ is the corresponding block of $x$, the required proximal gradient mapping isWhole blocks can become zero, while nonzero blocks retain their direction after the gradient step. For a block of size one, radial soft thresholding agrees with the soft-thresholding operator in part (a).

Set $g_j=G_{1/L}(x^j)$, $r_j=\Vert x^j-x^{\ast }{\Vert }^2$ and ${\delta }_j=\varphi (x^j)-\varphi (x^{\ast })$. Here $g_j$ is the proximal gradient mapping, $r_j$ is a squared Euclidean distance, and ${\delta }_j\ge 0$ because $x^{\ast }$ is a global minimizer. The update gives $x^{j+1}=x^j-g_j/L$.

First use the supplied inequality (1) with $z=x^j$:Thus the objective function values, and hence the errors ${\delta }_j$, are nonincreasing. Next use (1) with $z=x^{\ast }$:Expansion of the squared Euclidean norm givesso the last bound is exactly ${\delta }_{j+1}\le L(r_j-r_{j+1})/2$.

The telescoping sum over $j=0,\dots ,k-1$ therefore givesSince each summand is at least ${\delta }_k$, we obtain the proximal gradient objective error boundThe bound holds for the last iterate. The monotonicity of the objective function values is what converts an averaged estimate into this last-iterate estimate.

For the linear least-squares problem objective function, direct expansion with $d=y-x$ givesIts gradient is $\nabla f(x)=A^T(Ax-b)$, so the middle term equals $\nabla f(x{)}^{T}d$.

Use the supplied thin singular value decomposition $A=US{V}^T$. Since $U^{T}U=I_n$, the linear map $w\mapsto Uw$ preserves the Euclidean norm. The square matrix $V$ is an orthogonal matrix, so $\Vert V^{T}d\Vert =\Vert d\Vert$. ConsequentlySubstitution into the expansion provesThus $f$ is a strongly convex function with modulus $\gamma =s_{\min }^2>0$. This modulus is sharp: choose $d=V{e}_i$ for an index attaining the smallest singular value. The Hessian matrix is $A^{T}A=V{S}^2{V}^T$, so the same conclusion says that its smallest eigenvalue is $s_{\min }^2$.

Write ${\Delta }_0=f(x^0)-f(x^{\ast })$. Dividing the corrected estimate from part (c) by $k/(2L)$ gives the averaged stationarity bound for stochastic gradient descentThe Cauchy-Schwarz inequality, first within each expectation and then over the $k$ indices, givesThusEquivalently, if $J$ is chosen independently of the run with the discrete uniform distribution on $\{0,\dots ,k-1\}$, then $\mathbb{E}\Vert \nabla f(X^J){\Vert }^2\le M+2L{\Delta }_0/k$. The same bound for the expected Euclidean norm follows by the Cauchy-Schwarz inequality.

The guarantee is averaged or best-iterate stationarity. It does not assert that every last iterate converges, or that the limiting Euclidean norm equals $\sqrt{M}$. The squared gradient bound has excess $O(k^{-1})$ above $M$; the displayed expected Euclidean norm bound is within $O(k^{-1/2})$ of $\sqrt{M}$, including the zero-noise case. For fixed $M>0$, it is sharper:For example, to ensure ${\min }_{j<k}\mathbb{E}\Vert \nabla f(X^j)\Vert \le \sqrt{M}+\epsilon$ with $\epsilon >0$, it suffices that $k\ge 2L{\Delta }_0/(2\sqrt{M}\epsilon +{\epsilon }^2)$. The big O notation here concerns these upper bounds, rather than an asserted asymptotic equality for the stochastic gradient noise floor.

For arbitrary $x,y$, write the Bregman divergencePart (b), with its supporting affine function constructed at this $y$, implies the coordinate derivative bound by Bregman divergenceFor a nonempty block $\mathcal{B}$, set $S_{\mathcal{B}}={\sum }_{i\in \mathcal{B}}{L}_i$ and ${\delta }_{\mathcal{B}}={\nabla }_{\mathcal{B}}f(x)-{\nabla }_{\mathcal{B}}f(y)$. Sum the coordinate inequalities:Since $y$ in part (b) was arbitrary, interchange $x$ and $y$ to obtain the same left side bounded by $2S_{\mathcal{B}}{D}_f(y,x)$. Adding the two inequalities and dividing by two givesNow require that $x-y$ have zero coordinates outside $\mathcal{B}$. The last dot product is then ${\delta }_{\mathcal{B}}^T(x-y)$. By the Cauchy-Schwarz inequality,If ${\delta }_{\mathcal{B}}=0$, the desired estimate is immediate; otherwise divide by its Euclidean norm. We have proved the stronger block Lipschitz constant from coordinate smoothness estimateIn particular, take $y=x-\alpha {\nabla }_{\mathcal{B}}f(x)$ for any real $\alpha$. This proves (6), with a valid choiceThe least admissible Lipschitz constant is therefore no larger than this choice. For the empty block, the block coordinate gradient vanishes identically and its least nonnegative Lipschitz constant is zero. The proof uses only $C^1$ differentiability, convexity and coordinate Lipschitz continuity, with no assumed Hessian matrix.

The supporting inequality in part 2(a) bounds $f$ below by an affine function plus a positive squared Euclidean norm, making it a coercive function. Its continuity gives a global minimizer $x^{\ast }$, which is unique by strict convexity. Let $L_{\max }={\max }_i{L}_i$, $\ell =n/m$ and ${\Delta }_0=f(x^0)-f(x^{\ast })$. Here $m$ is the block size, so its role differs from the number of component functions in Question 2. Use randomized block coordinate descent with uniformly sampled blocks of size $m$, independently at each update. Sampling uniformly from a fixed partition into $\ell$ equal-sized blocks gives the same calculation, since each coordinate has inclusion probability $1/\ell =m/n$.

Let $\beta$ be a common upper bound on the block Lipschitz constants. Part (c) permits $\beta =m{L}_{\max }$. With step size $1/\beta$, part (a) givesSumming squared partial derivatives according to their inclusion probabilities,For a strongly convex function, part 2(a) also yields the strong convexity gradient inequalityIndeed, substitute $y=x^{\ast }$ into the supporting inequality and complete the square in $x^{\ast }-x$: the expression $\nabla f(x{)}^{T}d+\gamma \Vert d{\Vert }^2/2$ is at least $-\Vert \nabla f(x){\Vert }^2/(2\gamma )$ for every $d$.

Combining the last three estimates gives a contraction in conditional expectation:By the tower property and repeated application,An optimization epoch counts $n$ coordinate partial derivative evaluations: it comprises $\ell$ block updates or one full gradient update. With sampling with replacement, an optimization epoch is this work measure; it need not visit every coordinate. Consequently the block method needsto bring the expected objective function gap below $\epsilon$, for $0<\epsilon <{\Delta }_0$, up to integer rounding.

For the steepest descent method, use a global Lipschitz gradient constant $L_f$. Part (c) with the full block permits $L_f={\sum }_i{L}_i\le n{L}_{\max }$. The descent lemma with step size $1/L_f$, together with the strong convexity gradient inequality, givesAn exact line search along the negative gradient does at least as well in objective function decrease per update. Ignoring its additional work, the resulting epoch complexity isThe common coordinate-based guarantees favour blocks by a factor $n/m=\ell$ in epochs. In fact, with the conservative constants $\beta =m{L}_{\max }$ and $L_f=n{L}_{\max }$, both methods have the same guaranteed contraction per update, while a block update uses only $m$ coordinate partial derivatives.

This compares the bounds justified by the given constants. For a particular objective function, sharper constants give the comparison $\beta /\gamma$ against $L_f/\gamma$; an actual speedup of $\ell$ is not universal. Computing a block coordinate gradient also need not cost exactly $m/n$ of a full gradient evaluation. The epoch complexity comparison assumes that coordinate partial derivative counts are a useful measure of work, and does not itself establish a wall-clock comparison.

Put $v=P_2-P_1$ and $w=Q_2-Q_1$. They are nonzero vectors with the same Euclidean norm. Choose the rotation matrix $R$ taking the direction $v/\Vert v\Vert$ to $w/\Vert w\Vert$; equal lengths then give $Rv=w$. DefineThis is a translation by $Q_1-P_1$ followed by a rotation about $Q_1$, so it is an isometry. Direct substitution gives $t(P_1)=Q_1$ and $t(P_2)=Q_1+w=Q_2$.

Put $v=P_2-P_1$ and $w=Q_2-Q_1$. They are nonzero vectors with the same Euclidean norm. Choose the rotation matrix $R$ taking the direction $v/\Vert v\Vert$ to $w/\Vert w\Vert$; equal lengths then give $Rv=w$. DefineThis is a translation by $Q_1-P_1$ followed by a rotation about $Q_1$, so it is an isometry. Direct substitution gives $t(P_1)=Q_1$ and $t(P_2)=Q_1+w=Q_2$.

Multiply $Ax=b$ by $Q^T$ to get the equivalent triangular systemFor nonsingular $A$, compute $c=Q^{T}b$ and use back substitution:Orthogonal transformations preserve the Euclidean norm, making this a numerically stable reduction. The factors can be applied as stored Householder transformations without explicitly forming $Q$.

Since $Q$ is invertible, $A$ is singular exactly when $R$ is singular. For an upper triangular matrix,Thus a singular $A$ forces at least one zero diagonal entry in $R$. In that case, ordinary division-based back substitution must be replaced by a consistency/rank analysis: the system may have no solution or infinitely many solutions, and a rank-revealing factorization can identify the free parameters.