How to find upper and lower bound

398 Views Asked by At

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$

2

There are 2 best solutions below

3
On

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.

0
On

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