Main Content

本页的翻译已过时。点击此处可查看最新英文版本。

svdsketch

计算低秩矩阵草图的 SVD

说明

示例

[U,S,V] = svdsketch(A) 返回输入矩阵 A 的低秩矩阵草图的奇异值分解 (SVD)。矩阵草图是一种低秩逼近,仅反映 A 的最重要特征(最大容差)。与使用 svds 相比,它能够更快地计算大型矩阵的部分 SVD。

示例

[U,S,V] = svdsketch(A,tol) 指定矩阵草图的容差。svdsketch 使用 tol 以自适应方式确定矩阵草图逼近的秩。随着容差变大,矩阵草图中使用的 A 的特征越来越少。

示例

[U,S,V] = svdsketch(A,tol,Name,Value) 指定具有一个或多个 Name,Value 对组参数的其他选项。例如,您可以指定 'MaxIterations' 和标量来调整用于形成矩阵草图的迭代次数。

示例

[U,S,V,apxErr] = svdsketch(___) 还返回向量 apxErr,该向量包含每次迭代的相对逼近误差 norm(U*S*V'-A,'fro')/norm(A,'fro')。向量 apxErr(end) 中的最后一项是 svdsketch 返回的输出的相对逼近误差。

示例

全部折叠

使用 svdsketch 计算低秩矩阵逼近的 SVD 因子。

使用 gallery 创建一个具有几何分布奇异值的 200×200 随机矩阵。

A = gallery('randsvd',200);

使用 svdsketch 计算 A 的低秩逼近的 SVD。

[U,S,V] = svdsketch(A);

检查输出的大小。

size(S)
ans = 1×2

   120   120

结果表明 A 的低秩矩阵逼近的秩为 120。

svdsketch 指定容差,以计算低秩矩阵逼近的 SVD 因子。svdsketch 根据指定的容差以自适应方式确定矩阵草图的适当秩。

使用 gallery 创建一个具有几何分布奇异值的 200×200 随机矩阵。

A = gallery('randsvd',200);

使用 svdsketch 计算 A 的低秩逼近的 SVD。指定容差 1e-2,并查找输出 S 的大小以确定 svdsketch 对矩阵草图使用的秩。

tol = 1e-2;
[U,S,V] = svdsketch(A,tol);
size(S)
ans = 1×2

    60    60

结果表明 A 的低秩矩阵逼近的秩为 60。

通过比较 AU*S*V',检查矩阵草图与 A 的逼近程度。

norm(U*S*V' - A,'fro')/norm(A,'fro')
ans = 0.0048

结果表明,矩阵草图与 A 的逼近程度在指定的容差 1e-2 范围内。

对于具有缓慢衰减的奇异值的矩阵,将 svdsketchMaxSubspaceDimension 选项结合使用。您可以使用此选项强制 svdsketch 在矩阵草图中使用 A 的特征子集。

用服从标准正态分布的值创建一个 5000×5000 矩阵。查看矩阵奇异值的分布。

A = randn(5000);
semilogy(svd(A),'-o')

由于 A 中的奇异值缓慢衰减,因此 A 具有许多重要特征,并且使自身不适用于低秩逼近。要形成合理逼近 A 的矩阵草图,需要保留大部分或几乎所有特征。

对矩阵使用 svdsketch,容差为 1e-5。指定四个输出以返回每个迭代中的 SVD 因子以及相对逼近误差。

tol = 1e-5;
[U1,S1,V1,apxError1] = svdsketch(A,tol);
size(S1)
ans = 1×2

        5000        5000

S 的大小表明,为了满足容差,svdsketch 需要保留 A 的所有特征。对于大型稀疏输入矩阵,这可能会导致内存问题,因为由 svdsketch 形成的 A 的低秩逼近与 A 的大小大致相同,从而可能无法作为稠密矩阵放入内存中。

检查输出的逼近误差。由于 svdsketch 保留 A 中的所有内容,计算出的解是准确的,但计算 svd(X) 的成本非常高。

apxError1(end)
ans = 1.9075e-08

现在,进行相同的计算但将 MaxSubspaceDimension 指定为 650,以限制用于缩略 A 的子空间的大小。这有助于强制 svdsketch 仅使用 A 中的特征子集来形成矩阵草图,从而减小输出的大小。

[U2,S2,V2,apxError2] = svdsketch(A,tol,'MaxSubspaceDimension',650);
size(S2)
ans = 1×2

   650   650

现在,输出比原来小了。

检查新输出的逼近误差。强制输出变小的折衷是,矩阵草图中需要省略 A 的许多重要特征,得到的 A 的秩 650 逼近不满足指定的容差。

apxError2(end)
ans = 0.8214

输入参数

全部折叠

输入矩阵,指定为稀疏矩阵或满矩阵。A 通常为大型稀疏矩阵,但不总是这样。svdsketch 最适合对特征数量相对较少的秩亏矩阵进行操作。

数据类型: single | double
复数支持:

矩阵草图容差,指定为范围 sqrt(eps(class(A))) <= tol < 1 内的实数标量。

svdsketch 使用 tol 的值以自适应方式确定 A 的哪些特征用于 A 的低秩逼近(矩阵草图)。随着 tol 值的增大,svdsketch 使用 A 的更少特征来形成矩阵草图。

示例: [U,S,V] = svdsketch(A,1e-4)

数据类型: single | double

名称-值对组参数

指定可选的、以逗号分隔的 Name,Value 对组参数。Name 为参数名称,Value 为对应的值。Name 必须放在引号中。您可采用任意顺序指定多个名称-值对组参数,如 Name1,Value1,...,NameN,ValueN 所示。

示例: [U,S,V] = svdsketch(A,1e-10,'MaxIterations',100)svdsketch 算法中使用 100 次迭代。

最大子空间维度,指定为正整数标量。子空间维度控制 svdsketch 算法的内存消耗。如果算法在使用指定容差时耗尽内存,则可以为 MaxSubspaceDimension 指定较小的值,以便算法不会耗尽内存。例如,当 A 具有缓慢衰减的奇异值时,调整此参数会很有用。

当您指定 MaxSubspaceDimension 选项时,您可以为 svdsketch 使用的矩阵草图的秩设置最大值。因此,如果 svdsketch 在秩小于 MaxSubspaceDimension 时无法满足指定容差,它将使用允许的最大秩,生成的输出可能不满足指定容差。

示例: [U,S,V] = svdsketch(A,1e-7,'MaxSubspaceDimension',150)

数据类型: single | double

初始算法的块大小,指定为正整数标量。块大小是矩阵草图的秩在每次迭代中增加的数量。较大的块大小会通过在每次迭代中做更多工作来减少所需的迭代次数,但也可能向计算中添加的详细信息超过实现收敛所必需的信息。

随着算法的进行,如果相对逼近误差 apxErr 衰减不够快,则 svdsketch 可能会根据初始值调整块大小以加快收敛速度。

如果指定 BlockSize,该值应小于 MaxSubspaceDimension

示例: [U,S,V] = svdsketch(A,1e-7,'BlockSize',10)

数据类型: single | double

算法迭代的最大次数,指定为正整数标量。更多迭代可以产生更高质量的矩阵草图,代价是更多执行时间和更高的内存消耗。

示例: [U,S,V] = svdsketch(A,1e-7,'MaxIterations',25)

数据类型: single | double

幂迭代的次数,指定为非负整数标量。幂迭代可改进 UV 输出的正交性。您通常应选择 012 作为幂迭代次数,因为较大的值会对舍入误差产生不利影响。

示例: [U,S,V] = svdsketch(A,1e-7,'NumPowerIterations',2)

数据类型: single | double

输出参数

全部折叠

矩阵草图的左奇异向量,以矩阵形式返回。U 的列是正交列,并且它们形成 A 的矩阵草图范围的一组基向量。

U 的大小取决于 tol 的值。随着 tol 变大,svdsketch 使用更少的输入矩阵特征来形成矩阵草图,因此 UV 也具有更少的列。

不同的计算机和 MATLAB® 版本可以生成不同的奇异向量,它们在数值上依然精确。UV 中的相应列可以翻转其符号,因为这不会影响表达式 A = U*S*V' 的值。

矩阵草图的奇异值,以对角方阵形式返回。S 的对角线元素是严格递减的矩阵草图的正奇异值。

S 的大小取决于 tol 的值。随着容差的增大,svdsketch 使用更少的输入矩阵特征来形成矩阵草图,因此 S 相应地具有更少的行和列。

矩阵草图的右奇异向量,以矩阵形式返回。V 的列是正交列,并且它们形成 A 的矩阵草图的零空间的一组基向量。

V 的大小取决于 tol 的值。随着 tol 变大,svdsketch 使用更少的输入矩阵特征来形成矩阵草图,因此 UV 也具有更少的列。

不同的计算机和 MATLAB 版本可以生成不同的奇异向量,它们在数值上依然精确。UV 中的相应列可以翻转其符号,因为这不会影响表达式 A = U*S*V' 的值。

每次迭代的相对逼近误差,以向量形式返回。apxErr 的长度等于 svdsketch 算法中使用的迭代次数。使用 MaxIterations 调整迭代次数。

apxErr 的条目是每次迭代中的相对逼近误差 norm(U*S*V'-A,'fro')/norm(A,'fro')。向量 apxErr(end) 中的最后一项是 svdsketch 返回的输出的相对逼近误差。

提示

  • 如果您事先不知道用 svds 指定什么秩但知道 SVD 的逼近应满足什么容差,请使用 svdsketch

  • svds 计算 SVD 的最佳可能秩 k 逼近(使用默认 "largest" 方法)。svdsketch 无法保证其秩 k 逼近是最好的,这只说明它相对于 svds 的速度优势。

算法

svdsketch 应用一个容差来形成输入矩阵 A 的低秩矩阵逼近 AQB。此低秩逼近称为矩阵草图。矩阵草图仅保留 A 中的重要特征,而滤除不必要的信息。矩阵草图的相对逼近误差 apxErr 旨在满足指定的容差 tol

esketch=QBAFAFtol

svdsketch 形成矩阵草图所遵循的过程如下:

  • svdsketch 以迭代方式形成矩阵草图,每次迭代向 Q 添加新列,向 B 添加新行。通过使用随机采样矩阵从 A 中提取特征来创建新列和行。您可以使用 BlockSize 名称-值对组控制每次迭代中添加的列数和行数。

  • 在每次迭代期间,svdsketch 使用幂迭代来改进 Q 中新列的正交性。您可以使用 NumPowerIterations 名称-值对组来调整幂迭代的次数。

  • 当 Q 中的列数和 B 中的行数达到 MaxSubspaceDimension 的指定值、迭代次数达到 MaxIterations 或相对逼近误差收敛 (apxErr <= tol) 时,形成矩阵草图的迭代停止。

  • 如果 apxErr 中的衰减不足,为了提高收敛速度,svdsketch 可能会在各迭代之间增大 BlockSize 的指定初始值。

在形成矩阵草图 AQB 后,svdsketch 通过 [U1,S,V] = svd(B,'econ') 计算矩阵草图的奇异值分解 (SVD),使得

AQB=(QU1)SVH=USVH.

如果 svdsketch 能够根据指定的容差滤除 A 的某些特征,则与对 A 执行完整 SVD 相比,得到的 SVD 因子包含更少的奇异值和奇异向量。

参考

[1] Yu, Wenjian, Yu Gu, and Yaohang Li. “Efficient Randomized Algorithms for the Fixed-Precision Low-Rank Matrix Approximation.” SIAM Journal on Matrix Analysis and Applications 39, no. 3 (January 2018): 1339–59. https://doi.org/10.1137/17M1141977.

在 R2020b 中推出