# Bounding the second derivative of the log-determinant

I'm trying to use the log-determinant to regularize an optimization problem. To make the argument work, I need to bound the second derivative of the log-determinant.

I need to prove that $\text{Tr}\left( \left(A^{-1} B\right)^2\right) \geq 1$ whenever:

1. $A$ is positive semidefinite
2. $B$ is symmetric, has zeroes on the diagonal, and has at least one entry which is $\geq 1$.
3. The diagonal entries of $A$ are 1.

From messing around a bit it seems like in fact there are always unit vectors $v, w$ such that $v^T A^{-1} B w \geq 1$---for example, this is true if B has only a single large entry, or if A and B commute. That would imply the conclusion and seems like it should be easy enough to confirm or deny, but I'm stumped.

Any thoughts?

-
By "positive" you mean "positive definite"? –  Robert Israel Mar 25 '13 at 6:41
A is not assumed to be symmetric, is it? –  Pietro Majer Mar 25 '13 at 7:43
A is positive, thus symmetric. The problem is invariant under the $GL(n)$-action $X\mapsto g^T.X g$ for $g\in GL(n)$. Any $g$ is of the form $g=n.a.k$ where $n$ is lower triangular with 1's on the diagonal, $a$ is diagonal with positive entries, and $k$ is orthogonal (Gram-Schmidt or Iwasawa). Choose $a=I$ so to not mess up too much your assumptions. There is an $n$ such that $n^T.A.n$ is diagonal with positive entries. Compute this entries. Check $n^t.B.n$. I hope this helps. –  Peter Michor Mar 25 '13 at 8:32
About the entry of $B$ larger than $1$, is it diagonal ? –  Denis Serre Mar 25 '13 at 9:23
Sorry for the ambiguity, A is positive semidefinite (and symmetric). The large entry of B is not necessarily on the diagonal. Also, note that the claim is easy by rote computation if B has only one large entry. This is the observation that inspired me to try to prove this bound (that, and hope). Peter: I don't see how to use the large entry of B after making such a transformation. Does this translate into some nice property of $n^T B n$ or $g^T B g$? –  Paul Christiano Mar 25 '13 at 18:57

Here is an argument based on convex optimization.

Consider the case where $B$ has a one on the diagonal and the rest of the matrix is arbitrary. Without loss of generality, we can assume that $b_{11}=1$. Thus, we can write the general matrix $B=E+C$, where $E=e_1e_1^T$ with $e_1=(1,0,\ldots,0)$ being the first canonical basis vector, and $C$ is a symmetric matrix with $C_{11}=0$.

(Note: If the entry $\ge 1$ is an off-diagonal, then we can write $B=e_ie_j^T+e_je_i^T$, and run an argument similar to the one below---this one is somewhat more tedious so I did not work it out).

To save on typing, first define the notation: $\DeclareMathOperator{\vect}{vec}$

Then, the trace under question is: \begin{equation*} \mbox{trace}(Z(E+C)Z(E+C)) = e^TMe + c^TMc + 2c^TMe. \end{equation*} Actually, we have $(Kc)^TMc$ as the second term, where $K$ is the commutation matrix, but after some simplifications, it will turn out that we can drop $K$.

Now, we minimize $c^TMc + 2c^TMe$ subject to $c^Te=0$ (and the constraint that $Kc=c$ to ensure symmetry, but this constraint can be eliminated, so I've dropped it).

Introduce the Lagrange multiplier $\nu$ corresponding to the constraint $c^Te=0$, the first-order optimality conditions for this convex optimization problem are: \begin{equation*} 2Mc + 2Me - \nu e = 0,\qquad c^Te=0. \end{equation*}

Thus, we have \begin{eqnarray*} Mc &=& (\nu/2) e - Me\\\\ c &=& (\nu/2) M^{-1}e - e\\\\ &\implies& c^Te = (\nu/2) e^TM^{-1}e - e^Te\\\\ &\implies& \nu=2\qquad\text{since}\ e^TM^{-1}e=1. \end{eqnarray*}

Thus, in particular, an optimum $c$ must satisfy \begin{equation*} c = M^{-1}e - e, \end{equation*} from which it follows that $e^TMc = 1 - e^TMe$ and $c^TMc=0-c^TMe$. Thus, the objective is \begin{equation*} c^TMc + 2c^TMe= c^TMe = 1 - e^TMe, \end{equation*} from it immediately follows that \begin{equation*} \mbox{trace}(Z(E+C)Z(E+C)) = e^TMe + c^TMc + 2c^TMe \ge 1. \end{equation*}

-
Thanks! This is perfect. –  Paul Christiano Mar 26 '13 at 21:00
You're welcome :-) –  Suvrit Mar 26 '13 at 22:00