当前位置：文档之家 › SVD(奇异值分解)算法及其评估

SVD(奇异值分解)算法及其评估

  • 格式：pdf
  • 大小：419.60 KB
  • 文档页数：43

下载文档原格式

  / 43

合集下载

随机矩阵奇异值分解算法在机器学习中的应用优化与效果评估

随机矩阵奇异值分解算法在机器学习中的应用优化与效果评估

随机矩阵奇异值分解算法在机器学习中的应用优化与效果评估随机矩阵奇异值分解（Randomized Singular Value Decomposition，简称RSVD）算法是一种常用的矩阵分解方法，广泛应用于机器学习领域。

本文将探讨该算法在机器学习中的应用优化及效果评估。

一、介绍RSVD算法是基于奇异值分解（Singular Value Decomposition，简称SVD）算法的一种改进方法。

与传统的SVD算法相比，RSVD通过随机选择矩阵的列向量构建一个近似矩阵，然后再对该近似矩阵进行SVD分解，从而在减少计算量的同时，保持了较高的分解精度。

二、应用优化1.计算效率优化传统的SVD算法计算复杂度较高，随着数据规模的增大，计算时间会显著增加。

RSVD算法通过随机选择矩阵的列向量，将原始矩阵的规模缩小，从而减少了计算时间。

此外，RSVD还可以通过调节随机选择的列向量的数量来平衡计算效率和分解精度之间的关系。

2.精度保证优化尽管RSVD算法在计算效率上有较大优势，但在一些场景下可能会对分解精度产生影响。

为了保证结果的精度，可以适当增加随机选择的列向量的数量，提高近似矩阵的质量，从而达到更高的分解精度。

三、效果评估1.算法比较实验为了评估RSVD算法在机器学习中的效果，可以搭建实验环境，对RSVD算法与其他矩阵分解算法进行比较。

实验可以选择一些具有代表性的数据集，如Movielens数据集，通过对比不同算法在预测评分准确度和计算时间上的表现，来评估RSVD算法在推荐系统等应用中的优势。

2.性能对比评估除了算法比较实验外，还可以进行性能对比评估。

通过对比不同规模数据集上RSVD算法的计算时间和内存占用等指标，来分析RSVD算法的可扩展性和适用性。

四、总结RSVD算法作为一种优化的矩阵分解方法，在机器学习领域有着广泛的应用。

通过对矩阵的随机选择和近似构建，RSVD可以在保证一定分解精度的同时，显著提高计算效率。

矩阵的奇异值分解

矩阵的奇异值分解

矩阵的奇异值分解（Singular Value Decomposition，SVD）是一种重要的矩阵分解方法，可以将一个复杂的矩阵分解为三个简单的矩阵相乘的形式。

SVD 可以应用于各种领域，如图像处理、语音识别、推荐系统等。

SVD 分解将一个m × n 的矩阵 M 分解为U × Σ × V^T 的形式，其中 U 是一个m × m 的酉矩阵（unitary matrix），Σ 是一个m × n 的矩阵，只有对角线上的元素大于等于 0，V^T 是一个n × n 的酉矩阵。

通常情况下，SVD 可以通过奇异值分解定理进行求解。

首先，我们需要计算矩阵M × M^T 和M^T × M 的特征向量和特征值。

设 M 是一个m × n 的矩阵，M^T 是它的转置矩阵，那么M × M^T 是一个m × m 的矩阵，M^T × M 是一个n × n 的矩阵。

我们可以通过特征值分解方法求解这两个矩阵的特征向量和特征值。

然后，我们可以将M × M^T 和M^T × M 的特征向量和特征值组成两个酉矩阵 U 和 V。

特征值的平方根构成了Σ 矩阵的对角线元素。

我们可以将 U 和V 按照特征值降序排列，以保证U × Σ × V^T 是一个矩阵。

最后，我们可以利用奇异值分解定理，将 M 分解为U × Σ × V^T 的形式。

这样的分解可以帮助我们理解原始矩阵的结构和特征，提取重要信息，并进行维度降低等操作。

在某些情况下，SVD 还可以作为矩阵的伪逆（pseudo-inverse），帮助我们解决线性方程组等问题。

SVD 分解在各个领域都有广泛的应用。

在图像处理中，SVD 可以用于图像压缩和降噪等操作。

在语音识别中，SVD 可以用于语音特征提取和模式匹配。

矩阵奇异值分解算法及应用改进分析

矩阵奇异值分解算法及应用改进分析

矩阵奇异值分解算法及应用改进分析矩阵奇异值分解（Singular Value Decomposition, SVD）是一种常用的矩阵分解方法。

在大数据处理、图像处理、推荐系统等领域都有广泛的应用。

本文将介绍SVD的基本原理，并对其应用进行改进分析。

一、矩阵奇异值分解的基本原理矩阵奇异值分解是将一个矩阵分解为三个矩阵相乘的形式。

设M 是一个m行n列的实数矩阵，那么SVD可表示为以下形式：M=UΣV^T其中，U是一个m行m列的正交矩阵，Σ是一个m行n列的对角矩阵，V^T是一个n行n列的正交矩阵。

对角矩阵Σ的对角线元素称为奇异值，代表了原始矩阵在相应方向上的信息量。

在矩阵奇异值分解中，U矩阵是原始矩阵M乘以其转置M^T的特征向量组成的矩阵，V矩阵是M^T乘以M的特征向量组成的矩阵。

特征向量的选择保证了矩阵的正交性，而奇异值的排序表明了它们的重要性，排序靠前的奇异值所对应的特征向量往往包含了较多的信息。

二、SVD的应用改进分析1. 矩阵降维和压缩在大数据处理中，往往需要对高维稀疏矩阵进行降维和压缩。

通过SVD分解后，可以选择保留较小的奇异值和对应的特征向量，从而实现对矩阵的降维和压缩。

降维和压缩后的矩阵占用更小的存储空间，便于后续的计算和处理。

2. 推荐系统在推荐系统中，SVD可以被用于对用户和物品之间的关系进行建模。

通过对用户-物品评分矩阵进行SVD分解，可以得到用户和物品的隐含特征向量。

利用这些特征向量，可以给用户推荐未曾接触过的物品。

3. 图像处理SVD也被广泛应用于图像压缩和去噪领域。

通过对图像矩阵进行SVD分解，可以得到图像的主要特征分量。

如果舍弃一些较小的奇异值和对应的特征向量，可以实现对图像的降噪和压缩。

4. 数据挖掘SVD还可以用于数据挖掘中的降维和特征提取。

通过保留较大的奇异值和对应的特征向量，可以提取出数据中最重要的特征，并减少数据的维度，从而提高后续的数据挖掘效果和计算效率。

三、结论矩阵奇异值分解是一种重要的矩阵分解方法，具有广泛的应用前景。

随机矩阵奇异值分解算法在知识表达中应用效果评估

随机矩阵奇异值分解算法在知识表达中应用效果评估

随机矩阵奇异值分解算法在知识表达中应用效果评估随机矩阵奇异值分解（RSVD）算法是一种应用于大规模数据处理的有效方法，它可以用于知识表达中的数据降维和特征提取。

本文将对RSVD算法在知识表达中的应用效果进行评估，并探讨其优点和局限性。

一、介绍在知识表达任务中，需要从大量的文本数据中提取有用的信息和特征。

传统的机器学习算法通常在处理大规模数据时会面临计算耗时和存储开销大的问题。

而RSVD算法通过随机采样的方式，对原始数据进行了降维处理，从而大大减少了计算开销和存储开销。

二、RSVD算法原理RSVD算法的核心思想是通过矩阵奇异值分解（SVD）来实现数据的降维和特征提取。

传统的SVD算法需要对整个数据矩阵进行分解，计算复杂度较高。

而RSVD算法则通过随机采样的方式，仅对采样后的子集进行SVD分解，从而降低了计算复杂度。

经过分解得到的奇异值和奇异向量可以表示原始数据的主要特征，可以应用于知识表达任务中。

三、RSVD算法在知识表达中的应用1. 数据降维知识表达任务中，常常需要处理大规模的高维数据。

RSVD算法可以通过降维，将高维数据映射到低维空间中，从而减少数据的冗余和噪声，提取出数据的主要特征。

这样不仅可以减小计算开销，还可以提高模型的准确性和泛化能力。

2. 特征提取RSVD算法还可以用于特征提取。

通过对原始数据进行RSVD分解，得到的奇异向量表示了数据的重要特征。

这些特征可以应用于知识表达任务，比如文本分类、推荐系统等。

在文本分类中，可以利用RSVD得到的特征向量表示文本的语义信息，从而实现有效的分类。

在推荐系统中，可以利用RSVD提取出用户和物品的隐含特征，用于个性化推荐。

四、RSVD算法的评估指标对于评估RSVD算法在知识表达中的应用效果，可以采用以下指标：1. 准确性：评估算法在知识表达任务中的分类或预测准确率。

2. 效率：评估算法在处理大规模数据时的计算效率和存储开销。

3. 泛化能力：评估算法在未知数据上的表现能力，即模型的泛化能力。

随机矩阵奇异值分解算法在图像去噪中的应用效果评估

随机矩阵奇异值分解算法在图像去噪中的应用效果评估

随机矩阵奇异值分解算法在图像去噪中的应用效果评估随机矩阵奇异值分解（Randomized Singular Value Decomposition，简称rSVD）是一种高效的矩阵分解算法，已在许多领域得到广泛应用。

本文将评估rSVD算法在图像去噪中的应用效果。

一、引言图像去噪是数字图像处理中的重要任务之一。

随着图像采集设备的不断发展，图像噪声问题也变得日益突出。

传统的去噪方法如小波变换、均值滤波等存在着对细节信息的模糊以及计算复杂度较高的问题。

因此，研究一种有效的图像去噪算法具有重要意义。

二、rSVD算法原理rSVD算法是基于奇异值分解（Singular Value Decomposition，简称SVD）的一种近似算法。

传统的SVD算法可以将一个矩阵分解为三个矩阵的乘积，即A = UΣV^T，其中U和V是正交矩阵，Σ是对角矩阵。

但是，在实际应用中，SVD计算复杂度较高，因此rSVD算法提出了一种近似的计算方法。

rSVD算法的基本思想是通过随机映射将原始矩阵A降维，然后对降维后的矩阵进行SVD分解。

具体步骤如下：1. 从标准正态分布中随机生成一个n×k的矩阵P；2. 计算样本矩阵B = AP；3. 对B进行SVD分解，得到B = UΣV^T；4. 计算原始矩阵的近似矩阵A' = UΣV^TPT。

三、rSVD在图像去噪中的应用在图像去噪中，可以将图像看作一个矩阵，并将之前的rSVD算法应用于图像去噪任务中。

具体步骤如下：1. 读取待去噪的图像，并将其转换为灰度图像；2. 将图像转换为矩阵形式，并进行归一化处理；3. 对图像矩阵应用rSVD算法，得到近似矩阵；4. 对近似矩阵进行反归一化处理，并显示去噪结果。

四、实验设计与结果分析为了评估rSVD算法在图像去噪中的应用效果，我们选取了多张包含不同程度噪声的图像作为实验样本。

通过与传统的去噪方法进行对比，我们评估了rSVD算法的去噪效果。

矩阵奇异值分解具体计算过程_解释说明以及概述

矩阵奇异值分解具体计算过程_解释说明以及概述

矩阵奇异值分解具体计算过程解释说明以及概述1. 引言1.1 概述矩阵奇异值分解（Singular Value Decomposition，简称SVD）是一种重要的矩阵分解方法，广泛应用于数据降维、图像处理、推荐系统和信号处理等领域。

通过将一个矩阵分解为三个独特的部分，即原始矩阵的奇异向量和奇异值，SVD 可以提供有关原始数据的宝贵信息。

本文旨在详细介绍矩阵奇异值分解的具体计算过程，并对其应用领域以及算法优化和改进方向进行探讨。

首先，我们将给出该方法的定义和基本原理，并描述其计算方法和数学推导。

接着，我们将深入探究矩阵奇异值分解在图像压缩与降维、推荐系统和数据挖掘以及信号处理和模式识别等方面的应用。

然后，我们将讨论近似求解算法、加速技术以及大规模矩阵奇异值分解算法的最新进展。

最后，我们还将探索结合其他矩阵分解技术发展方向。

1.2 文章结构本文共包含五个主要部分。

第一部分是引言，主要概述了本文的目的和结构。

第二部分将详细介绍矩阵奇异值分解的具体计算过程，包括定义、基本原理、计算方法和数学推导。

第三部分将解释说明矩阵奇异值分解在不同领域中的应用，如图像压缩与降维、推荐系统和数据挖掘以及信号处理和模式识别。

第四部分将讨论矩阵奇异值分解算法的优化和改进方向，包括近似求解算法、加速技术以及结合其他矩阵分解技术的发展方向。

最后一部分是结论，总结文章的主要内容和贡献，并对未来研究方向进行展望。

1.3 目的本文旨在通过详细讲解矩阵奇异值分解的具体计算过程，深入理解其原理和应用，并探讨其改进方向。

通过对该方法进行全面系统地介绍，希望能够增加读者对矩阵奇异值分解有关知识的了解，并为相关领域的研究者提供参考和启示。

同时，本文也为后续相关领域深入研究和应用提供了理论基础和开发方向。

2. 矩阵奇异值分解具体计算过程2.1 矩阵奇异值分解定义和基本原理矩阵奇异值分解（Singular Value Decomposition，简称SVD）是一种常用的矩阵分解方法。

了解机器学习的SVD算法

了解机器学习的SVD算法机器学习的SVD算法机器学习是人工智能领域中一个非常重要的分支，其在数据建模、分类与回归、模式识别等领域都有广泛的应用。

其中，矩阵分解是机器学习领域的重要技术之一。

矩阵的分解可以将原始矩阵分解为更多有意义的子矩阵，这些子矩阵可以帮助我们理解和处理数据。

SVD（奇异值分解）算法就是一种矩阵分解的方法，通过将一个大的矩阵分解成三个小的矩阵来实现矩阵的分解。

一、理解SVD算法SVD算法的核心思想是将矩阵分解成三个矩阵的乘积，分别是左奇异矩阵U、奇异值矩阵Σ和右奇异矩阵VT。

其中，U和VT矩阵都是正交矩阵（orthogonal matrix），Σ矩阵是对角矩阵（diagonal matrix）。

下面是SVD算法的数学公式：M=UΣVT其中，M表示原始矩阵，U表示左奇异矩阵，Σ表示奇异值矩阵，VT表示右奇异矩阵。

这个公式的意义是将原始矩阵M分解为三个小矩阵U、Σ和VT的乘积。

在这个分解过程中，U矩阵和VT矩阵都是正交矩阵，Σ矩阵是对角矩阵。

二、SVD算法的应用SVD算法可用于大量机器学习的任务中。

以下是具体应用事例：1. 图像压缩SVD算法是图像压缩中最常用的算法之一。

图像可以表示为一个矩阵，利用SVD算法将一个大的矩阵分解成三个小的矩阵后，可以通过选择奇异值较大的子矩阵来实现图像的压缩。

由于大多数图像中的信息都分布在少数的奇异值中，因此可以大大压缩图像的大小。

2. 推荐系统在推荐系统中，利用SVD算法可以快速计算出用户对物品的评分。

将用户对物品的评分矩阵分解成三个小矩阵后，可以通过计算用户和物品的奇异值矩阵来实现推荐算法。

在实际应用中，SVD算法可以帮助用户发现物品的隐藏特征，从而更好地进行推荐。

3. 协同过滤协同过滤是将用户的偏好关联到其他用户的偏好上，获取物品的推荐评分。

SVD算法可以从偏好矩阵中获取用户的偏好，将原始矩阵分解成三个矩阵，并选择部分奇异值和对应的向量，就可以得到一个低维的奇异向量矩阵。

奇异值矩阵分解算法改进设计与应用效果分析

奇异值矩阵分解算法改进设计与应用效果分析1.引言奇异值矩阵分解（Singular Value Matrix Factorization, SVD）是一种常用的矩阵分解算法，被广泛应用于推荐系统、图像压缩、自然语言处理等领域。

然而，在实际应用中，原始的SVD算法存在一些限制，如计算复杂度较高、容易产生过拟合等问题。

为了克服这些限制，研究者们提出了一系列的改进设计，本文将对这些改进进行分析，并评估其在实际应用中的效果。

2.奇异值矩阵分解算法2.1 基本原理SVD算法通过将矩阵分解为三个矩阵的乘积，实现对原始矩阵的降维和特征提取。

具体而言，对于一个m×n的矩阵A，SVD将其分解为U、S和V三个矩阵的乘积，即A=USV^T，其中U和V是正交矩阵，S是对角矩阵。

S的对角元素称为奇异值，表示矩阵A在对应的特征向量方向上的重要性。

2.2 算法流程传统的SVD算法主要包括以下几个步骤：（1）计算A^TA的特征向量和特征值，得到V；（2）计算AA^T的特征向量和特征值，得到U；（3）将A进行奇异值分解，得到S。

3.算法改进设计3.1 隐式反馈数据处理在许多应用场景中，用户对物品的喜好往往是隐式的，例如用户的点击、观看历史等。

传统的SVD算法无法直接利用这些隐式反馈数据，因此研究者们提出了一系列的改进方法，如隐反馈矩阵分解（Implicit Matrix Factorization, IMF）算法。

IMF算法通过将隐式反馈数据转化为正态分布的隐式评分进行计算，从而提升了推荐系统的性能。

3.2 正则化项引入SVD算法容易受到过拟合的影响，为了解决这个问题，研究者们引入了正则化项。

正则化项可以限制模型的复杂度，防止过拟合的发生。

常用的正则化项有L1正则化和L2正则化，通过最小化正则项与损失函数的和来求解优化问题，达到控制模型复杂度的目的。

3.3 基于深度学习的改进近年来，深度学习在推荐系统领域取得了巨大的成功。

矩阵svd分解算法

矩阵svd分解算法SVD全称为Singular Value Decomposition(奇异值分解)，是一种非常重要的矩阵分解方法，被广泛应用于信号处理、图像处理、机器学习等领域。

本文将介绍SVD的定义、求解方法以及应用。

一、SVD定义矩阵SVD分解，指将一个复矩阵A分解成如下的形式：A = UΣV^T其中，U和V是正交矩阵，Σ是一个对角矩阵，对角线上的元素称为奇异值，通常用σ1 ≥ σ2 ≥ … ≥ σr > 0来表示。

二、SVD求解方法下面我们针对mxn的矩阵A，讲述一下SVD的求解步骤。

1. 首先求A^T·A的特征值和特征向量，设A^T·A的特征值为λ1, λ2, …, λm，对应的特征向量为v1, v2, …, vm 。

其中λ1≥λ2≥…≥λr>0。

2. 接着我们对v1, v2, …, vm进行标准化。

3. 将标准化后的v1, v2, …, vm组成正交矩阵V，即：V=[v1, v2, …, vm]。

特别的，当A为实矩阵时，可得到实特征向量和实奇异值，此时V 是一个正交矩阵。

4. 由于λ1, λ2, …, λr是A^T·A的非负特征值，我们可以得到A^T·A的奇异值：σ1=√λ1, σ2=√λ2, …, σr=√λr。

并将非零奇异值按照从大到小降序排列。

5. 求解奇异值对应的左奇异向量，设A^T·A的第i大特征值对应的特征向量为vi，i=1,2,...,r。

则A的左奇异向量为：ui=1/σi·Avi，i=1,2,...,r。

将u1, u2, …, ur组成正交矩阵U，即：U=[u1, u2, …, ur]。

特别的，当A为实矩阵时，可得到实左奇异向量。

6. 当m>n时，需要计算A·A^T的右奇异向量。

根据定义可得：vi=1/σi·A^Tui，i=1,2,...,r。

这些向量也组成了一个正交矩阵V，将它们作为A的右奇异向量。

随机矩阵奇异值分解算法在图像处理中的应用效果评估

随机矩阵奇异值分解算法在图像处理中的应用效果评估随机矩阵奇异值分解（Randomized SVD）算法是一种用于矩阵分解的快速、高效的方法。

在图像处理中，该算法被广泛应用于图像压缩、图像恢复、图像聚类等多个领域。

本文将对随机矩阵奇异值分解算法在图像处理中的应用效果进行评估。

一、随机矩阵奇异值分解算法介绍随机矩阵奇异值分解算法是一种非确定性算法，通过引入随机噪声来加速奇异值分解的过程。

它通过选择一个适当的随机矩阵对原始矩阵进行采样，并利用采样的结果来近似原始矩阵的奇异值分解。

相比传统的奇异值分解算法，随机矩阵奇异值分解算法在保持精度的同时，大大降低了计算复杂度，提高了运行效率。

二、随机矩阵奇异值分解算法在图像压缩中的应用效果评估在图像处理中，图像压缩是一项关键技术，能够通过减少图像数据的冗余信息来减小图像文件的大小。

使用随机矩阵奇异值分解算法进行图像压缩可以有效地降低计算复杂度，提高图像压缩的速度和效率。

同时，由于随机矩阵奇异值分解算法在保持精度的同时可以实现较高的压缩比，因此在图像质量方面也取得了较好的效果。

三、随机矩阵奇异值分解算法在图像恢复中的应用效果评估图像恢复是指在图像受损、缺失或降质的情况下，通过一系列的算法和处理手段，恢复出图像的原貌。

随机矩阵奇异值分解算法通过对图像进行分解，可以提取出图像的主要特征，从而在图像恢复过程中起到关键作用。

实验结果表明，随机矩阵奇异值分解算法在图像恢复方面具有较高的成功率和较好的恢复效果。

四、随机矩阵奇异值分解算法在图像聚类中的应用效果评估图像聚类是指将具有某种相似性的图像归为一类的过程。

随机矩阵奇异值分解算法可以通过对图像的奇异值分解来提取图像的特征，进而实现图像的聚类。

实验结果表明，随机矩阵奇异值分解算法在图像聚类方面具有较好的效果，并且在处理大规模图像数据时，具有较高的计算效率。

五、结论随机矩阵奇异值分解算法在图像处理中的应用效果得到了有效的验证。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
r
n−r
0 r ，…(1.1) 0 m−r
其中 Σ r diag (σ 1 ,..., σ r ), σ 1 ≥ ... ≥ σ r > 0 [2]。 = 当 A 为复矩阵 C m×n 时，只需将定理中 U , V 改为酉矩阵，其它不变，定理 1.2 仍 然成立[1]。 称分解式(1.1)为矩阵 A 的奇异值分解，通常简称为 SVD。σ i 是 A 的奇异值，向 量 ui 和 vi 分别是第 i 个左奇异向量和第 i 个右奇异向量。 从 A 的奇异值分解，我们可以得到 A 的一些非常有用的信息，下面的推论就列 举其中几条最基本的结论[1]： 推论 1.2 设 A ∈ Crm×n ，则 (1) A 的非零奇异值的个数就等于 r = rank ( A) ； (2) vr +1 ,..., vn 是 ( A) 的一组标准正交基； (3) u1 ,..., vr 是 ( A) 的一组标准正交基； (4) A = ∑ σ i ui viH 称为 A 的满秩奇异值分解；
SVD（奇异值分解）算法及其评估 本文第一部分对 SVD 进行了简单的介绍，给出了定义和奇异值分解定理；第二 部分简要地列举了 SVD 的应用；第三部分则构造和分析了各种求解 SVD 的算法， 特别对传统 QR 迭代算法和零位移 QR 迭代算法进行了详细完整的分析；第四部分 给出了复矩阵时的处理办法；第五部分是对各种算法的一个简要的总结。 一、 SVD 简介
= U (ΣV T x) − U (U T b)......(2.2) = U ( Σy − c ) T 其中 y = V x ， c = U T b 。 因为 U 是一正交矩阵，所以 Ax − b 2 = U (Σy − c) 2 = Σy − c 2 ，从而把原
最小二乘法问题化为求使 Σy − c 2 最小的 y 这一最小二乘法问题，因为 Σ 为 对角矩阵， 所以使得新的这一最小二乘法问题简单的多， 接着将对此仔细分 析[4]。 假设矩阵 A 的秩为 r ，则有： σ 1 y1 − c1 σ 1 y1 σ r yr − cr σ r yr Σy − c= −cr +1 Σy = 0 ， −cr + 2 0 −c 0 m
1/ 2
3
(4) 广义逆问题(pseudo-inverse) 记 A+= V ∑ + U T ，从(2.3)式我们可以看出，最小二乘法的解为 x = A+ b ， 和一般的线性方程组 Ax = b 的解为 x = A−1b 相类似，所以我们当我们已知矩 阵 A 的奇异值分解 A = U ΣV T 后可以定义 A 的广义逆为 A+= V ∑ + U T 。 (5) 条件数 如果已知矩阵 A 的秩为 r ，那么在式子(2.3)中，解 x 随着矩阵 A 的扰动 而改变的剧烈程度有多大呢？这可以用矩阵的条件数来衡量， 条件数的定义 如下： κ r ( A) = σ 1 / σ r ......(2.5) 以上只是针对 SVD 的应用，而简单地介绍了 LS 问题，广义逆；而在文献[5,6] 中则对这两个问题有详细的说明，在以后的报告中也将进行更进一步的分析，并且 综合其它方法来全面分析和处理这些问题。 除了这些传统的应用以外，在图像压缩和大型数据库的数据恢复中，SVD 也具 有广泛的应用[7]。 三、 各种 SVD 算法及其特点
m 2 可知 使得 达到它的最小长度 并且可 = yi c= / σ , ( i 1, 2,..., r ) Σ y − c i i ∑ ci ， i = r +1 见当 r = m 时，上面的这一长度为 0，也就是当矩阵 A 的列张成 m 空间时最 小二乘法问题可以无误差地求解。而当 r < n 时， yk +1 ,..., yn 可以任意取，而
定义 1.1 设 A ∈ R m×n ， AT A 的特征值的非负平方根称作 A 的奇异值； A 的奇异 值的全体记作 σ ( A ) [1]。 当 A 为复矩阵 C m×n 时，只需将 AT A 改为 AH A ，定义 1.1 仍然成立。 定理 1.1（奇异值分解定理） 设 A ∈ R m×n ，则必存在正交矩阵 m×m = U [u1 ,..., um ] ∈ R= 和 V [ v1 ,..., vn ] ∈ R n×n 使得 Σ U T AV = r 0
在现代科学计算中 SVD 具有广泛的应用，在已经比较成熟的软件包 LINPACK 中列举的应用有以下几点[3]: (1) 确定矩阵的秩(rank) 假设矩阵 A 的秩为 r ，那么 A 的奇异值满足如下式子 σ 1 ≥ ... ≥ σ r > σ r +1 = ... = σ n = 0 ； 反之，如果 σ r ≠ 0 ，且 σ r +1 = ... = σn = 0 ，那么矩阵 A 的秩为 r ，这样奇异值 分解就可以被用来确定矩阵的秩了。 事实的计算中我们几乎不可能计算得到奇异值正好等于 0，所以我们还 要确定什么时候计算得到的奇异值足够接近于 0， 以致可以忽略而近似为 0。 关于这个问题， 不同的算法有不同的判断标准， 将在给出各种算法的时候详 细说明。 (2) 确定投影算子 假设矩阵 A 的秩为 r ,那么我们可以将(1.3)式中的 U1 划分为以下的形式
4
3.1：传统 QR 迭代算法[1,2,3] 设 A ∈ R m×n (m ≥ n) ，可知奇异值分解可从实对称矩阵 C = AT A 的 Schur 分解导出 [1]，因此我们自然想到先利用对称 QR 方法来实现 C 的 Schur 分解，然后借助 C 的 Schur 分解来实现 A 的奇异值分解，然而这样做有两个缺点：一是计算 C = AT A 要 很大的计算量；二是计算 C = AT A 会引入较大的误差。因此 Golub 和 Kahan 在 1965 年提出了另一种十分稳定的方法，其基本思想就是隐含地应用对称 QR 算法于 AT A 上，而并不需要将 C = AT A 计算出来。 方法第一步是：将 A 二对角化，即求正交矩阵 U1 和 V1 ，使得
不影响 Σy − c 的长度。 我们将对 ∑ 转置并且对非零的对角元素求逆所得到的矩阵定义为 ∑ + ， 那么 y = Σ + c 的前 r 个元素将等于 ci / σ i , (i = 1, 2,..., r ) ，并且其余的元素为 0。 并且由 y = V T x ， c = U T b ，容易得到： x = V ∑ + U T b......(2.3) 由此得到的是 LS 问题的最小范数解。 而文献[3]中还给出了一般通解的形式如下： x= V ∑ + U T b + V2 w......(2.4) 其中 V2 如前定义，而 w 是任意的 n − r 维向量。
(1) U1 = U1(1) , U 2
(Leabharlann )并且 U1(1) 的列向量构成了矩阵 A 的列空间的正交向 其中 U 为 m × r 的矩阵， 量基。 容易得到 PA = U1(1)U1(1)T 为投影到矩阵 A 的列空间上的正交投影算子；而
(1) 1
(1) (1) PA⊥ = (U 2 , U 2 )(U 2 ,U 2 )T 则是到矩阵 A 列空间的正交补空间上的投影。
i =1 r
其中 ( A) ， ( A) 分别指得是 A 的零空间和值域。 为了方便，我们采用如下表示奇异值的记号： σ i ( A)＝A 的第 i 大奇异值；
σ max ( A)＝A 的最大奇异值； σ min ( A)＝A 的最小奇异值。
现在来考察矩阵奇异值的几何意义[1,2]，不妨设 m = n ，此时有 En =∈ y Cn : y = Ax, x ∈ C n , x 2 = 1
{
}
1
是一个超椭球面，它的 n 个半轴长正好是 A 的 n 个奇异值 σ 1 ≥ σ 2 ≥ ... ≥ σ n ≥ 0 ，这些 轴所在的直线正好是 A 的左奇异向量所在的直线，它们分别是对应的右奇异向量所 在直线的象。 一般地我们假设 m ≥ n ， （对于 m < n 的情况，我们可以先对 A 转置，然后进行 奇异值分解，最后对所求得的 SVD 分解式进行转置就可以得到原式 SVD 分解式） ， 此时我们对(1.1)进行化简将 U 表示为： U = (U1 , U 2 ), …(1.2) 则可以得到更加细腻的 SVD 分解式[2,3]： A = U1ΣV T …(1.3) 其中 U1 具有 n 列 m 维正交向量， V 和(1.1)式中的定义相同；Σ =diag (σ 1 , σ 2 ,..., σ n ) ， 并且 σ 1 ≥ σ 2 ≥ ... ≥ σ n ≥ 0 为矩阵 A 的奇异值。 二、 SVD 应用
2
促进人们研究 SVD 并且应用 SVD 比较早的应该是最小二乘法问题了， 在前一份关于 QR 分解的报告已经对 LS 问题进行了一些介绍，这里继续讨 论 SVD 在 LS 问题中的应用。 LS 问题即相当于，设 A ∈ R m×n (m > n), b ∈ R m ，求 x ∈ R n 使得 Ax −= b 2 min{ Av − b 2 : v ∈ R n }. ……(2.1) 假设已知矩阵 A 有式子(1.1)得到的 SVD 分解式为 U ΣV T ， U 和 V 分别为 m, n 阶正交方阵，而 ∑ 为和 A 具有相同维数的对角矩阵，那么我们可以得到[4]： Ax − b = U ΣV T x − b
同理如果将 V 划分为以下的形式 V = (V1 , V2 ) 其中 V1 为 n × r 的矩阵，则 V1 的列向量构成矩阵 A 的行空间的正交向量
⊥ 基。且 RA = V1V1T 为投影到矩阵 A 的行空间上的正交投影算子；而 RA = V2V2T 则是到矩阵 A 行空间的正交补空间上的投影。 (3) 最小二乘法问题(LS 问题)
首先来对 SVD 算法的发展来做简单的回顾[11,12]：关于 SVD 算法的研究最早 可以追溯到 1873 年 Beltrami 所做的工作， 这中间在理论方面进行了大量的工作， 这 个历史过程可以参考 Stewart 的文献[8]。 但是直到 1965 年 Golub 和 Kahan 才在 SVD 的数值计算领域取得突破性进展[9]，并且于 1969 给出了比较稳定的算法[10]（以下 简称传统 QR 迭代算法） ，这也是后来在 LINPACK 中所采用的方法[3]。它的中心思 想是用正交变换将原矩阵化为双对角线矩阵，然后再对双对角线矩阵迭代进行 QR 分解。 六十年代一份没有出版的技术报告中，Kahan 证明了双对角线矩阵的奇异值可 以精确地计算，具有和原矩阵元素的相对的精确度；进一步，1990 年 Demmel 和 Kahan 给出了一种零位移的 QR 算法(zero-shift QR algorithm)，这种算法计算双对角 矩阵的奇异值具有很高的相对精度[13]，并且由此得到的奇异向量也具有很高的精 度[14]。 Fernando 和 Parlett 在 1994 年将 qd 算法应用到奇异值的计算上，从而得到了一 种全新的比 zero-shift QR algorithm 更加精确和快速的计算奇异值的算法[15,16]。 而 Demmel 和 Veselic 在文献[17]中则说明了用 Jacobi 方法与其它方法相比计算 所得到的奇异值和奇异向量具有更高的精度，可惜 Jacobi 算法比 DK 算法速度要慢 的多；在文献[18]中对 Jacobi 方法进行了改进使得其在速度上几乎和 DK 算法相当。 和 Strassen 算法类似，SVD 问题也有快速的分而制之算法，在文献[19,20]对其 有详细的介绍， 由此得到的算法在总计算量上比现有的 LAPACK 软件包中所采用的 方法要少的多。 在文献[21,22]中给出的 bisection 算法也可以对双对角线矩阵计算得到具有相对 精度的全部奇异值。 以下就开始对各种算法原理进行详细说明，并分析它们的计算量，计算的精确 度，以及所占得内存。