低秩近似 📖 Wikipedia

給定

• 結構映射 ${\displaystyle {\mathcal {S}}:\mathbb {R} ^{n_{p}}\to \mathbb {R} ^{m\times n}}$ ,
• 結構參數向量 ${\displaystyle p\in \mathbb {R} ^{n_{p}}}$ ,
• 範數 ${\displaystyle \|\cdot \|}$ ，以及
• 希望的秩 ${\displaystyle r}$ ，

${\displaystyle \min _{\widehat {p}}\|p-{\widehat {p}}\|\quad {\text{subject to}}\quad \operatorname {rank} {\big (}{\mathcal {S}}({\widehat {p}}){\big )}\leq r}$ 

無結構且擬合度以弗羅貝尼烏斯範數衡量的問題，即

${\displaystyle \min _{\widehat {D}}\|D-{\widehat {D}}\|_{\mathrm {F} }\quad {\text{subject to}}\quad \operatorname {rank} ({\widehat {D}})\leq r}$ 

有解析解，該解可由資料矩陣的奇異值分解得到。此結果稱為矩陣近似引理或Eckart–Young–Mirsky 定理。此問題最初由埃哈德·施密特^[1]在無限維積分算子情境中提出（其方法可擴展至希爾伯特空間中任意緊算子），後由C. Eckart與G. Young重新發現。^[2] L. Mirsky將結果推廣至任意單位不變範數。^[3] 設

${\displaystyle D=U\Sigma V^{\top }\in \mathbb {R} ^{m\times n},\quad m\geq n}$ 

為 ${\displaystyle D}$  的奇異值分解，其中 ${\displaystyle \Sigma =:\operatorname {diag} (\sigma _{1},\ldots ,\sigma _{r})}$ ，${\displaystyle r\leq \min\{m,n\}=n}$ ，為一個 ${\displaystyle m\times n}$  的矩形對角矩陣，具有 ${\displaystyle r}$  個非零奇異值，且

${\displaystyle \sigma _{1}\geq \cdots \geq \sigma _{r}>\sigma _{r+1}=\cdots =\sigma _{n}=0}$ 。對於給定的 ${\displaystyle k\in \{1,\dots ,r\}}$ ，將 ${\displaystyle U}$ 、${\displaystyle \Sigma }$  和 ${\displaystyle V}$  分割為：

${\displaystyle U=:{\begin{bmatrix}U_{1}&U_{2}\end{bmatrix}},\quad \Sigma =:{\begin{bmatrix}\Sigma _{1}&0\\0&\Sigma _{2}\end{bmatrix}},\quad {\text{且}}\quad V=:{\begin{bmatrix}V_{1}&V_{2}\end{bmatrix}},}$ 

其中 ${\displaystyle U_{1}}$  是 ${\displaystyle m\times k}$ ，${\displaystyle \Sigma _{1}}$  是 ${\displaystyle k\times k}$ ，${\displaystyle V_{1}}$  是 ${\displaystyle n\times k}$ 。則透過截斷奇異值分解得到的秩為 ${\displaystyle k}$  的矩陣為：

${\displaystyle {\widehat {D}}^{*}=U_{1}\Sigma _{1}V_{1}^{\top },}$ 

且滿足

${\displaystyle \|D-{\widehat {D}}^{*}\|_{\text{F}}=\min _{\operatorname {rank} ({\widehat {D}})\leq k}\|D-{\widehat {D}}\|_{\text{F}}={\sqrt {\sigma _{k+1}^{2}+\cdots +\sigma _{r}^{2}}}.}$ 

當且僅當 ${\displaystyle \sigma _{k}>\sigma _{k+1}}$  時，最小化解 ${\displaystyle {\widehat {D}}^{*}}$  唯一。

設 ${\displaystyle A\in \mathbb {R} ^{m\times n}}$  為一個實數（可能非方陣）矩陣，且 ${\displaystyle m\leq n}$ 。假設

${\displaystyle A=U\Sigma V^{\top }}$ 

為 ${\displaystyle A}$  的奇異值分解，其中 ${\displaystyle U}$  和 ${\displaystyle V}$  為正交矩陣，${\displaystyle \Sigma }$  為 ${\displaystyle m\times n}$  的對角矩陣，對角線元素為 ${\displaystyle (\sigma _{1},\sigma _{2},\ldots ,\sigma _{m})}$ ，且 ${\displaystyle \sigma _{1}\geq \sigma _{2}\geq \cdots \geq \sigma _{m}\geq 0}$ 。

我們宣稱，在譜範數 ${\displaystyle \|\cdot \|_{2}}$  下，對 ${\displaystyle A}$  的最佳秩為 ${\displaystyle k}$  近似為：

${\displaystyle A_{k}:=\sum _{i=1}^{k}\sigma _{i}u_{i}v_{i}^{\top }}$ 

其中 ${\displaystyle u_{i}}$  和 ${\displaystyle v_{i}}$  分別為 ${\displaystyle U}$  與 ${\displaystyle V}$  的第 ${\displaystyle i}$  欄。

首先，注意

${\displaystyle \|A-A_{k}\|_{2}=\left\|\sum _{i=1}^{n}\sigma _{i}u_{i}v_{i}^{\top }-\sum _{i=1}^{k}\sigma _{i}u_{i}v_{i}^{\top }\right\|_{2}=\left\|\sum _{i=k+1}^{n}\sigma _{i}u_{i}v_{i}^{\top }\right\|_{2}=\sigma _{k+1}.}$ 

因此，我們要證明若 ${\displaystyle B_{k}=XY^{\top }}$ ，其中 ${\displaystyle X}$  與 ${\displaystyle Y}$  均有 ${\displaystyle k}$  欄，則

${\displaystyle \|A-A_{k}\|_{2}=\sigma _{k+1}\leq \|A-B_{k}\|_{2}.}$ 

由於 ${\displaystyle Y}$  有 ${\displaystyle k}$  欄，必存在第一個 ${\displaystyle k+1}$  欄的非平凡線性組合

${\displaystyle w=\gamma _{1}v_{1}+\cdots +\gamma _{k+1}v_{k+1},}$ 

使得 ${\displaystyle Y^{\top }w=0}$ 。不失一般性，將 ${\displaystyle w}$  正規化，使得 ${\displaystyle \|w\|_{2}=1}$  或等價地

${\displaystyle \gamma _{1}^{2}+\cdots +\gamma _{k+1}^{2}=1}$ 。因此，

${\displaystyle \|A-B_{k}\|_{2}^{2}\geq \|(A-B_{k})w\|_{2}^{2}=\|Aw\|_{2}^{2}=\gamma _{1}^{2}\sigma _{1}^{2}+\cdots +\gamma _{k+1}^{2}\sigma _{k+1}^{2}\geq \sigma _{k+1}^{2}.}$ 

由上述不等式兩邊取平方根即得證。

設 ${\displaystyle A\in \mathbb {R} ^{m\times n}}$  為一個實數矩陣（可能為長方形矩陣），且 ${\displaystyle m\leq n}$ 。假設

${\displaystyle A=U\Sigma V^{\top }}$ 

為 ${\displaystyle A}$  的奇異值分解。

我們主張，對於 Frobenius 範數（記為 ${\displaystyle \|\cdot \|_{F}}$ ），對 ${\displaystyle A}$  的最佳秩為 ${\displaystyle k}$  的近似矩陣為

${\displaystyle A_{k}=\sum _{i=1}^{k}\sigma _{i}u_{i}v_{i}^{\top }}$ 

其中 ${\displaystyle u_{i}}$  和 ${\displaystyle v_{i}}$  分別為矩陣 ${\displaystyle U}$  和 ${\displaystyle V}$  的第 ${\displaystyle i}$  欄。

首先注意，我們有

${\displaystyle \|A-A_{k}\|_{F}^{2}=\left\|\sum _{i=k+1}^{n}\sigma _{i}u_{i}v_{i}^{\top }\right\|_{F}^{2}=\sum _{i=k+1}^{n}\sigma _{i}^{2}}$ 

因此，我們需要證明：若 ${\displaystyle B_{k}=XY^{\top }}$ ，其中 ${\displaystyle X}$  和 ${\displaystyle Y}$  均有 ${\displaystyle k}$  欄，則

${\displaystyle \|A-A_{k}\|_{F}^{2}=\sum _{i=k+1}^{n}\sigma _{i}^{2}\leq \|A-B_{k}\|_{F}^{2}.}$ 

利用譜範數的三角不等式，若 ${\displaystyle A=A'+A''}$ ，則

${\displaystyle \sigma _{1}(A)\leq \sigma _{1}(A')+\sigma _{1}(A'').}$ 

設 ${\displaystyle A'_{k}}$  與 ${\displaystyle A''_{k}}$  分別為上述奇異值分解所得 ${\displaystyle A'}$  與 ${\displaystyle A''}$  的秩為 ${\displaystyle k}$  的近似矩陣。則對任意 ${\displaystyle i,j\geq 1}$  有

${\displaystyle {\begin{aligned}\sigma _{i}(A')+\sigma _{j}(A'')&=\sigma _{1}(A'-A'_{i-1})+\sigma _{1}(A''-A''_{j-1})\\&\geq \sigma _{1}(A-A'_{i-1}-A''_{j-1})\\&\geq \sigma _{1}(A-A_{i+j-2})\qquad (\because {\rm {rank}}(A'_{i-1}+A''_{j-1})\leq i+j-2))\\&=\sigma _{i+j-1}(A).\end{aligned}}}$ 

因為 ${\displaystyle \sigma _{k+1}(B_{k})=0}$ ，令 ${\displaystyle A'=A-B_{k}}$ ，${\displaystyle A''=B_{k}}$ ，我們得到對所有 ${\displaystyle i\geq 1}$  有

${\displaystyle \sigma _{i}(A-B_{k})\geq \sigma _{k+i}(A).}$ 

因此，

${\displaystyle \|A-B_{k}\|_{F}^{2}=\sum _{i=1}^{n}\sigma _{i}(A-B_{k})^{2}\geq \sum _{i=k+1}^{n}\sigma _{i}(A)^{2}=\|A-A_{k}\|_{F}^{2},}$ 

證畢。

Frobenius 範數對近似誤差 ${\displaystyle D-{\widehat {D}}}$  的所有元素均等加權。若想考慮誤差分佈的先驗知識，可利用加權低秩近似問題：

${\displaystyle \min _{\widehat {D}}\quad \operatorname {vec} (D-{\widehat {D}})^{\top }W\operatorname {vec} (D-{\widehat {D}})\quad {\text{subject to}}\quad \operatorname {rank} ({\widehat {D}})\leq r,}$ 

其中 ${\displaystyle \operatorname {vec} (A)}$  表示將矩陣 ${\displaystyle A}$  按欄向量化，而 ${\displaystyle W}$  是給定的正（半）定權重矩陣。

一般加權低秩近似問題無法透過奇異值分解求得解析解，需使用局部優化方法，且無法保證能找到全域最優解。

當權重為無相關性時，加權低秩近似問題亦可如下表示：^[4][5] 對非負矩陣 ${\displaystyle W}$  及矩陣 ${\displaystyle A}$ ，目標為最小化

${\displaystyle \sum _{i,j}{\big (}W_{i,j}(A_{i,j}-B_{i,j}){\big )}^{2}}$ 

在秩不超過 ${\displaystyle r}$  的矩陣 ${\displaystyle B}$  上。

利用等價關係

${\displaystyle \operatorname {rank} ({\widehat {D}})\leq r\quad \iff \quad \exists P\in \mathbb {R} ^{m\times r},\ L\in \mathbb {R} ^{r\times n}{\text{ s.t. }}{\widehat {D}}=PL}$ 

及

${\displaystyle \operatorname {rank} ({\widehat {D}})\leq r\quad \iff \quad \exists R\in \mathbb {R} ^{(m-r)\times m},\ \operatorname {rank} ({\widehat {R}})=m-r{\text{ s.t. }}\ R{\widehat {D}}=0}$ 

加權低秩近似問題可轉換為參數優化問題

${\displaystyle \min _{{\widehat {D}},P,L}\quad \operatorname {vec} ^{\top }(D-{\widehat {D}})W\operatorname {vec} (D-{\widehat {D}})\quad {\text{subject to}}\quad {\widehat {D}}=PL}$ 

及

${\displaystyle \min _{{\widehat {D}},R}\quad \operatorname {vec} ^{\top }(D-{\widehat {D}})W\operatorname {vec} (D-{\widehat {D}})\quad {\text{subject to}}\quad R{\widehat {D}}=0,\quad RR^{\top }=I_{r},}$ 

其中 ${\displaystyle I_{r}}$  為大小為 ${\displaystyle r}$  的單位矩陣。

秩約束的像空間表示啟發了一種參數優化方法，即交替固定其中一組變數（${\displaystyle P}$  或 ${\displaystyle L}$ ）最小化目標函數。雖然同時對 ${\displaystyle P}$  與 ${\displaystyle L}$  最小化是困難的雙凸最佳化問題，但單獨固定一組變數的最小化是線性最小平方法問題，可有效且全域求解。

該演算法稱為交替投影（alternating projections），在加權低秩近似問題中可保證全域收斂且收斂速率為線性，收斂至局部最優解。使用者需給定初始 ${\displaystyle P}$ （或 ${\displaystyle L}$ ）值，並在滿足預設收斂條件時停止迭代。

Matlab 實作如下：

function [dh, f] = wlra_ap(d, w, p, tol, maxiter)
[m, n] = size(d); r = size(p, 2); f = inf;
for i = 2:maxiter
    % minimization over L
    bp = kron(eye(n), p);
    vl = (bp' * w * bp) \ bp' * w * d(:);
    l  = reshape(vl, r, n);
    % minimization over P
    bl = kron(l', eye(m));
    vp = (bl' * w * bl) \ bl' * w * d(:);
    p  = reshape(vp, m, r);
    % check exit condition
    dh = p * l; dd = d - dh;
    f(i) = dd(:)' * w * dd(:);
    if abs(f(i - 1) - f(i)) < tol, break, end
endfor

交替投影演算法利用低秩近似問題（以像空間參數化）對 ${\displaystyle P}$  與 ${\displaystyle L}$  為雙線性的特性。變數投影法（variable projections）則進一步利用此雙線性結構。^[6]

考慮加權低秩近似問題的像空間參數化，對 ${\displaystyle L}$  變數（線性最小平方法）求解得關於 ${\displaystyle P}$  的近似誤差封閉式

${\displaystyle f(P)={\sqrt {\operatorname {vec} ^{\top }(D){\Big (}W-W(I_{n}\otimes P){\big (}(I_{n}\otimes P)^{\top }W(I_{n}\otimes P){\big )}^{-1}(I_{n}\otimes P)^{\top }W{\Big )}\operatorname {vec} (D)}}.}$ 

因此原問題等價於非線性最小平方問題，透過標準優化方法（如萊文伯格-馬夸特方法）可求解 ${\displaystyle f(P)}$  的最小值。

Matlab 實作如下：

function [dh, f] = wlra_varpro(d, w, p, tol, maxiter)
prob = optimset(); prob.solver = 'lsqnonlin';
prob.options = optimset('MaxIter', maxiter, 'TolFun', tol); 
prob.x0 = p; prob.objective = @(p) cost_fun(p, d, w);
[p, f ] = lsqnonlin(prob); 
[f, vl] = cost_fun(p, d, w); 
dh = p * reshape(vl, size(p, 2), size(d, 2));

function [f, vl] = cost_fun(p, d, w)
bp = kron(eye(size(d, 2)), p);
vl = (bp' * w * bp) \ bp' * w * d(:);
f = d(:)' * w * (d(:) - bp * vl);

變數投影法亦可應用於核空間參數化的低秩近似問題。當消除變數數量遠大於剩餘優化變數時，該方法尤為有效。此類問題常見於以核形式參數化的系統識別，消除的變數為近似軌跡，剩餘變數為模型參數。在線性時不變系統（LTI）理論中，消除步驟相當於卡尔曼滤波（Kalman smoothing）。

設 ${\displaystyle \|A\|_{p}=\left(\sum _{i,j}|A_{i,j}^{p}|\right)^{1/p}}$ 。當 ${\displaystyle p=2}$  時，最快演算法時間為 ${\displaystyle nnz(A)+n\cdot \mathrm {poly} (k/\epsilon )}$ 。^[7][8] 其中一個重要概念為「Oblivious Subspace Embedding (OSE)」，最早由 Sarlos 提出。^[9]

當 ${\displaystyle p=1}$  時，元素逐點的 L1 範數在面對離群值時比 Frobenius 範數更具魯棒性，適用於雜訊不服從高斯分布的模型。很自然的會想要最小化 ${\displaystyle \|B-A\|_{1}}$ 。^[10] 對於 ${\displaystyle p=0}$  和 ${\displaystyle p\geq 1}$ ，已有部分帶有理論保證的演算法。^[11][12]

設 ${\displaystyle P={p_{1},\ldots ,p_{m}}}$  與 ${\displaystyle Q={q_{1},\ldots ,q_{n}}}$  為任意度量空間中的兩組點集。令 ${\displaystyle A}$  表示 ${\displaystyle m\times n}$  的矩陣，其中元素定義為 ${\displaystyle A_{i,j}=\operatorname {dist} (p_{i},q_{j})}$ 。此類距離矩陣常見於軟體套件中，並應用於學習影像流形（image manifolds）、手寫辨識（handwriting recognition）及多維展開（multi-dimensional unfolding）。為了嘗試縮減其描述大小，^[13][14] 可研究此類矩陣的低秩近似。

通常，我們不僅希望解為低秩，還要符合應用需求的其他凸限制。問題可表述為：

${\displaystyle {\text{minimize}}\quad {\text{over }}{\widehat {p}}\quad \|p-{\widehat {p}}\|\quad {\text{subject to}}\quad \operatorname {rank} {\big (}{\mathcal {S}}({\widehat {p}}){\big )}\leq r{\text{ and }}g({\widehat {p}})\leq 0}$ 

此問題有多項實際應用，包括從不精確的（半正定規劃）鬆弛中恢復良好解。若額外限制 ${\displaystyle g({\widehat {p}})\leq 0}$  為線性（如要求元素非負），此問題稱為結構化低秩近似（structured low-rank approximation）。^[15] 更一般的形式則稱為凸限制低秩近似（convex-restricted low rank approximation）。

此問題雖具有實用價值，但由於同時涉及凸限制與非凸的低秩限制，因此具有相當的挑戰性。根據不同形式的限制條件 ${\displaystyle g({\widehat {p}})\leq 0}$ ，已有多種技術被提出。值得注意的是，交替方向乘子法（ADMM）可應用於目標函數為凸、同時具有秩限制與其他凸限制的非凸問題中，^[16]，因此特別適合處理上述類型的問題。此外，與一般非凸問題不同，只要對偶變數在迭代過程中收斂，ADMM 即可保證收斂至一個可行解。

• 線性系統識別，此時近似矩陣具漢克爾結構。
• 機器學習，此時近似矩陣具有非線性結構。
• 推薦系統，資料矩陣中存在缺失數據且近似為分类变量。
• 距離矩陣還原，附帶正定性約束。
• 自然語言處理，近似矩陣要求非負矩陣。
• 計算機代數，近似矩陣具西爾維斯特結構。

• C++ package for structured-low rank approximation