Frobenius Norm Düzenleme ve Lineer Eşitlik Kısıtlamaları ile Matris Lineer En Küçük Kareleri Çözün

Question

Aşağıdaki kısıtlı minimizasyon problemi nasıl çözülür:$$ \arg_S min_\; \frac{1}{2}\left \{ \left \| K_2SK_1^T-M \right \|_F^2 +\lambda \left \| S \right \|_F^2\right \} \\ s.t. \sum_{1}^{col}S=Sum1 \\ \sum_{1}^{row}S=Sum2 \\ $$nerede$K_1$,$K_2$,$M$ve$S$2d Matrix'tir ve yalnızca$S$bilinmeyen. Kısıtlamalarda,$Sum1$sütunu boyunca toplamıdır$S$, bu bir satır vektörüdür.$Sum2$satırı boyunca toplamıdır$S$, bir sütun vektörüdür.

İşte mat formatında saklanan veriler. Bu tür bir problem nasıl çözülür?

    load('matlab.mat');
%　 min norm( K2*X*K1'-M,'fro')^2+lambda*norm(X,'fro')^2
%   s.t. sum(X,1) = Sum1 ;   sum(X,2) = Sum2;

Answer 1

Buradaki fikir, sorunu şu şekle getirmektir:

$$\begin{aligned} \arg \min_{ \boldsymbol{s} } \quad & \frac{1}{2} {\left\| K \boldsymbol{s} - \boldsymbol{m} \right\|}_{2}^{2} + \frac{\lambda}{2} {\left\| \boldsymbol{s} \right\|}_{2}^{2} \\ \text{subject to} \quad & A \boldsymbol{s} = \boldsymbol{u} \\ \quad & B \boldsymbol{s} = \boldsymbol{v} \end{aligned}$$

Kronecker Ürününü kullanarak şunu görebiliriz:

• $ K = {K}_{1} \otimes {K}_{2} $.
• $ \boldsymbol{s} = \operatorname{vec} \left( S \right) $nerede$ \operatorname{vec} \left( \cdot \right) $vektörleştirme operatörüdür .
• $ \boldsymbol{m} = \operatorname{vec} \left( M \right) $.

matrisler$ A $ve$ B $sadece ilgili öğelerin Seçicileridir$ \boldsymbol{s} $.

Şuna
dikkat edin:$ A $ve$ B $her bir elemanını seçen bir matrisi temsil eder.$ \boldsymbol{s} $ tam olarak bir kez o zaman$ \sum_{i} {u}_{i} = \sum_{i} {v}_{i} $toplamını temsil ettiği için tutmalı$ \boldsymbol{s} $. Yani$ \boldsymbol{1}^{T} A \boldsymbol{s} = \boldsymbol{1}^{T} B \boldsymbol{s} = \sum_{i} {s}_{i} $. Kısıtlamalarınız için durum budur. Dolayısıyla, uygulanabilir bir çözüme sahip olmak için böyle olmalıdır.

Şimdi yukarıdaki, 2 eşitlik kısıtlamasının kesişimine yansıttığımız Projeksiyonlu Gradient Descent tarafından çözülebilen temel bir Dışbükey problemdir .

Matrisleri ve vektörleri birleştirerek daha basit bir şey bile yapabilirsiniz:

$$ C \boldsymbol{s} = \begin{bmatrix} A \\ B \end{bmatrix} \boldsymbol{s} = \boldsymbol{w} = \begin{bmatrix} \boldsymbol{u} \\ \boldsymbol{v} \end{bmatrix} $$

O halde Eşitlik Kısıtlamalı Doğrusal En Küçük Kareler'e çok benzer .

Bu bağlamda ilginç bir kaynak Robert M. Freund - Doğrusal Eşitlik Kısıtlı Problemler için Projeksiyon Yöntemleri'dir .

Answer 2

Zaten MATLAB kullanıyorsunuz, bu yüzden CVX'i kullanmak çok kolay.

cvx_begin
variable S(size(K2,2),size(K1,2))
minimize(0.5*(square_pos(norm(K2*S*K1'-M,'fro'))+lambda*square_pos(norm(S,'fro'))))
sum(S,1) == Sum1
sum(S,2) == Sum2
cvx_end