Résoudre les moindres carrés linéaires matriciels avec la régularisation de la norme de Frobenius et les contraintes d'égalité linéaire
Comment résoudre le problème de minimisation contrainte suivant :$$ \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 \\ $$où$K_1$,$K_2$,$M$et$S$sont 2d Matrix, et seulement$S$est inconnu. Dans les contraintes,$Sum1$est la somme le long de la colonne de$S$, qui est un vecteur ligne.$Sum2$est la somme le long de la ligne de$S$, qui est un vecteur colonne.
Voici les données stockées au format mat. Comment résoudre ce genre de problème ?
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;
Réponses
L'idée est de mettre le problème sous la forme :
$$\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}$$
En utilisant le produit Kronecker , nous pouvons voir que :
- $ K = {K}_{1} \otimes {K}_{2} $.
- $ \boldsymbol{s} = \operatorname{vec} \left( S \right) $où$ \operatorname{vec} \left( \cdot \right) $est l' opérateur de vectorisation .
- $ \boldsymbol{m} = \operatorname{vec} \left( M \right) $.
Les matrices$ A $et$ B $ne sont que des sélecteurs des éléments correspondants dans$ \boldsymbol{s} $.
Remarque
Faites attention que si$ A $et$ B $représentent une matrice qui sélectionne chaque élément de$ \boldsymbol{s} $ exactement une fois alors$ \sum_{i} {u}_{i} = \sum_{i} {v}_{i} $doit tenir car il représente la somme de$ \boldsymbol{s} $. À savoir$ \boldsymbol{1}^{T} A \boldsymbol{s} = \boldsymbol{1}^{T} B \boldsymbol{s} = \sum_{i} {s}_{i} $. C'est le cas de vos contraintes. Il faut donc que ce soit comme ça pour avoir une solution réalisable.
Maintenant, ce qui précède est un problème convexe de base qui peut être résolu par Projected Gradient Descent où nous projetons sur l' intersection des 2 contraintes d'égalité .
Vous pourriez même faire quelque chose de plus simple en concaténant les matrices et les vecteurs :
$$ C \boldsymbol{s} = \begin{bmatrix} A \\ B \end{bmatrix} \boldsymbol{s} = \boldsymbol{w} = \begin{bmatrix} \boldsymbol{u} \\ \boldsymbol{v} \end{bmatrix} $$
Ensuite, il est très similaire aux moindres carrés linéaires avec contrainte d'égalité .
Une ressource intéressante à cet égard est Robert M. Freund - Projection Methods for Linear Equality Constrained Problems .
Vous utilisez déjà MATLAB, il est donc facile d'utiliser 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