Codex @codex  0

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