Lanczos,Householder transformations,and implicit deflation for fast and reliable dominant singular subspace computation

Many applications, such as subspace‐based models in information retrieval and signal processing, require the computation of singular subspaces associated with the k dominant, or largest, singular values of an m×n data matrix A, where k?min(m,n). Frequently, A is sparse or structured, which usually means matrix–vector multiplications involving A and its transpose can be done with much less than ??(mn) flops, and A and its transpose can be stored with much less than ??(mn) storage locations. Many Lanczos‐based algorithms have been proposed through the years because the underlying Lanczos method only accesses A and its transpose through matrix–vector multiplications. We implement a new algorithm, called KSVD, in the Matlab environment for computing approximations to the singular subspaces associated with the k dominant singular values of a real or complex matrix A. KSVD is based upon the Lanczos tridiagonalization method, the WY representation for storing products of Householder transformations, implicit deflation, and the QR factorization. Our Matlab simulations suggest it is a fast and reliable strategy for handling troublesome singular‐value spectra. Copyright © 2001 John Wiley & Sons, Ltd.     

Low-rank Orthogonal Decompositions for Information Retrieval Applications

Current methods to index and retrieve documents from databases usually depend on a lexical match between query terms and keywords extracted from documents in a database. These methods can produce incomplete or irrelevant results due to the use of synonyms and polysemus words. The association of terms with documents (or implicit semantic structure) can be derived using large sparse {\it term-by-document} matrices. In fact, both terms and documents can be matched with user queries using representations in k-space (where 100 ≤ k ≤ 200) derived from k of the largest approximate singular vectors of these term-by-document matrices. This completely automated approach called latent semantic indexing or LSI, uses subspaces spanned by the approximate singular vectors to encode important associative relationships between terms and documents in k-space. Using LSI, two or more documents may be closeto each other in k-space (and hence meaning) yet share no common terms. The focus of this work is to demonstrate the computational advantages of exploiting low-rank orthogonal decompositions such as the ULV (or URV) as opposed to the truncated singular value decomposition (SVD) for the construction of initial and updated rank-k subspaces arising from LSI applications.     

Inverse subspace problems with applications

Given a square matrix A, the inverse subspace problem is concerned with determining a closest matrix to A with a prescribed invariant subspace. When A is Hermitian, the closest matrix may be required to be Hermitian. We measure distance in the Frobenius norm and discuss applications to Krylov subspace methods for the solution of large‐scale linear systems of equations and eigenvalue problems as well as to the construction of blurring matrices. Extensions that allow the matrix A to be rectangular and applications to Lanczos bidiagonalization, as well as to the recently proposed subspace‐restricted SVD method for the solution of linear discrete ill‐posed problems, also are considered.Copyright © 2013 John Wiley & Sons, Ltd.     

Restarted block Lanczos bidiagonalization methods

The problem of computing a few of the largest or smallest singular values and associated singular vectors of a large matrix arises in many applications. This paper describes restarted block Lanczos bidiagonalization methods based on augmentation of Ritz vectors or harmonic Ritz vectors by block Krylov subspaces. Research supported in part by NSF grant DMS-0107858, NSF grant DMS-0311786, and an OBR Research Challenge Grant.     

矩阵奇异值分解及其在高维数据处理中的应用

矩阵奇异值分解能够实现对高维数据的局部特征提取及维数约减,在智能信息处理和模式识别研究领域具有十分重要的应用价值.首先分析了高维数据处理所面临的困境,并对常用的降维算法进行简单的归纳总结;然后阐述了矩阵奇异值分解的基本原理及其在维数约减和数据压缩中的物理意义;接着通过分析两种建立在奇异值分解基础上的PCA与LSA降维算法的数学导出过程,进一步给出了两者的等价性证明;最后总结了矩阵奇异值分解的优缺点,并且预测了高维数据处理技术未来的发展趋势.     

On application of the Lanczos method to solution of some partial differential equations

Let A be a square symmetric n × n matrix, φ be a vector from ⁿ, and f be a function defined on the spectral interval of A. The problem of computation of the vector u = f(A)φ arises very often in mathematical physics.

We propose the following method to compute u. First, perform m steps of the Lanczos method with A and φ. Define the spectral Lanczos decomposition method (SLDM) solution as u_m = φ Qf(H)e₁, where Q is the n × m matrix of the m Lanczos vectors and H is the m × m tridiagonal symmetric matrix of the Lanczos method. We obtain estimates for u − u_m that are stable in the presence of computer round-off errors when using the simple Lanczos method.

We concentrate on computation of exp(− tA)φ, when A is nonnegative definite. Error estimates for this special case show superconvergence of the SLDM solution. Sample computational results are given for the two-dimensional equation of heat conduction. These results show that computational costs are reduced by a factor between 3 and 90 compared to the most efficient explicit time-stepping schemes. Finally, we consider application of SLDM to hyperbolic and elliptic equations.     

Dealing with linear dependence during the iterations of the restarted block Lanczos methods

The Lanczos method can be generalized to block form to compute multiple eigenvalues without the need of any deflation techniques. The block Lanczos method reduces a general sparse symmetric matrix to a block tridiagonal matrix via a Gram–Schmidt process. During the iterations of the block Lanczos method an off-diagonal block of the block tridiagonal matrix may become singular, implying that the new set of Lanczos vectors are linearly dependent on the previously generated vectors. Unlike the single vector Lanczos method, this occurrence of linearly dependent vectors may not imply an invariant subspace has been computed. This difficulty of a singular off-diagonal block is easily overcome in non-restarted block Lanczos methods, see [12,30]. The same schemes applied in non-restarted block Lanczos methods can also be applied in restarted block Lanczos methods. This allows the largest possible subspace to be built before restarting. However, in some cases a modification of the restart vectors is required or a singular block will continue to reoccur. In this paper we examine the different schemes mentioned in [12,30] for overcoming a singular block for the restarted block Lanczos methods, namely the restarted method reported in [12] and the Implicitly Restarted Block Lanczos (IRBL) method developed by Baglama et al. [3]. Numerical examples are presented to illustrate the different strategies discussed.     

Estimating a largest eigenvector by Lanczos and polynomial algorithms with a random start

We study Lanczos and polynomial algorithms with random start for estimating an eigenvector corresponding to the largest eigenvalue of an n × n large symmetric positive definite matrix. We analyze the two error criteria: the randomized error and the randomized residual error. For the randomized error, we prove that it is not possible to get distribution-free bounds, i.e., the bounds must depend on the distribution of eigenvalues of the matrix. We supply such bounds and show that they depend on the ratio of the two largest eigenvalues. For the randomized residual error, distribution-free bounds exist and are provided in the paper. We also provide asymptotic bounds, as well as bounds depending on the ratio of the two largest eigenvalues. The bounds for the Lanczos algorithm may be helpful in a practical implementation and termination of this algorithm. © 1998 John Wiley & Sons, Ltd.     

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

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

Structured multi-way arrays and their applications

Based on the structure of the rank-1 matrix and the different unfolding ways of the tensor, we present two types of structured tensors which contain the rank-1 tensors as special cases. We study some properties of the ranks and the best rank-r approximations of the structured tensors. By using the upper-semicontinuity of the matrix rank, we show that for the structured tensors, there always exist the best rank-r approximations. This can help one to better understand the sequential unfolding singular value decomposition (SVD) method for tensors proposed by J. Salmi et al. [IEEE Trans Signal Process, 2009, 57(12): 4719–4733] and offer a generalized way of low rank approximations of tensors. Moreover, we apply the structured tensors to estimate the upper and lower bounds of the best rank-1 approximations of the 3rd-order and 4th-order tensors, and to distinguish the well written and non-well written digits.     

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

We correct two errors of the paper [1].     

Rational Lanczos approximations to the matrix square root and related functions

We consider restricted rational Lanczos approximations to matrix functions representable by some integral forms. A convergence analysis that stresses the effectiveness of the proposed method is developed. Error estimates are derived. Numerical experiments are presented. Copyright © 2008 John Wiley & Sons, Ltd.     

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.     

Changing poles in the rational Lanczos method for the Hermitian eigenvalue problem

Applications such as the modal analysis of structures and acoustic cavities require a number of eigenvalues and eigenvectors of large‐scale Hermitian eigenvalue problems. The most popular method is probably the spectral transformation Lanczos method. An important disadvantage of this method is that a change of pole requires a complete restart. In this paper, we investigate the use of the rational Krylov method for this application. This method does not require a complete restart after a change of pole. It is shown that the change of pole can be considered as a change of Lanczos basis. The major conclusion of this paper is that the method is numerically stable when the poles are chosen in between clusters of the approximate eigenvalues. Copyright © 2001 John Wiley & Sons, Ltd.     

The Stabilization of Weights in the Lanczos and Conjugate Gradient Method

The Lanczos and the Conjugate Gradient method both compute implicitly a sequence of Gauss quadrature approximations to a certain Riemann-Stieltjes integral. In finite precision computations the corresponding weight function will be slightly perturbed. The purpose of this paper is to solve a conjecture posed by Anne Greenbaum and Zdeněk Strakoš on the stabilization of weights for the Gauss quadrature approximations, i.e. in particular we prove that for a tight well separated cluster of Ritz values (nodes) an upper bound for the change in the sum of the corresponding weights can be developed that depends mainly on the ratio of the cluster diameter and the gap in the spectrum. AMS subject classification (2000) 65F10, 65F15, 65F50     

Computing the field of values and pseudospectra using the Lanczos method with continuation

The field of values and pseudospectra are useful tools for understanding the behaviour of various matrix processes. To compute these subsets of the complex plane it is necessary to estimate one or two eigenvalues of a large number of parametrized Hermitian matrices; these computations are prohibitively expensive for large, possibly sparse, matrices, if done by use of the QR algorithm. We describe an approach based on the Lanczos method with selective reorthogonalization and Chebyshev acceleration that, when combined with continuation and a shift and invert technique, enables efficient and reliable computation of the field of values and pseudospectra for large matrices. The idea of using the Lanczos method with continuation to compute pseudospectra is not new, but in experiments reported here our algorithm is faster and more accurate than existing algorithms of this type.This work was supported by Engineering and Physical Sciences Research Council grants GR/H/52139 and GR/H/94528.     

Heyting algebras with Boolean operators for rough sets and information retrieval applications

This paper presents an algebraic formalism for reasoning on finite increasing sequences over Boolean algebras in general and on generalizations of rough set concepts in particular. We argue that these generalizations are suitable for modeling relevance of documents in an information retrieval system.     

MATRIX NORM VERSIONS OF THE KANTOROVICH INEQUALITY AND ITS APPLICATIONS

In this paper we discuss the generalizations of the Kantorovich inequality and obtain some generalized Kantorovich inequalities in the sense of matrix norm. We further illustrate how to use these inequalities to determine the lower bound of relative efficiency of the parameter estimate in linear model.     

Hyperbolic 0–1 programming and query optimization in information retrieval

Unconstrained hyperbolic 0–1 programming can be solved in linear time when the numerator and the denominator are linear and the latter is always positive. It is NP-hard, and finding an approximate solution with a value equal to a positive multiple of the optimal one is also NP-hard, if this last hypothesis does not hold. Determining the optimal logical form of a query in information retrieval, given the attributes to be used, can be expressed as a parametric hyperbolic 0–1 program and solved in O(n logn) time, wheren is the number of elementary logical conjunctions of the attributes. This allows to characterize the optimal queries for the Van Rijsbergen synthetic criterion.This research was done in part during a visit of the first author to the Pontifical Catholic University of Rio de Janeiro in July and August 1987, sponsored by CNPq. It was also supported in part by grants 0271 and 0066 of the AFOSR to Rutgers University. The second author was with Centro de Análise de Sistemas Navais, Rio de Janeiro.     

Application of the Lanczos algorithm for solving the linear systems that occur in continuation problems

We study the Lanczos method for solving symmetric linear systems with multiple right‐hand sides. First, we propose a numerical method of implementing the Lanczos method, which can provide all approximations to the solution vectors of the remaining linear systems. We also seek possible application of this algorithm for solving the linear systems that occur in continuation problems. Sample numerical results are reported. Copyright © 2002 John Wiley & Sons, Ltd.