CUR分解
要理解CUR分解，需要先看下SVD分解。SVD理論以及Python實現
算法流程
給定輸入的矩陣A。
A = C ? U ? R A = C* U *R A = C ? U ? R
- 隨機選r個列構成C和r個行構成R（也可以使用，平方和加權過的行和列（ 常用 ））
- 然后選取W矩陣（C和R的交集，也就是被選出來的部分，在C和R中同時出現的A矩陣中的位置。）
- 對W做SVD分解，得到 X ∑ Y T X\sum Y^T X ∑ Y T
- 對 ∑ \sum ∑ 做廣義逆矩陣 ( ∑ ) + (\sum)^+ ( ∑ ) + ，也就是只有非0元的部分才變成原來的倒數。
- U = Y ? ( ∑ ) + ? X T U = Y*(\sum)^+* X^T U = Y ? ( ∑ ) + ? X T
Python實現
- 導入包
import
numpy
as
np
- 數據
A
=
np
.
linspace
(
0
,
14
,
15
)
.
reshape
(
(
3
,
-
1
)
)
- 算法
def
CUR
(
A
,
n
)
:
A_sq
=
A
**
2
sum_A_sq
=
np
.
sum
(
A_sq
)
sum_A_sq_0
=
np
.
sum
(
A_sq
,
axis
=
0
)
sum_A_sq_1
=
np
.
sum
(
A_sq
,
axis
=
1
)
P_x_c
=
sum_A_sq_0
/
sum_A_sq
P_x_r
=
sum_A_sq_1
/
sum_A_sq
r
,
c
=
A
.
shape
c_index
=
[
np
.
random
.
choice
(
np
.
arange
(
0
,
c
)
,
p
=
P_x_c
)
for
i
in
range
(
n
)
]
r_index
=
[
np
.
random
.
choice
(
np
.
arange
(
0
,
r
)
,
p
=
P_x_r
)
for
i
in
range
(
n
)
]
# print(c_index, r_index)
C
=
A
[
:
,
c_index
]
R
=
A
[
r_index
,
:
]
W
=
C
[
r_index
]
# print(C, R, W)
def
SVD
(
A
,
n
)
:
M
=
np
.
dot
(
A
,
A
.
T
)
eigval
,
eigvec
=
np
.
linalg
.
eig
(
M
)
indexes
=
np
.
argsort
(
-
eigval
)
[
:
n
]
U
=
eigvec
[
:
,
indexes
]
sigma_sq
=
eigval
[
indexes
]
M
=
np
.
dot
(
A
.
T
,
A
)
eigval
,
eigvec
=
np
.
linalg
.
eig
(
M
)
indexes
=
np
.
argsort
(
-
eigval
)
[
:
n
]
V
=
eigvec
[
:
,
indexes
]
sigma
=
sigma_sq
# not diag and not sqrt
return
U
,
sigma
,
V
X
,
sigma
,
Y
=
SVD
(
W
,
n
)
for
i
in
range
(
len
(
sigma
)
)
:
if
sigma
[
i
]
==
0
:
continue
else
:
sigma
[
i
]
=
1
/
sigma
[
i
]
sigma
=
np
.
diag
(
sigma
)
U
=
np
.
dot
(
np
.
dot
(
Y
,
sigma
)
,
X
.
T
)
return
np
.
dot
(
np
.
dot
(
C
,
U
)
,
R
)
- 調用
CUR
(
A
,
3
)
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
