# How to find upper and lower bound

Let $$\Sigma \in S_{++}^n$$ be a symmteric positive definte matrix with all diagonal entries one. Let $$U \in R^{n \times k_1}$$, $$W \in R^{n \times k_2}$$, $$\Lambda \in R^{k_1 \times k_1}$$ and $$T \in R^{k_2 \times k_2}$$, where $$\Lambda$$ and $$T$$ are both diagonal matrix with positive elements, and $$n > k_2 > k_1$$. We also know $$\text{trace}(\mathbf{\Lambda}) = \mu \times \text{trace}(\mathbf{T})$$ and sum of absolute values of all the elements of $$U$$ is less than $$W$$. Then how can I find upper and lower bound 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$$. Assume that $$\|\Sigma \|_F^2 \geq \|UTU^\top \|_F^2$$ and $$\| \Sigma\|_F^2 \geq \|W\Lambda W^\top \|_F^2$$

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

So we will search for extremes of the function

$$f(\mu, W, \Lambda, \Sigma) = \frac{\|\Sigma - UTU^\top\|_F^2}{\|\Sigma - W\Lambda W^\top\|_F^2}$$

We note that the denominator is fully defined by the parameters of the function, so for the purposes of optimization it is just a constant, let's call it $$K$$. Also, we can explicitly insert that $$T$$ is diagonal, namely $$T_{ij} = t_i \delta_{ij}$$. We can write an optimization problem as follows: Maximize or minimize the L2 norm of some difference

$$f(\mu, W, \Lambda, \Sigma) = \frac{1}{K} \sum_{ij} \biggl(\Sigma_{ij} - \sum_k t_kU_{ik}U_{kj} \biggr)^2 \rightarrow \max or \min$$

subject to constraints:

$$\sum_i t_i = \frac{1}{\mu} \sum_i \Lambda_{ii} = \alpha$$

and

$$|U|_1 < |W|_1 = \beta$$

where $$\alpha$$ and $$\beta$$ are known constants.

This problem is effectively Lasso regularization with an additional equality constraint. AFAIK, regularization problems of this kind typically are solved numerically, which means that explicit analytical solutions are not available.

• I am looking for upper and lower bound which can be found analytically, and the bounds need to be super strict. Commented Oct 20, 2020 at 17:14
• @DushyantSahoo I see. I am sorry, I misunderstood the question. I wrongly assumed that the goal was to find the maximum and minimum value, which is much more strict than an upper or a lower bound. Commented Oct 20, 2020 at 20:15
• No worries, I wrote a solution, but I am not sure how correct it is. Commented Oct 20, 2020 at 22:23