Frobenius Norm 정규화 및 선형 등식 제약 조건을 사용하여 행렬 선형 최소제곱 풀기
다음과 같은 제약된 최소화 문제를 해결하는 방법:$$ \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$2차원 매트릭스이며,$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;
답변
아이디어는 문제를 다음 형식으로 가져오는 것입니다.
$$\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}$$
Kronecker 제품 을 사용하여 다음 을 확인할 수 있습니다.
- $ 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개의 등식 제약 조건의 교차점에 투영하는 Projected Gradient Descent로 해결할 수 있는 기본 볼록 문제입니다 .
행렬과 벡터를 연결하여 더 간단한 작업을 수행할 수도 있습니다.
$$ C \boldsymbol{s} = \begin{bmatrix} A \\ B \end{bmatrix} \boldsymbol{s} = \boldsymbol{w} = \begin{bmatrix} \boldsymbol{u} \\ \boldsymbol{v} \end{bmatrix} $$
그런 다음 Equality Constraint 가 있는 Linear Least Squares 와 매우 유사합니다 .
이와 관련하여 흥미로운 리소스는 Robert M. Freund-Linear Equality Constrained Problems에 대한 투영 방법입니다 .
이미 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