Üst ve alt sınır nasıl bulunur

Question

İzin Vermek $\Sigma \in S_{++}^n$tüm çapraz girişler bir olan simterik pozitif tanımlı bir matris olun. İzin Vermek$U \in R^{n \times k_1}$, $W \in R^{n \times k_2}$, $\Lambda \in R^{k_1 \times k_1}$ ve $T \in R^{k_2 \times k_2}$, nerede $\Lambda$ ve $T$ her ikisi de pozitif öğeler içeren köşegen matristir ve $n > k_2 > k_1$. Biz de biliyoruz$\text{trace}(\mathbf{\Lambda}) = \mu \times \text{trace}(\mathbf{T})$ ve tüm öğelerinin mutlak değerlerinin toplamı $U$ daha az $W$. O zaman üst ve alt sınırları nasıl bulabilirim?

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

açısından $\mu$, $W$, $\Lambda$ ve $\Sigma$. Varsayalım ki$\|\Sigma \|_F^2 \geq \|UTU^\top \|_F^2$ ve $\| \Sigma\|_F^2 \geq \|W\Lambda W^\top \|_F^2$

Answer 1

Bu yüzden fonksiyonun aşırı uçlarını arayacağız

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

Paydanın fonksiyonun parametreleri tarafından tamamen tanımlandığını not ediyoruz, bu yüzden optimizasyon amacıyla sadece bir sabittir, hadi onu arayalım $K$. Ayrıca, bunu açıkça ekleyebiliriz$T$ köşegendir, yani $T_{ij} = t_i \delta_{ij}$. Bir optimizasyon problemini şu şekilde yazabiliriz: L2 normunu bazı farklılıkların maksimize et veya minimize et

$$ 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 $$

kısıtlamalara tabidir:

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

ve

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

nerede $\alpha$ ve $\beta$ bilinen sabitlerdir.

Bu sorun, ek bir eşitlik kısıtlamasıyla etkin bir şekilde Kement düzenlemesidir. AFAIK, bu türden düzenlilik problemleri tipik olarak sayısal olarak çözülür, bu da açık analitik çözümlerin mevcut olmadığı anlamına gelir.

Answer 2

Önce bir üst sınır buluruz $\|UTU^\top \|_F^2$ açısından $W$ ve $\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*}

Şimdi varsayarsak $\|\Sigma \|_F^2 \geq \| UTU^\top \|_F^2$ ve $\|\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*} Varsayalım ki $c\|\Sigma \|_F^2 = \| W\Lambda W^\top \|_F^2$ nerede $0 \leq c\leq 1$, anlıyoruz

\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*} Gibi $W$, $\Lambda$ ve $\Sigma$ düzeltildi $\frac{\|W \|_F^4 \| \Lambda\|_F^2}{\|\Sigma \|_F^2} = t$o zaman bizde \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*}