2
$\begingroup$

I wonder what is the most explicit characterization that can be given for the solution to the ($N$-dimensional) problem of maximizing the criterion

$$ -\textrm{trace}[AS^{-1}] - b^\top Sb $$

over positive semidefinite (symmetric) $S$ is, where $A$ is also positive semidefinite, and nonzero $b \in [0,\infty)^N$.

This arises in a model of choosing to sample some signal with precision $S$ and cost parameterized by $b$. Of course, the solution should nest the scalar solution of $S = \sqrt{A}/b$. Many thanks.

$\endgroup$

1 Answer 1

2
$\begingroup$

$S$ must be positive-definite, not just positive-semidefinite, else $AS^{-1}$ does not exist. Suppose $A$ is positive-definite, and let $A^{1/2}$ be its positive-definite square root. Then the supremum over positive-definite $S$ of $-{\rm tr}(AS^{-1}) - b^\top S b$ is $-2 |A^{1/2}b|$, as in the scalar case. But once $N>1$ the supremum is not attained by any finite $S$.

We have $$ {\rm tr}(AS^{-1}) = {\rm tr}(A^{1/2} A^{1/2} S^{-1}) = {\rm tr}(A^{1/2} S^{-1} A^{1/2}) = {\rm tr}(M^{-1}), $$ where $M$ is the positive-definite matrix $A^{-1/2} S A^{-1/2}$. Then $S = A^{1/2} M A^{1/2}$, so $$ b^\top S b = (A^{1/2} b)^\top M (A^{1/2} b) = v^\top S v $$ where $v = A^{1/2} b$. It will be convenient to choose coordinates so that $v$ is a multiple of the first unit vector. Then $$ -{\rm tr}(AS^{-1}) - b^\top S b = -{\rm tr}(M^{-1}) - \left|v\right|^2 M_{11} $$ (as usual $M_{11}$ is the first diagonal entry of $M$). But for positive-definite $M$ we have $(M^{-1})_{11} \geq M_{11}^{-1}$, with equality iff $M_{1j}=0$ for all $j \neq 1$. Therefore $$ -{\rm tr}(M^{-1}) - \left|v\right|^2 M_{11} < -(M_{11})^{-1} - \left|v\right|^2 M_{11} \leq -2 \left|v\right|. $$ In the last step equality holds iff $M_{11} = \left| v \right|^{-1}$. But $-$ unless $N=1$ $-$ there cannot be equality in the first step, because the diagonal entries $(M^{-1})_{jj}$ for $j \geq 2$ must be positive, though they can be arbitrarily small. We can get within $(N-1)\epsilon$ by making $M^{-1}$ the diagonal matrix ${\rm diag}(\left| v \right|^{-1},\epsilon,\epsilon,\ldots,\epsilon)$ and then recovering $S = A^{1/2} (M^{-1})^{-1} A^{1/2}$ which will be large in all directions except the one measured by ${\rm tr}(AS^{-1})$. If $v=0$ then we can get within $N \epsilon$ of zero by making $(M^{-1})_{11} = \epsilon$, so the formula $-2\left|v\right|$ for the supremum holds in this case too.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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