# Can zeroing entries of vector increase norm?

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.

• It is certainly true for monotone norms: Ones with the property that $|x_i| \le |y_i|$ for all $i$ implies $\|x\| \le \|y\|$. Dec 3, 2016 at 21:11
• Would you be better asking on the mathematics SE?
– mdewey
Dec 4, 2016 at 10:07
• see thm 1.7 here: di.ens.fr/~fbach/bach_jenatton_mairal_obozinski_FOT.pdf Sep 10, 2017 at 23:42

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.

• Awesome! Thanks for the great help! It's interesting that the counterexample ends up being from within the class of norms that the generalized lasso uses. Dec 3, 2016 at 21:33
• @Benjamin, no problem. Yes, that is interesting. I didn't notice that it is generalized lasso. Dec 3, 2016 at 21:44
• @Benjamin, also added a version which is symmetric. Dec 3, 2016 at 21:45
• Very nice! I've plotted a ball in $‖\cdot ‖'$ if anyone else is curious. imgur.com/a/7v4jn Dec 4, 2016 at 17:23
• @Calvin Khor, thanks, geometrically it is a lot easier to see as Nick Alger's answer points out. Dec 4, 2016 at 17:33

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:

• Very nice geometric interpretation. Dec 4, 2016 at 17:31
• Great explanation! Dec 4, 2016 at 23:37