Diagonal taxicab norm

Definition 2.1: Given a -vector space , a norm on is a function with the following properties:

• Subadditivity: for all ,
• Absolute homogeneity: for all ,
• Positive definitivity: For all , if , then .

Definition 3.1: Let . We define the naïve diagonal taxicab norm as:

Proof: is indeed a norm because all of the following holds: Let and . Then:

In general, the following norm bounds hold (whereby is the taxicab norm):

Well-definedness:

Subadditivity:

Note that the in the definition doesn’t need any special considerations, and we want the to get smaller in the split case because it gets multiplied with . The transformation in the second line warrants special attention because there the values to minimize over actually get larger, but they only get larger in a sense bounded by the the smallest entry of in the first term.

Absolute homogeneity:

Positive definitivity:

Definition 4.1: We define the property of a function or sequence being a monotonically decreasing and non-negative by fulfilling all of the following:

• For with , we have that , and
• For , we have that .

Definition 4.2: On the space of monotonically decreasing, non-negative sequences , such that , we define the following fundamental diagonal taxicab norm:

Similarly, we define this inthe same way for tuples of finite length by embedding it in the space of these sequences, and extending them into infinite sequences by assigning for all .

For simplicity, we consider only sequences for which this “norm” is finite / converges.

Proof: Let be monotonically decreasing, non-negative sequences. Let .

Linearity:

Positive definitivity:

Theorem 4.3: Let . Then .

Proof: As stated at the beginning of this section, the left-hand side is equal to:

and the right-hand side is equal to:

which are equal.

Definition 4.4: Let be a commutative monoid, and be a step-size (for , we assume unless stated otherwise). Let be an abelian additive group with inverse . Then we have the forward difference operator

Remark 4.5: We can thus alternatively express/define this fundamental diagonal taxicab norm as follows:

Lemma 4.6: The functions

is convex, non-negative and monotonically decreasing.

Proof: Non-negativity is obvious. Convexity and monotonically decreasing follows from the ranges of the first and second derivative.

Lemma 4.7: Let . For a monotonically decreasing function the following holds for all :

Proof: Let be monotonically decreasing. Let and .

Definition 4.8: On the space of bounded sequences , such that a permutation exists with

we define the diagonal taxicab norm:

Similarly, we define this in the same way for tuples of finite length by embedding it in the space of these sequences, and extending them into infinite sequences by assigning for all .

For simplicity, we consider only sequences for which this “norm” is finite / converges.

Proof: Let be in the given space above with corresponding . W.l.o.g. assume that is the identity. The two given equation for are equal via:

Theorem 4.9: The diagonal taxicab norm is indeed a norm.

Proof: Let be in the given space above with corresponding . W.l.o.g. assume that are identity functions. Let be the corresponding permutation for , which is defined by pointwise addition.

Subadditivity:

i.e. changing the permutation away from the mon. decreasing one can only make the sum smaller.

Absolute homogeneity: Let . We have for all . Thus:

Positive definitivity: