Suppose we are given $H$, a positive semidefinite $d\times d$matrix. How do I find $k$, the largest $k'$ such that the following holds for all positive semidefinite $C$ with unit trace?
$$k' \operatorname{Tr} H^2 C \le (\operatorname{Tr} H C)^2$$
Earlier discussion shows that $k\ge\frac{\lambda_\text{min}(H)^2}{\lambda_\text{max}(H)^2}$. For the example below, this gives $k \ge 0.01$ where true value is $k\approx 0.330579$. Is there a better bound with a nice closed-form expression?
We can use numerical optimization to find $k$ for specific $H$ like this. For example, suppose
$$\text{H=}\left( \begin{array}{cccc} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 10 \\ \end{array} \right)$$
Then $$k = \frac{40}{121}$$
Realized by the following $C^*$
$$C^*=\left( \begin{array}{cccc} \frac{39}{176} & 0 & 0 & 0 \\ 0 & \frac{7}{16} & 0 & 0 \\ 0 & 0 & \frac{1}{4} & 0 \\ 0 & 0 & 0 & \frac{1}{11} \\ \end{array} \right)$$
Motivation: $k\times d$ gives "critical batch-size" of minibatch SGD for solving linear least-squares problem with Hessian $H$ and optimal error distribution $C=C^*$. Critical batch-size for isotropic error distribution $C=I$ is analyzed here.