Memecahkan Matriks Linear Least Squares dengan Regularisasi Norma Frobenius dan Kendala Persamaan Linier

Question

Bagaimana memecahkan masalah minimisasi terbatas berikut:$$ \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 \\ $$di mana$K_1$,$K_2$,$M$dan$S$adalah Matriks 2d, dan hanya$S$tidak diketahui. Dalam kendala,$Sum1$adalah jumlah sepanjang kolom dari$S$, yang merupakan vektor baris.$Sum2$adalah jumlah sepanjang baris dari$S$, yang merupakan vektor kolom.

Berikut adalah data yang disimpan dalam format mat. Bagaimana cara mengatasi masalah seperti ini?

    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

Idenya adalah untuk membawa masalah ke dalam bentuk:

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

Menggunakan Produk Kronecker kita dapat melihat bahwa:

• $ K = {K}_{1} \otimes {K}_{2} $.
• $ \boldsymbol{s} = \operatorname{vec} \left( S \right) $di mana$ \operatorname{vec} \left( \cdot \right) $adalah operator vektorisasi .
• $ \boldsymbol{m} = \operatorname{vec} \left( M \right) $.

Matriks$ A $dan$ B $hanyalah Selektor dari elemen yang sesuai di$ \boldsymbol{s} $.

Catatan
Perhatikan bahwa jika$ A $dan$ B $mewakili matriks yang memilih setiap elemen dari$ \boldsymbol{s} $ tepat sekali maka$ \sum_{i} {u}_{i} = \sum_{i} {v}_{i} $harus dipegang karena mewakili jumlah dari$ \boldsymbol{s} $. Yaitu$ \boldsymbol{1}^{T} A \boldsymbol{s} = \boldsymbol{1}^{T} B \boldsymbol{s} = \sum_{i} {s}_{i} $. Ini adalah kasus untuk kendala Anda. Jadi harus seperti itu agar memiliki solusi yang layak.

Sekarang di atas adalah masalah Convex dasar yang dapat diselesaikan dengan Projected Gradient Descent dimana kita memproyeksikan ke perpotongan dari 2 kendala kesetaraan .

Anda bahkan dapat melakukan sesuatu yang lebih sederhana dengan menggabungkan matriks dan vektor:

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

Maka sangat mirip dengan Linear Least Squares dengan Equality Constraint .

Sebuah sumber yang menarik sehubungan dengan itu adalah Robert M. Freund - Metode Proyeksi untuk Masalah Terbatas Persamaan Linier .

Answer 2

Anda sudah menggunakan MATLAB, jadi mudah menggunakan 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