Let $h, \tilde{h} \in \mathcal{H}$ be two discrete random variables that take values from the finite space $\mathcal{H}$. Also let $N = |\mathcal{H}|$ be the cardinality of $\mathcal{H}$. Let $p(h_j)$ denote the probability of $h_j$ and $p(h_j|{\tilde{h}}_i)$ be the probability of $h_j$ given $\tilde{h}_i$.
I want to show (or find a counter example) that the matrix $\boldsymbol{S}_i$, defined as: \begin{equation} \boldsymbol{S}_i = \boldsymbol{D}_i - \boldsymbol{u}_i \boldsymbol{u}^T_i \end{equation} is positive semi-definite $\forall i$, where $\boldsymbol{D}_i = \text{diag}\left(\frac{p(h_1)}{p(\tilde{h}_i|h_1)}, \frac{p(h_2)}{p(\tilde{h}_i|h_2)}, \dots, \frac{p(h_N)}{p(\tilde{h}_i|h_N)}\right)$, and $\boldsymbol{u}_i = \frac{1}{\sqrt{p(\tilde{h}_i)}}\left[p(h_1), p(h_2), \dots, p(h_N) \right]^T$
I tried to prove that $\boldsymbol{x}^T \boldsymbol{S}_i \boldsymbol{x} \geq 0$ $\forall \boldsymbol{x} \in \mathbb{R}^N$, which resulted in the following inequality
\begin{equation} \sum_{j = 1}^N x_j^2 \frac{p^2(h_j)}{p(h_j|\tilde{h}_i)} \geq \left( \sum_{j = 1}^N x_j p(h_j)\right)^2 \end{equation} but I still couldn't show that this inequality holds. I tried several numerical examples and it seems to hold but I'm struggling to come up with a proof.
For completeness, I will derive the above inequality. \begin{align} \boldsymbol{x}^T \boldsymbol{S}_i \boldsymbol{x} &= \boldsymbol{x}^T \left( \boldsymbol{D}_i - \boldsymbol{u}\boldsymbol{u}^T \right) \boldsymbol{x}\\ &= \boldsymbol{x}^T \boldsymbol{D}_i \boldsymbol{x} - \boldsymbol{x}^T \boldsymbol{u}\boldsymbol{u}^T \boldsymbol{x}\\ &= \boldsymbol{x}^T \boldsymbol{D}_i \boldsymbol{x} - (\boldsymbol{x}^T \boldsymbol{u})^2\\ &= \sum_{j=1}^N x_j^2 \frac{p(h_j)}{p(\tilde{h}_i|h_j)} - \left(\sum_{j=1}^N x_j \frac{p(h_j)}{\sqrt{p(\tilde{h}_i)}}\right)^2\\ &= \sum_{j=1}^N x_j^2 \frac{p(h_j)}{\frac{p(h_j|\tilde{h}_i)p(\tilde{h}_i)}{p(h_j)}} - \frac{1}{p(\tilde{h_i})} \left(\sum_{j=1}^N x_j p(h_j)\right)^2\\ &= \frac{1}{p(\tilde{h_i})} \sum_{j=1}^N x_j^2 \frac{p^2(h_j)}{p(h_j|\tilde{h}_i)} - \frac{1}{p(\tilde{h_i})} \left(\sum_{j=1}^N x_j p(h_j)\right)^2. \end{align} Thus, $\boldsymbol{x}^T \boldsymbol{S}_i \boldsymbol{x} \geq 0$ is equivalent to \begin{align} \frac{1}{p(\tilde{h_i})} \sum_{j=1}^N x_j^2 \frac{p^2(h_j)}{p(h_j|\tilde{h}_i)} - \frac{1}{p(\tilde{h_i})} \left(\sum_{j=1}^N x_j p(h_j)\right)^2 &\geq 0 \\ \Longleftrightarrow \sum_{j=1}^N x_j^2 \frac{p^2(h_j)}{p(h_j|\tilde{h}_i)} - \left(\sum_{j=1}^N x_j p(h_j)\right)^2 &\geq 0 \quad\quad\quad\quad\quad \longrightarrow (1) \end{align}
Now set $a_j = \frac{x_j p(h_j)}{\sqrt{p(h_j|\tilde{h}_i)}}$, and set $b_j = \sqrt{p(h_j|\tilde{h}_i)}$. Then, by Cauchy Schwartz inequality, we have that \begin{equation} \left( \sum_{j=1}^N a_j^2\right) \cdot \left( \sum_{j=1}^N b_j^2\right) \geq \left( \sum_{j=1}^N a_j \cdot b_j\right)^2 \end{equation} which gives us \begin{equation} \left( \sum_{j=1}^N \left(\frac{x_j p(h_j)}{\sqrt{p(h_j|\tilde{h}_i)}}\right)^2\right) \cdot \left( \sum_{j=1}^N \left( \sqrt{p(h_j|\tilde{h}_i)}\right)^2\right) \geq \left( \sum_{j=1}^N \frac{x_j p(h_j)}{\sqrt{p(h_j|\tilde{h}_i)}} \cdot \sqrt{p(h_j|\tilde{h}_i)} \right)^2 \end{equation} \begin{equation} \Longleftrightarrow \left( \sum_{j=1}^N \frac{x_j^2 p^2(h_j)}{p(h_j|\tilde{h}_i)}\right) \cdot \underbrace{\left( \sum_{j=1}^N p(h_j|\tilde{h}_i)\right)}_{ = 1} \geq \left( \sum_{j=1}^N x_j p(h_j) \right)^2 \end{equation} Hence, (1) follows.