低秩近似

低秩近似 (low-rank approximation) 是指用一個較低秩的矩陣去近似給定矩陣的過程。更精確地說，它是一個最佳化問題，其中損失函數衡量給定矩陣（資料）與近似矩陣（最佳化變數）之間的擬合程度，並且附帶近似矩陣秩的約束條件。此問題常用於數學模型建構與資料壓縮。秩的約束與對符合資料模型複雜度的限制相關。在應用中，近似矩陣通常還會有其他約束，例如非負性及漢克爾結構。

低秩近似與多種其他技術密切相關，包括主成分分析、因素分析、潛在語義分析、最小全平方法、正交迴歸及動態模態分解。

 定義 

給定

 結構映射 ,
 結構參數向量 ,
 範數 ，以及
 希望的秩 ，

 基本低秩近似 

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

有解析解，該解可由資料矩陣的奇異值分解得到。此結果稱為矩陣近似引理或Eckart–Young–Mirsky 定理。此問題最初由埃哈德·施密特E. Schmidt, Zur Theorie der linearen und nichtlinearen Integralgleichungen, Math. Annalen 63 (1907), 433-476. 在無限維積分算子情境中提出（其方法可擴展至希爾伯特空間中任意緊算子），後由C. Eckart與G. Young重新發現。C. Eckart, G. Young, The approximation of one matrix by another of lower rank. Psychometrika, Volume 1, 1936, Pages 211–8.  L. Mirsky將結果推廣至任意單位不變範數。L. Mirsky, Symmetric gauge functions and unitarily invariant norms, Q.J. Math. 11 (1960), 50-59.  設

為  的奇異值分解，其中 ，，為一個  的矩形對角矩陣，具有  個非零奇異值，且

。對於給定的 ，將 、 和  分割為：

其中  是 ， 是 ， 是 。則透過截斷奇異值分解得到的秩為  的矩陣為：

且滿足

當且僅當  時，最小化解  唯一。

 Eckart–Young–Mirsky 定理的證明（針對譜範數） 

設  為一個實數（可能非方陣）矩陣，且 。假設

為  的奇異值分解，其中  和  為正交矩陣， 為  的對角矩陣，對角線元素為 ，且 。

我們宣稱，在譜範數  下，對  的最佳秩為  近似為：

其中  和  分別為  與  的第  欄。

首先，注意

因此，我們要證明若 ，其中  與  均有  欄，則

由於  有  欄，必存在第一個  欄的非平凡線性組合

使得 。不失一般性，將  正規化，使得  或等價地

。因此，

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

 Eckart–Young–Mirsky 定理的證明（針對 弗羅貝尼烏斯範數） 

設  為一個實數矩陣（可能為長方形矩陣），且 。假設

為  的奇異值分解。

我們主張，對於 Frobenius 範數（記為 ），對  的最佳秩為  的近似矩陣為

其中  和  分別為矩陣  和  的第  欄。

首先注意，我們有



因此，我們需要證明：若 ，其中  和  均有  欄，則



利用譜範數的三角不等式，若 ，則

設  與  分別為上述奇異值分解所得  與  的秩為  的近似矩陣。則對任意  有



因為 ，令 ，，我們得到對所有  有

因此，



證畢。

 加權低秩近似 

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

其中  表示將矩陣  按欄向量化，而  是給定的正（半）定權重矩陣。

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

當權重為無相關性時，加權低秩近似問題亦可如下表示： 對非負矩陣  及矩陣 ，目標為最小化

在秩不超過  的矩陣  上。

 秩約束的像空間與核空間表示 
利用等價關係

及

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

及

其中  為大小為  的單位矩陣。

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

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

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

 變數投影演算法 
交替投影演算法利用低秩近似問題（以像空間參數化）對  與  為雙線性的特性。變數投影法（variable projections）則進一步利用此雙線性結構。G. Golub and V. Pereyra, Separable nonlinear least squares: the variable projection method and its applications, Institute of Physics, Inverse Problems, Volume 19, 2003, Pages 1-26.

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

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

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）。

 元素逐點的 Lp 低秩近似問題 

設 。當  時，最快演算法時間為 。 其中一個重要概念為「Oblivious Subspace Embedding (OSE)」，最早由 Sarlos 提出。

當  時，元素逐點的 L1 範數在面對離群值時比 Frobenius 範數更具魯棒性，適用於雜訊不服從高斯分布的模型。很自然的會想要最小化 。 對於  和 ，已有部分帶有理論保證的演算法。

 距離低秩近似問題 
設  與  為任意度量空間中的兩組點集。令  表示  的矩陣，其中元素定義為 。此類距離矩陣常見於軟體套件中，並應用於學習影像流形（image manifolds）、手寫辨識（handwriting recognition）及多維展開（multi-dimensional unfolding）。為了嘗試縮減其描述大小， 可研究此類矩陣的低秩近似。

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



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

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

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

 引用 

外部連結
C++ package for structured-low rank approximation

Category:数值线性代数
Category:降维
Category:数学最佳化