Is $\text{Tr}\left( (X^T X )^{-1} \right)$ convex in $X$?

Question

Let $X\in \mathbb{R}^{n \times n}$. Then, is the function

$$ \text{Tr}\left( (X^T X )^{-1} \right)$$

convex in $X$? ($\text{Tr}$ denotes the trace operator)

Answer 1

The previous answer is unfortunately not complete due to a nontrivial sign mistake. In fact, even the local convexity result does not hold in this case. To see the obstruction, let $X$ be an invertible matrix, $V$ arbitrary, and compute $$ (X + t\,V)^\intercal(X+t\,V) = X^\intercal X + t(V^\intercal X + X^\intercal V) + t^2\,V^\intercal V := S^{-2} + t\,Z + t^2\,V^\intercal V,$$ where $S^2 = (A^\intercal A)^{-1}$ is positive definite and $Z=Z^\intercal$. Then, series expansion yields \begin{equation} \begin{split} \left((X+t\,V)^{\intercal}(X+t\,V)\right)^{-1} &= \left(S^{-1}\left(I + t\,SZS + t^2\,SV^\intercal VS\right)S^{-1}\right)^{-1} \\ &= S\left(I + t\,SZS + t^2\,SV^\intercal VS\right)^{-1}S \\ &= S\left(I + t\left(SZS + t\,SV^\intercal VS\right)\right)^{-1}S \\ &= S\left(I - t\left(SZS + t\,SV^\intercal VS\right) + t^2\left(SZS + t\,SV^\intercal VS\right)^2 + \mathcal{O}(t^3)\right)S \\ &= S\left(I - t\,SZS + t^2\left(SZS^2ZS - SV^\intercal VS\right)\right)S + \mathcal{O}(t^3). \end{split} \end{equation} Notice the minus sign in the $\mathcal{O}(t^2)$ term, so that positive semidefiniteness is no longer obvious. On the other hand, \begin{equation} \begin{split} ZS^2Z - V^\intercal V &= \left(V^\intercal X + X^\intercal V\right)X^{-1}X^{-\intercal}\left(V^\intercal X + X^\intercal V\right) \\ &= \left(X^\intercal(VX^{-1}V) + (VX^{-1}V)^\intercal X\right) + (X^\intercal VX^{-1})(X^\intercal VX^{-1})^\intercal \\ &:= A + BB^\intercal. \end{split} \end{equation} Therefore, by linearity of the trace, we have \begin{equation} \begin{split} \frac{d^2}{dt^2}\bigg|_{t=0}\mathrm{tr}\left(\left((X+t\,V)^{\intercal}(X+t\,V)\right)^{-1}\right) &= 2\,\mathrm{tr}\left(S^2(A+BB^\intercal)S^2\right) \\ &= 2\,\mathrm{tr}\left(S^2AS^2\right) + 2\,\mathrm{tr}\left((S^2B)(S^2B)^\intercal\right), \end{split} \end{equation} and it remains to see if this is nonnegative. The second term is obviously nonnegative since $BB^\intercal$ is positive semidefinite. However, we compute $$ S^2 A S^2 = S^2\left((X^{-1}V)^2\right)^\intercal + (X^{-1}V)^2 S^2 = X^{-1}\left(\left(VX^{-1}VX^{-1}\right)^\intercal + VX^{-1}VX^{-1}\right)X^{-\intercal}, $$ which is clearly symmetric, but not necessarily positive semidefinite. Interestingly, using that $S^2B = X^{-1}VX^{-1}$ we can write $$ S^2AS^2 + (S^2B)(S^2B)^\intercal = X^{-1}\left((VX^{-1}VX^{-1})^\intercal + VX^{-1}VX^{-1} + (VX^{-1})(VX^{-1})^\intercal\right)X^{-\intercal}, $$ where the term in parentheses is one term away from $(C + C^\intercal)^2$ for $C = VX^{-1}$. So, it is conceivable that the trace of all this could be nonnegative, but in fact it is generally not. One counterexample is afforded by the matrices $$ X= \begin{pmatrix}0.9 & 0.85 \\ 0.37 & 0.2\end{pmatrix}, \quad V= \begin{pmatrix}0.08 & 0.34 \\ 0.66 & 0.77\end{pmatrix}. $$ Computing $\mathrm{tr}\left(\left[(X+t\,V)^{\intercal}(X+t\,V)\right]^{-1}\right)$ symbolically on the Wolfram Cloud and plotting the result yields the following:

Which is concave around $t=0$. Hence, the function in the OP cannot be convex at all, despite the fact that it is a composition of convex functions.

Answer 2

As pointed out in the above by user "1015" (who keeps changing his username ^_^ ), the set of all invertible matrices is not convex. Therefore your question does not make sense. However, $\operatorname{tr}\left((X^TX)\right)^{-1}$ is locally convex at every invertible matrix $X$ and this can be proved using the trick demonstrated in another thread by Robert Israel.

Let $S$ be the unique positive definite square root of $(X^TX)^{-1}$. Let $H\in M_n(\mathbb{R})$. We want to show that the function $f(t)=\operatorname{tr}\left\{\left[(X+tH)^T(X+tH)\right]^{-1}\right\}$ is locally convex at $t=0$. Now, \begin{align*} &\left[ (X+tH)^T (X+tH) \right]^{-1}\\ =&\left[ X^TX + t(H^TX+X^TH) + t^2H^TH \right]^{-1}\\ =&\left[ S^{-2} + t(H^TX+X^TH) + t^2H^TH \right]^{-1}\\ =&S \left[ I + t S(H^TX+X^TH)S + t^2 SH^THS \right]^{-1} S\\ =&S \left[ I + t \left(S(H^TX+X^TH)S + t SH^THS\right) \right]^{-1} S\\ =&S \left[ I + t \left(S(H^TX+X^TH)S + t SH^THS\right) + t^2 \left(S(H^TX+X^TH)S + t SH^THS\right)^2 \right] S + O(t^3). \end{align*} Therefore, the second order term is equal to $$ S \left[ SH^THS + \left(S(H^TX+X^TH)S\right)^2 \right] S $$ which is positive semidefinite. Hence its trace (i.e. $f''(0)$) is nonnegative and $f$ is locally convex at $t=0$.