フロベニウスノルム正則化と線形不等式制約を使用して行列線形最小二乗法を解く

Question

次の制約付き最小化問題を解決する方法： $$ \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 \\ $$ どこ $K_1$、$K_2$、$M$ そして $S$ 2Dマトリックスであり、 $S$不明です。制約では、$Sum1$ の列に沿った合計です $S$、これは行ベクトルです。 $Sum2$ の行に沿った合計です $S$、これは列ベクトルです。

これがマット形式で保存されたデータです。この種の問題を解決するにはどうすればよいですか？

    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

アイデアは、問題を次の形式にすることです。

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

クロネッカー積を使用すると、次のことがわかります。

• $ K = {K}_{1} \otimes {K}_{2} $。
• $ \boldsymbol{s} = \operatorname{vec} \left( S \right) $ どこ $ \operatorname{vec} \left( \cdot \right) $はベクトル化演算子です。
• $ \boldsymbol{m} = \operatorname{vec} \left( M \right) $。

行列 $ A $ そして $ B $の対応する要素の単なるセレクターです$ \boldsymbol{s} $。

備考
注意してください$ A $ そして $ B $ の各要素を選択する行列を表します $ \boldsymbol{s} $ 正確に一度、その後$ \sum_{i} {u}_{i} = \sum_{i} {v}_{i} $ の合計を表すため、保持する必要があります $ \boldsymbol{s} $。つまり、$ \boldsymbol{1}^{T} A \boldsymbol{s} = \boldsymbol{1}^{T} B \boldsymbol{s} = \sum_{i} {s}_{i} $。これはあなたの制約の場合です。したがって、実行可能な解決策を得るには、そのようなものでなければなりません。

上記は基本的な凸問題であり、2つの等式制約の交点に射影する最急降下法によって解決できます。

行列とベクトルを連結することで、もっと簡単なことをすることもできます。

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

次に、等式制約のある線形最小二乗法と非常によく似ています。

その点に関する興味深いリソースは、Robert M.Freund-線形不等式制約付き問題の射影法です。

Answer 2

すでにMATLABを使用しているので、CVXを使用するのは簡単です。

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