Resolver Mínimos Cuadrados Lineales de Matriz con Regularización de Norma de Frobenius y Restricciones de Igualdad Lineal

Question

Cómo resolver el siguiente problema de minimización con restricciones:$$ \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 \\ $$donde$K_1$,$K_2$,$M$y$S$son 2d Matrix, y solo$S$es desconocido. En las restricciones,$Sum1$es la suma a lo largo de la columna de$S$, que es un vector fila.$Sum2$es la suma a lo largo de la fila de$S$, que es un vector columna.

Aquí están los datos almacenados en formato mat. ¿Cómo solucionar este tipo de problema?

    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

La idea es llevar el problema a la forma:

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

Usando el Producto Kronecker podemos ver que:

• $ K = {K}_{1} \otimes {K}_{2} $.
• $ \boldsymbol{s} = \operatorname{vec} \left( S \right) $donde$ \operatorname{vec} \left( \cdot \right) $es el operador de vectorización .
• $ \boldsymbol{m} = \operatorname{vec} \left( M \right) $.

las matrices$ A $y$ B $son solo selectores de los elementos correspondientes en$ \boldsymbol{s} $.

Observación
Preste atención a que si$ A $y$ B $representan una matriz que selecciona cada elemento de$ \boldsymbol{s} $ exactamente una vez entonces$ \sum_{i} {u}_{i} = \sum_{i} {v}_{i} $debe contener ya que representa la suma de$ \boldsymbol{s} $. A saber$ \boldsymbol{1}^{T} A \boldsymbol{s} = \boldsymbol{1}^{T} B \boldsymbol{s} = \sum_{i} {s}_{i} $. Este es el caso de sus restricciones. Entonces debe ser así para tener una solución factible.

Ahora, lo anterior es un problema convexo básico que puede resolverse mediante el descenso de gradiente proyectado donde proyectamos en la intersección de las 2 restricciones de igualdad .

Incluso podría hacer algo más simple al concatenar las matrices y los vectores:

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

Entonces es muy similar a Linear Least Squares with Equality Constraint .

Un recurso interesante al respecto es Robert M. Freund - Métodos de proyección para problemas con restricciones de igualdad lineal .

Answer 2

Ya está usando MATLAB, por lo que es fácil usar 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