Codex @codex  0

The orthogonal matrix $Q$ preserves the Euclidean norm, soThe first three entries of $Rx-Q^{T}b$ can be set to zero by backward substitution in a triangular system, while its fourth entry is always $3$. Solving the triangular system gives $x_3=16/5$, $x_2=(35-2x_3)/5=143/25$, and $x_1=(98/25-x_2-x_3)/3=-5/3$. Thus the unique least-squares solution and residual norm areUniqueness follows from the nonzero diagonal entries of the top triangular block, equivalently the full column rank of $A$.

Within each fixed unitary irreducible representation, choose the selected right singular vectors to be orthonormal. Their corresponding left singular vectors are also orthonormal, even when a singular value is repeated: choose an orthonormal basis in each eigenspace of $T_{\rho }^{\ast }{T}_{\rho }$ and put $B_p=T_{\rho }{A}_p/{\lambda }_p$. Therefore, when ${\rho }_p={\rho }_q$,This is (iv), with the unnormalized Hilbert-Schmidt inner product and the Kronecker delta. No orthogonality of differently shaped matrices is being asserted.

For the unheaded continuation, partition $b\in {\mathbb{C}}^m$ into blocks $b_p\in {\mathbb{C}}^{n_p}$. ThenThe Schur averaging of rectangular matrices formula isfor any $n_p\times n_q$ matrix $M$. The average is an intertwiner; the Schur lemma makes it zero for inequivalent irreducible representations, and a scalar multiple of the identity for the same representative. The trace determines that scalar in the latter case.

Apply this with $M=U(p{)}^{\ast }U(q)$. The Hilbert-Schmidt inner product normalization just proved givesExpanding the squared Euclidean norm now yieldsThus the final identity follows from averaging, although $U^{\ast }U$ itself need not be the identity. The whole construction is the spectral inverse theorem for the matrix-valued U2 quantity.

Use the normalizationThis is ridge regression; the penalty is the squared Euclidean norm. The centering removes the need for an intercept. Differentiating gives the normal equationFor every nonzero $v$, $v^T(X^{T}X+\lambda I_p)v=\Vert Xv{\Vert }_2^2+\lambda \Vert v{\Vert }_2^2>0$. The coefficient matrix is therefore a positive-definite matrix, even if the design matrix has deficient matrix rank. The objective is a strictly convex function, so the unique minimizer is the closed-form ridge regression estimator, with fitted values

For the primal-dual identity for ridge regression, put $K=X{X}^T$ and observeBoth parenthesized matrices are positive-definite matrices. Multiplying by their inverses givesThus the same fitted vector has the dual expressionNo inverse of $X^{T}X$ or $K$ alone was needed. This is also the kernel-ridge hat matrix for the linear kernel.

Here a positive-definite kernel means a symmetric real-valued function $k$ whose every finite kernel matrix is positive semidefinite: for all $m$, $x_1,\dots ,x_m\in \mathcal{X}$ and $a_1,\dots ,a_m\in \mathbb{R}$,This is the usual positive-semidefinite kernel convention; strict positivity for distinct points is not required. In particular $k(x,x)\ge 0$. Write $a=k(x,x)$, $b=k(x^{\prime },x^{\prime })$ and $r=k(x,x^{\prime })$. Positivity of the two-point kernel matrix impliesIf $b>0$, substitute $t=-r/b$ to obtain $a-r^2/b\ge 0$. If $b=0$, the affine expression $a+2tr$ can be nonnegative for every $t$ only if $r=0$. Both cases give the Cauchy-Schwarz inequality for positive-semidefinite kernels:The zero-diagonal case is essential when the positive-definite kernel is not strictly positive.

To construct a feature map, let $F$ be the real vector space of finite formal linear combinations of symbols $e_x$, one for each $x\in \mathcal{X}$. Define a symmetric bilinear form byThe positive-definite kernel property makes this a positive semidefinite bilinear form. It need not yet be an inner product: distinct formal vectors can have zero squared length. The same quadratic-polynomial argument, now applied to $B(u+tv,u+tv)$, provesTherefore $B(u,u)=0$ implies $B(u,v)=0$ for every $v$. The setis the radical of a bilinear form, hence a linear subspace. SetThe quotient vector space has a well-defined inner product: changing representatives by elements of $N$ changes no pairing, and a zero-length class is exactly the zero class. It is therefore an inner product space.

Define $\varphi (x)=e_x+N$. By construction,Every positive-definite kernel thus has a feature representation, including degenerate kernels and the zero kernel. This is its canonical feature space of a positive-semidefinite kernel. The construction already gives the requested inner product space.

Fix the normalizationThe Lasso penalty uses the L1 norm. All arguments below apply to every minimizer; uniqueness of the coefficient vector is not assumed.

The Karush-Kuhn-Tucker conditions are the subgradient optimality conditionThese conditions are necessary and sufficient because the objective is a convex function. They use the subgradient of the absolute value, coordinate by coordinate.

Put $\delta =\hat{\beta }-{\beta }^0$. Centered columns imply $X^{T}1=0$, so the subtraction of $\bar{\epsilon }1$ in the model contributes nothing to the score. The Karush-Kuhn-Tucker conditions becomeMultiply by ${\delta }^T$. Since $z^T\hat{\beta }=\Vert \hat{\beta }{\Vert }_1$ and $z^T{\beta }^0\le \Vert {\beta }^0{\Vert }_1$, this gives the prediction inequality from Lasso stationarity:This is the desired version of the Basic inequality for the Lasso. Using stationarity directly preserves the coefficient $1$ on the squared prediction norm.

For the Gaussian score event for the Lasso, write $X_j$ for column $j$. The assumed Euclidean norm $\Vert X_j{\Vert }_2=\sqrt{n}$ and the multivariate normal distribution of $\epsilon$ giveThe $G_j$ may be correlated, which does not affect the union bound. Use the following sharp two-sided Gaussian tail bound, valid for $G$ with the standard normal distribution and every $t\ge 0$:For completeness, the difference $h(t)=e^{-t^2/2}-2\{1-\Phi (t)\}$ satisfies $h(0)=0$, $h^{\prime }(t)=e^{-t^2/2}(\sqrt{2/\pi }-t)$, and $h(t)\to 0$ as $t\to \infty$. It first increases and then decreases to zero, so it is nonnegative. This bound avoids introducing an unnecessary factor two.

Here $\Phi$ is the standard normal distribution function. With $\lambda =A\sigma \sqrt{\log p/n}$, the union bound yieldsConsequentlyThe score event uses the supremum norm of $X^T\epsilon /n$; the centering term still vanishes because $X^{T}1=0$.

We next work deterministically on $\Omega$. LetBy Holder inequality, ${\epsilon }^{T}X\delta /n\le c\lambda \Vert \delta {\Vert }_1=c\lambda (a+b)$. Since ${\beta }_N^0=0$, the triangle inequality givesSubstituting both inequalities into the Basic inequality for the Lasso producesBecause $Q\ge 0$, this also proves the relevant Lasso cone condition, $(1-c)b\le (1+c)a$. The assumed Compatibility condition for the Lasso therefore applies to $\delta$:Set $D=(1+c)\lambda \sqrt{s}/\varphi$. Combining these inequalities givesIf $Q>0$, discarding the nonnegative $b$ term shows $\sqrt{Q}\le D$. If $Q=0$, compatibility gives $a=0$, and the preceding inequality then gives $b=0$. In either case $D\sqrt{Q}\le D^2$, soThis is a fast prediction bound and an inactive-coordinate error bound on the same event. It is the fast-rate Lasso prediction bound under compatibility.

Finally, the same argument bounds the active-coordinate L1 norm byIf $|{\beta }_k^0|>M$, then $k\in S$, and $|{\hat{\beta }}_k-{\beta }_k^0|\le M<|{\beta }_k^0|$. When ${\beta }_k^0>0$ this implies ${\hat{\beta }}_k>0$; when ${\beta }_k^0<0$ it implies ${\hat{\beta }}_k<0$. Thus the sign function obeysThis is Lasso sign recovery under compatibility. It concerns the sufficiently large nonzero coefficients; it does not assert that every estimated inactive coefficient is zero.

Let $m=\mathbb{E}\Vert X_1{\Vert }_2$ and $q=\sqrt{n}K\ge 2$. The Lipschitz continuity of cosine and the Cauchy-Schwarz inequality implyThe centered expectation term contributes $nm$; omitting it would leave the Lipschitz bound incomplete. In particular $S_n$ has continuous sample paths on the compact cube, so its maximum exists and is measurable.

PutChoose a Cartesian finite net $G\subset [-K,K{]}^d$ whose coordinate spacings are at most $\eta$, including the endpoints. Every point of the cube is within Euclidean norm distance $\sqrt{d}\eta$ of $G$, andOn the event $L_n\le n{q}^a$, replacing any $u$ by a nearby grid point changes $S_n$ by at most $\sqrt{dn}$. Since $R>8\sqrt{d}$ and $\log (n{K}^2)\ge \log 4$, this is less than $\frac{R}{4}\sqrt{n\log (n{K}^2)}$. ThereforeThe Markov inequality bounds the first event by $2m{q}^{-a}$. At a fixed $v$, the summands are centered, independent and identically distributed, and have absolute value at most $2$. The supplied Hoeffding inequality, with $M=2$, bounds each grid event byA union bound now givesThe choice of $a$ balances the cost of a large random Lipschitz constant against the covering number of the cube: $d(1+a)-R^2/64=-a$. Consequently $C=2m+2\cdot 4^d$ works, withThis uses only the first moment $m$ and has a constant independent of $n,K,R$. The finite net is deterministic even though the Lipschitz constant is random.

Let $h=\hat{\theta }-{\theta }^{\ast }$. The defining minimum for graph total variation denoising, compared with the feasible value ${\theta }^{\ast }$, gives $n^{-1}\Vert z-h{\Vert }_2^2+\lambda \Vert D\hat{\theta }{\Vert }_1\le n^{-1}\Vert z{\Vert }_2^2+\lambda \Vert D{\theta }^{\ast }{\Vert }_1$. Expand the squared Euclidean norm and cancel $\Vert z{\Vert }_2^2/n$ to obtain the basic inequality for a penalized least-squares estimator:

Let $B_{\delta }=\sqrt{\log (2m)}+\sqrt{\log (1/\delta )}$. The columns of $D^{†}/L$ have Euclidean norm at most one. Under the usual sub-Gaussian random vector convention, 3(d) justifies the tuning choice $\lambda =2\sqrt{2}L{B}_{\delta }/n$, which is independent of ${\theta }^{\ast }$. Also $\Vert {\Pi }_{1}z{\Vert }_2=|⟨z,1/\sqrt{n}⟩|$, so the Chernoff bound gives $\Vert {\Pi }_{1}z{\Vert }_2^2\le c_{\delta }=2\log (2/\delta )$ with probability at least $1-\delta$.

On the intersection of these events, of probability at least $1-2\delta$, set $a=\Vert h{\Vert }_2/\sqrt{n}$ and $b=\Vert {\Pi }_{1}z{\Vert }_2/\sqrt{n}$. The weighted Young inequality gives $2ab\le t^2{a}^2+b^2/t^2$ for $0<t<1$. Applying it to 3(c) and rearranging yields the rigorous boundIf the coefficient-one concentration statement in 3(d) is taken as an extra hypothesis, instead choose $\lambda =2L{B}_{\delta }/n$; the identical argument gives precisely the printed coefficient $4$ in the first term. Thus the deterministic argument and its risk rate are sound; its concentration constants depend on correcting or strengthening 3(d).

For the Euclidean norm, rotational symmetry and minimizing the radial objective give the radial soft thresholding formulaIndeed, if $r=\Vert x{\Vert }_2$, an optimal $u$ is a nonnegative scalar multiple of $x$; minimizing $s+(r-s{)}^2/(2\tau )$ over $s\ge 0$ gives $s=(r-\tau {)}_{+}$. The gradient of a Moreau envelope is consequentlyAt $x=0$ this is $\{0\}$, and the two expressions agree when $\Vert x{\Vert }_2=\tau$. The Moreau envelope of the Euclidean norm itself isThus a quadratic core replaces the nondifferentiable tip while the outer gradient remains the normalized radial direction. The Euclidean norm has an unbounded effective domain, unlike the earlier bounded-domain hypothesis; the preceding argument explicitly shows that this restriction is unnecessary here.

For convex optimization, this Moreau–Yosida regularisation permits gradient descent and other methods for functions with a Lipschitz gradient, using a gradient Lipschitz constant $1/\tau$. It approximates the norm uniformly: $0\le \Vert x{\Vert }_2-f_{\tau }(x)\le \tau /2$. Smaller $\tau$ improves approximation but makes the permitted gradient steps smaller. Minimizing $f_{\tau }$ alone preserves the minimizers and minimum value of $f$; replacing one term in a larger objective can shift the minimizer, so the smoothing parameter controls that approximation error.

The matrix $N$ is a skew-symmetric matrix, so $x^{T}Nx=0$ for real $x$. Therefore the energy-neutral rotational nonlinearity contributes nothing directly to the energy balance:The nonlinear term rotates the state without changing its Euclidean norm. It can still change the orientation, and thereby affect later energy growth through the linear term. Thus energy cancellation does not mean the nonlinear and linear trajectories have identical energy histories.

For unit $u$, put $A=I-2u{u}^T$. Then $A^T=A$ and $A^2=I$, so $A$ is an orthogonal matrix. The affine reflection in a hyperplane is $R(x)=Ax+2cu$. Hence $R(x)-R(y)=A(x-y)$ preserves the Euclidean norm and distance, and $R(x)=x$ whenever $u\cdot x=c$. Thus it is an Euclidean isometry fixing the hyperplane pointwise.

For $p\ne q$, any reflection exchanging them must have normal parallel to $p-q$, and its fixed hyperplane must contain their midpoint. These requirements determine the perpendicular bisector uniquely:Changing both signs of $u,c$ leaves the same reflection. It belongs to the orthogonal group $O(n)$ exactly when its translation term vanishes, that is, $c=0$. Since $c=(\Vert p{\Vert }^2-\Vert q{\Vert }^2)/(2\Vert p-q\Vert )$,To prove the finite reflection decomposition of a Euclidean isometry, first note that a distance-preserving map $g$ fixing zero preserves inner products by the polarization identity. Its values on an orthonormal basis $e_i$ form an orthonormal basis, and $g(x)\cdot g(e_i)=x_i$ shows $g(x)={\sum }_i{x}_{i}g(e_i)$. Thus $g$ is orthogonal.

Every orthogonal transformation is a product of at most $n$ linear reflections: if $g(e_1)\ne e_1$, reflect $g(e_1)$ to $e_1$ using the hyperplane normal $g(e_1)-e_1$, which passes through zero. The resulting orthogonal transformation fixes $e_1$, and its restriction to $e_1^{\perp }$ is handled inductively in dimension $n-1$. If $g(e_1)=e_1$, no initial reflection is necessary. Reflections on the complement extend by fixing $e_1$; the induction starts in dimension zero.

For an arbitrary isometry $f$, if $f(0)\ne 0$, first reflect $f(0)$ to zero across its perpendicular bisector with zero. Composing this one affine reflection with $f$ gives an orthogonal transformation. If $f(0)=0$, skip the initial reflection. ThereforeThe glide reflection $(x,y)\mapsto (x+1,-y)$ cannot use fewer than three: its determinant sign is negative, excluding zero or two reflections, while absence of fixed points excludes a single reflection. Three suffice by reflecting successively in $x=0$, $x=1/2$, and $y=0$.

The linear least-squares problem is to minimize $\Vert Ax-b{\Vert }_2^2$ over $x\in {\mathbb{R}}^n$, allowing an overdetermined system to have a nonzero residual. For a full QR decomposition, $Q$ is $m\times m$ orthogonal and $R$ is $m\times n$ with an upper-triangular top block. Orthogonal transformations preserve the Euclidean norm, soIf $A$ has full column rank, the top triangular block is nonsingular; setting its residual to zero gives the unique minimizer, while the remaining residual is independent of $x$. Without full column rank, minimizers still exist but need not be unique.

For the specified matrix, one Householder reflection already produces an upper-triangular matrix. Take $v=(-1,1,1,1{)}^T$, the difference between the first column and $2e_1$, and setThe formula gives $H^T=H$, $H^2=I$. Direct multiplication yields the Householder QR decompositionAll subdiagonal entries in the remaining columns are already zero, so no further reflection is needed. For the supplied right-hand side, $Q^{T}b=(2,0,2,-2{)}^T$. Back substitution gives $x_3=1$, $x_2=-1$, $x_1=2$, henceThe residual $A{x}^{\ast }-b=(1,-1,-1,1{)}^T$ is orthogonal to every column of $A$, independently confirming the normal equations $A^T(A{x}^{\ast }-b)=0$.

Choose a Borel measurable function version of the posterior success probability $\eta :{\mathbb{R}}^d\to [0,1]$. Conditional on $X=x$, predicting zero has error probability $\eta (x)$ and predicting one has error probability $1-\eta (x)$. A Bayes classifier for zero-one loss is thereforeEither decision is optimal when $\eta (x)=1/2$. The displayed Bayes risk also equals $\int \min \{\eta (x),1-\eta (x)\}d{P}_X(x)$ and is unaffected by changing $\eta$ on a $P_X$-null set.

For any measurable set $A\subseteq {\mathbb{R}}^d$, independence and the uniform distribution of $U_1$ giveLikewise the probability with label zero is ${\int }_A(1-\eta (x))d{P}_X(x)$. These sets determine the joint probability distribution, soThe same construction makes all training pairs independent and identically distributed random variables.

Fix a feature-measurable nearest-neighbour tie-breaking rule, for example increasing original index for observations at equal Euclidean norm distance from the query. This is important: the ordering may depend on the features, but not on the $U_i$ or labels. Let $Y_{(j)}(x)$ be the label attached to the $j$th ordered feature. The classifier from the K-nearest neighbors algorithm isThe displayed rule resolves a tied vote in favour of one; any fixed vote convention would also define the method. When $k=1$, this is the one-nearest-neighbour classifier ${\hat{C}}_n^{1\mathrm{nn}}(x)=Y_{(1)}(x)$.

Write $I_n(x)$ for the selected original index. Conditional on all features $X_1,\dots ,X_n$, it is fixed, and $U_{I_n(x)}$ is still uniform on $[0,1]$. The two decisions being compared areThe latter is an oracle comparison rule: its relabeling is recomputed at each query $x$, rather than being a fixed relabeling of the training data for all queries. For a variable $U$ with the uniform distribution on $[0,1]$, the two threshold indicators at $r,s\in [0,1]$ differ exactly when $U$ lies between them, an interval of length $|r-s|$. This Bernoulli coupling by a shared uniform random variable proves

Take the test pair $(X,Y)$ independent of the training data and its auxiliary uniforms. Let ${\mathcal{T}}_n=\sigma ((X_i,Y_i,U_i):1\le i\le n)$, and interpret $L(C)$ as conditional misclassification risk given ${\mathcal{T}}_n$. The tower property of conditional expectation gives $\mathbb{E}L(C)=\mathbb{P}(C(X)\ne Y)$. Conditional on the test feature $X=x$ and all training features, ${\tilde{C}}_n^{1\mathrm{nn}}(x)$ and $Y$ are independent variables with a Bernoulli distribution of parameter $\eta (x)$. Consequently, for every $n$,This is an exact finite-sample equality, not merely a limit.

The two error indicators can differ only if the two classifiers disagree, soThe permitted nearest-neighbour approximation theorem states that the last expected value tends to zero for the feature-based selection rule. This establishes the one-nearest-neighbour asymptotic risk

For $r\in [0,1]$, put $a=\min (r,1-r)\in [0,1/2]$. Then $2r(1-r)=2a(1-a)$, and $a\le 2a(1-a)\le 2a$. Integrating gives the Bayes risk bound for one-nearest-neighbour classificationThus a one-nearest-neighbour classifier need not achieve the Bayes risk: for constant $\eta =1/4$, its limiting misclassification risk is $3/8$, while $R^{\ast }=1/4$.

Feature-based neighbour tie-breaking is required. The convention cannot be dropped for arbitrary $P_X$. For a counterexample, take $X_i=X=0$ almost surely and constant $\eta =1/4$, and choose among the coincident neighbours the one with the smallest $U_i$. Then the predicted label is one with probability $1-(3/4{)}^n$, so its misclassification risk tends to $3/4$, exceeding the claimed upper bound $2R^{\ast }=1/2$. The corrected theorem uses ties determined independently of the uniforms and labels, as above.

Let $A$ be the interior-grid matrix representing ${\Gamma }_9$, with zero boundary error. It is real symmetric and has the stated sine eigenbasis. Put $s={\sin }^2(k\pi h/2)$ and $t={\sin }^2(\ell \pi h/2)$; the negative of its eigenvalue isThis increases in each variable on $[0,1{]}^2$. With $s_1={\sin }^2(\pi h/2)\ge h^2$, the smallest absolute eigenvalue is at least $8s_1-(8/3)s_1^2\ge (16/3)h^2$. Hence its Euclidean norm operator norm satisfiesThe corrected scheme has an unscaled residual $r$ whose individual entries are uniformly $O(h^6)$. There are $m^2$ entries and $m<h^{-1}$, so $\Vert r{\Vert }_2=O(h^5)$. Subtracting the exact nodal equations from the numerical equations gives $Ae=-r$ (with sign depending on the residual convention), and thereforeChoose a constant slightly larger than the resulting bound to obtain the requested strict $\Vert e\Vert <c{h}^3$ for all sufficiently small $h$. Uniform smoothness is needed for an $h$-independent constant; unspecified smoothness only in the interior would not by itself guarantee it.

Let $L=\mathrm{tridiag}(1,-2,1)$. The zero Dirichlet boundary values introduce no forcing terms, so the scheme isThe common orthogonal sine eigenvectors have $L$-eigenvalues $-4{\sin }^2[\pi j/(2(M+1))]$. Thus $B$ is invertible for every $\mu >0$, and each amplification eigenvalue isThe matrix $B^{-1}C$ is orthogonally diagonalizable, so its powers have Euclidean norm at most one, uniformly in the mesh and time step. Therefore Crank-Nicolson diffusion scheme is stable for every $\mu >0$. Negative amplification factors at large $\mu$ can create temporal sign oscillations, which do not contradict this norm stability.

The dot product and Euclidean norm are $\mathbf{x}\cdot \mathbf{y}={\sum }_i{x}_i{y}_i$ and $|\mathbf{x}|=\sqrt{\mathbf{x}\cdot \mathbf{x}}$. For every real $t$,Its quadratic discriminant is nonpositive, proving the Cauchy-Schwarz inequality $|\mathbf{x}\cdot \mathbf{y}|\le |\mathbf{x}||\mathbf{y}|$. In the inequality asked for, equality holds exactly when $\mathbf{x}$ is a positive scalar multiple of $\mathbf{y}$, and

Using the Levi-Civita symbol and its contraction identity,

Put $T=\mathbf{a}\cdot (\mathbf{b}\times \mathbf{c})$, the scalar triple product. Cyclic symmetry gives $\mathbf{m}\cdot \mathbf{a}=\mathbf{m}\cdot \mathbf{b}=\mathbf{m}\cdot \mathbf{c}=T$, so each requested angle $\varphi$ satisfies $\cos \varphi =T/|\mathbf{m}|$. If every pairwise angle is $\theta$ and $t=\cos \theta$, the preceding identity givesand therefore $|\mathbf{m}|=\sqrt{3}(1-\cos \theta )$. This is $0$ when $\theta =0$; for a right-handed orthonormal basis and $\theta =\pi /2$, $\mathbf{m}=\mathbf{a}+\mathbf{b}+\mathbf{c}$ has norm $\sqrt{3}$.

The three planes have equations $\mathbf{a}\cdot \mathbf{x}=\mathbf{a}\cdot \mathbf{p}$, $\mathbf{b}\cdot \mathbf{x}=\mathbf{b}\cdot \mathbf{q}$, and $\mathbf{c}\cdot \mathbf{x}=\mathbf{c}\cdot \mathbf{r}$. They meet at one point exactly when $\Delta =\mathbf{a}\cdot (\mathbf{b}\times \mathbf{c})\ne 0$, meaning their normals are linearly independent vectors. The point is