2.6 低秩矩陣補全

動機

部分觀測的數據表包含兩種資訊：量得的數值，以及尚未量度的位置。矩陣補全利用行與欄之間的關係，估計這些缺值。低秩模型以少量共同潛在因子描述關係；同一批因子連接已觀測與未觀測項，使表內不同位置的資訊能夠互相影響。

缺值分佈與量度數目同樣重要。三項觀測可以確定一個小型秩一矩陣；換一種觀測分佈，則可能存在很多補全方式。以下先準確指定哪些觀測進入損失，再用凸的奇異值懲罰鼓勵較簡單的擬合矩陣。算法結合觀測殘差的梯度步，以及作用於整個矩陣的奇異值軟閾值。

定義

設 $P\in\mathbb R^{n\times d}$ 儲存可用數據，$\Omega\subseteq\{1,\ldots,n\}\times\{1,\ldots,d\}$ 記錄已觀測位置。$P$ 在 $\Omega$ 以外的數字只是儲存選擇，不是擬合目標。觀測到的零仍是量度，屬於 $\Omega$。

定義

觀測投影與矩陣範數

觀測算子只保留已觀測座標：

$$(\mathcal P_\Omega X)_{ij}= \begin{cases}X_{ij},&(i,j)\in\Omega,\\0,&(i,j)\notin\Omega.\end{cases} \qquad \mathcal P_{\Omega^c}=I-\mathcal P_\Omega.$$

同形矩陣的 Frobenius 內積與範數是 $\langle X,Y\rangle_F=\sum_{ij}X_{ij}Y_{ij}$、$\|X\|_F^2=\sum_{ij}X_{ij}^2$。若 $X$ 的奇異值為 $\sigma_1,\ldots,\sigma_p$，$p=\min(n,d)$，核範數定義為

$$\|X\|_*=\sum_{j=1}^p\sigma_j,\qquad \|X\|_F^2=\sum_{j=1}^p\sigma_j^2.$$

兩個範數描述奇異譜的不同面向。Frobenius 範數量度總平方大小，核範數則合計奇異值大小；秩計算的是正奇異值數目。核範數懲罰透過閾值步把部分奇異值變成零，毋須直接搜尋離散的秩。

觀測幾何與低秩因子

定理

觀測掩碼是正交投影

在 Frobenius 內積下，$\mathcal P_\Omega$ 自伴且冪等。特別地，

$$\|X\|_F^2=\|\mathcal P_\Omega X\|_F^2+ \|\mathcal P_{\Omega^c}X\|_F^2,\qquad \|\mathcal P_\Omega X\|_F\le\|X\|_F.$$

證明

投影到已量度座標

$\langle\mathcal P_\Omega X,Y\rangle_F$ 與 $\langle X,\mathcal P_\Omega Y\rangle_F$ 均等於 $\sum_{(i,j)\in\Omega}X_{ij}Y_{ij}$，所以算子自伴。同一掩碼作用兩次不變，所以冪等。已觀測部分與未觀測部分的非零位置不重疊，內積為零；畢氏定理給出範數等式及不等式。

秩不超過 $r$ 的模型可寫成 $X=LR^T$，其中 $L\in\mathbb R^{n\times r}$、$R\in\mathbb R^{d\times r}$。$X_{ij}$ 是 $L$ 第 $i$ 行與 $R$ 第 $j$ 行的內積。這些共同座標讓缺值依賴解釋觀測的同一批因子。直接搜尋兩組因子是非凸問題，因為它們互相相乘。

因子座標本身並不唯一。任取可逆 $Q\in\mathbb R^{r\times r}$，把因子換成 $LQ$ 和 $RQ^{-T}$，乘積 $LR^T$ 不變。完整矩陣也可能無法由觀測唯一決定。討論恢復時，須區分因子座標自由與缺值是否唯一：低秩提供結構假設，觀測分佈仍須有足夠連繫。

例題

1. 確定的缺值與含糊的觀測分佈

設已知項構成

$$X=\begin{bmatrix}2&b\\3&6\end{bmatrix}.$$

秩一要求 $\det X=12-3b=0$，故唯一得到 $b=4$。完成矩陣可分解為 $(2,3)^T(1,2)$。

若只觀測兩個對角項，則全部矩陣

$$X_t=\begin{bmatrix}2&t\\12/t&6\end{bmatrix},\qquad t\ne0,$$

都是秩一且符合觀測。例如 $t=2$ 與 $t=4$ 給出不同缺值。單靠低秩無法選出真正數據表；正則化可以表達對擬合的偏好，卻不會增加觀測資訊。

只計觀測項的損失

容許量度含噪聲時，考慮

$$\Phi(X)=f(X)+\lambda\|X\|_*,\qquad f(X)=\frac12\|\mathcal P_\Omega(X-P)\|_F^2,\qquad\lambda>0.$$

只有已量度殘差進入 $f$。改寫 $P$ 未使用的項不改變目標。核範數作用於整個候選矩陣，以奇異方向連接各座標。兩項皆凸，但不完整觀測下，整體目標未必嚴格凸。

參數控制擬合與複雜度的取捨。較大參數更重視縮小奇異值，常會移除更多奇異方向；觀測位置的擬合值也可偏離量度。精確量度可另建約束模型：在 $\mathcal P_\Omega X=\mathcal P_\Omega P$ 下最小化 $\|X\|_*$。本節推導的是上述懲罰模型，觀測殘差仍參與最優化。

核範數是凸矩陣範數。它亦可寫成：在譜範數不超過一的矩陣中，與 $X$ 作內積的最大值。奇異值跡不等式把內積界於奇異值總和，對齊奇異方向即可達界；線性函數的最大值是凸函數。這把懲罰的凸性連到以下同一套奇異向量幾何。

奇異值軟閾值

定義

對奇異值作軟閾值

設 $Y=U\operatorname{diag}(s_j)V^T$、$\tau\ge0$，定義

$$\operatorname{SVT}_\tau(Y) =U\operatorname{diag}\big((s_j-\tau)_+\big)V^T, \qquad (a)_+=\max(a,0).$$

定理

核範數的近端問題

對任意完整指定的矩陣 $Y$ 及 $\tau\ge0$，

$$\frac12\|X-Y\|_F^2+\tau\|X\|_*$$

的唯一最小化矩陣是 $\operatorname{SVT}_\tau(Y)$。

證明

把矩陣問題化為逐個奇異值的閾值

設 $X$、$Y$ 已排序奇異值分別為 $t_j$、$s_j$。von Neumann 跡不等式給出 $\langle X,Y\rangle_F\le\sum_jt_js_j$。展開平方距離，目標因此至少是

$$\sum_j\left[\frac12(t_j-s_j)^2+\tau t_j\right],\qquad t_j\ge0.$$

每項在 $t_j=(s_j-\tau)_+$ 最小；此運算保持排序。把 $X$ 的奇異向量與 $Y$ 對齊，跡不等式取等號，並同時達到全部純量最小值。平方距離嚴格凸，故最小化矩陣唯一，即使奇異向量基底未必唯一。

軟閾值從每個正奇異值減去相同數量，把小於或等於閾值的奇異值設成零；秩截斷則把選中的大奇異值原樣保留。兩者都可能產生較低秩矩陣，但解不同目標。遇到重複奇異值，數值 SVD 可換用該子空間的另一正交歸一基底；在整個子空間施加同一閾值，重建矩陣仍相同。

例題

2. 完整觀測的閾值計算

取 $Y=\operatorname{diag}(3,1)$、$\tau=1/2$。奇異方向為座標軸，解是 $X=\operatorname{diag}(5/2,1/2)$。平方距離項為 $\tfrac12(1/4+1/4)=1/4$，懲罰為 $\tfrac12(5/2+1/2)=3/2$，目標總值是 $7/4$。保持 $Y$ 不變則得 $2$，所以精確符合數據並非此懲罰問題的最小值；兩個觀測奇異值都被縮小。

帶掩碼的近端梯度步

觀測損失的梯度為

$$\nabla f(X)=\mathcal P_\Omega(X-P),\qquad \|\nabla f(X)-\nabla f(Y)\|_F\le\|X-Y\|_F.$$

不等式來自投影定理，故梯度的 Lipschitz 常數可取一。步長 $0<\eta\le1$ 給出

$$X^+=\operatorname{SVT}_{\eta\lambda} \left(X-\eta\mathcal P_\Omega(X-P)\right).$$

單位步長時，化為

$$X^+=\operatorname{SVT}_\lambda \left(\mathcal P_\Omega P+\mathcal P_{\Omega^c}X\right).$$

梯度步的中間矩陣在觀測處採用量度，其餘保留當前估計，然後對整個矩陣施加閾值。結果可以改變觀測項並填入缺值，符合殘差與核範數的取捨。缺值估計會留到下一個中間矩陣，影響下一次 SVD，而非每步都被視為量得的零。

為證明步長合理，對增量 $D$ 展開二次損失：

$$f(X+D)=f(X)+\langle\nabla f(X),D\rangle_F +\tfrac12\|\mathcal P_\Omega D\|_F^2 \le f(X)+\langle\nabla f(X),D\rangle_F+\tfrac12\|D\|_F^2.$$

加上核範數後，得到在 $X$ 處等於 $\Phi$ 的二次上界模型。由近端定理，其最小值正是單位步更新，故更新不增加 $\Phi$。較小步長把二次項係數換成 $1/(2\eta)$，仍是有效上界。步長限制直接來自掩碼的範數。

懲罰大小與零解的精確判準

令 $Y=\mathcal P_\Omega P$，以 $\|Y\|_2$ 表示其最大奇異值。跡不等式給出

$$\Phi(X)-\Phi(0) =\tfrac12\|\mathcal P_\Omega X\|_F^2-\langle Y,X\rangle_F +\lambda\|X\|_* \ge\tfrac12\|\mathcal P_\Omega X\|_F^2 +(\lambda-\|Y\|_2)\|X\|_*.$$

因此，參數至少等於此最大奇異值時，零矩陣是全域最小值。這精確解釋了為何迭代會移除全部奇異方向：模型對矩陣大小所收取的代價，已超過任何觀測擬合改善。這個尺度來自已觀測表及其掩碼，不依賴想像中的完整矩陣。比較一系列參數時，它提供明確端點；逐步減小參數，才容許更顯著的擬合結構。

不動點證明甚麼

非光滑懲罰目標的最優條件不只看梯度。核範數在 $X$ 的次梯度 $G$，意指對所有 $Z$ 都有 $\|Z\|_*\ge\|X\|_*+\langle G,Z-X\rangle_F$。單位步更新滿足

$$\frac{X-X^+-\nabla f(X)}{\lambda}\in\partial\|X^+\|_*.$$

若更新返回相同矩陣，這條支撐不等式便把觀測梯度與懲罰平衡。加上凸函數 $f$ 的一階不等式，即證明任意候選的目標均不小於當前值；不動點是指定凸目標的全域最小值。此時觀測殘差仍可非零，因其梯度由核範數次梯度平衡。

所以，除了目標值，亦可檢查近端更新的大小。變化很小量度的是整個懲罰問題的近似駐定性，不要求觀測梯度本身為零，也不等於已核對缺值的預測準確度。

例題

3. 一次迭代填入缺值

沿用首例的三項觀測，儲存 $P=\begin{bmatrix}2&0\\3&6\end{bmatrix}$，取 $X_0=0$、$\lambda=1$。右上缺值不在 $\Omega$ 中。中間矩陣 $Y=P$ 的奇異值為 $(\sqrt{73}+5)/2$、$(\sqrt{73}-5)/2$，兩者均大於一。其正交極分解因子為

$$UV^T=\frac1{\sqrt{73}}\begin{bmatrix}8&-3\\3&8\end{bmatrix},\qquad X_1=\begin{bmatrix} 2-8/\sqrt{73}&3/\sqrt{73}\\ 3-3/\sqrt{73}&6-8/\sqrt{73} \end{bmatrix}.$$

缺值由儲存的零變成約 $0.351123$，觀測項亦移動。目標從 $49/2=24.5$ 降至 $\sqrt{73}-2+137/146\approx7.482360$。精確秩一補全的缺值為 $4$；首次懲罰迭代給出的是擬合與懲罰準則下的中間估計。

可執行計算

布林掩碼獨立記錄觀測狀態。以下實作使用單位步長，以及剛推導的目標。

import numpy as np

observed = np.array([[True, False], [True, True]])
P = np.array([[2., 0.], [3., 6.]])
lam = 1.

def svt(Y, threshold):
    U, s, Vt = np.linalg.svd(Y, full_matrices=False)
    return (U * np.maximum(s - threshold, 0.)) @ Vt

def objective(X):
    residual = np.where(observed, X - P, 0.)
    return 0.5 * np.sum(residual**2) + lam * np.linalg.svd(
        X, compute_uv=False
    ).sum()

X = np.zeros_like(P)
first = svt(P, lam)
history = [objective(X)]
for _ in range(100):
    gradient = np.where(observed, X - P, 0.)
    X = svt(X - gradient, lam)
    history.append(objective(X))

assert np.all(np.diff(history) <= 1e-10)
print(np.round(first, 6))
print(round(history[0], 6), round(history[-1], 6))

首個輸出矩陣約為 $\begin{bmatrix}1.063671&0.351123\\2.648877&5.063671\end{bmatrix}$；目標值輸出為 $24.5$ 和約 $7.073338$。固定迭代次數讓例子可重現。較大型應用可同時記錄目標與迭代變化量，決定何時停止；未提供數值的位置，其預測準確度需要額外驗證資料。

參數尺度與擬合評估

參數數值受數據及損失的尺度影響。把量度乘以正常數 $c$ 時，也把參數乘以同一常數；候選矩陣同樣縮放後，殘差項與懲罰都乘以 $c^2$，全部候選目標的排序不變。這說明換量度單位後等價模型怎樣變化，而不是給某個參數數值一個絕對意義。

若把觀測平方損失總和改成平均值，要同時把懲罰係數除以觀測數目，才得到相同最優解。只平均損失卻保留原係數，會提高懲罰的相對影響。比較不同實作或觀測數量不同的數據表前，先說明損失的歸一化方式。

評估預測時，可留起部分真正量得的項作驗證，以其餘項建立擬合掩碼。梯度步不使用驗證位置，再用預測值與留起量度比較，便量度未參與擬合的觀測之預測表現。這也改變了擬合的觀測分佈，因此劃分時要保留模型所需的行欄資訊。最優化診斷檢查是否已最小化選定目標，預測診斷則評估估計值是否有用。

常見錯誤

常見錯誤

以數值是否為零判斷觀測狀態

觀測零也產生平方殘差。缺值則不產生殘差，與儲存的數字無關。掩碼須由觀測狀態建立。更新順序亦按推導：先作梯度步的中間矩陣，再作奇異值軟閾值，才能對應指定的懲罰目標與步長論證。

總結

觀測算子是正交投影，決定損失和梯度。低秩結構連接缺值，可辨識性則取決於量度位置。核範數給出凸奇異值懲罰，其近端映射是奇異值軟閾值。把它與觀測梯度結合，便得到可由二次上界直接解釋單位步長的算法。

練習

思考檢查

1. 秩不超過一的表已觀測 $X_{11}=0$、$X_{21}=2$、$X_{22}=4$。求缺值 $X_{12}$，並解釋觀測零為何屬於掩碼。

使用行列式及觀測定義。

思考檢查

2. 完整觀測 $Y=\operatorname{diag}(5,2)$，懲罰參數 $\tau=3$。求核範數近端解、其秩及最小目標值。

分別計算平方殘差項和核範數懲罰。

思考檢查

3. 在掩碼例子中，把懲罰改為 $\lambda=7$ 並由零開始。首次近端梯度更新是甚麼？此目標是否強制精確符合三項觀測？

比較閾值與已列出的較大奇異值。

解答

解答 · 1. 零量度也提供資訊

行列式為 $0\cdot4-2X_{12}$，所以秩不超過一要求 $X_{12}=0$。第二行非零，完成矩陣秩為一。若漏掉 $X_{11}=0$，便移除了一條實際方程，容許其他秩一補全。數值為零不等於缺失。

解答 · 2. 縮小奇異值

解為 $\operatorname{diag}(2,0)$，秩一。平方距離項為 $\tfrac12(3^2+2^2)=13/2$，懲罰為 $3\cdot2=6$，最小目標值是 $25/2=12.5$。

解答 · 3. 首步移除全部奇異值

中間矩陣的最大奇異值為 $(\sqrt{73}+5)/2<7$，閾值七給出零矩陣。模型對觀測殘差施加懲罰，容許擬合與量度不同；觀測相等並非其約束。

相關筆記

• 奇異值分解與主成分
• 最小二乘與殘差
• 二次函數的梯度下降
• 課程讀物