We propose a refinement algorithm for singular value decomposition (SVD) of a real matrix. In the same manner as Newton’s method, the proposed algorithm converges quadratically if a modestly accurate initial guess is given. Since the proposed algorithm is based on matrix multiplication, it can efficiently be implemented. Numerical results demonstrate the excellent performance of the proposed algorithm in terms of the convergence rate and the measured computing time compared to a standard approach using multiple precision arithmetic. 我们提出了一种用于实矩阵奇异值分解 (SVD) 的细化算法。与牛顿方法相同,如果给出适度准确的初始估计值,则所提出的算法将呈二次方收敛。由于所提出的算法是基于矩阵乘法的,因此可以有效地实现。数值结果表明,与使用多精度算术的标准方法相比,所提算法在收敛速率和实测计算时间方面具有优异的性能。
Let be a real matrix. In this paper, we propose a refinement algorithm for the singular value decomposition (SVD) of with . If , considering the SVD of yields equivalent results. It is well known that the SVD has many applications in various fields, such as signal processing [1], [2], statistical analysis [3], [4], and so forth. Excellent overviews of the SVD can be found in [5], [6]. 设 为实 矩阵。在本文中,我们提出了一种 with 的 奇异值分解 (SVD) 的细化算法。如果 ,考虑 的 SVD 会产生等效的结果。众所周知,SVD 在各个领域都有许多应用,例如信号处理、统计分析等。SVD 的精彩概述可以在 、 中找到。
Throughout the paper, let and denote the identity matrix and the zero matrix of appropriate size, respectively. Moreover, denotes the spectral norm for matrices. If necessary, we distinguish between the approximate quantities and the computed results, e.g., for some quantity , we write and as an approximation of and a computed result for , respectively. 在整篇论文中,let 和 分别表示适当大小的 单位矩阵和零矩阵。此外, 表示矩阵的谱范数。如有必要,我们区分近似量和计算结果,例如,对于某个量 ,我们分别将 和 写 为 的近似 值和 计算结果 。
Let , , denote the singular values of . We consider the (full size) SVD of such that where both and are orthogonal and is diagonal with . For simplicity, we assume that In other words, we consider the case that all singular values are simple, and has full column rank. If there are multiple or nearly multiple singular values, we need some special care as in [7], [8]. 设 , , 表示 的 奇异值。我们考虑 的(全尺寸)SVD 是 这样的,其中 和 都是正交的,并且 是与 的对角线。为简单起见,我们假设换句话说,我们考虑所有奇异值都是简单的,并且 具有完整的列排名。如果存在多个或几乎多个奇异值,则需要特别小心,如 , 。
Recently, the authors proposed refinement algorithms for symmetric eigenvalue decomposition in [7], [8]. In the same spirit of the previous papers, the use of higher-precision arithmetic in our proposed refinement algorithm for the SVD is primarily restricted to matrix multiplication, which accounts for most of the computational cost. There are several approaches for higher-precision matrix multiplication. For example, XBLAS (extra precise BLAS) [9] and fast and accurate algorithms for dot products [10] and matrix products [11] based on error-free transformations are available for efficient implementation. 最近,作者在 [7]、[8] 中提出了对称特征值分解的改进算法。本着与前几篇论文相同的精神,在我们提出的 SVD 细化算法中,更高精度算术的使用主要限于矩阵乘法,这占了大部分计算成本。有几种方法可以进行更高精度的矩阵乘法。例如,XBLAS (超精确 BLAS) [9] 和基于无差错变换的点积 [10] 和矩阵积 [11] 的快速准确算法可用于高效实现。
The idea of our algorithm is to use the following relations: (1)(2)(3) Using these relations, we develop a refinement algorithm for the SVD in the same manner as Newton’s method. Thus, the proposed algorithm has quadratic convergence. 我们算法的思路是使用以下关系式:(1)2)(3)利用这些关系,我们以与牛顿方法相同的方式为 SVD 开发了一种细化算法。因此,所提出的算法具有二次收敛性。
There exist several refinement algorithms for SVD that are based on Newton’s method for nonlinear equations (cf. e.g., [12]). Since this sort of algorithm is designed to improve a triplet individually, where is a singular value and and are corresponding left and right singular vectors, applying such an approach to all triplets requires arithmetic operations. In [13], Davies and Smith proposed an iterative refinement algorithm for updating the singular value decomposition in operations. However, similarly to the Davies–Modi algorithm [14] for the symmetric eigenvalue decomposition as mentioned in the previous paper [7], the Davies–Smith algorithm has the limitation of achievable accuracy of the results. The reason is as follows. The Davies–Smith algorithm assumes that a given real matrix is preconditioned to a nearly diagonal matrix such as , where and are computed SVD factors, i.e., and are approximately orthogonal matrices. Since and involve numerical errors, the matrix multiplications in are generally not orthogonal transformations, and the singular values of are slightly perturbed from the original matrix . Then, the singular vectors are also perturbed. Therefore, even if the Davies–Smith algorithm provides accurate singular vectors of , they are not necessarily accurate ones of . On the other hand, our proposed algorithm uses the original matrix for obtaining accurate singular vectors of . SVD 有几种基于牛顿非线性方程法的细化算法(参见 e.g.)。由于这种算法旨在单独改进三元组 ,其中 是奇异值 和 和 是相应的左和右奇异向量,因此将这种方法应用于所有三元组需要 算术运算。在 中,Davies 和 Smith 提出了一种迭代细化算法,用于更新运算中的 奇异值分解。然而,与上一篇文章中提到的对称特征值分解的 Davies-Modi 算法类似,Davies-Smith 算法在结果的可实现精度方面存在局限性。原因如下。Davies-Smith 算法假设给定的实数矩阵 被预设为接近对角线的矩阵,例如 ,其中 和 是计算的 SVD 因子,即 和 是近似正交矩阵。由于 和 涉及数值误差,因此 中的 矩阵乘法通常不是正交变换,并且 的 奇异值与原始矩阵 略有不同。然后,奇异向量也会受到扰动。因此,即使 Davies-Smith 算法提供了 的 精确奇异向量 ,它们也不一定是 的 准确向量。另一方面,我们提出的算法使用原始矩阵 来获取 的 精确奇异向量。
The rest of the paper is organized as follows. In Section 2, we present a refinement algorithm for the SVD. In Section 3, we provide a convergence analysis of the proposed algorithm. In Section 4, we present some numerical results showing the behavior and performance of the proposed algorithm. 本文的其余部分组织如下。在第 2 节中,我们提出了 SVD 的优化算法。在第 3 节中,我们提供了所提出的算法的收敛分析。在第 4 节中,我们提供了一些数值结果,显示了所提出的算法的行为和性能。
2. Proposed algorithm 2. 建议的算法
Let and be given approximation of and , respectively. Let further and be correction matrices satisfying and , respectively. Let be defined as (4)We assume that . Then, both and are nonsingular, and Inserting into (1), we have and which yields (5)Similarly, inserting into (2), we have (6)Moreover, inserting and into (3), we have (7)Here, (8)(9)(10) where 设 和 分别得到 和 的近似值。设 further 和 分别是满足 和 的校正矩阵。设 定义为 我们假设 。那么,和 都是 奇异的,并且 插入 到 ,我们有 和 ,得到 同样,插入 到 ,我们有 此外,插入 和 进入 ,我们有 这里 ,其中(11)
Omitting the second-order terms , , and from (5), (6), and (7) in a similar way to Newton’s method, we obtain a system of matrix equations for , , and as (12)(13) All that remains is to solve (12) for , , and . 以与牛顿方法类似的方式省略 (5)、(6) 和 (7) 中的二阶项 、 和 ,我们得到一个矩阵 方程组 , 因为 (12)(13) 剩下的就是求解 、 和 的 (12) 。
In the following, we will show that we can easily solve the system of matrix equations (12). We partition as follows: Then it follows from (12) that (14a)(14b)(14c)
and (15a)(15b) 在下文中,我们将展示我们可以轻松求解矩阵方程组 (12)。我们按如下方式进行分区 :{n {m−n
F ̃= F ̃11 F ̃12 }n
F ̃21 F ̃22 }m−n,
{n
Σ ̃= Σ ̃n }n
O }m−n
{n {m−n
R= R11 R12 }n
R21 R22 }m−n,
{n
T= T1 }n
T2 }m−n
然后,从 (12)(14a)(14b)(14c) 可以得出
和 (15a)(15b)
First, we focus on the diagonal parts of and . It follows from the first and second equations in (13) that Moreover, the third equation in (13) yields Thus, if for , we have (16) 首先,我们关注 和 的 对角线部分。从 (13) 中的第一个和第二个方程中可以得出, 此外,(13) 中的第三个方程得出 因此,如果 for ,我们有 (16)
Remark 1 注 1
In theory, there is a possibility that . However, and are residuals in terms of orthogonality, and it is likely that and , and in practice. 理论上,有可能 .但是, and 是正交性的残差,并且很可能是 和 ,并且 在实践中。
Next, we focus on the off-diagonal parts of and . Combining (13), (16), they can be determined by solving 4 × 4 linear systems(17)(18)(19)(20) for , . By multiplying (19) by and (20) by , and Inserting (18) into this yields Combining this and (17), we have Similarly, using (17)–(20), we obtain Hence, (21)where and . Moreover, combining (15b), (16), can also be determined as (22)Furthermore, combining (14b), (22), is determined as and Finally, can arbitrarily be determined on the condition (14c). Thus we choose as
Summarizing the above discussion, we present a refinement algorithm for the SVD of a real matrix in Algorithm 1. 总结上述讨论,我们在算法 1 中提出了一种实矩阵 SVD 的细化算法。
Remark 2 注 2
In Algorithm 1, we assume that for all . If for some , we need some care in a similar way to the treatment for the symmetric eigenvalue problem in [7]. 在算法 1 中, 我们假设对于所有 .如果 对于某些 ,我们需要一些小心,就像 [7] 中对称特征值问题的处理一样。
Remark 3 注 3
Algorithm 1 would not work for the thin SVD unless , as at each iteration, where is the column space of a matrix . 算法 1 不适用于瘦 SVD,除非 ,就像在每次迭代中一样 ,其中 是矩阵 的列空间。
In the next section, we will discuss the convergence of the proposed algorithms in this section, which is proved to be quadratic. 在下一节中,我们将讨论本节中提出的算法的收敛性,它被证明是二次的。
3. Convergence analysis 3. 收敛分析
Here we prove quadratic convergence of Algorithm 1. Let be defined as in (4). Recall that are obtained from the following equations: (23)(24)(25)(26)(27)(28) 在这里,我们证明了算法 1 的二次收敛性。设 定义为 (4) 中。回想一下, 从以下方程式中获得: (23)(24)(25)(26)(27)(28)
The main difference from the discussion about the symmetric eigenvalue decompositions is that we consider the case of rectangular matrices, i.e., . In connection with this, for , the th columns of are not unique. Hence, we uniquely determine depending on a given as follows. Define such that the lower right submatrix of is symmetric positive definite; see [7, § 3.2] for the proof of its uniqueness. Then, is symmetric. Moreover, the next lemma can be proved in the same manner as [7, Lemma 3]. 与对称特征值分解的讨论的主要区别在于,我们考虑了矩形矩阵的情况,即 。与此相关,对于 ,的 第 th 列不是唯一的。因此,我们根据给定 的给定来唯一确定 ,如下所示。定义 的右下角 子矩阵 是对称的正定矩阵;参见 [7, § 3.2] 以证明其唯一性。然后, 是对称的。此外,下一个引理可以用与 [7, 引理 3] 相同的方式证明。
Lemma 1 引理 1
Let,, andwith. In addition, letbe a set of orthogonal matrices comprising the normalized left singular vectors of. Forobtained by Algorithm1 and any fixed, we definesuch that(29)In addition, we definesuch that(30)wherecomprises normalized left singular vectors such that the lower rightsubmatrix ofis symmetric positive definite. Then, we have(31) 设, 和和。此外,设为一组正交矩阵,其中包含 的 归一化左奇异向量。对于通过算法1 和任何固定 获得,我们定义如下(29)此外,我们定义(30) where 包含归一化的左奇异向量,使得 的 右 下子矩阵是对称的正定。 那么,我们有(31)
Noting the above lemma, we prove the quadratic convergence. First, we estimate and in some neighborhood of the solutions. 注意到上述引理,我们证明了二次收敛。首先,我们估计 并在 解的某个邻域中。
Lemma 2 引理 2
Supposeand, and definefor the sake of convenience. Letbe defined as in(4). If(32)is satisfied, then(33)Moreover, letting(34)we obtain(35)wherein(11)andin(34)satisfy(36) 假设和,并为方便起见定义。设定义为 in(4)。如果(32)满足,则(33)此外,让我们(34)得到(35)其中in(11)和in(34)满足(36)
First of all, we estimate the diagonal elements of . From (23), (26), we have (37)In addition, we see (38)in the same manner as (37). Therefore, we obtain (39) 首先,我们估计 的 对角线元素。从 (23)、(26) 中,我们有 (37) 此外,我们以与 (37) 相同的方式看到 (38) 。因此,我们获得 (39)
Next, we estimate . From (25), (28), and are determined as and . Thus, from easy calculations, On the right hand side, we have (40)In addition, from (25). It then follows that Hence, it is easy to see that (41)Using (34), we have (42)In addition, we see for in view of (43)from (42), (32), and (36). 接下来,我们估计 。从 (25)、(28) 和 确定为 和 。因此,从简单的计算中, 在右侧,我们有 (40) 此外, 来自 (25)。因此 ,很容易看出 (41) 使用 (34),我们有 (42) 此外,我们从 (43)(42)、(32) 和 (36) 中看到 for 。
In what follows, we estimate the off-diagonal elements of and . Combining (25) with (42), we have (44)where (45)
In addition, from (28), (46)holds. Using (37), (38), and (46), we estimate the off-diagonal elements of and . 在下文中,我们估计 和 的非对角线元素。将 (25) 与 (42) 组合,我们得到 (44) 其中 (45)
此外,从 (28) 中, (46) 成立。使用 (37)、(38) 和 (46),我们估计 和 的非对角线元素。
Recall for in the proposed algorithm. Hence, from (37), (47)Next, for , from the bottom part of (46), we have (48)Combining this with (37), for , we have (49)Moreover, for , we have (50)(51)(52) from (37), (38), (45), and (46). Recall for 在建议的算法中。因此,从 (37)开始, (47) 接下来,对于 ,从 (46) 的底部,我们有 (48) Combine this 与 (37),对于 ,我们有 (49) 此外,对于 ,我们有 (50)(51)(52) 来自 (37)、(38)、(45) 和 (46)。
Similarly to (21), all of and are calculated as follows. By multiplying (52) by , where the second equation is due to the symmetry of and . Thus, Inserting (51) into this yields Combining this and (50), we have Thus, noting as in (43), we have where the second inequality is due to (50), (51), and (52), and the third inequality is due to (42) and . Therefore, for , we obtain (53)where the second inequality is due to (42). Similarly, for , we have (54) 与 (21) 类似,所有 和 的计算方式如下。通过将 (52) 乘以 , 其中第二个方程是由于 和 的 对称性。因此, 将 (51) 代入其中,得到 将 this 和 (50) 组合起来,我们得到 因此, 注意在 (43) 中,我们有 第二个不等式是由于 (50)、(51) 和 (52) 造成的,第三个不等式是由于 (42) 和 .因此,对于 ,我们得到 (53) 第二个不等式是由于 (42) 引起的。同样,对于 ,我们有 (54)
From Lemma 2, the next lemma is readily accessible. 从引理 2 开始,下一个引理很容易获得。
Lemma 3 引理 3
Under the same assumption as inLemma 2, we obtain(55)(56) 在与引理 2相同的假设下,我们得到(55)(56)
Proof 证明
Noting (36), we have (57)Therefore, we see (58)Since also holds, we have (55). Combining (35) with , we obtain (56). □ 注意 (36),我们有 (57) 因此,我们看到 (58) Since 也成立,我们有 (55)。将 (35) 与 组合在一起,我们得到 (56)。 □
On the basis of the above lemmas, we obtain the main theorem that states the quadratic convergence. 根据上述引理,我们得到了陈述二次收敛的主定理。
Theorem 1 定理 1
Let,, andwithand. Definefor the sake of convenience. Definewith,satisfying. Similarly, definewith,satisfying,, where,are obtained in Algorithm 1. If(59)is satisfied, then(60)(61) 设, 和和和。为方便起见,定义 。定义满足.同样,使用 satisfying定义,其中在算法 1 中获得。如果(59)满足,则(60)(61)
Proof 证明
Define such that . Noting and , we have It then follows that (62)Noting (55) and from (33), we have (63)In Lemma 1, letting , we see (64)Thus we obtain Regarding , it is easy to see that in the same manner as (63). Therefore, we obtain (60). Moreover, using (56), (62), and (64), we obtain (61). □ 定义 ,使 .注意 和 ,我们得到 然后, (62) 注意到 (55) 并从 (33) 中,我们有 (63) 在引理 1 中,让 ,我们看到 (64) 因此我们得到 关于 ,很容易看出它与 (63) 相同。因此,我们得到 (60)。此外,使用 (56)、(62) 和 (64),我们得到 (61)。 □
Remark 4 注 4
From (42), singular values are convergent, where the rate can be estimated by that is quadratically convergent. 从 (42) 中,奇异值是收敛的,其中速率可以通过 来估计是二次收敛的。
4. Numerical results 4. 数值结果
We present numerical results to demonstrate the effectiveness of the proposed algorithm (Algorithm 1). The numerical experiments were conducted using MATLAB R2017b on a PC with 2.5 GHz Intel Core i7 and 16 GB of main memory. To realize multiple-precision arithmetic, we adopt Advanpix Multiprecision Computing Toolbox version 4.6.0 [15], which utilizes well-known, fast, and reliable multiple-precision arithmetic libraries including GMP and MPFR. In the multiple-precision toolbox, we can control the arithmetic precision in decimal digits using the command mp.Digits
(). 我们提供了数值结果来证明所提出的算法的有效性 (算法 1)。数值实验是在配备 2.5 GHz Intel Core i7 和 16 GB 主内存的 PC 上使用 MATLAB R2017b 进行的。为了实现多精度算术,我们采用了 Advanpix Multiprecision Computing Toolbox 版本 4.6.0 [15],它利用了众所周知、快速且可靠的多精度算术库,包括 GMP 和 MPFR。在多精度工具箱中,我们可以使用命令 mp 控制以十进制数字为单位的算术精度 。数字
( )。
4.1. Convergence property 4.1. 收敛属性
First, we confirm the convergence property of the proposed algorithm for various singular value distributions. We generate rectangular real matrices using Higham’s randsvd[16] by the following MATLAB command.
The singular value distribution and condition number of can be controlled by the input arguments and , as follows: 首先,我们确认了所提出的算法对各种奇异值分布的收敛特性。我们使用以下 MATLAB 命令使用 Higham 的 randsvd[16] 生成 矩形实矩阵。
random with uniformly distributed logarithm: , , where are pseudo-random values drawn from the standard uniform distribution on . 具有均匀分布对数的 random: , , 其中 是从 上的 标准均匀分布中提取的伪随机值。
Here, for . Note that for , there is a cluster of singular values. 在这里, 对于 .请注意,对于 ,存在一组奇异值。
We start with small examples such as and to observe the convergence behavior of the algorithm. Moreover, we set to generate moderately ill-conditioned problems in binary64. We compute , as initial approximate left and right singular vector matrices using the MATLAB function svd for the singular value decomposition in binary64 arithmetic. To see the behavior of the proposed algorithm precisely, we use multiple-precision arithmetic with sufficiently long precision to simulate the exact arithmetic in the algorithm. Then, we expect that Algorithm 1 (RefSVD) works effectively for , but does not for . For reference, we also use the built-in function svd in the multiple-precision toolbox to compute the singular values , . The results are shown in Fig. 1, which provides as the maximum relative error of the computed singular values , where and as the orthogonality of computed left and right singular vector matrices, as the diagonality of , and where and are computed in Algorithm 1. Here, denotes the off-diagonal part. The horizontal axis shows the number of iterations of Algorithm 1. 我们从 和 等小例子开始,观察算法的收敛行为。此外,我们设置 在 binary64 中生成中度病态问题。我们使用 MATLAB 函数 svd 计算 , 作为初始近似左和右奇异向量矩阵,用于 binary64 算术中的奇异值分解。为了精确地查看所提出的算法的行为,我们使用具有足够长精度的多精度算术来模拟算法中的精确算术。然后,我们期望算法 1 (RefSVD) 对 有效, 但 对 无效。作为参考,我们还使用多精度工具箱中的内置函数 svd 来计算奇异值 。 结果如图 1 所示,其中 提供 计算奇异值 的最大相对误差 , 其中 和 作为计算的左和右奇异向量矩阵的正交性, 作为 的 对角线, 其中 和 在算法 1 中计算。这里, 表示非对角线部分。横轴显示算法 1 的迭代 次数。
In the case of , all the quantities decrease quadratically in every iteration, i.e., we observe the quadratic convergence of Algorithm 1, as expected. On the other hand, in the case of , the algorithm fails to improve the accuracy of approximate singular vector matrices because the test matrices for have clustered singular values. In fact, the assumption (59) for the convergence of Algorithm 1 is not satisfied. 在 的情况下 ,所有量在每次迭代中都呈二次方递减,即,正如我们预期的那样,我们观察到算法 1 的二次收敛。另一方面,在 的情况下,该算法无法提高近似奇异向量矩阵的准确率,因为 的 测试矩阵具有聚类奇异值。事实上,算法 1 收敛的假设 (59) 不满足。
Fig. 1. Results of iterative refinement by Algorithm 1 () in sufficiently long precision arithmetic for matrices. 图 1.算法 1 ( ) 在足够长的矩阵精度算术 中迭代细化的结果。
4.2. Computational speed 4.2. 计算速度
To evaluate the computational speed of the proposed algorithm, we compare the computing time of Algorithm 1 to that of an approach using multiple-precision arithmetic, which is called “MP-approach”. In the multiple-precision toolbox, LAPACK’s routine xGESDD, which is based on a divide-and-conquer method, is implemented sophisticatedly with parallelism to solve singular value problems. 为了评估所提出的算法的计算速度,我们将算法 1 的计算时间与使用多精度算术的方法(称为 “MP-approach”)的计算时间进行了比较。在多精度工具箱中,LAPACK 的例程 xGESDD 基于分而治之法,通过并行性复杂地实现,以解决奇异值问题。
We generate a pseudo-random real matrix with using the MATLAB function randn such as A = randn(n). We use the MATLAB function svd in binary64, and iteratively refine the computed left and right singular vectors using Algorithm 1 twice. In Algorithm 1, for matrix multiplication at steps 1 and 8 we adopt a fast and accurate algorithm [11] using IEEE 754 binary64 (double precision) as working precision, and for other parts we use the multiple-precision toolbox with necessary arithmetic precision for , where denotes the iteration number of Algorithm 1. Since the binary64 arithmetic is used for obtaining initial guesses , , and , it is reasonable for the binary128 (quadruple precision) arithmetic to be used for in order to achieve the quadratic convergence of the proposed algorithm. In the multiple-precision toolbox, the binary128 arithmetic can be realized when for mp.Digits
(), and we set . For , we determine by estimating the error of and using where and can be obtained at the first iteration (). Since we expect that the error of and is of the order of , the computational precision required in the second iteration should correspond to . Thus, we set . In the MP-approach, we adjust the arithmetic precision to and corresponding to Algorithm 1. Note that the case for is specially tuned in the multiple-precision toolbox and faster than that for , and we do not set such that for timing fairness. 我们使用 MATLAB 函数 randn 生成一个伪随机实 矩阵,例如 A = randn(n)。我们在 binary64 中使用 MATLAB 函数 svd,并使用算法 1 迭代优化计算出的左和右奇异向量两次。在算法 1 中,对于步骤 1 和 8 的矩阵乘法,我们采用快速准确的算法 [11],使用 IEEE 754 binary64(双精度)作为工作精度,对于其他部分,我们使用具有必要算术精度 的多精度工具箱, 其中 表示算法 1 的迭代次数。由于 binary64 算术用于获取初始猜测值 、 和 ,因此使用 binary128(四倍精度)算术是合理的,以实现所提算法的二次收敛。在多精度工具箱中,当 for mp.数字
( ),我们设置 。对于 ,我们 通过估计 的误差 并使用 where 来确定 ,并且可以 在第一次迭代 ( ) 时获得 。由于我们预计 的误差为 , 因此第二次迭代所需的计算精度应对应于 。因此,我们设置 。在 MP 方法中,我们将算术精度 调整为 并 对应于算法 1。请注意,case for 在 multiple-precision 工具箱中进行了专门调整,并且比 for 更快,我们没有设置 that 以实现 timing fairness。
In Table 1, Table 2, we show as the relative residual norm, as the orthogonality of and , and the measured computing time. In addition, we show in Algorithm 1 for each iteration. As can be seen from in the tables, Algorithm 1 quadratically improves the accuracy of the computed singular vectors. The residual decreases and the orthogonality is improved when the iteration number increases. Moreover, Algorithm 1 is considerably faster than the MP-approach. 在表 1 和表 2 中,我们表示 为相对残差范数, 以及 和 的正交性,以及测得的计算时间。此外,我们在 算法 1 中显示了 每次迭代的 Algorithm 1。从 表中可以看出,算法 1 二次方提高了计算的奇异向量的精度。当迭代次数 增加时,残差 减少,正交性 提高。此外,算法 1 比 MP 方法快得多。
Acknowledgments 确认
The authors wish to thank the anonymous referees for their valuable comments. This study was partially supported by JST CREST Grant Number JPMJCR14D4 and JSPS
KAKENHI Grant Numbers 16H03917, 17K14143. 作者感谢匿名审稿人的宝贵意见。这项研究得到了 JST CREST Grant Number JPMJCR14D4 和 JSPS 的部分支持
KAKENHI 授权号 16H03917、17K14143。
Table 1. Results for a pseudo-random real 500 × 500 matrix. 表 1.伪随机实数 500 × 500 矩阵的结果。
Algorithm 1 算法 1
(svd in binary64) (Binary64 中的 SVD)
()
( )
()
( )
Accumulated elapsed time (s) 累计运行时间 (s)
0.05
1.24
5.54
MP-approach MP 方法
mp.Digits
() MP.数字
( )
Elapsed time (s) 经过时间 (s)
18.80
73.92
Table 2. Results for a pseudo-random real 1000 × 1000 matrix. 表 2.伪随机实数 1000 × 1000 矩阵的结果。
Singular value decomposition and principal component analysis
Berrar D.P., Dubitzky W., Granzow M. (Eds.), A Practical Approach to Microarray Data Analysis, Kluwer Academic Publishers, Norwell, MA, USA (2003), pp. 91-109
2020, Chemometrics and Intelligent Laboratory Systems
Continuum regression (CR) provides a promising regression framework encompassing ordinary least squares (OLS), partial least squares (PLS), and principal component regression (PCR). One important parameter of CR, namely shrinkage factor, determines how CR compromises between OLS and PCR. As the factor suggests, the rationale behind CR is that it aims at realizing a balance between achieving a good fit and establishing a stable model. However, traditional CR always uses a single shrinkage factor when extracting successive latent variables. As a consequence, the power of CR is surely limited. Aiming at this problem, we offer a vector of shrinkage factors for CR and one shrinkage factor for each latent variable. But now, identifying the optimal vector of shrinkage factors becomes a non-deterministic polynomial complete problem. As an effective optimization method, genetic algorithm (GA) is utilized to handle this tedious task. Together, the GACR framework is proposed in this study. The experiments on two real-world datasets illustrate the method’s applicability in practice.
2022, Proceedings of ScalAH 2022: 13th Workshop on Latest Advances in Scalable Algorithms for Large-Scale Heterogeneous Systems, Held in conjunction with SC 2022: The International Conference for High Performance Computing, Networking, Storage and Analysis