Norm ($\Vert \cdot \Vert$)

A norm assigns a nonnegative length to each vector, is zero only at the zero vector, is absolutely homogeneous, and satisfies the triangle inequality.

For a real or complex polynomial $p(t)={\sum }_{k\ge 0}{a}_k{t}^k$, this finite sum defines a norm: definiteness follows from uniqueness of polynomial coefficients, absolute homogeneity of a norm follows termwise, and the triangle inequality follows by summing $|a_k+b_k|\le |a_k|+|b_k|$. On $[0,1]$, its supremum norm satisfies $\Vert p{\Vert }_{\infty }\le \Vert p{\Vert }_{\mathrm{coef},1}$, since $|t^k|\le 1$. The reverse comparison has no constant independent of the degree of a polynomial: for $p_n(t)=(1-t{)}^n$, the two norms are $1$ and $2^n$ respectively, by the binomial theorem.

A quasi-norm on a vector space is nonnegative, vanishes only at zero, is absolutely homogeneous, and satisfies a triangle inequality with one constant factor $C\ge 1$. For $0<p<1$, $(\int |f{|}^p{)}^{1/p}$ on an Lp space is a quasi-norm: $\Vert f+g{\Vert }_p^p\le \Vert f{\Vert }_p^p+\Vert g{\Vert }_p^p$ gives a quasi-triangle inequality. Measure-preserving composition preserves this quantity even though the Minkowski inequality is unavailable below exponent one.

A dual norm measures how strongly a bounded linear functional can respond to a unit-sized input. If $p$ is a bounded linear functional on a normed vector space $X$, write $⟨p,x⟩=p(x)$ and defineIt is the operator norm of $p$ when its scalar output is measured by absolute value. On ${\mathbb{R}}^n$, represent $p(x)=a^{T}x$ using a coefficient vector $a$. The unit ball is symmetric, so maximizing $|a^{T}x|$ gives the same value as maximizing $a^{T}x$: negate an input whenever its output is negative.^[ref]

For an original two-coordinate example, fix $a=(2,-1{)}^T$, so $p(x)=2x_1-x_2$. The input norm changes the allowable unit ball and hence the dual norm:Under the L1 norm, $|2x_1-x_2|\le 2(|x_1|+|x_2|)\le 2$, and $(1,0{)}^T$ attains the bound. Under the Euclidean norm, the Cauchy-Schwarz inequality gives $|a^{T}x|\le \Vert a{\Vert }_2\Vert x{\Vert }_2\le \sqrt{5}$, with equality at the displayed normalized vector. Under the maximum norm, each coordinate can reach unit absolute value, so $|2x_1-x_2|\le 2+1=3$; $(1,-1{)}^T$ attains it. Thus the dual norms of these three vector norms are respectively the maximum norm, the Euclidean norm, and the L1 norm. For $1\le p\le \infty$, Lp norms on a finite coordinate space pair with their Holder conjugate exponents.^[ref]

This geometry explains the usefulness of a dual norm: it translates a bound on inputs into the sharp bound on a linear output. The support function of the unit ball gives its value in the coefficient direction $a$. Changing the input budget changes the set of possible inputs; the three different answers do not conflict. In finite dimensions a closed unit ball is compact, so a continuous linear functional achieves its maximum absolute value. In an infinite-dimensional normed vector space, the supremum remains the definition and need not be achieved.

Suppose a perturbation $\delta x$ satisfies $\Vert \delta x\Vert \le \epsilon$, with $\epsilon \ge 0$. Absolute homogeneity of a norm and the dual norm definition giveFor nonzero $\delta x$, divide it by its norm to obtain an input in the unit ball; for zero perturbation the inequality is immediate. This is an exact error bound for a linear functional, for every perturbation in the stated input set.

For $p(x)=2x_1-x_2$ and a budget $\epsilon =0.1$, the sharp output-error bounds are $0.2$ for $\Vert \delta x{\Vert }_1\le 0.1$, $\sqrt{5}/10\simeq 0.224$ for $\Vert \delta x{\Vert }_2\le 0.1$, and $0.3$ for $\Vert \delta x{\Vert }_{\infty }\le 0.1$. Scale the maximizing vectors from the preceding example by $0.1$ to attain the positive endpoints; their negatives attain the negative endpoints. The L1 norm budget constrains a total absolute error; the maximum norm budget permits each coordinate to have that error separately. These budgets define nested sets and carry different information.

The coordinates must use the stated scale and units. Rescaling one coordinate changes both its coefficient in $a$ and the meaning of its input budget. For a nonlinear differentiable function with scalar values, its Fréchet derivative at the base point is a linear functional governing the first-order response. An exact finite-perturbation error bound additionally needs control of the Taylor remainder or of the Fréchet derivative along the path.

On the real space of sequences converging to zero $c_0$, use the supremum norm and define the linear functionalThe geometric series gives $|p(x)|\le \Vert x{\Vert }_{\infty }$, so $p$ is a bounded linear functional and $\Vert p{\Vert }_{\ast }\le 1$. The sequence with its first $N$ entries equal to one and all later entries zero belongs to $c_0$, has unit supremum norm, and gives $p(x)=1-2^{-N}$. Hence $\Vert p{\Vert }_{\ast }=1$. But if $\Vert x{\Vert }_{\infty }\le 1$ and $x_n\to 0$, not all coordinates can equal one or all equal minus one. Since every weight $2^{-n}$ is positive, $-1<p(x)<1$. The supremum is approached but never attained on the unit ball.

The block mixed norm sums the ${\ell }^q$ norm of each block, for $q\ge 1$. Its dual norm is $\Vert p{\Vert }_{q^{\prime },\infty }={\max }_i\Vert p_i{\Vert }_{q^{\prime }}$, where $q^{\prime }=q/(q-1)$ for $q>1$ and $q^{\prime }=\infty$ for $q=1$. Apply Holder inequality blockwise and choose a norming block to attain equality. Absolute values are essential for signed components.

For $\lambda \ge 0$ and a linear map $A$ between finite-dimensional real inner product spaces,Thus the penalty is the support function of the compact convex set $A^{\ast }\{p:{\max }_i\Vert p_i{\Vert }_{q^{\prime }}\le \lambda \}$. The Moreau decomposition makes its proximal operator the identity minus the Euclidean projection onto a convex set.

Definiteness says that a norm vanishes only at the zero vector. The box norm on a nonempty finite Cartesian product is definite because its defining sum of squares includes equal-column terms, each of which is the square of an average of squares. Omitting repeated coordinates would destroy this proof and can produce a different quantity.

Absolute homogeneity is the norm axiom $\Vert av\Vert =|a|\Vert v\Vert$ for every scalar $a$ and vector $v$. It distinguishes a norm from a merely homogeneous expression of a different degree; for example the fourth root in the box norm converts a degree-four expression into a degree-one norm.

On a real vector space, suppose $B$ contains zero, is convex, and meets every line $\mathbb{R}v$, $v\ne 0$, in the finite symmetric open segment $\{tv:|t|<\lambda (v)\}$ with $\lambda (v)>0$. Then its Minkowski functional is a norm, with $p_B(v)=1/\lambda (v)$ and $B=\{x:p_B(x)<1\}$. Absolute homogeneity follows by rescaling the segment. If $s>p_B(x)$ and $t>p_B(y)$, convexity puts $(x+y)/(s+t)$ in $B$, giving $p_B(x+y)<s+t$; passing to the infima proves the triangle inequality. Conversely the open unit ball uniquely determines any norm by the displayed formula. No prior topology on the vector space is needed for these radial hypotheses.

On a uniform $d$-dimensional spatial grid, the discrete L2 norm weights the squared Euclidean norm by the cell volume. It approximates the continuous L2 norm and is induced by the discrete L2 inner product. A contraction bound in this norm with a mesh-independent constant proves stability of a numerical method for the spatially discretized evolution.