Lösen Sie lineare Kleinste-Quadrate-Matrizen mit Frobenius-Norm-Regularisierung und linearen Gleichheitsbeschränkungen
So lösen Sie das folgende eingeschränkte Minimierungsproblem:$$ \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 \\ $$wo$K_1$,$K_2$,$M$und$S$sind 2d Matrix, und nur$S$ist unbekannt. In den Einschränkungen,$Sum1$ist die Summe entlang der Spalte von$S$, was ein Zeilenvektor ist.$Sum2$ist die Summe entlang der Reihe von$S$, was ein Spaltenvektor ist.
Hier sind die Daten im Mat-Format gespeichert. Wie kann man diese Art von Problem lösen?
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;
Antworten
Die Idee ist, das Problem in die Form zu bringen:
$$\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}$$
Mit dem Kronecker-Produkt können wir Folgendes sehen:
- $ K = {K}_{1} \otimes {K}_{2} $.
- $ \boldsymbol{s} = \operatorname{vec} \left( S \right) $wo$ \operatorname{vec} \left( \cdot \right) $ist der Vektorisierungsoperator .
- $ \boldsymbol{m} = \operatorname{vec} \left( M \right) $.
Die Matrizen$ A $und$ B $sind nur Selektoren der entsprechenden Elemente in$ \boldsymbol{s} $.
Bemerkung
Achten Sie darauf, dass if$ A $und$ B $stellen eine Matrix dar, die jedes Element von auswählt$ \boldsymbol{s} $ dann genau einmal$ \sum_{i} {u}_{i} = \sum_{i} {v}_{i} $muss gelten, da es die Summe von darstellt$ \boldsymbol{s} $. Nämlich$ \boldsymbol{1}^{T} A \boldsymbol{s} = \boldsymbol{1}^{T} B \boldsymbol{s} = \sum_{i} {s}_{i} $. Dies ist der Fall für Ihre Einschränkungen. Also muss es so sein, um eine praktikable Lösung zu haben.
Das Obige ist nun ein grundlegendes konvexes Problem, das durch Projected Gradient Descent gelöst werden kann, wobei wir auf den Schnittpunkt der beiden Gleichheitsbeschränkungen projizieren .
Sie könnten sogar etwas Einfacheres tun, indem Sie die Matrizen und Vektoren verketten:
$$ C \boldsymbol{s} = \begin{bmatrix} A \\ B \end{bmatrix} \boldsymbol{s} = \boldsymbol{w} = \begin{bmatrix} \boldsymbol{u} \\ \boldsymbol{v} \end{bmatrix} $$
Dann ist es sehr ähnlich zu Linear Least Squares with Equality Constraint .
Eine interessante Ressource in dieser Hinsicht ist Robert M. Freund – Projection Methods for Linear Equality Constrained Problems .
Sie verwenden bereits MATLAB, daher ist die Verwendung von CVX einfach.
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