Concavity inequality for the matrix square root

inequalitymatrices

Let $A$, $B$ and $C$ be symmetric, positive semi-definite matrices. Is it true that
$$ \|(A + C)^{1/2} – (B + C)^{1/2}\| \leq \|A^{1/2} – B^{1/2}\|,$$
in either the 2 or Frobenius norm?

It is clearly true when $A, B$ and $C$ commute, but the general case is less clear to me. In fact, even the particular case $B = 0$ does not seem obvious.

Without loss of generality, it is clear that we can assume that $C$ is diagonal.
We show that it is sufficient to prove to prove the inequality for the matrix with zeros everywhere except on any position $k$ on the diagonal,
$$
(C_k)_{ij} = \begin{cases} 1 & \text{if } i=j=k\\ 0 & \text{otherwise} \end{cases}
$$
Clearly, if the inequality is true for one $C_k$, it is true for any $C_k$, by flipping the axes, and also for $C = \alpha C_k$, for any $\alpha \geq 0$, because
\begin{align}
\|(A + \alpha \, C_k)^{1/2} – (B + \alpha C_k)^{1/2}\|
&= \sqrt{\alpha} \|(A/\alpha + C_k)^{1/2} – (B/\alpha + C_k)^{1/2}\| \\
&\leq \sqrt{\alpha} \|(A/\alpha)^{1/2} – (B/\alpha)^{1/2}\|
= \sqrt{\alpha} \|A^{1/2} – B^{1/2}\|
\end{align}
Now, a general diagonal $C$ can be decomposed as $C = \sum_{k=1}^{n} \alpha_k C_k$.
Applying the previous inequality (specialized for a matrix $C$ with only one nonzero diagonal element) repeatedly,
we can remove the diagonal elements one by one
\begin{align}
&\|(A + \sum_{k=1}^{n}\alpha_k \, C_k)^{1/2} – (B + \sum_{k=1}^{n}\alpha_k \, C_k)^{1/2}\| \\
&\qquad = \|((A + \sum_{k=1}^{n-1}\alpha_k \, C_k) + \alpha_n C_n)^{1/2} – ((B + \sum_{k=1}^{n-1}\alpha_k \, C_k) + \alpha_n C_n)^{1/2}\| \\
&\qquad \leq \|(A + \sum_{k=1}^{n-1}\alpha_k \, C_k)^{1/2} – (B + \sum_{k=1}^{n-1}\alpha_k \, C_k)^{1/2}\| \\
&\qquad \leq \|(A + \sum_{k=1}^{n-2}\alpha_k \, C_k)^{1/2} – (B + \sum_{k=1}^{n-2}\alpha_k \, C_k)^{1/2}\| \\
&\qquad \leq \dots \leq \sqrt{\alpha} \|A^{1/2} – B^{1/2}\|.
\end{align}

Here are three ways of proving the inequality in 1 dimension,
which I tried to generalize to the multidimensional case without success.
Let us write $a$, $b$, $c$ instead of $A$, $B$, $C$,
to emphasize that we are working in one dimension,
and let us assume without loss of generality that $a \leq b$.

  • Let us write:
    $$ f(c) = \sqrt{b + c} – \sqrt{a + c} $$
    We calculate that the derivative of $f$ is given by
    $$
    f'(c) = \frac{1}{2} \left( \frac{1}{\sqrt{b + c}} – \frac{1}{\sqrt{a + c}} \right) \leq 0,
    $$
    and so $f(c) = f(0) + \int_{0}^{c} f'(x) \, d x \leq f(0)$.

  • We have, by the fundamental theorem of calculus and a change of variable
    \begin{align}
    \sqrt{b + c} – \sqrt{a + c} &= \int_{a + c}^{b + c} \frac{1}{2 \sqrt{x}} \, d x = \int_{a}^{b} \frac{1}{2 \sqrt{x + c}} \, d x \\
    &\leq \int_{a}^{b} \frac{1}{2 \sqrt{x}} \, d x = \sqrt{b} – \sqrt{a}.
    \end{align}

  • Squaring the two sides of the inequality, we obtain
    $$
    a + c – 2 \sqrt{a+ c} \, \sqrt{b + c} + b + c \leq a + b – 2 \sqrt{a} \sqrt{b}.
    $$
    Simplifying and rearranging,
    $$
    c + \sqrt{a} \sqrt{b} \leq \sqrt{a+ c} \, \sqrt{b + c} .
    $$
    Squaring again
    $$
    \require{cancel} \cancel{c^2 + a b} + 2 c \sqrt{a b} \leq \cancel{c^2 + ab} + ac + bc,
    $$
    leading to
    $$ a + b – 2 \sqrt{ab} = (\sqrt{b} – \sqrt{a})^2 \geq 0$$.

Numerical experiments suggest that the inequality is true in both the 2 and the Frobenius norm.
(One realization of) the following code prints 0.9998775.

import numpy as np
import scipy.linalg as la

n, d, ratios = 100000, 3, []
for i in range(n):
    A = np.random.randn(d, d)
    B = np.random.randn(d, d)
    C = .1*np.random.randn(d, d)
    A, B, C = A.dot(A.T), B.dot(B.T), C.dot(C.T)
    lhs = la.norm(la.sqrtm(A + C) - la.sqrtm(B + C), ord='fro')
    rhs = la.norm(la.sqrtm(A) - la.sqrtm(B), ord='fro')
    ratios.append(lhs/rhs)

print(np.max(ratios))

Best Answer

Not an answer. I would like to discuss some equivalent problems.

Let $\mathbb{S}^n_{\succeq 0}$ denote the set of $n\times n$ real symmetric positive semi-definite matrices. We have \begin{align} &\|(A+C)^{1/2} - (B+C)^{1/2}\| \le \|A^{1/2} - B^{1/2}\|, \quad \forall A, B, C \in \mathbb{S}^n_{\succeq 0} \tag{1}\\ \Leftrightarrow \quad &\|(A+uu^T)^{1/2} - (B+uu^T)^{1/2}\| \le \|A^{1/2} - B^{1/2}\|, \quad \forall A, B\in \mathbb{S}^n_{\succeq 0}, \quad \forall u\in \mathbb{R}^n\tag{2}\\ \Leftrightarrow \quad &\|(A+\mathrm{diag}(u^Tu, 0, \cdots, 0))^{1/2} - (B+\mathrm{diag}(u^Tu, 0, \cdots, 0))^{1/2}\| \le \|A^{1/2} - B^{1/2}\|, \\ &\qquad \forall A, B\in \mathbb{S}^n_{\succeq 0}, \quad \forall u\in \mathbb{R}^n\tag{3}\\ \Leftrightarrow \quad &\|(A+\mathrm{diag}(1, 0, \cdots, 0))^{1/2} - (B+\mathrm{diag}(1, 0, \cdots, 0))^{1/2}\| \le \|A^{1/2} - B^{1/2}\|,\\ & \qquad \forall A, B\in \mathbb{S}^n_{\succeq 0}.\tag{4} \end{align} Thus, it suffices to prove that $$\|(A+\mathrm{diag}(1, 0, \cdots, 0))^{1/2} - (B+\mathrm{diag}(1, 0, \cdots, 0))^{1/2}\| \le \|A^{1/2} - B^{1/2}\|.$$

Related Question