Sum of norms induced by PSD matrices

Question

Suppose you have two positive definite matrices $M$ and $N \in \mathcal{S}_{++}^n$. They induce scalar products and norms on $\mathbb{R}^n$:

\begin{align} \lVert x \rVert_M &= \sqrt{x^\intercal M^{-1} x}, & \lVert x \rVert_N &= \sqrt{x^\intercal N^{-1} x}. \end{align}

Introduce the function $f:x\mapsto \lVert x \rVert_M + \lVert x \rVert_N$. It is a norm as it is the sim of two norms. However, it is not induced by a scalar product.

Can we upper-bound $f$ by a norm induced by another positive definite matrix?

Answer 1

Since $2\sqrt{ab}\leq a+b$, we have $$\| x \|_M + \| x \|_N=\sqrt{x^TMx}+\sqrt{x^TNx}\leq \\\sqrt{2(x^TMx+x^TNx)}= \sqrt{2x^T(M+N)x}=\| x \|_{2(M+N)}.$$

Answer 2

In addition to the answer by Gérard, we can use the concavity of the function $\sqrt{\cdot}$ to get a whole family of bounds.

For any $\theta \in (0,1)$: \begin{align} \sqrt{m} + \sqrt{n} &= \theta\sqrt{\frac{1}{\theta^2}m} + (1-\theta)\sqrt{\frac{1}{(1-\theta)^2}n}, \\ &\le \sqrt{\frac{1}{\theta}m + \frac{1}{1-\theta}n}. \end{align} This gives: \begin{align} \| x \|_M + \| x \|_N &=\sqrt{x^TMx}+\sqrt{x^TNx}, \\ & \le \sqrt{\frac{1}{\theta}x^TMx+ \frac{1}{1-\theta}x^TNx}, \\ &= \sqrt{x^T\left(\frac{1}{\theta}M + \frac{1}{1-\theta}N\right) x}, \\ &=\| x \|_{\frac{1}{\theta}M+\frac{1}{1-\theta}N}. \end{align}

---

In particular with $\theta = \frac{1}{2}$: $$ \| x \|_M + \| x \|_N \le \| x \|_{2(M+N)}.$$