Resolva os Mínimos Quadrados Lineares da Matriz com Regularização de Norma de Frobenius e Restrições de Igualdade Linear

Question

Como resolver o seguinte problema de minimização restrita:$$ \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 \\ $$Onde$K_1$,$K_2$,$M$e$S$são 2d Matrix, e apenas$S$É desconhecido. Nas restrições,$Sum1$é a soma ao longo da coluna de$S$, que é um vetor linha.$Sum2$é a soma ao longo da linha de$S$, que é um vetor coluna.

Aqui estão os dados armazenados no formato mat. Como resolver esse 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

A ideia é trazer o problema para a 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 o Produto Kronecker podemos ver que:

• $ K = {K}_{1} \otimes {K}_{2} $.
• $ \boldsymbol{s} = \operatorname{vec} \left( S \right) $Onde$ \operatorname{vec} \left( \cdot \right) $é o operador de vetorização .
• $ \boldsymbol{m} = \operatorname{vec} \left( M \right) $.

As matrizes$ A $e$ B $são apenas seletores dos elementos correspondentes em$ \boldsymbol{s} $.

Observação
Preste atenção que se$ A $e$ B $representam uma matriz que seleciona cada elemento de$ \boldsymbol{s} $ exatamente uma vez então$ \sum_{i} {u}_{i} = \sum_{i} {v}_{i} $deve conter, pois representa a soma de$ \boldsymbol{s} $. Nomeadamente$ \boldsymbol{1}^{T} A \boldsymbol{s} = \boldsymbol{1}^{T} B \boldsymbol{s} = \sum_{i} {s}_{i} $. Este é o caso de suas restrições. Então deve ser assim para ter uma solução viável.

Agora o acima é um problema convexo básico que pode ser resolvido por Descida Gradiente Projetada onde projetamos na interseção das 2 restrições de igualdade .

Você pode até fazer algo mais simples concatenando as matrizes e vetores:

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

Então é muito semelhante ao Linear Mínimos Quadrados com Restrição de Igualdade .

Um recurso interessante a esse respeito é Robert M. Freund - Métodos de Projeção para Problemas Restritos de Igualdade Linear .

Answer 2

Você já está usando o MATLAB, então é fácil usar o 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