Question

动机

如果 n×n 矩阵 A 具有 n 个线性独立的特征向量 ，则它是可对角化的。

那么对于一些标量 ，任何 w 都可以表示为 。

练习：证明：

问题：对于较大的 k ，表现如何？

这是幂方法的灵感来源。

代码

def show_ex(v):
    print(', '.join(names[i].decode() for i in np.abs(v.squeeze()).argsort()[-1:-10:-1]))

?np.squeeze

如何规范化稀疏矩阵：

S = sparse.csr_matrix(np.array([[1,2],[3,4]]))
Sr = S.sum(axis=0).A1; Sr

# array([4, 6], dtype=int64)

numpy.matrix.A1 。

S.indices

# array([0, 1, 0, 1], dtype=int32)

S.data

# array([1, 2, 3, 4], dtype=int64)

S.data / np.take(Sr, S.indices)

# array([ 0.25   ,  0.33333,  0.75   ,  0.66667])

def power_method(A, max_iter=100):
    n = A.shape[1]
    A = np.copy(A)
    A.data /= np.take(A.sum(axis=0).A1, A.indices)

    scores = np.ones(n, dtype=np.float32) * np.sqrt(A.sum()/(n*n)) # initial guess
    for i in range(max_iter):
        scores = A @ scores
        nrm = np.linalg.norm(scores)
        scores /= nrm
        print(nrm)

    return scores

问题：为什么要对每次迭代的得分标准化？

scores = power_method(X, max_iter=10)

'''
0.621209
0.856139
1.02793
1.02029
1.02645
1.02504
1.02364
1.02126
1.019
1.01679
'''

show_ex(scores)

'''
Living_people, Year_of_birth_missing_%28living_people%29, United_States, United_Kingdom, Race_and_ethnicity_in_the_United_States_Census, France, Year_of_birth_missing, World_War_II, Germany
'''

mem_usage()

# 11.692331008

评论

在实践中使用的许多高级特征值算法是幂方法的变体。

在第 3 课：背景消除中，我们使用了 Facebook 的 快速随机 pca/svd 库 fbpca 。 查看我们使用的 pca 方法的 源代码 。 它使用的是幂方法！

深入研究

查看 Google 网页排名，幂迭代和 Google Matrix 的第二个特征值 ，观看它收敛过程中的分布的动画。

幂方法的收敛速度是最大特征值与第二大特征值的比率。 它可以通过添加移位来加速。 为了找到除最大值之外的特征值，可以使用称为 deflation 的方法。 详细信息，请参阅 Greenbaum 和 Chartier 的第 12.1 章。

Krylov 子空间：在幂迭代中，注意我们每次乘以矩阵 A ，有效地计算

将这些向量作为列的矩阵称为 Krylov 矩阵，由这些向量跨越的空间是 Krylov 子空间。请记住这些内容以便之后使用。

与 SVD 比较

%time U, s, V = randomized_svd(X, 3, n_iter=3)

'''
CPU times: user 8min 40s, sys: 1min 20s, total: 10min 1s
Wall time: 5min 56s
'''

mem_usage()

# 28.353073152

# 根据主要奇异向量的顶级维基百科页面
show_ex(U.T[0])

# List_of_World_War_II_air_aces, List_of_animated_feature-length_films, List_of_animated_feature_films:2000s, International_Swimming_Hall_of_Fame, List_of_museum_ships, List_of_linguists, List_of_television_programs_by_episode_count, List_of_game_show_hosts, List_of_astronomers

show_ex(U.T[1])

# List_of_former_United_States_senators, List_of_United_States_Representatives_from_New_York, List_of_United_States_Representatives_from_Pennsylvania, Members_of_the_110th_United_States_Congress, List_of_Justices_of_the_Ohio_Supreme_Court, Congressional_endorsements_for_the_2008_United_States_presidential_election, List_of_United_States_Representatives_in_the_110th_Congress_by_seniority, List_of_Members_of_the_United_States_House_of_Representatives_in_the_103rd_Congress_by_seniority, List_of_United_States_Representatives_in_the_111th_Congress_by_seniority

show_ex(V[0])

# United_States, Japan, United_Kingdom, Germany, Race_and_ethnicity_in_the_United_States_Census, France, United_States_Army_Air_Forces, Australia, Canada

show_ex(V[1])

# Democratic_Party_%28United_States%29, Republican_Party_%28United_States%29, Democratic-Republican_Party, United_States, Whig_Party_%28United_States%29, Federalist_Party, National_Republican_Party, Catholic_Church, Jacksonian_democracy

练习：以各种方式规范化数据。 不要覆盖邻接矩阵，而是创建一个新矩阵。 了解你的结果有何不同。

特征值分解与 SVD：

• SVD 涉及 2 个基，特征分解涉及 1 个基
• SVD 基是正交的，特征基通常不是正交的
• 所有矩阵都有 SVD，并非所有矩阵（甚至不是所有的矩阵）都有一个特征值分解。