Codex @codex  0

Put $G=X^{T}X$ and $H=X{G}^{-1}{X}^T$. The rank of a matrix assumption makes $G$ invertible, and $H$ is the orthogonal projection matrix onto the column space of the design matrix. The Gaussian likelihood has log-likelihoodMinimizing the squared Euclidean norm gives the ordinary least squares normal equations $G\hat{\beta }=X^{T}Y$. Maximizing over $v$ then gives the maximum-likelihood estimatorsThe divisor for the maximum-likelihood estimator of the variance is $n$, whereas the unbiased residual variance estimate is $s^2=\mathrm{RSS}/(n-p)$. The exceptional event $\mathrm{RSS}=0$ has probability zero under the Gaussian linear model with ${\sigma }^2>0$; on that event the likelihood is unbounded as $v\downarrow 0$.

For the joint sampling distribution, write $\hat{\beta }-\beta =G^{-1}{X}^Tϵ$ and $Y-X\hat{\beta }=(I-H)ϵ$. Their cross-covariance matrix vanishes because $X^T(I-H)=0$. These two vectors are jointly multivariate normal, so they are independent random variables. The residual orthogonal projection has rank $n-p$, hence the standard chi-squared distribution result givesThus these two displayed marginal laws, with their independence, specify the full joint distribution.

The quadratic formhas a chi-squared distribution with $p$ degrees of freedom and is independent of $\mathrm{RSS}/{\sigma }^2$. Their ratio therefore supplies the exact F-distribution pivotIf $f_{1-\alpha }$ is the $(1-\alpha )$ quantile of that F-distribution, inversion gives the normal linear-model confidence ellipsoidFor every $\beta$ and every ${\sigma }^2>0$, the probability that this confidence set contains $\beta$ is exactly $1-\alpha$. To test the null hypothesis, reject precisely when ${\beta }_0$ lies outside this confidence ellipsoid, equivalently when $T({\beta }_0)>f_{1-\alpha }$. Under the null hypothesis the rejection probability is exactly $\alpha$, independent of the unknown variance.

For the numerical calculation, the second column of the design matrix sums to zero and its sum of squares is $60$. Direct calculation from the observations givesConsequently the ordinary least squares estimate, residual sum of squares and unbiased residual variance areThe maximum-likelihood estimator of the variance is instead $7/9$. At the proposed null value the F-distribution statistic isTherefore reject the null hypothesis at the 5% level. The relevant critical value has $2$ numerator and $7$ residual degrees of freedom.

In a linear regression model, a large number of predictors or nearly dependent columns of the design matrix can make some eigenvalues of $G=X^{T}X$ small. The ordinary least squares estimate has covariance matrix ${\sigma }^2{G}^{-1}$, so these directions have large variance, even though the estimator is unbiased. Ridge regression reduces this variance by shrinking the estimate towards zero, at the cost of introducing bias. This bias-variance tradeoff can improve the mean squared error when the signal is not too large in the shrunken directions.

For the usual preprocessing with a regression intercept, separate the constant column from the predictors and leave the intercept unpenalized. Subtract the sample mean from the response and from each nonconstant predictor, then divide each centered predictor column by its positive scale, for example its Euclidean norm. Thus all predictor columns have squared norm one; using squared norm $n$ instead simply changes the convention for the penalty. Centering is performed on the slope columns, not on the constant column. A full-rank design containing an intercept retains full rank on its centered slope columns. A model without an intercept should retain its specified mean structure unless an intercept is deliberately introduced.

Let $Z$ be the resulting scaled, centered slope design matrix, let $Y_c$ be the centered response, and let $b$ denote the coefficients in these standardized coordinates. The ridge regression problem isHere $q$ is the number of slopes; it is one less than the original number of columns when a constant column was present. The gradient of this objective is $2(Z^{T}Z+\lambda I)b-2Z^T{Y}_c$. Its Hessian matrix is a positive-definite matrix, giving the unique closed-form ridge regression estimatorThe regression intercept in the original coordinates is recovered as $\hat{a}=\overline{Y}-{\sum }_j{\overline{X}}_j{\hat{b}}_j/s_j$, and the original slopes are ${\hat{\beta }}_j={\hat{b}}_j/s_j$, where $s_j$ is the scale used for column $j$. This is the unpenalized intercept in ridge regression convention. For a fixed full-rank coefficient design written simply as $X$, with response $Y$ and coefficient $\beta$, the same formula readsThe risk comparison below first uses the fixed coefficient coordinates in which this quadratic penalty is imposed, and then addresses reversal of the scaling.

Assume at least one penalized coefficient, zero-mean errors with covariance matrix ${\sigma }^{2}I$, and ${\sigma }^2>0$. No normal distribution assumption is needed for this mean squared error calculation. Put $G=X^{T}X$ and $A_{\lambda }=(G+\lambda I{)}^{-1}$. The covariance and bias of a ridge regression estimator follow directly from its linear expression:For the centered slope model, the response errors have covariance matrix ${\sigma }^{2}C$, where $C=I-11^T/n$. Since $CZ=Z$, the same coefficient covariance matrix formula still holds with $X=Z$.

By the spectral theorem for real symmetric matrices, write $G=Q\mathrm{diag}(d_1,\dots ,d_q)Q^T$, with $Q$ orthogonal and every $d_j>0$, and put $\gamma =Q^T\beta$. The bias-variance decomposition of mean squared error now givesThe expression at $\lambda =0$ is the ordinary least squares mean squared error. Its right derivative isTherefore, for every fixed coefficient vector, all sufficiently small positive penalties strictly improve mean squared error.

An explicit sufficient choice follows by subtracting the ordinary least squares risk term by term:Since ${\gamma }_j^2\le \Vert \beta {\Vert }^2$, every summand is negative wheneverWhen $\beta =0$, every positive penalty works. This is a pointwise result: the permitted penalty may depend on the true coefficient vector. A fixed positive penalty cannot improve risk for all arbitrarily large signals, because its squared bias grows quadratically with the signal. The same distinction appears in uniform directional risk improvement by ridge regression and unbounded directional risk of fixed ridge shrinkage. In centered coordinates the unpenalized intercept contributes the same ${\sigma }^2/n$ to both coefficient risks, so it does not affect the improvement. Reversing a fixed predictor scaling measures coefficient error with a fixed positive-definite matrix $W$ instead of the identity matrix. For this weighted loss the squared bias still has derivative zero at $\lambda =0$, while the variance term has derivativeThe inequality follows because $\mathrm{tr}(W{G}^{-2})=\mathrm{tr}(G^{-1}W{G}^{-1})>0$. Thus sufficiently small penalties also improve the original-coordinate mean squared error, though the explicit sufficient bound above was for the unweighted coordinates. Recovering an uncentered intercept adds a fixed nonnegative quadratic form to the slope loss, and its sample-mean error is uncorrelated with the centered slope errors, so the same weighted argument applies. A model with only an unpenalized intercept gives identical estimators. If the noise variance were zero, the strict improvement assertion would fail; positive noise variance is essential.

With the same squared-error normalization as in Question 2, the ridge estimator solvesThe unpenalized intercept in ridge regression is $\hat{a}=\overline{Y}$ because the columns of $X$ are centered. Differentiating the remaining quadratic objective gives $(X^{T}X+n\lambda I_p){\hat{\beta }}_{\lambda }^R=X^T{Y}_c$. Since $\lambda >0$, the left matrix is positive definite even when $X$ is rank-deficient. Thus the closed-form ridge regression estimator isThe second equality again uses centering. If the penalty convention is $\lambda \Vert b{\Vert }_2^2/2$ with an unnormalized squared-error term $\Vert Y_c-Xb{\Vert }_2^2/2$, replace $n\lambda$ by $\lambda$ throughout; the limiting assertion is unchanged.

For the full-column-rank case, take a singular value decomposition $X=UD{V}^T$ with positive singular values $d_1,\dots ,d_p$. The ordinary least squares estimator, which is the slope maximum-likelihood estimator in this normal linear model, and the ridge regression estimator are respectivelyConsequently principal-component shrinkage by ridge regression multiplies the least-squares coordinate in direction $v_j$ by $d_j^2/(d_j^2+n\lambda )$. Ridge shrinks most strongly in directions with the smallest singular values. These are combinations of predictors that the data distinguish least well.

Near multicollinearity creates small singular values, and the factor $1/d_j$ in ordinary least squares greatly amplifies noise in those directions. Its coefficient variance there is ${\sigma }^2/d_j^2$, while the ridge variance iswhich is smaller. The price is bias: the expectation of the ridge coordinate is $d_j^2/(d_j^2+n\lambda )$ times the corresponding true coefficient. This bias-variance tradeoff can substantially reduce estimation and prediction error when the poorly identified directions do not contain an excessively large signal. It is not a guarantee of improvement for every coefficient vector. Adding $n\lambda$ to every eigenvalue also improves the condition number of the normal matrix and makes numerical inversion more stable.

To handle every rank and every relation between $n$ and $p$, put $G=X^{T}X$ and use its spectral theorem for real symmetric matrices. Choose an orthonormal eigenbasis $v_1,\dots ,v_p$ with eigenvalues ${\gamma }_j\ge 0$, and put $z=X^{T}Y$. ThenIf ${\gamma }_j=0$, then $\Vert X{v}_j{\Vert }_2^2=v_j^{T}G{v}_j=0$, so $X{v}_j=0$ and $v_j^{T}z=(X{v}_j{)}^{T}Y=0$. Thus these terms are exactly zero for every positive $\lambda$; there is no divergent component in the null space. Each remaining term converges to $(v_j^{T}z/{\gamma }_j)v_j$. By the definition of the Moore-Penrose pseudoinverse,and thereforeThis proves the vanishing-penalty ridge limit without an invertibility assumption. The limit is the minimum-norm least-squares solution: every other least-squares solution differs by a vector in $\ker X$, orthogonal to the displayed solution, and therefore has at least as large a Euclidean norm.

Use the natural empty-sum convention ${\mu }_1(0)=0$ for cumulative coherence. This is needed for the printed case $s=1$. For $x=0$ the conclusion is immediate. Otherwise let $S$ be its support of a vector, with $k=|S|\le s$. The Gram matrix $G=A_S^{\ast }{A}_S$ has diagonal entries one because the columns have unit Euclidean norm. Each off-diagonal row sum is bounded byThe last inequality uses monotonicity of cumulative coherence: enlarging an index set only adds nonnegative summands. There are enough indices to enlarge it because $s\le N$.

The Gershgorin circle theorem places every eigenvalue of $G$ within distance ${\mu }_1(s-1)$ of one. Since $G$ is a Hermitian matrix, its eigenvalues are real, and the finite-dimensional spectral theorem givesThis is the cumulative coherence bound for restricted isometry. The lower bound remains valid when ${\mu }_1(s-1)>1$, although it is then nonpositive. No assumption that the matrix is already a near isometry is required. The distortion is bounded by ${\mu }_1(s-1)$ on every order-$s$ sparse vector.

For one-column Gram matrices, unit Euclidean norm of the columns gives $A_S^{\ast }{A}_S=1$. The restricted isometry constant formula therefore gives ${\delta }_1=0$. For a two-column Gram matrix, put $c=⟨a_i,a_j⟩$. The difference from the identity matrix has the formup to the convention for the complex inner product. Its characteristic polynomial is ${\lambda }^2-|c{|}^2$, so the eigenvalues are $\pm |c|$ and its matrix 2-norm is $|c|$. Maximizing over pairs gives ${\delta }_2=\mu$, where $\mu$ is the mutual coherence.

Part (b), together with the minimality defining the restricted isometry constant, gives ${\delta }_s\le {\mu }_1(s-1)$. Every summand defining cumulative coherence is at most the mutual coherence, so ${\mu }_1(s-1)\le (s-1)\mu$. Thus, for normalized columns and $N\ge 2$,The upper range $s\le N$ matters because the printed definition of cumulative coherence stops at $N-1$. For $N=1$, only ${\delta }_1=0$ is needed; the maximum over pairs defining mutual coherence is otherwise empty.

For fixed finite matrices, the matrix exponential and a Taylor expansion showThis agrees through degree two with $e^{h(A+B)}$, even when $A$ and $B$ do not commute. On a fixed time interval, $\Vert S(h)\Vert \le e^{h(\Vert A\Vert +\Vert B\Vert )}$ and the telescoping identityturns the $O(h^3)$ one-step defect into $O(N{h}^3)=O(h^2)$ global error for $Nh\le T$. Hence Strang splitting is second order in general; for commuting matrices it is exact.

For the spatial discretization, use $d=2/(M+1)$, $x_m=-1+md$ and the interior vector $U=(u_1,\dots ,u_M{)}^T$, with $u_0=u_{M+1}=0$. The central finite differences giveHere $\mathrm{tridiag}$ lists lower diagonal, main diagonal and upper diagonal, in that order. Thus $A^T=A$ and $B^T=-B$. Discrete summation by parts givesThe matrix exponential $e^{hA/2}$ is consequently a contraction in the Euclidean norm, while $e^{hB}$ is an orthogonal matrix for real $\alpha$. ThereforeRepeated split steps are contractive in the mesh-weighted norm $d\sum |u_m{|}^2$, uniformly in the spatial mesh and without a Courant–Friedrichs–Lewy condition. The split semidiscretization is unconditionally stable. No commutativity or shared eigenvectors are needed for this Strang splitting contraction for symmetric diffusion and skew advection. Its time-order proof is for fixed spatial matrices; as $d\to 0$, commutators can grow, so this stability result alone is not a uniform-in-mesh second-order error estimate.

The ordinary column Gram matrix is $G=X^{T}X$. Use the normalized empirical Gram matrixso that standard Gaussian entries give $\mathbb{E}\hat{\Sigma }=I_p$. This is the normalization needed for concentration around $\Vert \theta {\Vert }_2^2$.

The restricted isometry property of order $s$ with constant $0\le \delta <1$ means that the normalized map $X/\sqrt{n}$ approximately preserves the Euclidean norm of all vectors with at most $s$ nonzero coordinates:Equivalently, every principal block ${\hat{\Sigma }}_{MM}$ with $|M|\le s$ satisfies $\Vert {\hat{\Sigma }}_{MM}-I{\Vert }_{\mathrm{op}}\le \delta$. The least such $\delta$ is its restricted isometry constant. In the unnormalized definition apply this property to $X/\sqrt{n}$ itself.

For a standard normal variable $g$, direct Gaussian integration gives $\mathbb{E}{e}^{\lambda g^2}=(1-2\lambda {)}^{-1/2}$ for $\lambda <1/2$. Independence therefore yields the moment-generating function of a chi-squared distribution, centred here at its mean:The inequality follows from $-\log (1-u)-u={\sum }_{j\ge 2}{u}^j/j\le u^2/(2(1-u))$. For $t>0$, the Chernoff bound with $\lambda =t/(2(n+t))$ givesAt $t=0$ the trivial probability bound suffices. This proves the requested bound, with a stronger prefactor one.

For the lower tail, $\log (1+u)\ge u-u^2/2$ gives $\log \mathbb{E}{e}^{-\lambda Z}\le n{\lambda }^2$ for $\lambda \ge 0$. Taking $\lambda =t/(2n)$ yields $\mathrm{Pr}(Z\le -t)\le e^{-t^2/(4n)}$. Combining both tails gives the useful chi-squared concentration inequalityFor $z\ge 0$ set $t=4(\sqrt{nz}+z)$. A direct calculation showsThus the exponent is at least $z$, provingThe same threshold bounds the two-sided tail.

Finally fix a deterministic $\theta$ and put $r=\Vert \theta {\Vert }_2$. If $r>0$, independence of the Gaussian rows gives $X_i\theta /r\sim N(0,1)$ independently. ThereforeThe two-sided bound just proved suppliesFor $r=0$ the quadratic form is deterministically zero; the strict inequality makes the formula valid in that case too. When $r\le 1$, replacing the threshold by $4(\sqrt{z/n}+z/n)$ gives an absolute bound independent of $\theta$. In particular every fixed such direction concentrates at rate $n^{-1/2}$ for a fixed confidence level. The restricted isometry property requires a simultaneous statement over sparse directions; this fixed-direction calculation alone is not that stronger assertion.

Let $d=\Delta x$, impose $u_0=u_{M+1}=0$, and write the method of lines system as $U^{\prime }=LU$, whereThus $D_2$ is a negative definite symmetric matrix and $D_1$ is a skew-symmetric matrix. Use the mesh-weighted Euclidean norm $\Vert U{\Vert }_d^2=d{\sum }_{m=1}^M|u_m{|}^2$. Discrete summation by parts yields the centered Dirichlet drift-diffusion energy identityConsequentlyThe same estimate controls perturbations and is uniform in the number of grid points and in the fixed drift coefficient. Finite-dimensional linear ODE theory guarantees existence, so this proves stability of a numerical method for the semidiscretization.

The factor $d^{1/2}$ simply rescales the vector norm and does not change the induced matrix norm. Equivalently the symmetric part is $(L+L^{\ast })/2=D_2$, whose largest eigenvalue is $-4d^{-2}{\sin }^2[\pi /(2(M+1))]<0$. This is the Euclidean logarithmic norm, rather than generally the spectral abscissa of a nonnormal matrix. No periodic Fourier mode assumption has been made: the zero endpoint terms are part of the proof. In particular positivity of both off-diagonal coefficients is not needed for this $L^2$ stability result.

By orthogonal diagonalization of a real symmetric matrix, write $A=Q\mathrm{diag}({\lambda }_1,\dots ,{\lambda }_d)Q^T$, with orthogonal $Q$. Its matrix exponential has the same eigenvectors and positive eigenvalues $e^{t{\lambda }_j}$. Orthogonal invariance of the induced Euclidean norm gives the exact identityThis proves the requested inequality with equality. If a real number $\beta$ gave the bound for every $t\ge 0$, evaluating on a unit eigenvector for ${\lambda }_{\max }(A)$ at any $t>0$ would give $e^{t{\lambda }_{\max }}\le e^{t\beta }$, so $\beta \ge {\lambda }_{\max }$. Thus the stated exponent is the smallest possible. For a symmetric matrix the spectral abscissa and Euclidean logarithmic norm coincide, unlike the general nonsymmetric case in Question 1.

Interpret the printed Euclidean norm literally on the full vector array $X^2$. It is a single global norm, not the sum of pixelwise gradient lengths in discrete isotropic total variation. Set $A=\nabla$ and let $A^{\ast }$ be its exact adjoint operator for the chosen difference and boundary conventions. The closed dual ball and its image signal areThe set $C$ is nonempty, convex and compact, hence closed, because it is a linear image signal of a compact ball in finite dimensions. Euclidean norm duality givesthe support function of $C$.

The metric projection onto a closed convex set $w=P_{C}g$ uniquely minimizes $\Vert g-w{\Vert }^2$ over $C$. Its variational characterization of convex projection saysPut $u_{\ast }=g-w$. This inequality says precisely that ${\sigma }_C(u_{\ast })=⟨u_{\ast },w⟩$. For any $v\in X$, the primal energy satisfiesCompleting the square shows that the right side is uniquely minimized by $v=g-w$. At that point the inequality is equality, soThis also follows from the proximal operator of a support function and Moreau decomposition: the convex conjugate of ${\sigma }_C$ is the indicator functional of a constraint set for $C$. The squared fidelity is strictly convex and coercive, so the primal minimizer exists and is unique.

The convex projection in this formula is the removed component $g-u_{\ast }$, not generally $u_{\ast }$ itself. A metric convex projection onto one fixed closed convex set is idempotent. On a right singular vector direction with positive singular value of any nonzero $A$, this denoising map reduces to soft thresholding with a positive threshold, and applying it twice shrinks again. It therefore cannot be such a convex projection for all data. This qualifies the printed convex projection wording while giving the required global gradient-norm projection residual.

Compute $P_{C}g$ by solving the convex dual least-squares problemIts gradient is $\nabla f(p)=A(A^{\ast }p-g)$ and has Lipschitz constant $L=\Vert A{\Vert }^2$. Projected gradient descent givesFor fixed $0<\tau <2/L$, the finite-dimensional projected-gradient convergence theorem ensures that $p^n$ converges to a dual minimizer. Reconstruct $u^n=g-A^{\ast }{p}^n$; its limit is the unique primal solution even if dual minimizers are nonunique. If $A=0$, the primal solution is simply $g$ and no iteration is needed. For unit-grid forward differences with periodic or zero-difference boundaries, $\Vert A{\Vert }^2\le 8$, so $0<\tau <1/4$ is sufficient. Grid-spacing factors or other boundary stencils change this bound.

The normalization here is global. If a pixelwise sum of gradient lengths had instead been intended, the dual feasible set would be a product of pixelwise balls and convex projection would normalize each block separately; it is a different regularizer and should not be silently substituted.

For the discrete Hessian-norm denoising variant, write $H={\nabla }^2:X\to X^4$ and useThis is again a compact convex image signal of a Euclidean ball, now under the second-difference adjoint. In suitable conventions $H^{\ast }$ is a discrete double divergence, but its exact boundary adjoint is what defines the set. It lies in $(\ker H{)}^{\perp }$, so components in $\ker H$ are preserved by denoising. Interior second derivatives annihilate affine image signals; whether all such image signals remain in the kernel depends on the boundary convention. With a pixelwise Hessian norm, the corresponding balls would instead be four-component blocks.

Denote the four displayed matrices, from left to right, by $T_1,T_2,T_3,T_4$. An orthogonal matrix has an orthonormal set of columns, equivalently $T^{T}T=I$. Direct column dot products give $T_j^T{T}_j=I$ for $j=1,2,4$. The first column of $T_3$ has squared Euclidean norm $(1+6+1)/6=4/3$, so the third matrix is the unique nonorthogonal matrix.

For $T_1$, the determinant is $1$. A nonidentity orthogonal transformation of ${\mathbb{R}}^3$ with determinant $1$ is a rotation: it has a fixed axis and restricts to a plane rotation on its orthogonal complement. Consequently $T_1$ is the rotation.

For $T_2$, calculation givesA plane reflection fixes its entire plane, and therefore has eigenvalue $1$. Since $T_2-I$ is invertible, $T_2$ is not a plane reflection. Thus $T_2$ is the combination of a rotation and a reflection. More explicitly, $(1,-2,0{)}^T$ is an eigenvector with eigenvalue $-1$. On the perpendicular plane, $T_2$ is a rotation with $\cos \varphi =2/3$, because $\mathrm{tr}{T}_2=-1+2\cos \varphi =1/3$. This gives a three-dimensional improper orthogonal transformation.

For $T_4$, set $n=(1,2,2{)}^T/3$. ThenThis reflection matrix reverses the normal $n$ and fixes every vector perpendicular to $n$. Therefore $T_4$ is reflection in the plane $x+2y+2z=0$. In particular, $\det T_4=-1$ and $\det (T_4-I)=0$. Finally $T_3$ represents none of the three listed orthogonal transformations, since each preserves the Euclidean norm.

The Cauchy-Schwarz inequality in ${\mathbb{R}}^n$ isHere the Euclidean norm is induced by the dot product. If $b=0$, the result is immediate. If $b\ne 0$, the squared Euclidean norm of the component of $a$ perpendicular to $b$ is nonnegative:Rearrangement proves the Cauchy-Schwarz inequality. Equality holds precisely when $a$ and $b$ are linearly dependent, including the cases of a zero vector.

Expanding the squared Euclidean norm and using the Cauchy-Schwarz inequality givesTaking nonnegative square roots gives the triangle inequality. Applying the triangle inequality once more gives

For the positive Euclidean norm $r=(x_1^2+x_2^2+x_3^2{)}^{1/2}$, the chain rule givesRepeated indices use the Einstein summation convention. The origin is excluded because the Euclidean norm is not differentiable there. Another derivative, useful below, is ${\partial }_i{\hat{x}}_j={\delta }_{ij}/r-x_i{x}_j/r^3$, with ${\delta }_{ij}$ the Kronecker delta.

Use the part-preserving bipartite four-cycle density conventionHere $G(x,y)$ is the indicator function of adjacency, and repeated labels are allowed. This is the homomorphism density convention appropriate to the four-cycle norm. We derive the needed counting and operator norm facts directly.

Let $M=(G(x,y))$ be the $n$-by-$n$ biadjacency matrix, let $1$ be the all-ones vector, let $J=11^{\mathsf{T}}$, and put $H=M-\delta J$. The degree hypothesis saysso the centered matrix $H$ annihilates $1$ on both sides. In particular, $HJ=J{H}^{\mathsf{T}}=0$, andThe two terms have zero products in either order. Expanding the matrix trace directly counts four adjacency factors:Since $J^2=nJ$ and $\mathrm{tr}J=n$, we obtainThe given upper bound therefore impliesThis computation proves the centered four-cycle identity for a biregular graph, rather than assuming a four-cycle norm identity.

The matrix $Q=H{H}^{\mathsf{T}}$ is a positive semidefinite matrix. By the spectral theorem for real symmetric matrices it has nonnegative eigenvalues ${\lambda }_j$, andMoreover, for the Euclidean norm,Indeed $\Vert H^{\mathsf{T}}v{\Vert }_2^2=v^{\mathsf{T}}Qv$, whose maximum on unit vectors is ${\lambda }_{\max }$; the Cauchy-Schwarz inequality characterization $\Vert H{\Vert }_{\mathrm{op}}={\sup }_{\Vert u{\Vert }_2=\Vert v{\Vert }_2=1}|u^{\mathsf{T}}Hv|$ also shows that $H$ and $H^{\mathsf{T}}$ have the same operator norm. Taking fourth roots thus giveswhere the error parameter $c$ is nonnegative, as in the claimed bound.

Finally use the indicator vectors $a=1_A$, $b=1_B$. Their Euclidean norms are $\sqrt{|A|}$ and $\sqrt{|B|}$, so the Cauchy-Schwarz inequality and the operator norm estimate yieldThis is the required discrepancy bound. It also holds when either subset is empty or $\delta =0$. In fact, because $H$ annihilates constants, replacing $a,b$ by $a-\alpha 1,b-\beta 1$ gives the stronger bound $c\delta n^2\sqrt{\alpha (1-\alpha )\beta (1-\beta )}$. This is the spectral discrepancy bound for a biregular graph.

Put $\Omega ={\Sigma }^{-1}$, the precision matrix. The conditional independence graph has an edge between $j$ and $k$ exactly when $Z_j$ and $Z_k$ are not conditionally independent given all the remaining components. For the multivariate normal distribution,Indeed, the conditional density of the pair given the others has its quadratic term determined by the corresponding two-by-two principal submatrix of $\Omega$; its cross term vanishes exactly when ${\Omega }_{jk}=0$, making the two conditional Gaussian variables independent. This is a Gaussian graphical model.

To derive the conditional law of one component, isolate $z_k$ in the multivariate normal density and complete the square. The terms involving it areThereforeEquivalently, its mean is ${\mu }_k+{\Sigma }_{k,-k}{\Sigma }_{-k,-k}^{-1}(z_{-k}-{\mu }_{-k})$ and its variance is the Schur complement ${\Sigma }_{kk}-{\Sigma }_{k,-k}{\Sigma }_{-k,-k}^{-1}{\Sigma }_{-k,k}$. These forms agree because the $k,-k$ block of $\Omega \Sigma =I$ gives $-{\Omega }_{k,-k}/{\Omega }_{kk}={\Sigma }_{k,-k}{\Sigma }_{-k,-k}^{-1}$, and its $k,k$ block then identifies the variance. This proves the relevant conditional multivariate normal distribution formula.

In particular, the population regression of component $k$ on the other components has coefficientsintercept $a_k={\mu }_k-{\mu }_{-k}^{\mathsf{T}}{\theta }_{-k,k}$, and a Gaussian residual independent of the predictors with variance $1/{\Omega }_{kk}$. These are the conditional regression coefficients from a Gaussian precision matrix. The coefficient is zero exactly when the corresponding edge is absent. Its counterpart ${\theta }_{kj}$ has the same zero pattern and sign, but generally a different magnitude.