How to find upper and lower bound

Question

Let $\Sigma \in S_{++}^n$ be a symmetric positive definite matrix with all diagonal entries equal to one. Let $U \in \mathbb{R}^{n \times k_1}$, $W \in \mathbb{R}^{n \times k_2}$, $\Lambda \in \mathbb{R}^{k_1 \times k_1}$ and $T \in \mathbb{R}^{k_2 \times k_2}$, where $\Lambda$ and $T$ are both diagonal matrices with positive elements, and $n > k_2 > k_1$. We also know $\text{trace}(\mathbf{\Lambda}) = \mu \times \text{trace}(\mathbf{T})$, and the sum of the absolute values of all the elements of $U$ is less than $W$. Then how can I find upper and lower bounds on

\begin{align*} \frac{\|\Sigma - UTU^\top\|_F^2}{\|\Sigma - W\Lambda W^\top\|_F^2} \end{align*}

in terms of $\mu$, $W$, $\Lambda$ and $\Sigma$?

Answer 1

We first find an upper bound on $\|UTU^\top \|_F^2$ in terms of $W$ and $\Lambda$-

\begin{align*} \|UTU^\top \|_F^2 &\leq \| U\|_F^4 \|T \|_F^2 \\ & \leq \frac{1}{\mu} \| W\|_F^4 \|\Lambda \|_F^2 \\ \end{align*}

Now, assuming that $\|\Sigma \|_F^2 \geq \| UTU^\top \|_F^2$ and $\|\Sigma \|_F^2 \geq \| W\Lambda W^\top \|_F^2$

\begin{align*} \|\Sigma\|_F^2 - \| UTU^\top \|_F^2 \leq \|\Sigma - UTU^\top \|_F^2 \leq \|\Sigma \|_F^2+\| UTU^\top \|_F^2 \\ \|\Sigma\|_F^2 - \frac{1}{\mu} \| W\|_F^4 \|\Lambda \|_F^2 \leq \|\Sigma - UTU^\top \|_F^2 \leq \|\Sigma \|_F^2+\frac{1}{\mu} \| W\|_F^4 \|\Lambda \|_F^2 \\ \Rightarrow \frac{\|\Sigma\|_F^2 - \frac{1}{\mu} \| W\|_F^4 \|\Lambda \|_F^2}{\|\Sigma - W\Lambda W^\top \|_F^2} \leq \frac{\|\Sigma - UTU^\top \|_F^2}{{\|\Sigma - W\Lambda W^\top \|_F^2}} \leq \frac{\|\Sigma \|_F^2+\frac{1}{\mu} \| W\|_F^4 \|\Lambda \|_F^2}{{\|\Sigma - W\Lambda W^\top \|_F^2}} \\ \Rightarrow \frac{\|\Sigma\|_F^2 - \frac{1}{\mu} \| W\|_F^4 \|\Lambda \|_F^2}{\|\Sigma\|_F^2 + \|W\Lambda W^\top \|_F^2} \leq \frac{\|\Sigma - UTU^\top \|_F^2}{{\|\Sigma - W\Lambda W^\top \|_F^2}} \leq \frac{\|\Sigma \|_F^2+\frac{1}{\mu} \| W\|_F^4 \|\Lambda \|_F^2}{{\|\Sigma\|_F^2 - \|W\Lambda W^\top \|_F^2}} \\ \end{align*} Assume that $c\|\Sigma \|_F^2 = \| W\Lambda W^\top \|_F^2$ where $0 \leq c\leq 1$, we get

\begin{align*} \frac{\|\Sigma\|_F^2 - \frac{1}{\mu} \| W\|_F^4 \|\Lambda \|_F^2}{(1+c)\|\Sigma\|_F^2 } \leq \frac{\|\Sigma - UTU^\top \|_F^2}{{\|\Sigma - W\Lambda W^\top \|_F^2}} \leq \frac{\|\Sigma \|_F^2+\frac{1}{\mu} \| W\|_F^4 \|\Lambda \|_F^2}{{(1-c)\|\Sigma\|_F^2 }} \\ \end{align*} As $W$, $\Lambda$ and $\Sigma$ are fixed, let $\frac{\|W \|_F^4 \| \Lambda\|_F^2}{\|\Sigma \|_F^2} = t$, then we have \begin{align*} \frac{1 - \frac{t}{\mu}}{(1+c) } \leq \frac{\|\Sigma - UTU^\top \|_F^2}{{\|\Sigma - W\Lambda W^\top \|_F^2}} \leq \frac{1 + \frac{t}{\mu}}{(1-c) } \\ \end{align*}