Can zeroing entries of vector increase norm?

Question

Let $\Omega$ be an arbitrary norm on $\mathbb{R}^p$.

For any vector $\beta \in \mathbb{R}^p$ and subset $S \subseteq \{1, \dots, p\}$, define $\beta_S \in \mathbb{R}^p$ so that $\left( \beta_S \right)_i = \beta_i \mathbb{I}_{i \in S}$, where $\mathbb{I}$ is the indicator. (i.e. $\beta_S$ agrees with $\beta$ on it's support $S$.)

Is it true that $\Omega(\beta) \geq \Omega(\beta_S) \tag{1}$ for all $\beta$?

It's certainly true for all $\ell_q$ norms--which are basically all of the norms I've ever seen. However, I can't get any traction in trying to prove it. Does there exist a counterexample?

I'm asking because I recently came across a result that assumed that (1) was true.

Answer 1

Let $x,y \in \mathbb R^p$, and let $|x| = (|x_1|,\dots,|x_n|)$.

We say that a norm $\|\cdot\|$ on $\mathbb R^p$ is gauge invariant if $\| x\| = \| |x| \|$, and we say that it is monotone if $|x| \le |y| \implies \|x\| \le \|y\|$.

According to Proposition IV.1.1 of Matrix Analysis by Bhatia, these two properties are equivalent. That is, a norm is gauge invariant if and only if it is monotone.

The property you are asking for certainly holds (at least) for this class of norms.

Counter-example. Consider the norm $\|\beta\| = |\beta_1| + |\beta_1 - \beta_2|$ on $\mathbb R^2$. (Example IV.1.2 of the same book.) This norm is not gauge invariant. Let $\beta = (\alpha,\alpha)$ and $\beta_S = (\alpha,0)$ for some $\alpha > 0$. Then, $\|\beta\| = \alpha < 2\alpha =\|\beta_S\| $.

You could also consider $\|\beta\|' = \frac12(|\beta_1| + |\beta_2|) + |\beta_1 - \beta_2|$ which is symmetric and fails in the same way.

EDIT: Here is a proof that gauge invariance implies the desired property using the geometric interpretation in Nick Alger's answer: Suppose that there is a $\beta$ such that $\|\beta\| = r < \|\beta_S\|$ for $S$ some proper subset of $[p]$. For convenience, let us call $S$ the support in the following. Then, there exists $i \notin S$ with $\beta_i \neq 0$. Let us define $\beta_\pm$ $$ [\beta_\pm]_j = \begin{cases} \beta_j, & j \in S \\ \pm \beta_i, & j = i \\ 0 & \text{otherwise} \end{cases} $$ We have $\beta_S = \frac12 \beta_+ + \frac12 \beta_-$ and $r < \|\beta_S\| \le \frac12 \|\beta_+\| + \frac12\|\beta_-\|$. Now, if $\| \beta_+\| \neq \|\beta_-\|$ we have proved the failure of gauge invariance. Thus, assume otherwise, i.e., $\|\beta_+\| = \|\beta_-\|$, which combined with the inequality gives $\|\beta_+\| > r$. We are back with our starting assumption but with the size of the support increased by 1 ($\beta_+$ in place of $\beta_S$ and $S \cup \{i\}$ in place of $S$). Repeating the process, we either obtain a counter-example to gauge invariance or add 1 to the size of the support. This process should terminate before the support reaches the full set $[p]$, producing a counter-example to gauge invariance.

Answer 2

You can construct counterexamples easily by thinking of norms in terms of their unit balls.

Every norm is completely determined by the shape if its unit ball (set of all points with norm $\le 1$), which is a balanced absorbing convex set. Likewise, every balanced absorbing convex set is the unit ball for some norm. For more details about this, look into the Minkowski functional.

So, all you need to do is find a balanced absorbing convex set, and a point within that set, such that when you draw a line from that point to one of the axes, it exits the set.

One easy example is an ellipsoid that is rotated so that it is not axis-aligned, as shown in the following image: