2. it
  3. 学习笔记1：矩阵恢复算法1——奇异值阈值算法（SVT）

学习笔记1：矩阵恢复算法1——奇异值阈值算法（SVT）

mac2026-01-18  10

承接低秩矩阵恢复模型笔记，记录第一个低秩矩阵恢复算法——奇异值阈值（Singular Value Thresholding, SVT），记录学习内容，内容非原创。

1奇异值分解(Singular Value Decomposition,SVD)

设 X ∈ R m × n X\in R_{m\times n} X∈Rm×n​,定义 X = U Σ V T X=U\Sigma V^T X=UΣVT其中，U，V为正交矩阵， Σ \Sigma Σ为对角矩阵，对角线上元素为矩阵X的奇异值。 Matlab有矩阵奇异值分解的函数，[U,S,V] = svd(A)。 奇异值的性质： （1）非负性，即奇异值 σ i \sigma_i σi​必大于等于0； （2）矩阵非零奇异值的个数等于矩阵的秩； （3）矩阵最大奇异值等于其谱范数，即 σ m a x = ∥ A ∥ 2 。 \sigma_max=\lVert A\rVert_2。 σm​ax=∥A∥2​。

2奇异值阈值算法（Singular Value Thresholding,SVT）

2.1求解模型

min ⁡ x ∈ C r a n k ( X ) \min_{x\in C}rank(X) x∈Cmin​rank(X) s . t . P ( U − X ) = 0 s.t.P(U-X)=0 s.t.P(U−X)=0因为秩函数非凸，求解是np难问题，转而求解凸优化模型 min ⁡ x ∈ C ∥ X ∥ ∗ \min_{x\in C}\lVert X\rVert_* x∈Cmin​∥X∥∗​ s . t . P ( U − X ) = 0 s.t.P(U-X)=0 s.t.P(U−X)=0

2.2奇异值收紧（Singular value shrinkge，SVS）

定义

对于 X = U Σ V T X=U\Sigma V^T X=UΣVT, Σ = d i a g ( { σ i } , 1 ≤ i ≤ r ) \Sigma=diag(\{\sigma_i\},1\leq i \leq r) Σ=diag({σi​},1≤i≤r),对于每个 τ ≥ 0 \tau\ge0 τ≥0,有 D τ ( X ) : = U D τ ( Σ ) V T D_{\tau}(X):=UD_\tau(\Sigma)V^T Dτ​(X):=UDτ​(Σ)VT其中， D τ ( Σ ) = d i a g ( { σ i − τ } + ) D_\tau(\Sigma)=diag(\{\sigma_i-\tau\}_+) Dτ​(Σ)=diag({σi​−τ}+​)，为软阈值操作 d i a g diag diag指奇异值矩阵的对角元素，即奇异值，+号表示使奇异值 σ i \sigma_i σi​趋向于0，但保证其为非负。

优化模型

又因为奇异值收紧（SVS）是核范式的近似操作，上式可以转化为 D τ ( Y ) = arg ⁡ min ⁡ X 1 2 ∥ X − Y ∥ F 2 + τ ∥ X ∥ ∗ D_\tau(Y)=\arg\min_{X}\frac{1}{2}\lVert X-Y \rVert_F^2+ \tau\lVert X \rVert_* Dτ​(Y)=argXmin​21​∥X−Y∥F2​+τ∥X∥∗​其中， arg ⁡ \arg arg指使后面的式中成立时的 τ \tau τ的取值。

程序实现

使用matlab实现奇异值收紧操作：

function B = svso( t,A ) % Singular Value Shrinkage Operator % function：求解如下形式的优化模型 % argminB { p1||B||* + 0.5||B-A||F2 } % input：参数t，矩阵A % output：优化模型的最优解B [ U,s,V ] = svd( A );%求解U，sigma,V s = s - t; %σ-t ZeroLog = s > 0; s = s.*ZeroLog; B = U * s * V'; %输出奇异值缩紧后的矩阵 end

2.3SVT的迭代过程

X k = D τ ( Y k − 1 ) X^k=D_\tau(Y^{k-1}) Xk=Dτ​(Yk−1)

Y k = Y k − 1 + δ k P Ω ( M − X k ) Y^k=Y^{k-1}+\delta_kP_\Omega(M-X^k) Yk=Yk−1+δk​PΩ​(M−Xk)其中，Y为辅助矩阵，M为测量矩阵（有缺失）， P Ω P_\Omega PΩ​为未缺失元素的位置矩阵， δ k \delta_k δk​为迭代步长。

2.4收敛判据

∥ P Ω ( M − X k ) ∥ F ∥ P Ω M ∥ F < ε \frac{\lVert P_\Omega(M-X^k)\rVert_F}{\lVert P_\Omega M\rVert_F}<\varepsilon ∥PΩ​M∥F​∥PΩ​(M−Xk)∥F​​<ε

2.5MATLAB实现

function [ X,iterations ] = SVT(M,P,T,delta_t) %Single value thresholding algorithm，SVT % function：求解如下模型 % min ||U||* % s.t. P(U-M) = 0 % 其中，U是恢复后得到的低秩矩阵；M是观测矩阵 % input：观测矩阵M,观测元素位置矩阵P,参数T(奇异值缩紧步长),delta_t % output：输出恢复后的矩阵X,迭代次数iterations epsilon= 1e3;%迭代终止阈值 Y = zeros(size(M));% 辅助矩阵Y初始化 iterations = 0;%迭代次数 while epsilon>1e-3 %奇异值紧缩 X = SVS( T,Y ); %更新辅助矩阵Y Y = Y + delta_t* P.* (M-X); %计算阈值 epsilon= norm( P.* (M-X),'fro' )/norm( P.* M,'fro' ); %更新迭代次数 iterations = iterations + 1; end end

参考: http://blog.csdn.net/shanglianlm/article/details/46009387

最新回复(0)