您所提交的草稿仍需改善。在2025年6月12日由Hehua (留言 )审阅。
条目有很多段落都没有来源，比如“应用”段，请补充上。
如果您想继续改善您的草稿再提交，请单击窗口顶部的“编辑”选项。
如果您尚未解决上面列出的问题而直接提交，您的草稿将再次被拒绝并可能被删除。
如果您需要其它的帮助，请在建立條目專題的詢問桌 询问 即时通讯软件
在提交被接受之前，请不要删除審核的评论或此通知。 在2025年6月12日由Hehua (留言 )审阅。 · 最后由Lyhyhlhly 于36天前编辑。 通知作者 再次提交 请注意，如果问题未得到解决，草稿将再次被拒绝。
低秩近似 (low-rank approximation) 是指用一個較低秩的矩陣去近似給定矩陣的過程。更精確地說，它是一個最佳化 問題，其中損失函數 衡量給定矩陣（資料）與近似矩陣（最佳化變數）之間的擬合程度，並且附帶近似矩陣秩的約束條件。此問題常用於數學模型 建構與資料壓縮 。秩的約束與對符合資料模型複雜度的限制相關。在應用中，近似矩陣通常還會有其他約束，例如非負性及漢克爾結構 。
低秩近似與多種其他技術密切相關，包括主成分分析 、因素分析 、潛在語義分析 、最小全平方法、正交迴歸及動態模態分解。
給定
結構映射
S
:
R
n
p
→
R
m
×
n
{\displaystyle {\mathcal {S}}:\mathbb {R} ^{n_{p}}\to \mathbb {R} ^{m\times n}}
結構參數向量
p
∈
R
n
p
{\displaystyle p\in \mathbb {R} ^{n_{p}}}
範數
‖
⋅
‖
{\displaystyle \|\cdot \|}
希望的秩
r
{\displaystyle r}
min
p
^
‖
p
−
p
^
‖
subject to
rank
(
S
(
p
^
)
)
≤
r
{\displaystyle \min _{\widehat {p}}\|p-{\widehat {p}}\|\quad {\text{subject to}}\quad \operatorname {rank} {\big (}{\mathcal {S}}({\widehat {p}}){\big )}\leq r}
無結構且擬合度以弗羅貝尼烏斯範數 衡量的問題，即
min
D
^
‖
D
−
D
^
‖
F
subject to
rank
(
D
^
)
≤
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] [ 2] [ 3]
D
=
U
Σ
V
⊤
∈
R
m
×
n
,
m
≥
n
{\displaystyle D=U\Sigma V^{\top }\in \mathbb {R} ^{m\times n},\quad m\geq n}
為
D
{\displaystyle D}
Σ
=:
diag
(
σ
1
,
…
,
σ
r
)
{\displaystyle \Sigma =:\operatorname {diag} (\sigma _{1},\ldots ,\sigma _{r})}
r
≤
min
{
m
,
n
}
=
n
{\displaystyle r\leq \min\{m,n\}=n}
m
×
n
{\displaystyle m\times n}
r
{\displaystyle r}
σ
1
≥
⋯
≥
σ
r
>
σ
r
+
1
=
⋯
=
σ
n
=
0
{\displaystyle \sigma _{1}\geq \cdots \geq \sigma _{r}>\sigma _{r+1}=\cdots =\sigma _{n}=0}
k
∈
{
1
,
…
,
r
}
{\displaystyle k\in \{1,\dots ,r\}}
U
{\displaystyle U}
Σ
{\displaystyle \Sigma }
V
{\displaystyle V}
U
=:
[
U
1
U
2
]
,
Σ
=:
[
Σ
1
0
0
Σ
2
]
,
且
V
=:
[
V
1
V
2
]
,
{\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}},}
其中
U
1
{\displaystyle U_{1}}
m
×
k
{\displaystyle m\times k}
Σ
1
{\displaystyle \Sigma _{1}}
k
×
k
{\displaystyle k\times k}
V
1
{\displaystyle V_{1}}
n
×
k
{\displaystyle n\times k}
k
{\displaystyle k}
D
^
∗
=
U
1
Σ
1
V
1
⊤
,
{\displaystyle {\widehat {D}}^{*}=U_{1}\Sigma _{1}V_{1}^{\top },}
且滿足
‖
D
−
D
^
∗
‖
F
=
min
rank
(
D
^
)
≤
k
‖
D
−
D
^
‖
F
=
σ
k
+
1
2
+
⋯
+
σ
r
2
.
{\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}}}.}
當且僅當
σ
k
>
σ
k
+
1
{\displaystyle \sigma _{k}>\sigma _{k+1}}
D
^
∗
{\displaystyle {\widehat {D}}^{*}}
譜範數 ）[ 编辑 ] 設
A
∈
R
m
×
n
{\displaystyle A\in \mathbb {R} ^{m\times n}}
m
≤
n
{\displaystyle m\leq n}
A
=
U
Σ
V
⊤
{\displaystyle A=U\Sigma V^{\top }}
為
A
{\displaystyle A}
奇異值分解 ，其中
U
{\displaystyle U}
V
{\displaystyle V}
Σ
{\displaystyle \Sigma }
m
×
n
{\displaystyle m\times n}
(
σ
1
,
σ
2
,
…
,
σ
m
)
{\displaystyle (\sigma _{1},\sigma _{2},\ldots ,\sigma _{m})}
σ
1
≥
σ
2
≥
⋯
≥
σ
m
≥
0
{\displaystyle \sigma _{1}\geq \sigma _{2}\geq \cdots \geq \sigma _{m}\geq 0}
我們宣稱，在譜範數
‖
⋅
‖
2
{\displaystyle \|\cdot \|_{2}}
A
{\displaystyle A}
k
{\displaystyle k}
A
k
:=
∑
i
=
1
k
σ
i
u
i
v
i
⊤
{\displaystyle A_{k}:=\sum _{i=1}^{k}\sigma _{i}u_{i}v_{i}^{\top }}
其中
u
i
{\displaystyle u_{i}}
v
i
{\displaystyle v_{i}}
U
{\displaystyle U}
V
{\displaystyle V}
i
{\displaystyle i}
首先，注意
‖
A
−
A
k
‖
2
=
‖
∑
i
=
1
n
σ
i
u
i
v
i
⊤
−
∑
i
=
1
k
σ
i
u
i
v
i
⊤
‖
2
=
‖
∑
i
=
k
+
1
n
σ
i
u
i
v
i
⊤
‖
2
=
σ
k
+
1
.
{\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}.}
因此，我們要證明若
B
k
=
X
Y
⊤
{\displaystyle B_{k}=XY^{\top }}
X
{\displaystyle X}
Y
{\displaystyle Y}
k
{\displaystyle k}
‖
A
−
A
k
‖
2
=
σ
k
+
1
≤
‖
A
−
B
k
‖
2
.
{\displaystyle \|A-A_{k}\|_{2}=\sigma _{k+1}\leq \|A-B_{k}\|_{2}.}
由於
Y
{\displaystyle Y}
k
{\displaystyle k}
k
+
1
{\displaystyle k+1}
w
=
γ
1
v
1
+
⋯
+
γ
k
+
1
v
k
+
1
,
{\displaystyle w=\gamma _{1}v_{1}+\cdots +\gamma _{k+1}v_{k+1},}
使得
Y
⊤
w
=
0
{\displaystyle Y^{\top }w=0}
w
{\displaystyle w}
‖
w
‖
2
=
1
{\displaystyle \|w\|_{2}=1}
γ
1
2
+
⋯
+
γ
k
+
1
2
=
1
{\displaystyle \gamma _{1}^{2}+\cdots +\gamma _{k+1}^{2}=1}
‖
A
−
B
k
‖
2
2
≥
‖
(
A
−
B
k
)
w
‖
2
2
=
‖
A
w
‖
2
2
=
γ
1
2
σ
1
2
+
⋯
+
γ
k
+
1
2
σ
k
+
1
2
≥
σ
k
+
1
2
.
{\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}.}
由上述不等式兩邊取平方根即得證。
設
A
∈
R
m
×
n
{\displaystyle A\in \mathbb {R} ^{m\times n}}
m
≤
n
{\displaystyle m\leq n}
A
=
U
Σ
V
⊤
{\displaystyle A=U\Sigma V^{\top }}
為
A
{\displaystyle A}
奇異值分解 。
我們主張，對於 Frobenius 範數（記為
‖
⋅
‖
F
{\displaystyle \|\cdot \|_{F}}
A
{\displaystyle A}
k
{\displaystyle k}
A
k
=
∑
i
=
1
k
σ
i
u
i
v
i
⊤
{\displaystyle A_{k}=\sum _{i=1}^{k}\sigma _{i}u_{i}v_{i}^{\top }}
其中
u
i
{\displaystyle u_{i}}
v
i
{\displaystyle v_{i}}
U
{\displaystyle U}
V
{\displaystyle V}
i
{\displaystyle i}
首先注意，我們有
‖
A
−
A
k
‖
F
2
=
‖
∑
i
=
k
+
1
n
σ
i
u
i
v
i
⊤
‖
F
2
=
∑
i
=
k
+
1
n
σ
i
2
{\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}}
因此，我們需要證明：若
B
k
=
X
Y
⊤
{\displaystyle B_{k}=XY^{\top }}
X
{\displaystyle X}
Y
{\displaystyle Y}
k
{\displaystyle k}
‖
A
−
A
k
‖
F
2
=
∑
i
=
k
+
1
n
σ
i
2
≤
‖
A
−
B
k
‖
F
2
.
{\displaystyle \|A-A_{k}\|_{F}^{2}=\sum _{i=k+1}^{n}\sigma _{i}^{2}\leq \|A-B_{k}\|_{F}^{2}.}
利用譜範數的三角不等式，若
A
=
A
′
+
A
″
{\displaystyle A=A'+A''}
σ
1
(
A
)
≤
σ
1
(
A
′
)
+
σ
1
(
A
″
)
.
{\displaystyle \sigma _{1}(A)\leq \sigma _{1}(A')+\sigma _{1}(A'').}
設
A
k
′
{\displaystyle A'_{k}}
A
k
″
{\displaystyle A''_{k}}
A
′
{\displaystyle A'}
A
″
{\displaystyle A''}
k
{\displaystyle k}
i
,
j
≥
1
{\displaystyle i,j\geq 1}
σ
i
(
A
′
)
+
σ
j
(
A
″
)
=
σ
1
(
A
′
−
A
i
−
1
′
)
+
σ
1
(
A
″
−
A
j
−
1
″
)
≥
σ
1
(
A
−
A
i
−
1
′
−
A
j
−
1
″
)
≥
σ
1
(
A
−
A
i
+
j
−
2
)
(
∵
r
a
n
k
(
A
i
−
1
′
+
A
j
−
1
″
)
≤
i
+
j
−
2
)
)
=
σ
i
+
j
−
1
(
A
)
.
{\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}}}
因為
σ
k
+
1
(
B
k
)
=
0
{\displaystyle \sigma _{k+1}(B_{k})=0}
A
′
=
A
−
B
k
{\displaystyle A'=A-B_{k}}
A
″
=
B
k
{\displaystyle A''=B_{k}}
i
≥
1
{\displaystyle i\geq 1}
σ
i
(
A
−
B
k
)
≥
σ
k
+
i
(
A
)
.
{\displaystyle \sigma _{i}(A-B_{k})\geq \sigma _{k+i}(A).}
因此，
‖
A
−
B
k
‖
F
2
=
∑
i
=
1
n
σ
i
(
A
−
B
k
)
2
≥
∑
i
=
k
+
1
n
σ
i
(
A
)
2
=
‖
A
−
A
k
‖
F
2
,
{\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 範數對近似誤差
D
−
D
^
{\displaystyle D-{\widehat {D}}}
min
D
^
vec
(
D
−
D
^
)
⊤
W
vec
(
D
−
D
^
)
subject to
rank
(
D
^
)
≤
r
,
{\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,}
其中
vec
(
A
)
{\displaystyle \operatorname {vec} (A)}
A
{\displaystyle A}
W
{\displaystyle W}
一般加權低秩近似問題無法透過奇異值分解求得解析解，需使用局部優化方法，且無法保證能找到全域最優解。
當權重為無相關性時，加權低秩近似問題亦可如下表示：[ 4] [ 5]
W
{\displaystyle W}
A
{\displaystyle A}
∑
i
,
j
(
W
i
,
j
(
A
i
,
j
−
B
i
,
j
)
)
2
{\displaystyle \sum _{i,j}{\big (}W_{i,j}(A_{i,j}-B_{i,j}){\big )}^{2}}
在秩不超過
r
{\displaystyle r}
B
{\displaystyle B}
利用等價關係
rank
(
D
^
)
≤
r
⟺
∃
P
∈
R
m
×
r
,
L
∈
R
r
×
n
s.t.
D
^
=
P
L
{\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}
及
rank
(
D
^
)
≤
r
⟺
∃
R
∈
R
(
m
−
r
)
×
m
,
rank
(
R
^
)
=
m
−
r
s.t.
R
D
^
=
0
{\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}
加權低秩近似問題可轉換為參數優化問題
min
D
^
,
P
,
L
vec
⊤
(
D
−
D
^
)
W
vec
(
D
−
D
^
)
subject to
D
^
=
P
L
{\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}
及
min
D
^
,
R
vec
⊤
(
D
−
D
^
)
W
vec
(
D
−
D
^
)
subject to
R
D
^
=
0
,
R
R
⊤
=
I
r
,
{\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},}
其中
I
r
{\displaystyle I_{r}}
r
{\displaystyle r}
秩約束的像空間表示啟發了一種參數優化方法，即交替固定其中一組變數（
P
{\displaystyle P}
L
{\displaystyle L}
P
{\displaystyle P}
L
{\displaystyle L}
該演算法稱為交替投影（alternating projections），在加權低秩近似問題中可保證全域收斂且收斂速率為線性，收斂至局部最優解。使用者需給定初始
P
{\displaystyle P}
L
{\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
交替投影演算法利用低秩近似問題（以像空間參數化）對
P
{\displaystyle P}
L
{\displaystyle L}
[ 6]
考慮加權低秩近似問題的像空間參數化，對
L
{\displaystyle L}
P
{\displaystyle P}
f
(
P
)
=
vec
⊤
(
D
)
(
W
−
W
(
I
n
⊗
P
)
(
(
I
n
⊗
P
)
⊤
W
(
I
n
⊗
P
)
)
−
1
(
I
n
⊗
P
)
⊤
W
)
vec
(
D
)
.
{\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)}}.}
因此原問題等價於非線性最小平方問題，透過標準優化方法（如萊文伯格-馬夸特方法 ）可求解
f
(
P
)
{\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）。
設
‖
A
‖
p
=
(
∑
i
,
j
|
A
i
,
j
p
|
)
1
/
p
{\displaystyle \|A\|_{p}=\left(\sum _{i,j}|A_{i,j}^{p}|\right)^{1/p}}
p
=
2
{\displaystyle p=2}
n
n
z
(
A
)
+
n
⋅
p
o
l
y
(
k
/
ϵ
)
{\displaystyle nnz(A)+n\cdot \mathrm {poly} (k/\epsilon )}
[ 7] [ 8] [ 9]
當
p
=
1
{\displaystyle p=1}
‖
B
−
A
‖
1
{\displaystyle \|B-A\|_{1}}
[ 10]
p
=
0
{\displaystyle p=0}
p
≥
1
{\displaystyle p\geq 1}
[ 11] [ 12]
設
P
=
p
1
,
…
,
p
m
{\displaystyle P={p_{1},\ldots ,p_{m}}}
Q
=
q
1
,
…
,
q
n
{\displaystyle Q={q_{1},\ldots ,q_{n}}}
A
{\displaystyle A}
m
×
n
{\displaystyle m\times n}
A
i
,
j
=
dist
(
p
i
,
q
j
)
{\displaystyle A_{i,j}=\operatorname {dist} (p_{i},q_{j})}
[ 13] [ 14]
通常，我們不僅希望解為低秩，還要符合應用需求的其他凸限制。問題可表述為：
minimize
over
p
^
‖
p
−
p
^
‖
subject to
rank
(
S
(
p
^
)
)
≤
r
and
g
(
p
^
)
≤
0
{\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}
此問題有多項實際應用，包括從不精確的（半正定規劃）鬆弛中恢復良好解。若額外限制
g
(
p
^
)
≤
0
{\displaystyle g({\widehat {p}})\leq 0}
[ 15]
此問題雖具有實用價值，但由於同時涉及凸限制與非凸的低秩限制，因此具有相當的挑戰性。根據不同形式的限制條件
g
(
p
^
)
≤
0
{\displaystyle g({\widehat {p}})\leq 0}
[ 16]
^ E. Schmidt, Zur Theorie der linearen und nichtlinearen Integralgleichungen, Math. Annalen 63 (1907), 433-476. doi :10.1007/BF01449770
^ C. Eckart, G. Young, The approximation of one matrix by another of lower rank. Psychometrika, Volume 1, 1936, Pages 211–8. doi :10.1007/BF02288367
^ L. Mirsky, Symmetric gauge functions and unitarily invariant norms, Q.J. Math. 11 (1960), 50-59. doi :10.1093/qmath/11.1.50
^ Srebro, Nathan; Jaakkola, Tommi. Weighted Low-Rank Approximations (PDF) . ICML'03. 2003. ^ Razenshteyn, Ilya; Song, Zhao; Woodruff, David P. Weighted Low Rank Approximations with Provable Guarantees . STOC '16 Proceedings of the forty-eighth annual ACM symposium on Theory of Computing. 2016. ^ 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.
^ Clarkson, Kenneth L.; Woodruff, David P. Low Rank Approximation and Regression in Input Sparsity Time. STOC '13 Proceedings of the forty-fifth annual ACM symposium on Theory of Computing. 2013. arXiv:1207.6365 ^ Nelson, Jelani; Nguyen, Huy L. OSNAP: Faster numerical linear algebra algorithms via sparser subspace embeddings. FOCS '13. 2013. arXiv:1211.1002 ^ Sarlos, Tamas. Improved approximation algorithms for large matrices via random projections. FOCS'06. 2006. ^ Song, Zhao; Woodruff, David P.; Zhong, Peilin. Low Rank Approximation with Entrywise L1-Norm Error. STOC '17 Proceedings of the forty-ninth annual ACM symposium on Theory of Computing. 2017. arXiv:1611.00898 ^ Bringmann, Karl; Kolev, Pavel; Woodruff, David P. Approximation Algorithms for L0-Low Rank Approximation. NIPS'17. 2017. arXiv:1710.11253 ^ Chierichetti, Flavio; Gollapudi, Sreenivas; Kumar, Ravi; Lattanzi, Silvio; Panigrahy, Rina; Woodruff, David P. Algorithms for Lp Low-Rank Approximation. ICML'17. 2017. arXiv:1705.06730 ^ Bakshi, Ainesh L.; Woodruff, David P. Sublinear Time Low-Rank Approximation of Distance Matrices. NeurIPS. 2018. arXiv:1809.06986 ^ Indyk, Piotr; Vakilian, Ali; Wagner, Tal; Woodruff, David P. Sample-Optimal Low-Rank Approximation of Distance Matrices. COLT. 2019. ^ Chu, Moody T.; Funderlic, Robert E.; Plemmons, Robert J. structured low-rank approximation. Linear Algebra and Its Applications. 2003, 366 : 157–172. doi:10.1016/S0024-3795(02)00505-0 ^ A General System for Heuristic Solution of Convex Problems over Nonconvex Sets (PDF) .
Category:数值线性代数
Category:降维
Category:数学最佳化
.
