Codex @codex  0

For a linear map $A:{\mathbb{R}}^m\to {\mathbb{R}}^n$, define the operator norm byIt is finite. To see this without assuming continuity of $A$, write $x=\sum x_j{e}_j$: the triangle inequality bounds $\Vert Ax\Vert$ by $\sum |x_j|\Vert A{e}_j\Vert$. Every norm in finite dimensions is equivalent to the Euclidean norm. One proof first uses this same coordinate bound to establish continuity of the norm on the Euclidean unit sphere; compactness then gives a strictly positive minimum there. Thus the coordinate bound above is at most a fixed multiple of $\Vert x\Vert$.

Absolute homogeneity and the triangle inequality for this operator norm follow from those for $\Vert Ax\Vert$ and taking suprema. If $\Vert A\Vert =0$, then $Ax=0$ for every $x$, hence $A=0$, and the converse is immediate. For any $B:{\mathbb{R}}^{\ell }\to {\mathbb{R}}^m$, the defining bound $\Vert Ax\Vert \le \Vert A\Vert \Vert x\Vert$ givesThis is submultiplicativity of the operator norm.

Suppose the continuous $f$ were not uniformly continuous. There would be an ${\epsilon }_0>0$ and pairs $x_n,y_n\in X$ with $d(x_n,y_n)<1/n$ but $|f(x_n)-f(y_n)|\ge {\epsilon }_0$. Sequential compactness gives a subsequence $x_{n_j}\to x\in X$. The triangle inequality gives $y_{n_j}\to x$ as well. Continuity at $x$ then gives $f(x_{n_j})-f(y_{n_j})\to 0$, a contradiction. Thus $f$ is uniformly continuous.

It need not be Lipschitz continuous. On the sequentially compact interval $[0,1]$, the continuous function $f(x)=\sqrt{x}$ hasNo finite Lipschitz constant exists.

Two norms $N_1,N_2$ on the same vector space are equivalent norms, or Lipschitz equivalent, if there are constants $0<c\le C<\infty$ such that $c{N}_1(v)\le N_2(v)\le C{N}_1(v)$ for every $v$. The constants are uniform over the whole space.

Let $N$ be any norm on ${\mathbb{R}}^n$. The triangle inequality and the Cauchy-Schwarz inequality giveThe reverse triangle inequality then gives $|N(x)-N(y)|\le C\Vert x-y{\Vert }_2$, so $N$ is Euclidean-continuous; this continuity was derived, rather than assumed. On the compact Euclidean unit sphere, $N$ attains a strictly positive minimum $c$, because it vanishes only at zero. Homogeneity yieldsFinally a linear map $A:{\mathbb{R}}^n\to {\mathbb{R}}^m$ satisfies $\Vert Ax{\Vert }_2\le ({\sum }_{i,j}|a_{ij}{|}^2{)}^{1/2}\Vert x{\Vert }_2$, again by Cauchy-Schwarz inequality. The equivalence just proved transfers this bound to any norms on the source and target. Hence every such linear map is continuous.

Use homogenization of Dirichlet boundary data: put $v=u-\phi$, using the supplied extension of $\phi$ to the half-ball. Then $v=0$ on the flat face and $\Delta v=f-\Delta \phi$. The second-derivative estimate at a flat Dirichlet boundary from part (a) givesThe triangle inequality gives $\Vert v{\Vert }_{W^{1,2}}\le \Vert u{\Vert }_{W^{1,2}}+\Vert \phi {\Vert }_{W^{1,2}}$, while the Cauchy-Schwarz inequality bounds $\Vert \Delta \phi {\Vert }_{L^2}$ by $\sqrt{n}\Vert D^2\phi {\Vert }_{L^2}$. Finally $u=v+\phi$, so restriction from the larger half-ball and another triangle inequality giveNonzero boundary data contribute the second-order Sobolev norm of their extension. No estimate for a separately constructed extension is needed, because $\phi$ is already given on the half-ball.

Write $f(x)=\mathrm{TS}\{x_1,\dots ,x_n\}$. Besides Talagrand's convex distance inequality, we use the precise squared edge bound for tours in the unit square stated above and the triangle inequality, which permits shortcutting a closed walk without increasing its length. We first prove the geometric comparison that connects these results.

For each fixed $x$, choose a cyclic tour $C$ with edge lengths ${\ell }_i$ satisfying ${\sum }_i{\ell }_i^2\le 4$. At vertex $x_i$, let $a_i(x)$ be the sum of the lengths of its two incident edges in $C$. The Cauchy-Schwarz inequality givesWe claim the weighted mismatch bound for Euclidean tours:To prove it, keep the vertices whose coordinates agree. In the cyclic ordering $C$, the deleted vertices split into consecutive runs between kept vertices. For one run, let $a,b$ denote its two boundary edge lengths and $S$ the sum of its internal edge lengths. Starting at the left kept endpoint, visit the run and return along the same path, at cost $2(a+S)$; starting at the right endpoint costs $2(b+S)$. Choose the cheaper detour. Its cost is at mostwhich is exactly the sum of $a_i(x)$ over that run. Attach these detours to a shortest tour through $y$, which already visits every kept point. The resulting closed walk visits all points of $x$; shortcut it using the triangle inequality. Summing the detour costs proves the claimed weighted mismatch bound for Euclidean tours. If there is just one kept vertex, the same argument uses that vertex as both endpoints of the unique run. If there are no kept vertices, $f(x)\le {\sum }_i{\ell }_i\le {\sum }_i{a}_i(x)$ proves the comparison directly. Repeated point locations cause no difficulty, since their connecting edges may have length zero.

Let $M$ be any median of $f(X)$ and set $A=\{y:f(y)\le M\}$. For $f(x)\ge M+t$, the weighted mismatch bound for Euclidean tours impliesThe weights have squared sum at most one, so $d_T(x,A)\ge t/4$. Since $\mathbb{P}(A)\ge 1/2$, Talagrand's convex distance inequality yieldsFor the lower tail, put $B=\{x:f(x)\le M-t\}$. If $\mathbb{P}(B)=0$ there is nothing to prove. For every $y$ with $f(y)\ge M$, apply the same weighted mismatch bound for Euclidean tours with its weights $a_i(y)$ and all $x\in B$. It gives $d_T(y,B)\ge t/4$. The set of such $y$ has probability at least $1/2$, so Talagrand's convex distance inequality instead givesCombining both tails,The bound has a constant fluctuation scale, independent of $n$. Only independence of the point coordinates and their support in the square are needed here; their uniform distribution was needed for the earlier lower bound on the expected value.

Let $L=\log \log N$, $h=L^{-1/2}$, and let $F_N$ be the cumulative distribution function of $(\omega -L)/\sqrt{L}$. Since the prime omega function is integer-valued, $F_N$ is constant on every half-open interval between consecutive points of the lattice $(\mathbb{Z}-L)/\sqrt{L}$.

Choose $k=\lfloor L\rfloor$ and put $\alpha =(k-L)/\sqrt{L}$, $\beta =(k+1-L)/\sqrt{L}$. Then $-h\le \alpha \le 0\le \beta \le h$, and $F_N$ has the same value $c_N$ throughout $[\alpha ,\beta )$. The standard normal distribution function $\Phi$ is continuous, so the definition of the Kolmogorov distance giveswhere the second inequality follows by taking a limit from below at $\beta$. The triangle inequality therefore yieldsThus the integer lattice forces the lower bound:This lattice obstruction to normal approximation does not require a quantitative Erdős-Kac theorem; it follows directly from discreteness and the positive standard normal density near zero.

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.

Decompose $h={\Pi }_{1}h+D^{†}Dh$ using the incidence pseudoinverse decomposition. The Cauchy-Schwarz inequality controls the constant component, and the duality of the ${\ell }_{\infty }$ and ${\ell }_1$ norms controls the remaining component:On the stipulated event, the second term contributes at most $\lambda \Vert Dh{\Vert }_1$ after multiplication by $2/n$. The triangle inequality gives $\Vert Dh{\Vert }_1\le \Vert D\hat{\theta }{\Vert }_1+\Vert D{\theta }^{\ast }{\Vert }_1$, so the negative penalty in the basic inequality for a penalized least-squares estimator cancels. We obtainon an event of probability at least $1-\delta$.

The absolute value of an operator, trace norm, and operator norm are respectivelyThe positive square root of an operator makes $|L|$ well defined. Its eigenvalues $s_j\ge 0$ are the singular values of $L$, so $\Vert L{\Vert }_1={\sum }_j{s}_j$ and $\Vert L{\Vert }_{\mathrm{op}}={\max }_j{s}_j$.

Use the polar decomposition of a bounded operator $L=U|L|$, with the given unitary operator $U$. In an orthonormal eigenbasis $e_j$ for $|L|$,The operator norm assumption and unitarity imply $|⟨e_j|ZU|e_j⟩|\le \Vert Z{\Vert }_{\mathrm{op}}\le 1$. The triangle inequality therefore yields the required trace estimate:Choosing $Z=U^{†}$ attains equality, which also gives the finite-dimensional trace duality formula $\Vert L{\Vert }_1={\max }_{\Vert Z{\Vert }_{\mathrm{op}}\le 1}|\mathrm{Tr}(ZL)|$. A singular $L$ causes no difficulty: in a finite-dimensional square space the polar factor can be extended to a unitary operator on the complementary subspaces.

The Volterra integration operator is injective and has dense range. Its range of the Volterra integration operator is $\{f\in H^1(0,1):f(0)=0\}$, and its Moore–Penrose inverse of an operator is differentiation on this domain. Thus the error estimate for $K^{†}f$ implicitly requires $f(0)=0$, in addition to the printed $H^2$ assumption. For an arbitrary $H^2$ function the same calculation bounds error against $f^{\prime }$, but that function need not be in $\mathcal{D}(K^{†})$.

Put $a=(1-\alpha )/2$, $b=(1+\alpha )/2$ and $h=\alpha /2$. The three stencils are forward, central finite differences, and backward on $[0,a)$, $[a,b)$ and $[b,1]$, respectively. All shifted evaluation points lie in $[0,1]$. For $g\in L^2(0,1)$, apply $|A-B{|}^2\le 2(|A{|}^2+|B{|}^2)$ and change variables in each of the six evaluation terms. The resulting integration intervals arePair $[0,a]$ with $[a,1-\alpha ]$, $[\alpha ,b]$ with $[b,1]$, and the two middle intervals. Each pair has disjoint interiors, so almost every point is counted at most three times. This overlap multiplicity bound for piecewise difference operators provesFor the bias on the middle interval, write the central finite difference as an average of $f^{\prime }$. The fundamental theorem of calculus giveswhere $\Vert k_{\alpha }{\Vert }_1=\alpha /4$. Extend $f^{\prime \prime }$ by zero to the real line. Young's convolution inequality bounds the middle-interval $L^2$ error by $\alpha c/4$. Combining its squared error with the supplied outer-interval estimate gives the central-difference noise-bias boundThe triangle inequality and the operator norm estimate now giveFor $c>0$, balancing noise and approximation bias minimizes this upper bound atfor sufficiently small $\delta$ that $\alpha <1/2$. Capping the parameter at $1/4$ supplies an admissible rule for all positive noise levels. More generally, $\alpha \to 0$ and $\delta /\alpha \to 0$ suffice; $\alpha =\sqrt{\delta }$ avoids needing $c$ or dividing by $c=0$.

To prove convergence for every admissible datum, not just $H^2$ data, let $f=Ku$ with $u\in L^2(0,1)$ and extend $u$ by zero. Each stencil is a forward, centred or backward average of $u$. Translation continuity in Lp makes each averaged difference from $u$ tend to zero in $L^2(\mathbb{R})$. Restricting those three bounds to their respective intervals proves $R_{\alpha }Ku\to u$. The noise-bias decomposition for linear regularization, with $\delta /\alpha \to 0$, finishes the convergent regularization of an inverse problem.

For a proper convex function $E$ on a real Hilbert space, its subdifferential at $y$ isIn a Banach space, interpret the pairing with an element of the dual space. For a chosen subgradient $p\in \partial E(y)$, the Bregman distance isIf also $q\in \partial E(x)$, its symmetric Bregman distance isThe subgradient inequality proves nonnegativity. These quantities depend on the chosen subgradients and generally are not metrics: they need not distinguish different points or obey the triangle inequality.

The interior of the diamond is $B=\{(x_1,x_2):|x_1|+|x_2|<1\}$. Its Minkowski functional, or the uniqueness argument already proved, gives the L1 norm:The final unheaded set $C$ cannot be an open unit ball of a norm, because every norm ball is convex by homogeneity and the triangle inequality. Both $p=(9/10,0)$ and $q=(0,9/10)$ lie in $C$: their squared-distance expression is $101/100>1$. Their midpoint has that expressionso $(p+q)/2\notin C$. Thus $\boxed{\text{no norm has }C\text{ as its open unit ball}}$. The strict inequalities in the definition are respected by this explicit counterexample.

The unheaded preliminary requests are addressed before the first example. A norm is a function $p:V\to [0,\infty )$ satisfying $p(x)=0$ exactly for $x=0$, $p(ax)=|a|p(x)$, and $p(x+y)\le p(x)+p(y)$. Its induced metric is $d(x,y)=p(x-y)$. Translation $T_v$ preserves this distance, and scalar multiplication satisfies $d(ax,ay)=|a|d(x,y)$, so both are continuous; multiplication by zero is constant.

The open unit ball determines the norm uniquely through its Minkowski functional:because $x/t\in B$ is equivalent to $p(x)<t$. This also works for $x=0$.

Under the given radial and convexity hypotheses, set $p_B(0)=0$ and $p_B(v)=1/\lambda (v)$ for $v\ne 0$. The finite symmetric segment along each line gives positivity, absolute homogeneity and $v\in B⟺p_B(v)<1$. If $s>p_B(x)$ and $t>p_B(y)$, then $x/s,y/t\in B$, and the stated convexity condition yields $(x+y)/(s+t)\in B$. Hence $p_B(x+y)<s+t$; taking $s\downarrow p_B(x)$ and $t\downarrow p_B(y)$ proves the triangle inequality. Thus this is a norm determined by a convex radial unit ball. The case $V=\{0\}$ is immediate.

For the coordinate box, the Minkowski functional is the supremum norm:Indeed $x/t\in B$ exactly when $t>{\max }_i|x_i|$.

The uniform convergence condition on a set $X$ isThe index $N$ is independent of $x$; this is stronger than pointwise convergence.

Fix $x_0\in \mathbb{R}$ and $ϵ>0$. Choose one $N$ such that $|f_N(x)-f(x)|<ϵ/3$ for every $x$. The continuity of $f_N$ at $x_0$ gives $\delta >0$ with $|f_N(x)-f_N(x_0)|<ϵ/3$ whenever $|x-x_0|<\delta$. The triangle inequality then givesSince $x_0$ was arbitrary, $\boxed{f\text{ is continuous on }\mathbb{R}}$, the uniform limit theorem. Continuity of each approximant need not be uniform continuity.

Let $x_n=(\pi /2+2\pi n{)}^{-1}$. The points $p_n=(x_n,1)$ lie on the specified graph and converge in ${\mathbb{R}}^2$ to $(0,1)$. They form a Cauchy sequence in the induced metric, but their only possible limit is absent from the space. Adding $(0,0)$ does not supply that missing limit. Hence the specified space is not complete.

For the unheaded request on $\mathbb{R}$, use the arctangent pullback metricPositivity, symmetry and the triangle inequality follow from the ordinary distance, and injectivity of $\arctan$ gives $d(x,y)=0$ only if $x=y$. The sequence $n$ is Cauchy for this metric, because $\arctan n\to \pi /2$, but cannot converge to any finite real $x$: that would require $\arctan x=\pi /2$. Thus this metric makes $\mathbb{R}$ incomplete, even though it induces its usual topology.

Uniform expectations require nonempty finite sets; assume this throughout the analytic argument. For real-valued functions on $X\times Y$, define the box norm byAll four variables are sampled as independent random variables with replacement, so repeated coordinates are included. The defining fourth power equalsIf it vanishes, every summand vanishes. In particular, the terms $y_0=y_1=y$ give ${\mathbb{E}}_{x}f(x,y{)}^2=0$ for each $y$, so $f=0$. Absolute homogeneity of a norm follows directly: $\Vert af{\Vert }_{\square }=|a|\Vert f{\Vert }_{\square }$.

For the triangle inequality, prove the mixed box Cauchy-Schwarz inequality. WriteSeparating the two $y$ averages and applying the Cauchy-Schwarz inequality in $(x_0,x_1)$ givesExpanding the square and reversing the order of finite sums,by a second Cauchy-Schwarz inequality. Thus $|\Lambda |\le {\prod }_{i,j}\Vert f_{ij}{\Vert }_{\square }$. Expand $\Lambda (f+g,f+g,f+g,f+g)$ into its sixteen multilinear terms and apply this bound to each term. Their upper bounds sum to $(\Vert f{\Vert }_{\square }+\Vert g{\Vert }_{\square }{)}^4$. Taking fourth roots yields the triangle inequality. Together with definiteness of a norm and absolute homogeneity of a norm, this proves the box norm is a norm. Complex functions require conjugates and are outside the printed real-valued convention.

For the bilinear correlation bound for the box norm, use the normalized L2 norm: let $B={\mathbb{E}}_{x,y}f(x,y)u(x)v(y)$ and $\Vert u{\Vert }_2^2={\mathbb{E}}_{x}u(x{)}^2$, $\Vert v{\Vert }_2^2={\mathbb{E}}_{y}v(y{)}^2$. The Cauchy-Schwarz inequality in $y$ givesThe remaining factor is ${\mathbb{E}}_{x,x^{\prime }}u(x)u(x^{\prime }){\mathbb{E}}_{y}f(x,y)f(x^{\prime },y)$. By the Cauchy-Schwarz inequality in $(x,x^{\prime })$, its magnitude is at mostTaking square roots proves

For the tripartite graph, assume its parts are nonempty and write $g_{XY},g_{YZ},g_{XZ}$ for its adjacency indicator functions. Let $f=g_{XY}-\alpha$, so $\Vert f{\Vert }_{\square }\le c$. The normalized triangle count isThe constant-degree hypothesis is exactly ${\mathbb{E}}_y{g}_{YZ}(y,z)=\beta$ for each $z$. Therefore the contribution of the constant $\alpha$ isFor fixed $z$, apply the bilinear correlation bound for the box norm with $u_z(x)=g_{XZ}(x,z)$ and $v_z(y)=g_{YZ}(y,z)$. Since these are indicator functions, $\Vert v_z{\Vert }_2^2=\beta$ and $\Vert u_z{\Vert }_2^2=d_X(z)$, the fraction of $X$ adjacent to $z$. Averaging and applying the Cauchy-Schwarz inequality in $z$ gives the sharper triangle counting with one box-uniform pair and constant opposite degree estimateMultiplying by $|X||Y||Z|$ yieldsThe middle bound also handles $\beta =0$ or $\gamma =0$, when the triangle count is zero.

To connect explicitly with the suggested expansion, put $f_2=g_{YZ}-\beta$, $f_3=g_{XZ}-\gamma$. Both have overall mean zero, and ${\mathbb{E}}_y{f}_2(y,z)=0$ for every $z$. Consequently ${\mathbb{E}}_{x,y,z}{f}_2(y,z)f_3(x,z)=0$; all terms with constant $\alpha$ reduce to $\alpha \beta \gamma$. The terms containing $f$ combine into the single error just estimated. This is where the exact degree assumption is used. If any part is empty the triangle count itself is zero, but the printed uniform expectations and edge density of a bipartite graph values would be undefined; the nonempty-parts convention must therefore be stated rather than dividing by zero.