Cách tìm cận trên và cận dưới
Để cho $\Sigma \in S_{++}^n$là một ma trận khử liên kết dương tổng hợp với tất cả các mục đường chéo là một. Để cho$U \in R^{n \times k_1}$, $W \in R^{n \times k_2}$, $\Lambda \in R^{k_1 \times k_1}$ và $T \in R^{k_2 \times k_2}$, Ở đâu $\Lambda$ và $T$ đều là ma trận đường chéo có các phần tử dương và $n > k_2 > k_1$. Chúng tôi cũng biết$\text{trace}(\mathbf{\Lambda}) = \mu \times \text{trace}(\mathbf{T})$ và tổng các giá trị tuyệt đối của tất cả các phần tử của $U$ ít hơn $W$. Sau đó, làm thế nào tôi có thể tìm thấy giới hạn trên và giới hạn dưới trên-
\begin{align*} \frac{\|\Sigma - UTU^\top\|_F^2}{\|\Sigma - W\Lambda W^\top\|_F^2} \end{align*}
về mặt $\mu$, $W$, $\Lambda$ và $\Sigma$. Giả định rằng$\|\Sigma \|_F^2 \geq \|UTU^\top \|_F^2$ và $\| \Sigma\|_F^2 \geq \|W\Lambda W^\top \|_F^2$
Trả lời
Vì vậy, chúng tôi sẽ tìm kiếm các điểm cực trị của hàm
$$ f(\mu, W, \Lambda, \Sigma) = \frac{\|\Sigma - UTU^\top\|_F^2}{\|\Sigma - W\Lambda W^\top\|_F^2} $$
Chúng tôi lưu ý rằng mẫu số được xác định đầy đủ bởi các tham số của hàm, vì vậy với mục đích tối ưu hóa, nó chỉ là một hằng số, hãy gọi nó là $K$. Ngoài ra, chúng tôi có thể chèn rõ ràng rằng$T$ là đường chéo, cụ thể là $T_{ij} = t_i \delta_{ij}$. Chúng ta có thể viết một bài toán tối ưu hóa như sau: Tối đa hóa hoặc giảm thiểu định mức L2 của một số chênh lệch
$$ 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 $$
tuân theo các ràng buộc:
$$\sum_i t_i = \frac{1}{\mu} \sum_i \Lambda_{ii} = \alpha$$
và
$$|U|_1 < |W|_1 = \beta$$
Ở đâu $\alpha$ và $\beta$ là các hằng số đã biết.
Vấn đề này có hiệu quả là chính quy hóa Lasso với một ràng buộc bình đẳng bổ sung. AFAIK, các vấn đề về quy định của loại này thường được giải quyết bằng số, có nghĩa là không có các giải pháp phân tích rõ ràng.
Đầu tiên chúng tôi tìm thấy một giới hạn trên $\|UTU^\top \|_F^2$ về mặt $W$ và $\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*}
Bây giờ, giả sử rằng $\|\Sigma \|_F^2 \geq \| UTU^\top \|_F^2$ và $\|\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*} Giả định rằng $c\|\Sigma \|_F^2 = \| W\Lambda W^\top \|_F^2$ Ở đâu $0 \leq c\leq 1$, chúng tôi nhận được
\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*} Như $W$, $\Lambda$ và $\Sigma$ được sửa chữa, hãy để $\frac{\|W \|_F^4 \| \Lambda\|_F^2}{\|\Sigma \|_F^2} = t$, sau đó chúng tôi có \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*}