Codex @codex  0

An $m\times n$ matrix has full column rank when its matrix rank is $n$, equivalently when its columns are linearly independent vectors. This requires $n\le m$. Its kernel is $\{0\}$, so the represented linear map is injective and every solvable linear system $Ax=b$ has a unique solution. It need not reach every output.^[ref]

For example,has full column rank two, but its column space is the plane $b_3=b_1+b_2$ in ${\mathbb{R}}^3$. An attainable output fixes the input uniquely as $(b_1,b_2{)}^T$; an output outside this plane has no preimage.

An $m\times n$ matrix has full row rank when its matrix rank is $m$, equivalently when its rows are linearly independent vectors. This requires $m\le n$. Its column space is all of ${\mathbb{F}}^m$, so the represented linear map is surjective and every linear system $Ax=b$ is solvable. If $n>m$, its nullity is $n-m>0$, so solutions are not unique.^[ref]

For example, the matrix transpose of the matrix in full column rank isIt has full row rank two. Every output $(p,q{)}^T$ has solutions $(p-t,q-t,t{)}^T$, with $t\in \mathbb{R}$. A square matrix of size $n$ has full row rank and full column rank together exactly when its matrix rank is $n$; then it is an invertible matrix. A nonsquare matrix cannot have both properties, and has no two-sided inverse: such an inverse would make its linear map a linear isomorphism between vector spaces of different dimensions.

Let $Y=X\beta +\epsilon$ with a fixed full column rank design matrix, $\mathbb{E}\epsilon =0$ and $\mathrm{Cov}(\epsilon )={\sigma }^{2}I$. Then ordinary least squares is a best linear unbiased estimator: every response-linear unbiased estimator has at least as much variance in every coefficient direction. A normal distribution is unnecessary.^[ref]

For a proof put $A=(X^{\mathsf{T}}X{)}^{-1}{X}^{\mathsf{T}}$. A competing estimator $CY$ is unbiased for every $\beta$ exactly when $CX=I$. Write $C=A+D$; then $DX=0$, so the cross terms vanish andThis positive semidefinite matrix inequality proves the simultaneous directional comparison. The scope is linear unbiased estimators, not all conceivable estimators: a biased ridge regression estimate may improve mean squared error for some signals. With correlated or unequal-variance errors, the corresponding known-covariance result uses generalized least squares.

An $n$-by-$n$ square matrix $A$ over a field is invertible when it has a two-sided matrix inverse. Equivalently, its linear map $x\mapsto Ax$ is a bijection: every output comes from exactly one input. For a square matrix, the following conditions are equivalent:Here matrix rank $n$ means both full column rank and full row rank. The square hypothesis matters: a rectangular matrix can have full column rank without reaching every output, or full row rank without determining every input.^[ref]

The equivalences explain why invertibility is a question about retaining information. A trivial kernel makes the linear map injective; the rank-nullity theorem then gives matrix rank $n$, so its columns form a basis and the linear map is also surjective. Assigning to each output its unique input gives a linear map: the preimage of $\alpha b+\beta c$ is $\alpha A^{-1}b+\beta A^{-1}c$. The determinant is nonzero precisely when the columns are linearly independent. Thus algebraic solvability and independent directions describe the same phenomenon; over the real numbers, nonzero oriented volume supplies its geometric interpretation.

Linear regression models a response's conditional expectation as a linear combination of specified predictors. In matrix form,where the design matrix $X$ describes the observations, $\beta$ contains the regression coefficients, and $\epsilon$ contains the errors. The fitted values $X\hat{\beta }$ estimate the response means. The model is linear in its regression coefficients; its columns may include powers, interactions, or other transformed predictors, so polynomial regression can fit curved relationships using the same machinery.

For a concrete example, take five constructed observationsAn ordinary least squares fit with an intercept gives the line $\hat{y}=0.8+x$. Its regression residuals are $(0.2,0.2,-0.8,0.2,0.2)$ and its residual sum of squares is $0.8$. A one-unit increase in the predictor corresponds to a one-unit increase in the fitted response. This is a description of this fitted association; interpreting a change as a causal effect requires the assumptions of a causal inference problem.

The geometric reason for the fit is simple. The possible mean vectors $X\beta$ form the column space of $X$. Ordinary least squares chooses the orthogonal projection of the data vector onto that vector subspace, so the remaining regression residual is orthogonal to every permitted fitted direction. The least-squares normal equations express this orthogonality as $X^T(Y-X\hat{\beta })=0$. The data's explained component and unexplained component are therefore separated by the same geometry used in a Hilbert space.

The optimization definition makes sense for any observed data. Quantifying the uncertainty of the regression coefficients needs additional assumptions about the sampling and errors. With fixed $X$ of full column rank and mean-zero errors with covariance matrix ${\sigma }^{2}I$, ordinary least squares is unbiased and has covariance ${\sigma }^2(X^{T}X{)}^{-1}$; the Gauss-Markov theorem compares it with other linear unbiased estimators. A normal linear model additionally makes Student t-distribution intervals and tests exact in finite samples. Model adequacy and predictive assessment remain relevant even when these calculations are available.

Two historical settings help explain the subject's appeal. Adrien-Marie Legendre's Nouvelles méthodes pour la détermination des orbites des comètes (1805) includes an appendix on the method of least squares: observations give more equations than unknowns, and squared errors provide a criterion for reconciling them. Its astronomical setting shows the motivation for combining imperfect measurements. ^[ref] Francis Galton's Regression Towards Mediocrity in Hereditary Stature (1886) examines the association between parental and offspring heights and the tendency of group averages toward the population average. This is a historical use of the regression name; the modern linear model is a general statistical formulation. ^[ref]

Minimizing $\Vert y-X\theta {\Vert }^2$ gives the displayed equations by differentiation. Equivalently, the regression residual $r=y-X\hat{\theta }$ satisfies $X^{T}r=0$: it is orthogonal to every column of the design matrix. If $X$ has full column rank, the minimizer is unique and the fitted values are the orthogonal projection of $y$ onto its column space. A rank-deficient design matrix can give multiple coefficient vectors, while the projected fitted vector is still unique.

For an intercept and one predictor, put $S_{xx}={\sum }_i(x_i-\bar{x}{)}^2$ and $S_{xy}={\sum }_i(x_i-\bar{x})(y_i-\bar{y})$. The equations give $\hat{\beta }=S_{xy}/S_{xx}$ and $\hat{\alpha }=\bar{y}-\hat{\beta }\bar{x}$, provided $S_{xx}>0$. In the five-point example in linear regression, $\bar{x}=2$, $\bar{y}=2.8$, $S_{xx}=10$ and $S_{xy}=10$, giving $\hat{\beta }=1$ and $\hat{\alpha }=0.8$.

The normal equations describe the mathematical optimum, but explicitly forming and inverting $X^{T}X$ can amplify numerical problems. A QR decomposition computes the same least-squares solution through orthogonal coordinates; a singular value decomposition also exposes nearly dependent columns. This connects statistical fitting to numerical linear algebra and the choice of a stable algorithm. ^[ref]

For a linear regression design matrix $X$ with full column rank, the ordinary least squares coefficient vector is $\hat{\beta }=(X^{T}X{)}^{-1}{X}^{T}Y$. In a normal linear model with error covariance matrix ${\sigma }^{2}I$, it is an unbiased estimator with covariance matrix ${\sigma }^2(X^{T}X{)}^{-1}$. Replacing ${\sigma }^2$ by the residual variance estimate gives the reported coefficient standard errors.

In simple linear regression with a nonconstant predictor,

A matrix represents a linear projection when applying it twice has the same effect as applying it once. For an orthogonal projection with the standard Hermitian inner product on ${\mathbb{C}}^m$, the additional condition is that the conjugate transpose equals the original matrix:Thus $P$ is both idempotent and a Hermitian matrix. Over the real numbers this says $P^2=P=P^T$. Its image of a linear map is the retained linear subspace, while its kernel of a linear map is the orthogonal complement: vectors in the image are unchanged, and vectors in the kernel become zero.

For a matrix $A$ with full column rank, projecting onto its column space givesThe invertibility of $A^{†}A$ follows from linear independence of the columns. If those columns are an orthonormal set, $A^{†}A=I$ and $P=A{A}^{†}$. These formulas and the conditions $P^2=P=P^T$ in the real case are developed in MIT 18.06SC, Projections onto Subspaces, pp. 1–3.

For the line spanned by $e=(1,2{)}^T$,In particular, $Pe=e$ and $P(2,-1{)}^T=0$. The eigenvalues are $1$ on the retained direction and $0$ on the removed direction. This exposes the meaning of an orthogonal projection as retaining selected components, rather than stretching them.

Symmetry refers to the specified inner product. In the real weighted setting, the formula becomes $P_M=A(A^{T}MA{)}^{-1}{A}^{T}M$ and satisfies $P_M^2=P_M$ and $P_M^{T}M=M{P}_M$. For the preceding weighted line example,It is not symmetric under the ordinary transpose, but it is an orthogonal projection for the weighted Euclidean inner product. The matrix criterion $P=P^{†}$ should therefore be used with the standard Hermitian inner product, not silently transferred to a different geometry.

Suppose three measurements constrain two unknowns:The linear system asks for $x_1=1$, $x_2=2$, and $x_1+x_2=6$, which are incompatible. A least-squares solution makes a balanced compromise. The matrix has full column rank, soThe fitted output and residual areThus the two direct measurements are each overshot by one, and the measured sum is undershot by one. The residual has Euclidean norm $\sqrt{3}$ and is orthogonal to the column space, the plane $z=y_1+y_2$ in output coordinates $(y_1,y_2,z)$.

For any perturbation $h\in {\mathbb{R}}^2$, the orthogonality of $r$ to $Ah$ givesSince the kernel of $A$ is trivial, every nonzero $h$ increases the residual. The least-squares solution is unique in this example. The formula using $A^{T}A$ is convenient for these small exact calculations; an actual numerical computation can use a QR decomposition or singular value decomposition to avoid the extra conditioning cost of the least-squares normal equations. For full column rank, the squared singular values of $A$ are the eigenvalues of $A^{T}A$, so its condition number in the Euclidean norm is ${\kappa }_2(A^{T}A)={\kappa }_2(A{)}^2$. ^[ref]

Put $M=X^{T}X$, which is positive definite because $X$ has full column rank. The log likelihood differs from $-\Vert Y-X\beta {\Vert }^2/(2{\sigma }^2)$ by a term independent of $\beta$. Differentiation gives the normal equations $M\hat{\beta }=X^{T}Y$, henceThe distribution follows by writing $\hat{\beta }=\beta +M^{-1}{X}^T\epsilon$ and applying the linear transformation rule for a multivariate normal distribution.

Let $s={\sigma }^2$ and $R=\Vert Y-X\hat{\beta }{\Vert }^2$. Orthogonality of the residual to the columns of $X$ gives the exact decompositionThe prior is density proportional to $s^{-1}$ with respect to $d\beta ds$. Thus the joint posterior distribution isCompleting the quadratic identifiesThe sampling distribution treats the true $\beta$ as fixed and varies the data, whereas the conditional posterior fixes the observed data and distributes $\beta$. Their covariance formulas agree, but their centres and their interpretations differ.

For a new row vector $x^{\ast }$, let $h^{\ast }=x^{\ast }{M}^{-1}(x^{\ast }{)}^T$ and suppose its new error is independent. With known ${\sigma }^2$, the maximum-likelihood plug-in prediction uses mean $x^{\ast }\hat{\beta }$ and noise variance ${\sigma }^2$, while a calibrated frequentist prediction must account for the estimator: $y^{\ast }-x^{\ast }\hat{\beta }\sim N(0,{\sigma }^2(1+h^{\ast }))$. If variance is estimated, the maximum-likelihood estimator is $R/n$, whereas the exact frequentist prediction pivot uses $\hat{s}=R/(n-p)$ and has Student t-distribution with $n-p$ degrees of freedom.

In the Bayesian calculation, integrating $\beta$ first gives $y^{\ast }\mid s,X,Y\sim N(x^{\ast }\hat{\beta },s(1+h^{\ast }))$. Integrating $\beta$ out of the joint posterior gives $s\mid X,Y\sim \mathrm{InvGamma}((n-p)/2,R/2)$. For $\nu =n-p$, integration of the predictive normal against this inverse-gamma distribution has density proportional toThe substitution $t=[R+(y^{\ast }-x^{\ast }\hat{\beta }{)}^2/(1+h^{\ast })]/(2s)$ reduces the integral to a Gamma function. Normalizing identifies the Student t-distribution, givingwhere the second parameter is a scale, not its variance. These Bayesian intervals coincide with the usual exact Gaussian-regression prediction intervals for this prior, although their probability interpretations differ. Posterior propriety requires $R>0$ and $n>p$; the former holds almost surely under the nondegenerate Gaussian model. Prediction of the noiseless conditional mean omits the added one in $1+h^{\ast }$.

Represent the subset model by a set $M$ of $k$ column indices and let $X_M$ contain those columns. Its ordinary least squares estimator sets the omitted coefficients to zero and hasFor $k=0$, use $P_M=0$. Full column rank of $X$ implies full column rank for each $X_M$. The matrix $P_M$ is an orthogonal projection matrix of rank $k$.

Put $\mu =X\theta$ and $b_M=(I-P_M)\mu$. Projection orthogonality gives the bias-variance decomposition of mean squared errorwhile the expected residual sum of squares isThese equations distinguish the mean-vector prediction risk in this problem from the additional noise in predicting a new response vector.

First take $p<n$. Let $P_X$ project onto the full column space of $X$. Since the full model contains $\mu$, the residual estimate of Gaussian noise varianceis unbiased: its numerator has expectation $(n-p){\sigma }^2$. Consequently an unbiased Gaussian projection risk estimate isIndeed its expectation is $\Vert b_M{\Vert }^2+(n-k){\sigma }^2+(2k-n){\sigma }^2=R(M)$ for every $\theta$, even when the subset model omits true effects. Independence of the two terms is not needed for this expectation calculation. The full-model variance estimate is important: the subset residual variance generally includes omitted-variable bias.

For a finite candidate collection, choose a model minimizing $\hat{R}(M)$, breaking ties in favour of a smaller model. The term $-n{\hat{\sigma }}^2$ is common to all models, so this amounts to minimizingthe Mallows Cp form. The fit improvement competes with an increasing dimension penalty. Unbiasedness holds for each fixed model; the estimate at the data-selected model need not remain unbiased, because selection favours downward fluctuations. The method is a heuristic model selection rule, rather than an assertion that it finds the true model with certainty.

The printed $p\le n$ includes a genuine qualification. If $p=n$, there are no full-model residual degrees of freedom. Except in the balanced case $2k=n$, no integrable data-only unbiased estimator can satisfy the requested identity for all means and unknown variances. Here is a proof of the unknown-variance risk estimation in a saturated Gaussian model obstruction. Since $X$ is invertible, $\mu$ ranges over all ${\mathbb{R}}^n$. Suppose $T(Y)$ had the required expectation at every $\mu$ and variance $s>0$. For $v>0$, let $U\sim N_n(\mu ,vI)$ and let $Y\mid U\sim N_n(U,sI)$. Marginally $Y\sim N_n(\mu ,(s+v)I)$. Applying the assumed identity conditionally giveswhereas applying it to the marginal distribution gives $\Vert b_M{\Vert }^2+k(s+v)$. Their difference is $(n-2k)v$, which must vanish. Integrability under the marginal Gaussian justifies conditioning. If $2k=n$, the obstruction disappears and the residual sum of squares alone has expectation $\Vert b_M{\Vert }^2+k{\sigma }^2$. ThusThe general construction therefore requires $p<n$, or an independently available unbiased variance estimate.

Write $\Omega ={\Sigma }^{-1}$ for a positive-definite matrix. Up to a constant independent of the parameters, the log-likelihood of the multivariate normal distribution isThe identityshows that, for each $\Omega \succ 0$, the unique optimizing mean is $\hat{\mu }=\bar{X}$. Using the matrix trace to rewrite the first quadratic sum, the profile likelihood isTherefore maximum likelihood estimation of the precision matrix, whenever the maximum exists, is exactlyThis is the profile likelihood for a Gaussian precision matrix. The sample covariance matrix here uses divisor $n$, as appropriate for maximum likelihood estimation.

There is an important rank qualification in the printed assumptions. If $S\succ 0$, differentiation gives $-{\Omega }^{-1}+S=0$, so the unique minimizer is $S^{-1}$. Uniqueness follows because the negative log-determinant is a strictly convex function on the positive-definite matrices. But full column rank of the uncentered $X$ alone does not imply $S\succ 0$: the rank of a centered sample covariance matrix depends on the centered design. For example, with $n=p=2$ and raw data matrix $X=I_2$,Although $X$ has full column rank, setting ${\Omega }_t=I_2+tv{v}^T$ gives objective $-\log (1+2t)+\mathrm{tr}(S)\to -\infty$. Thus an unpenalized maximizer need not exist under the literal raw-rank assumption. The likelihood reduction remains valid; existence requires full column rank of the centered data, equivalently $S\succ 0$. For the nonsingular Gaussian model this holds almost surely when $n>p$.

Use the entrywise-penalty convention for the Graphical Lasso:The sum is the entrywise matrix L1 norm. Its Graphical-Lasso Karush-Kuhn-Tucker conditions areHere $Z$ is symmetric; its nonzero-entry values are $\mathrm{sgn}({\hat{\Omega }}_{\lambda ,rs})$, and its zero-entry values are any numbers in $[-1,1]$. These are the subgradient optimality condition for this convex optimization problem. Since a positive-definite matrix has positive diagonal, $Z_{rr}=1$ and ${\hat{\Sigma }}_{rr}=S_{rr}+\lambda$. Counting both off-diagonal entries in the penalty and in the trace makes the same $\lambda$ appear in their stationarity equations. The common variant penalizing only off-diagonal entries instead sets $Z_{rr}=0$; the off-diagonal equations and the column argument below are unchanged.

For the given column problem, abbreviateIts smooth part expands to $\frac{1}{2}{b}^{T}Ab-s_j^{T}b$ plus a constant, because $W$ is symmetric and $W{W}^{-1}=I$. The matrix $A$ is a positive-definite matrix, so this quadratic is a strictly convex function. Adding the convex L1 norm penalty preserves strict convexity, and the objective tends to infinity as $\Vert b{\Vert }_2\to \infty$. The minimizer $b^{\ast }$ exists and is unique. Its Karush-Kuhn-Tucker conditions are

We identify that minimizer directly from the precision matrix. Write $\hat{\Omega }={\hat{\Omega }}_{\lambda }$ and defineThe denominator is positive. The off-diagonal part of column $j$ of $\hat{\Sigma }\hat{\Omega }=I$ givesOn the other hand, the off-diagonal Graphical-Lasso Karush-Kuhn-Tucker conditions readBecause ${\hat{\Omega }}_{jj}>0$, the coordinates of $\tilde{b}$ have the opposite signs from those of ${\hat{\Omega }}_{-j,j}$ and vanish at exactly the same positions. The subgradient of the absolute value therefore satisfiesIt follows thatThese are exactly the Lasso column problem's Karush-Kuhn-Tucker conditions. Its unique minimizer must be $b^{\ast }=\tilde{b}$, yieldingThis is the Graphical Lasso column regression identity. The minus sign is essential: it converts the precision-entry subgradient into the regression-coefficient subgradient. The argument uses the inverse identity directly, so it does not require proving the supplied block inverse formula.

The Gaussian likelihood has log-likelihood, apart from no omitted parameter-dependent terms,For fixed ${\sigma }^2$, maximizing it is ordinary least squares. Differentiating with respect to $\beta$ gives the normal equation $X^{T}X\hat{\beta }=X^{T}Y$. Full column rank makes the quadratic strictly convex, soAt this value, differentiating with respect to $v={\sigma }^2$ gives $-n/(2v)+\mathrm{RSS}/(2v^2)=0$, soFor positive RSS this is the global likelihood maximum in $v>0$. RSS is positive almost surely under the model since $p<n$; an exactly zero observed RSS instead gives a boundary supremum as $v\downarrow 0$.

As a linear image of a multivariate normal vector, the coefficient estimate satisfiesIndeed, $\hat{\beta }-\beta =(X^{T}X{)}^{-1}{X}^T\epsilon$, and direct matrix multiplication gives its covariance matrix.

Assume the known covariance matrix $\Sigma$ is positive definite. The Gaussian likelihood, up to constants, isIts gradient is $X^T{\Sigma }^{-1}(Y-X\beta )$. The negative Hessian matrix $X^T{\Sigma }^{-1}X$ is positive definite because $X$ has full column rank. Thus the unique maximum-likelihood estimator is the generalized least squares estimatorIt is unbiased, and multiplication of its linear coefficient matrix by $\Sigma$ givesIn fact ${\hat{\beta }}_{\mathrm{GLS}}\sim N_p(\beta ,(X^T{\Sigma }^{-1}X{)}^{-1})$. Equivalently, a whitening transformation premultiplies $Y$ and $X$ by ${\Sigma }^{-1/2}$, after which ordinary least squares applies. There is no extra ${\sigma }^2$ factor when $\Sigma$ is the complete known covariance; such a factor appears if only a shape matrix $\Omega$ is known and $\Sigma ={\sigma }^2\Omega$.

Because $X$ has full column rank, $X^{T}X$ is invertible. The ordinary least squares estimator isIt satisfies the normal equationsso the residual is orthogonal to the column space of $X$. For any $\beta$,The two terms are orthogonal, and the Pythagorean theorem in an inner-product space givesThus $\hat{\beta }$ minimizes the least-squares objective.

The Reverse-order law for the Moore--Penrose inverse is false in general. TakeThenA sufficient condition isso that $A$ has full column rank and $B$ has full row rank. Indeed $A^{†}A=I_n$ and $B{B}^{†}=I_n$; these identities make $B^{†}{A}^{†}$ satisfy all four Penrose equations for $AB$.

Put $B=A_1^T{A}_1$. It is a symmetric matrix and a positive semidefinite matrix, while $A_2^T{A}_2=I_n-B$ is also a positive semidefinite matrix. By the spectral theorem, choose an orthogonal matrix $V=[v_1,\dots ,v_n]$ such thatThe bounds follow directly from $z^{T}Bz=\Vert A_{1}z{\Vert }_2^2\in [0,\Vert z{\Vert }_2^2]$. Define the diagonal matricesThe columns of $A_{1}V$ are mutually orthogonal, since $(A_1{v}_i{)}^T(A_1{v}_j)={\lambda }_j{\delta }_{ij}$. For each ${\lambda }_j>0$, set $u_{1j}=A_1{v}_j/\sqrt{{\lambda }_j}$. These columns are orthonormal. At a zero ${\lambda }_j$, one has $A_1{v}_j=0$; choose $u_{1j}$ by completing the already prescribed columns to an orthonormal set of $n$ columns in ${\mathbb{R}}^k$. Such a completion exists because $k\ge n$. This gives $A_{1}V=U_1{\Sigma }_1$, including the zero columns.

Likewise, the Gram matrix of $A_{2}V$ is $\mathrm{diag}(1-{\lambda }_j)$. Normalize its nonzero columns and complete at its zero columns in ${\mathbb{R}}^{m-k}$, using $m-k\ge n$. The resulting $U_2$ has orthonormal columns and $A_{2}V=U_2{\Sigma }_2$. Combining the identities givesThis is a form of the cosine-sine decomposition. Completing the zero columns is essential: neither block was assumed to have full column rank.

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 $\ell =r/2$; the requested expression requires the positive even integer $r\ge 2$. Split the thin singular value decomposition after $\ell$ columns:Here $\Vert D_b{\Vert }_2={\sigma }_{\ell +1}=\Vert A-A_{\ell }{\Vert }_2$. Each column of a Gaussian random matrix is an orthogonally invariant random vector: its probability density function is proportional to $\exp (-\Vert z{\Vert }_2^2/2)$, and an orthogonal matrix preserves both $\Vert z{\Vert }_2$ and volume. Thus $V^{T}X$, where $V=[V_a,V_b]$, again has independent and identically distributed standard normal entries. In particular both displayed blocks have the Gaussian distributions needed below.

First prove a deterministic error bound for a randomized range finder. Put $P=Q{Q}^T$ and suppose ${\Omega }_a$ has full row rank. Its Moore-Penrose pseudoinverse is ${\Omega }_a^{†}={\Omega }_a^T({\Omega }_a{\Omega }_a^T{)}^{-1}$, so ${\Omega }_a{\Omega }_a^{†}=I_{\ell }$. The QR decomposition implies $(I_m-P)AX=0$, henceMultiplication by ${\Omega }_a^{†}$ expresses the missed leading columns in terms of the trailing columns. Substitution into $(I_m-P)A$ gives the exact identityFor any matrix $F$, the spectral norm of $[-FI]$ is $\sqrt{1+\Vert F{\Vert }_2^2}$, because its product with its transpose is $F{F}^T+I$. Using submultiplicativity of the operator norm, the orthonormality of $U_b$, and the contraction property of the orthogonal projection, we obtainThis estimate is deterministic and also covers rank-deficient $A$; if ${\sigma }_{\ell +1}=0$, its right-hand side vanishes.

Now use the paper's permitted singular value estimates. Apply the lower estimate to the tall matrix ${\Omega }_a^T$ of size $r\times \ell$, rather than to its wide transpose. It givesThe upper estimate for ${\Omega }_b$, transposing if necessary, givesThus, with $K=2/(1-1/\sqrt{2})$,Since $n/r>1$, the deterministic estimate yieldsThis proves the requested conclusion under the explicitly authorized estimates.

The probabilistic qualification is necessary. A Gaussian random matrix does not always have all its singular values between the two endpoints printed in the hint. Already a $1\times 1$ example would require $|Z|\le 2$ for every standard normal random variable $Z$, which fails with positive probability. The proof above holds on the event where the two block estimates hold. In a probabilistic formulation one supplies estimates for that event, usually allowing a positive margin in both endpoints; no failure probability is specified by the paper.

Nor can the requested inequality with one universal $C$ hold almost surely for every $A$. For example, take $n=m=3$, $r=2$, $A=\mathrm{diag}(L,1,1)$ with $L>1$, and a sampling matrixAt $X_0$, the sampled column space misses the first coordinate, so $\Vert A-\hat{A}{\Vert }_2=L$, whereas $\Vert A-A_1{\Vert }_2=1$. Choose $L>C\sqrt{3/2}$. Because $A{X}_0$ has full column rank, its orthogonal projection depends continuously on $X$ near $X_0$ through $AX(X^T{A}^{T}AX{)}^{-1}{X}^T{A}^T$. The strict violation persists in an open neighborhood of $X_0$. The joint Gaussian probability density function is positive there, so that neighborhood has positive probability. This identifies the missing qualification without weakening the conditional calculation.

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}|$.