Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
    
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
show 3 more comments

1 Answer

up vote 5 down vote accepted

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}$

\begin{equation*} Z = A^{-1},\quad M = Z \otimes Z,\quad e=\vect(E)\quad c=\vect(C). \end{equation*}

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*}

share|improve this answer
    
Thanks! This is perfect. –  Paul Christiano Mar 26 '13 at 21:00
    
You're welcome :-) –  Suvrit Mar 26 '13 at 22:00
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.