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).     

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.     

Analysis of Henrici's Transformation for Singular Problems

Henrici's transformation is the underlying scheme that generates, by cycling, Steffensen's method for the approximation of the solution of a nonlinear equation in several variables. The aim of this paper is to analyze the asymptotic behavior of the obtained sequence (s _n ^* ) by applying Henrici's transformation when the initial sequence (s _n ) behaves sublinearly. We extend the work done in the regular case by Sadok [17] to vector sequences in the singular case. Under suitable conditions, we show that the slowest convergence rate of (s _n ^* ) is to be expected in a certain subspace N of R ^p . More precisely, if we write s _n ^* =s _n ^* ,N+s _n ^* ,N, the orthogonal decomposition into N and N , then the convergence is linear for (s _n ^* ,N) but ( _n ^* ,N) converges to the same limit faster than the initial one. In certain cases, we can have N=R ^p and the convergence is linear everywhere.     

LSI潜在语义信息检索模型

本文介绍了基于向量空间的信息检索方法 ,检索词和文件之间的关系表示成一个矩阵 ,查寻信息表示为检索词权重的向量 ,通过求查寻和文件向量的夹角余弦确定出数据库中的相关文件 .使用矩阵的 QR分解和奇异值分解 ( SVD)来处理数据库本身的不确定性 ,本文的目的是说明线性代数中的基本概念可以很好解决信息检索 ( IR)问题     

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

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

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

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

Generalized Singular Value Decompositions for Tensors and Their Applications

In this paper, we consider the generalized singular value decompositions for two tensors via the T-product. We investigate and discuss in detail the structures of the quotient singular value decomposition (T-QSVD) and product singular value decomposition (T-PSVD) for two tensors. The algorithms are presented with numerical examples illustrating the results. For applications, we consider color image watermarking processing with T-QSVD and T-PSVD. There are two advantages to T-QSVD and T-PSVD approaches on color watermark processing: two color watermarks can be processed simultaneously and only one key needs to be saved.     

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

We correct two errors of the paper [1].     

A randomized tensor singular value decomposition based on the t‐product

The tensor SVD (t‐SVD) for third‐order tensors, previously proposed in the literature, has been applied successfully in many fields, such as computed tomography, facial recognition, and video completion. In this paper, we propose a method that extends a well‐known randomized matrix method to the t‐SVD. This method can produce a factorization with similar properties to the t‐SVD, but it is more computationally efficient on very large data sets. We present details of the algorithms and theoretical results and provide numerical results that show the promise of our approach for compressing and analyzing image‐based data sets. We also present an improved analysis of the randomized and simultaneous iteration for matrices, which may be of independent interest to the scientific community. We also use these new results to address the convergence properties of the new and randomized tensor method as well.     

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 the distribution singular values of Toeplitz matrices

We prove a second order formula concerning distribution of singular values of Toeplitz matrices in some cases when conditions of the H. Widom Theorem are not satisfied.

     

四元数正则矩阵束广义特征值反问题

对于任意给定的X∈Qn×m,∧=diag(λ1,…,λm)∈Rm×m,利用奇异值分解、谱分解及QR分解分别给出了满足AX=BX∧,及XHBX=Im,AX=BX∧,的正则矩阵束(A,B)的通解表达式.     

Sampling and multilevel coarsening algorithms for fast matrix approximations

This paper addresses matrix approximation problems for matrices that are large, sparse, and/or representations of large graphs. To tackle these problems, we consider algorithms that are based primarily on coarsening techniques, possibly combined with random sampling. A multilevel coarsening technique is proposed, which utilizes a hypergraph associated with the data matrix and a graph coarsening strategy based on column matching. We consider a number of standard applications of this technique as well as a few new ones. Among standard applications, we first consider the problem of computing partial singular value decomposition, for which a combination of sampling and coarsening yields significantly improved singular value decomposition results relative to sampling alone. We also consider the column subset selection problem, a popular low‐rank approximation method used in data‐related applications, and show how multilevel coarsening can be adapted for this problem. Similarly, we consider the problem of graph sparsification and show how coarsening techniques can be employed to solve it. We also establish theoretical results that characterize the approximation error obtained and the quality of the dimension reduction achieved by a coarsening step, when a proper column matching strategy is employed. Numerical experiments illustrate the performances of the methods in a few applications.     

Approximating dominant singular triplets of large sparse matrices via modified moments

A procedure for determining a few of the largest singular values and corresponding singular vectors of large sparse matrices is presented. Equivalent eigensystems are solved using a technique originally proposed by Golub and Kent based on the computation of modified moments. The asynchronicity in the computations of moments and eigenvalues makes this method attractive for parallel implementations on a network of workstations. Although no obvious relationship between modified moments and the corresponding eigenvectors is known to exist, a scheme to approximate both eigenvalues and eigenvectors (and subsequently singular values and singular vectors) has been produced. This scheme exploits both modified moments in conjunction with the Chebyshev semi-iterative method and deflation techniques to produce approximate eigenpairs of the equivalent sparse eigensystems. The performance of an ANSI-C implementation of this scheme on a network of UNIX workstations and a 256-processor Cray T3D is presented.This research was supported in part by the National Science Foundation under grant numbers NSF-ASC-92-03004 and NSF-ASC-94-11394.     

Approximating the inverse and the Moore‐Penrose inverse of complex matrices

A parametric family of fourth‐order schemes for computing the inverse and the Moore‐Penrose inverse of a complex matrix is designed. A particular value of the parameter allows us to obtain a fifth‐order method. Convergence analysis of the different methods is studied. Every iteration of the proposed schemes involves four matrix multiplications. A numerical comparison with other known methods, in terms of the average number of matrix multiplications and the mean of CPU time, is presented.     

The Algorithm of Sequential KKT Equations by Nonmonotone Search for Arbitrary Initial Point

In this paper, a new algorithm for arbitrary initial point is proposed. The feature of the algorithm is that only KKT equations are solved in each iteration which greatly decreases the amount of computation. Under some proper assumptions, the algorithm is globally and superlinearly convergent.     

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.     

Efficient Implementations of the Generalized Lasso Dual Path Algorithm

We consider efficient implementations of the generalized lasso dual path algorithm given by Tibshirani and Taylor in 2011 Tibshirani, R.J., Taylor, J. (2011), The Solution Path of the Generalized Lasso, Annals of Statistics, 39, 1335–1371.[Crossref], [Web of Science ®] , [Google Scholar]. We first describe a generic approach that covers any penalty matrix D and any (full column rank) matrix X of predictor variables. We then describe fast implementations for the special cases of trend filtering problems, fused lasso problems, and sparse fused lasso problems, both with X = I and a general matrix X. These specialized implementations offer a considerable improvement over the generic implementation, both in terms of numerical stability and efficiency of the solution path computation. These algorithms are all available for use in the genlasso R package, which can be found in the CRAN repository.     

On the Convergence of Solutions of Singularly Perturbed Boundary-Value Problems for the Laplace Operator

In this paper, we study the convergence of solutions and eigenvalues of singularly perturbed boundary-value problems for the Laplace operator in three-dimensional bounded domains with thin tubes cut out and variation of boundary conditions on narrow strips.     

On Kogbetliantz's SVD Algorithm in the Presence of Clusters

We consider matrices with off-diagonal blocks of small norm and derive tight bounds for the approximation of their singular values by those of their diagonal blocks. These results are used to show that triangular matrices with clusters of singular values must possess a principal submatrix of “nearly” diagonal form. From the latter we then derive results pertaining to the quadratic convergence of Kogbetliantz's algorithm for computing the SVD, in the presence of clusters.