Infinity norm quotient

322 Views Asked by At

Let $V = \mathbb{R}^n$ the canonical $n$ dimensional real vector space. We endow $V$ with the infinity norm defined as $\|x\|_\infty = \max_i |x_i|$ for any vector $x = (x_1, \dots, x_n) \in V$.

Let then $V'$ be a strict subspace of $V$. One can consider the quotient $$V/V'$$ which is naturally normed by the quotient norm: $$ \| x + V' \|_\infty = \inf_{v\in V'} \|x-v\|_\infty.$$

Is there a convenient way to compute generically this norm or at least get (non-trivial) bounds on it ?

In the $\ell_2$ norm case, this reduces easily to the computation of the orthogonal projection of $x$ on the space $V'$, which can be performed by Gram-Schmidt orthogonalisation.

1

There are 1 best solutions below

3
On

The unit ball in infinity-norm is a zonotope, the Minkowski sum of several line segments. The zonotope structure is preserved under linear map, in particular under the quotient map. Thus, the unit ball of the quotient space is also a zonotope.

The converse is also true: every zonotope is a projection of a cube, so every normed space whose unit ball is a zonotope is isometrically isomorphic to a quotient of $(\mathbb{R}^n, \ell_\infty)$ for sufficiently large $n$.

In practical terms, this allows for an explicit description of the unit ball of $V/V'$. Pick some subspace $W\subset V$ that is a complement of $V'$; the Euclidean-orthogonal complement is a natural choice. For each $k=1,\dots, n$, let $p_k$ be the projection of the $k$th standard basis vector of $V$ onto $W$ along $V'$ (so, if $W\perp V'$, this is orthogonal projection). Then the unit ball of $V/V'$, as represented by $W$, is the Minkowski sum of line segments $[-p_k, p_k]$, that is $$ B = \left\{\sum_{k=1}^n c_k p_k : -1\le c_k\le 1\right\} $$ For a concrete $V'$, one may be able to grasp the geometry of $B$, and then the description of the norm follows.

Formally, for $x\in W$ the quotient norm is $$ \|x\| = \inf\left\{\max|c_k| : x = \sum_{k=1}^n c_k p_k\right\} $$ where the infimum is taken over all such representations; however this isn't really different from the definition.