= Solution
Under the permitted <singular value> bounds, $m=4n$ gives
$$
\sqrt n\leq\sigma_{\min}(G)\leq\sigma_{\max}(G)\leq3\sqrt n.
$$
For the <symmetric positive-definite matrix> $H=G^TG$ in part (iii), its <eigenvalues> are the squared <singular values> of $G$, so
$$
n\leq\lambda_{\min}(H)\leq\lambda_{\max}(H)\leq9n,
\qquad \boxed{\kappa_2(H)\leq9}.
$$
Apply the supplied <conjugate gradient convergence bound> to $H$. For $e_k=x_k-x_*$ and nonzero $e_0$, the function $(\sqrt\kappa-1)/(\sqrt\kappa+1)$ increases with $\kappa\geq1$, giving
$$
\boxed{\frac{\|e_k\|_H}{\|e_0\|_H}\leq2\left(\frac{3-1}{3+1}\right)^k
=2^{1-k}}.
$$
Thus 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 $\|e\|_H=\|Ge\|_2$. The <Pythagorean identity> in part (iii) also identifies $\|e_k\|_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 $\|e_k\|_2/\|e_0\|_2\leq6\,2^{-k}$.
For relative accuracy $0<\epsilon<1$ in the $H$-<weighted norm>, it is sufficient to take
$$
k\geq\left\lceil\log_2\frac2\epsilon\right\rceil.
$$
Compute $c=G^Tb$ 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 is
$$
\boxed{O\!\left(n^2\log\frac2\epsilon\right)}.
$$
Using <finite termination of the conjugate gradient method> in exact arithmetic refines this to $O(n^2\min\{n,\lceil\log_2(2/\epsilon)\rceil\})$. Explicitly constructing $G^TG$ first would add $O(mn^2)=O(n^3)$ setup work and is unnecessary. These accuracy estimates concern relative error; an absolute tolerance replaces $2/\epsilon$ by $2\|e_0\|_H/\epsilon$ when $\|e_0\|_H>\epsilon$. 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 $\|G\|_F<\sqrt n$, contradicting the asserted lower endpoint. The displayed rate is therefore \b[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.
Back to article page
