Estimating the following ratio: $\frac{\sup_{A \succeq 0 : \, \mathrm{tr}(A) \leq 1} f(A)}{\sup_{a :\, \|a\|_2 \leq 1} f(aa^T)}$?

Question

Let $B$ be a positive semidefinite matrix and let $x$ be a fixed nonzero vector.

For any positive semidefinite matrix $A$, define $$ f(A) = x^TA(A + ABA)^\dagger A x $$ Above $P^\dagger$ denotes the Moore Penrose pseudoinverse of $P$.

I want to calculate (or estimate) the ratio $$ R(x, B) := \frac{\sup_{A \succeq 0 :\, \mathrm{tr}(A) \leq 1} f(A)}{\sup_{a :\, \left\|a\right\|_2 \leq 1} f(aa^T)} $$ Evidently, the ratio is at least $1$, since $aa^T$ has trace at most $1$ when $\left\|a\right\|_2 \leq 1$.

There is one case where we can see this holds:

• For the special case $B = I$, this is easily checked directly, and we can see that the ratio is equal to 1. Indeed, in this case, we have with eigendecomposition $A = \sum_{j=1}^d \lambda_j u_j u_j^T$, $$ f(A) = x^TA(A + A^2)^\dagger A x = \sum_{j=1}^d (x^T u_j)^2 \frac{\lambda_j}{1 + \lambda_j} \leq \|x\|_2^2/2. $$ since $\lambda/(1+\lambda) \leq 1/2$ for $\lambda \in [0, 1]$. Moreover, this upper bound is attained at $A = xx^T/\|x\|_2^2$. Since this is a symmetric, rank-one matrix, we see that the ratio is indeed equal to $1$ for $B = I$.

I am not sure how to generalize this argument to non-identity $B$.

Answer 1

Let us prove that $$\sup_{A \succeq 0 :\, \mathrm{tr}(A) \leq 1} f(A) = \sup_{\|a\|_2\le1}f(aa^T). \tag{1}$$

First, clearly we have $$\sup_{A \succeq 0 :\, \mathrm{tr}(A) \leq 1} f(A) \ge \sup_{\|a\|_2\le1}f(aa^T). \tag{2}$$

Second, let us prove that if $\mathrm{rank}(A) \ge 2$, then $$f(A) \le \sup_{\|a\|_2\le1}f(aa^T). \tag{3}$$

1. We have $$f(A) = x^T (I + AB)^{-1}A x. \tag{4}$$ (The proof is easy.)

2. Let us prove that $$(I + B)^{-1} \succeq (I + AB)^{-1} A. \tag{5}$$

We use continuity argument. For $t > 0$, we have $$(I + (A + tI)B)^{-1} (A + tI) = ((A + tI)^{-1} + B)^{-1}.$$

Since $\mathrm{rank}(A) \ge 2$, there exist $t_0 > 0$ such that $I - (A + tI)$ is PD for all $0 < t < t_0$. Thus, $(I + tA)^{-1} - I$ is PD for all $0 < t < t_0$. Thus, $(I + B)^{-1} \succeq ((A + tI)^{-1} + B)^{-1}$ for all $0 < t < t_0$. Thus, $(I + B)^{-1} \succeq (I + (A + tI)B)^{-1} (A + tI)$ for all $0 < t < t_0$. Taking $t\to 0$, we have $(I + B)^{-1} \succeq (I + AB)^{-1} A$.

From (4) and (5), we have $$f(A) \le x^T(I + B)^{-1} x. \tag{6}$$

3. Using (4), we have $$f(aa^T) = x^T (I + aa^TB)^{-1}aa^T x = \frac{(x^Ta)^2}{1 + a^TBa}.$$

We have $$\sup_{\|a\|_2\le1}\frac{(x^Ta)^2}{1+a^TBa} = \sup_{a\ne 0, ~\|a\|_2\le1}\frac{(x^Ta)^2}{a^Ta+a^TBa}. \tag{7}$$ (Proof: First, we have $\mathrm{LHS} \le \mathrm{RHS}$ since $\frac{(x^Ta)^2}{1+a^TBa} \le \frac{(x^Ta)^2}{a^Ta+a^TBa}$. Second, note that $\frac{(x^Ta)^2}{a^Ta+a^TBa}$ is homogeneous. Thus, we can find $b$ with $b^Tb = 1$ such that $\sup_{a\ne 0, ~\|a\|_2\le1}\frac{(x^Ta)^2}{a^Ta+a^TBa} = \frac{(x^Tb)^2}{b^Tb+b^TBb} = \frac{(x^Tb)^2}{1+b^TBb} \le \mathrm{LHS}$. We are done.)

Thus, we have $$\sup_{\|a\|_2\le1}f(aa^T) = \sup_{a\ne 0, ~\|a\|_2\le1}\frac{(x^Ta)^2}{a^Ta+a^TBa} = x^T(I + B)^{-1}x. \tag{8}$$

4. From (6) and (8), we have (3).

From (2) and (3), we have (1).

We are done.

Answer 2

For any Hermitian matrix $S$, denote by $\Pi_S$ the orthogonal projection matrix onto $\operatorname{range}(S)$. Note that $A(A+ABA)^+A=A^{1/2}\left(I+A^{1/2}BA^{1/2}\right)^{-1}A^{1/2}$ because $$ \begin{aligned} &(I+AB)A(A+ABA)^+A\\ &=(A+ABA)(A+ABA)^+A\\ &=\Pi_{A+ABA}A\\ &=A\\ &=A^{1/2}\left(I+A^{1/2}BA^{1/2}\right)\left(I+A^{1/2}BA^{1/2}\right)^{-1}A^{1/2}\\ &=(I+AB)A^{1/2}\left(I+A^{1/2}BA^{1/2}\right)^{-1}A^{1/2}. \end{aligned} $$ Therefore $$ \begin{aligned} f(A) &=x^TA^{1/2}\left(I+A^{1/2}BA^{1/2}\right)^{-1}A^{1/2}x\\ &\le x^TA^{1/2}\left(I+\lambda_\min(B)A\right)^{-1}A^{1/2}x\\ &\le \left\|A^{1/2}\left(I+\lambda_\min(B)A\right)^{-1}A^{1/2}\right\|_2\|x\|_2^2\\ &=\frac{\lambda_\max(A)\|x\|_2^2}{1+\lambda_\min(B)\lambda_\max(A)}\\ &\le\frac{\|x\|_2^2}{1+\lambda_\min(B)},\\ \end{aligned} $$ where the last inequality is due to the fact that $\lambda_\max(A)\le\operatorname{tr}(A)\le1$. Similarly, we also have $$ \sup_{\|a\|_2\le1}f(aa^T) =\sup_{\|a\|_2\le1}\frac{(x^Ta)^2}{1+a^TBa} \ge\sup_{\|a\|_2\le1}\frac{(x^Ta)^2}{1+\lambda_\max(B)\|a\|_2^2} =\frac{\|x\|_2^2}{1+\lambda_\max(B)}. $$ It follows that $$ \frac{\sup_{A\succeq0,\,\operatorname{tr}(A)\le1}f(A)}{\sup_{\|a\|_2\le1}f(aa^T)} \le\frac{1+\lambda_\max(B)}{1+\lambda_\min(B)}. $$ I have a feeling that the ratio in question is equal to $1$, but am not able to prove it.

Answer 3

This answer is not complete and prove only that $f$ is concave.

Let assume that, $B\succ 0$ and let $D = B^{-1}$ then it is easy to prove that:

$$f(A) = x^\intercal \left(A - A\left(D + A\right)^{-1}A\right)x$$

Indeed if $A$ is invertible, then by this,

$$A\left(A + ABA\right)^{+}A = A\left(A + ABA\right)^{-1}A = A - A\left(D+A\right)^{-1}A$$

and if $A\succeq 0$ apply it for $A + \varepsilon I$ and $\varepsilon \to 0$.

Now fix $X, Y \succeq 0$ and let $Z(t) = (1-t)X+tY$,

$$\varphi(t) = f(Z(t))$$

It is not hard to prove that:

\begin{align} \varphi''(t) &= -2 x^\intercal\left(Z' (D+Z)^{-1}Z' -2Z(D+Z)^{-1}Z'(D+Z)^{-1} + Z(D+Z)^{-1}Z'(D+Z)^{-1}Z'(D+Z)^{-1}Z\right)x\\ &= -2\left\|(D+Z)^{-\frac12}\left(Z' - (D+Z)^{-1} Z\right)x\right\|^2 \le 0 \end{align}

This proves that $f$ is concave.