用随机奇异值分解算法求解矩阵恢复问题

本文研究了大型低秩矩阵恢复问题.利用随机奇异值分解（RSVD）算法,对稀疏矩阵做奇异值分解.该算法与Lanczos方法相比,在误差精度一致的同时运算时间大大降低,且该算法对相对低秩矩阵也有效.     

A note on the recursive calculation of dominant singular subspaces

A recursive procedure for computing an approximation of the left and right dominant singular subspaces of a given matrix is proposed in [1]. The method is particularly suited for matrices with many more rows than columns. The procedure consists of a few steps. In one of these steps a Householder transformation is multiplied to an upper triangular matrix. The following step consists in recomputing an upper triangular matrix from the latter product. In [1] it is said that the latter step is accomplished in O(k³) operations, where k is the order of the triangular matrix. In this short note we show that this step can be accomplished in O(k²) operations. This research was partially supported by MIUR, grant number 2002014121 (first author) and by the Research Council K.U.Leuven, project OT/00/16 (SLAP: Structured Linear Algebra Package), by the Fund for Scientific Research–Flanders (Belgium), projects G.0078.01 (SMA: Structured Matrices and their Applications), G.0176.02 (ANCILA: Asymptotic aNalysis of the Convergence behavior of Iterative methods in numerical Linear Algebra), G.0184.02 (CORFU: Constructive study of Orthogonal Functions) and G.0455.0 (RHPH: Riemann–Hilbert problems, random matrices and Padé–Hermite approximation), and by the Belgian Programme on Interuniversity Poles of Attraction, initiated by the Belgian State, Prime Ministers Office for Science, Technology and Culture, project IUAP V-22 (Dynamical Systems and Control: Computation, Identification & Modelling) (second and third author). The scientific responsibility rests with the authors.AMS subject classification 15A15, 15A09, 15A23     

线性模型中基于SVD的一个新的有偏估计类

§1 .　IntroductionTheproblemofill_conditioninganditsstatisticalconsequencesonalinearregressionmodelarewell_knowninstatistics(Vinod&Ullah 1981;Belsley 1991) .Itis,forinstance ,knownthatoneofthemajorconsequencesofill_conditioningontheleastsquares(LS)regressionesti matoristhattheestimatorproduceslargesamplingvariance,whichinturnmightinappropri atelyleadtoexclusionofotherwisesignificantcoefficientfromthemodel,andthesignsofcoef ficientscanbecontrarytointuitionetc..Tocircumventthisproblem ,manybi…     

求矩阵奇异值分解的一种新方法

旨在给出求矩阵奇异值分解的一种新方法.改进和克服了以往方法的缺陷和不足.     

The generalized triangular decomposition

Given a complex matrix , we consider the decomposition , where is upper triangular and and have orthonormal columns. Special instances of this decomposition include the singular value decomposition (SVD) and the Schur decomposition where is an upper triangular matrix with the eigenvalues of on the diagonal. We show that any diagonal for can be achieved that satisfies Weyl's multiplicative majorization conditions:

where is the rank of , is the -th largest singular value of , and is the -th largest (in magnitude) diagonal element of . Given a vector which satisfies Weyl's conditions, we call the decomposition , where is upper triangular with prescribed diagonal , the generalized triangular decomposition (GTD). A direct (nonrecursive) algorithm is developed for computing the GTD. This algorithm starts with the SVD and applies a series of permutations and Givens rotations to obtain the GTD. The numerical stability of the GTD update step is established. The GTD can be used to optimize the power utilization of a communication channel, while taking into account quality of service requirements for subchannels. Another application of the GTD is to inverse eigenvalue problems where the goal is to construct matrices with prescribed eigenvalues and singular values.

     

《关于矩阵奇异值分解的注记》一文的注 （英）

We correct two errors of the paper [1].     

Using cross-product matrices to compute the SVD

This paper concerns accurate computation of the singular value decomposition (SVD) of an matrix . As is well known, cross-product matrix based SVD algorithms compute large singular values accurately but generally deliver poor small singular values. A new novel cross-product matrix based SVD method is proposed: (a) Use a backward stable algorithm to compute the eigenpairs of and take the square roots of the large eigenvalues of it as the large singular values of ; (b) form the Rayleigh quotient of with respect to the matrix consisting of the computed eigenvectors associated with the computed small eigenvalues of ; (c) compute the eigenvalues of the Rayleigh quotient and take the square roots of them as the small singular values of . A detailed quantitative error analysis is conducted on the method. It is proved that if small singular values are well separated from the large ones then the method can compute the small ones accurately up to the order of the unit roundoff . An algorithm is developed that is not only cheaper than the standard Golub–Reinsch and Chan SVD algorithms but also can update or downdate a new SVD by adding or deleting a row and compute certain refined Ritz vectors for large matrix eigenproblems at very low cost. Several variants of the algorithm are proposed that compute some or all parts of the SVD. Typical numerical examples confirm the high accuracy of our algorithm.Supported in part by the National Science Foundation of China (No. 10471074).     

Lanczos and the Riemannian SVD in information retrieval applications

Variations of the latent semantic indexing (LSI) method in information retrieval (IR) require the computation of singular subspaces associated with the k dominant singular values of a large m × n sparse matrix A, where k?min(m,n). The Riemannian SVD was recently generalized to low‐rank matrices arising in IR and shown to be an effective approach for formulating an enhanced semantic model that captures the latent term‐document structure of the data. However, in terms of storage and computation requirements, its implementation can be much improved for large‐scale applications. We discuss an efficient and reliable algorithm, called SPK‐RSVD‐LSI, as an alternative approach for deriving the enhanced semantic model. The algorithm combines the generalized Riemannian SVD and the Lanczos method with full reorthogonalization and explicit restart strategies. We demonstrate that our approach performs as well as the original low‐rank Riemannian SVD method by comparing their retrieval performance on a well‐known benchmark document collection. Copyright 2004 John Wiley & Sons, Ltd.     

On an improved-Levin oscillatory quadrature method

Performance of an improved-Levin quadrature method for oscillatory integrals is studied. In the study, the behavior of the target system of linear equations is analyzed and an error reduction factor is proposed to measure the behavior?s impact on the integral result. Numerical investigations show that the error reduction factor is extremely small for ill-conditioned case, and the ill-conditioning has little impact on the final integral result. Therefore, the concerned quadrature method is numerically very stable and it has addressed the Levin method?s problem of being susceptible to the ill-conditioning.     

A modified truncated singular value decomposition method for discrete ill‐posed problems

Truncated singular value decomposition is a popular method for solving linear discrete ill‐posed problems with a small to moderately sized matrix A. Regularization is achieved by replacing the matrix A by its best rank‐k approximant, which we denote by A_k. The rank may be determined in a variety of ways, for example, by the discrepancy principle or the L‐curve criterion. This paper describes a novel regularization approach, in which A is replaced by the closest matrix in a unitarily invariant matrix norm with the same spectral condition number as A_k. Computed examples illustrate that this regularization approach often yields approximate solutions of higher quality than the replacement of A by A_k.Copyright © 2014 John Wiley & Sons, Ltd.     

A truncated projected SVD method for linear discrete ill-posed problems

Truncated singular value decomposition is a popular solution method for linear discrete ill-posed problems. However, since the singular value decomposition of the matrix is independent of the right-hand side, there are linear discrete ill-posed problems for which this method fails to yield an accurate approximate solution. This paper describes a new approach to incorporating knowledge about properties of the desired solution into the solution process through an initial projection of the linear discrete ill-posed problem. The projected problem is solved by truncated singular value decomposition. Computed examples illustrate that suitably chosen projections can enhance the accuracy of the computed solution.     

THE POSITIVE SEMIDEFINITE SOLUTION OF THE MATRIX EQUATION （A^TXA, B^TXB） = （C,D）

In this paper, we consider the positive semidefinite solution of the matrixequation (A^TXA, B^TXB) = (C,D). A necessary and sufficient condition for the existence of such solution is derived using the generalized singular value decomposition.The general forms of positive semidefinite solution are given.     

Optimality of singular vector perturbation under maximum norm

Fan, Wang, and Zhong estimate the difference between the singular vectors of a matrix and those of a perturbed matrix in terms of the maximum norm. Their estimations are used effectively to establish the asymptotic properties of robust covariance estimators (see Journal of Machine Learning Research, 2018;18:1-42). In this paper, we give the corresponding lower bound estimates, which show Fan-Wang-Zhong's estimations optimal.     

Several Generalized Matrix Versions of Kantorovich Inequalities

Kantorovich inequalities are old results. In this paper we give several Kantorovich-type matrix inequalities.     

矩阵方程AXAT+BYBT=C的对称与反对称最小范数最小二乘解

对于任意给定的矩阵A∈Rk×m,B∈Rk×n和C∈Rk×k,利用奇异值分解和广义奇异值分解,我们给出了矩阵方程AXAT+BYBT=C的对称与反对称最小范数最小二乘解的表达式.     

A twisted factorization method for symmetric SVD of a complex symmetric tridiagonal matrix

This paper presents an O(n²) method based on the twisted factorization for computing the Takagi vectors of an n‐by‐n complex symmetric tridiagonal matrix with known singular values. Since the singular values can be obtained in O(n²) flops, the total cost of symmetric singular value decomposition or the Takagi factorization is O(n²) flops. An analysis shows the accuracy and orthogonality of Takagi vectors. Also, techniques for a practical implementation of our method are proposed. Our preliminary numerical experiments have verified our analysis and demonstrated that the twisted factorization method is much more efficient than the implicit QR method, divide‐and‐conquer method and Matlab singular value decomposition subroutine with comparable accuracy. Copyright © 2009 John Wiley & Sons, Ltd.     

矩阵奇异值分解问题重分析的直接摄动法

矩阵奇异值分解的摄动重分析技术具有广泛的应用前景,作者继在文[2]中提出了一种间接摄动分析方法之后,在本文中又进一步提出了直接摄动法,建立了一般实矩阵的非重奇异值及其左、古奇异向量的二阶摄动计算公式.这可满足大多数实际应用问题的一般需要.文中以算例说明了直接摄动法的有效性.     

四元数矩阵的奇异值分解及其应用

In this paper, a constructive proof of singular value decomposition of quaternion matrix is given by using the complex representation and companion vector of quaternion matrix and the computational method is described. As an application of the singular value decomposition, the CS decomposition is proved and the canonical angles on subspaces of Q^n is studied.     

线性流形上矩阵方程BTXB=F的双对称最小二乘解

1引言令R~(n×m)、OR~(n×n)、SR~(n×n)(SR_0~(n×n))分别表示所有n×m阶实矩阵、n阶实正交阵、n阶实对称矩阵(实对称半正定阵)的全体,A~ 表示A的Moore-Penrose广义逆,I_k表示k阶单位矩阵,S_k表示k阶反序单位矩阵。R(A)表示A的列空间,N(A)表示A的零空间,rank(A)表示矩阵A的秩。对A=(a_(ij)),B=(b_(ij))∈R~(n×m),A*B表示A与