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.     

On the Lanczos and Golub–Kahan reduction methods applied to discrete ill‐posed problems

The symmetric Lanczos method is commonly applied to reduce large‐scale symmetric linear discrete ill‐posed problems to small ones with a symmetric tridiagonal matrix. We investigate how quickly the nonnegative subdiagonal entries of this matrix decay to zero. Their fast decay to zero suggests that there is little benefit in expressing the solution of the discrete ill‐posed problems in terms of the eigenvectors of the matrix compared with using a basis of Lanczos vectors, which are cheaper to compute. Similarly, we show that the solution subspace determined by the LSQR method when applied to the solution of linear discrete ill‐posed problems with a nonsymmetric matrix often can be used instead of the solution subspace determined by the singular value decomposition without significant, if any, reduction of the quality of the computed solution. Copyright © 2015 John Wiley & Sons, Ltd.     

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.     

A weighted singular value decomposition for the discrete inverse problems

In this paper, we introduce and analyze a new singular value decomposition (SVD) called weighted SVD (WSVD) using a new inner product instead of the Euclidean one. We use the WSVD to approximate the singular values and the singular functions of the Fredholm integral operators. In this case, the new inner product arises from the numerical integration used to discretize the operator. Then, the truncated WSVD (TWSVD) is used to regularize the Nyström discretization of the first‐kind Fredholm integral equations. Also, we consider the weighted LSQR (WLSQR) to approximate the solution obtained by the TWSVD method for large problems. Numerical experiments on a few problems are used to illustrate that the TWSVD can perform better than the TSVD.     

An efficient method to set up a Lanczos based preconditioner for discrete ill-posed problems

Rezghi and Hosseini [M. Rezghi, S.M. Hosseini, Lanczos based preconditioner for discrete ill-posed problems, Computing 88 (2010) 79–96] presented a Lanczos based preconditioner for discrete ill-posed problems. Their preconditioner is constructed by using few steps (e.g., k) of the Lanczos bidiagonalization and corresponding computed singular values and right Lanczos vectors. In this article, we propose an efficient method to set up such preconditioner. Some numerical examples are given to show the effectiveness of the method.     

广义双对称矩阵反问题

利用矩阵的奇异值分解讨论了一类广义双对称矩阵反问题,得到了此类矩阵反问题有解的充要条件及通解的表达式.     

Multisplitting for regularized least squares with Krylov subspace recycling

The method of multisplitting (MS), implemented as a restricted additive Schwarz type algorithm, is extended for the solution of regularized least squares problems. The presented non‐stationary version of the algorithm uses dynamic updating of the weights applied to the subdomains in reconstituting the global solution. Standard convergence results follow from extensive prior literature on linear MS schemes. Additional convergence results on nonstationary iterations yield convergence conditions for the presented nonstationary MS algorithm. The global iteration uses repeated solves of local problems with changing right hand sides but a fixed system matrix. These problems are solved inexactly using a conjugate gradient least squares algorithm which provides a seed Krylov subspace. Recycling of the seed system Krylov subspace to obtain the solutions of subsequent nearby systems of equations improves the overall efficiency of the MS algorithm, and is apparently novel in this context. The obtained projected solution is not always of sufficient accuracy to satisfy a reasonable inner convergence condition on the local solution. Improvements to accuracy may be achieved by reseeding the solution space either every few steps, or when the successive right hand sides are sufficiently close as measured by a provided tolerance. Restarting and augmenting the solution space are also discussed. Any time a new space is generated it is used for subsequent steps. Numerical simulations validate the use of the recycling algorithm. These numerical experiments use the standard reconstruction of the two dimensional Shepp–Logan phantom, as well as a two dimensional problem from seismic tomography. Copyright © 2011 John Wiley & Sons, Ltd.     

计算最小奇异组的一个精化调和Lanczos双对角化方法

在很多实际应用中需要计算大规模矩阵的若干个最小奇异组.调和投影方法是计算内部特征对的常用方法,其原理可用于求解大规模奇异值分解问题.本文证明了,当投影空间足够好时,该方法得到的近似奇异值收敛,但近似奇异向量可能收敛很慢甚至不收敛.根据第二作者近年来提出的精化投影方法的原理,本文提出一种精化的调和Lanczos双对角化方法,证明了它的收敛性.然后将该方法与Sorensen提出的隐式重新启动技术相结合,开发出隐式重新启动的调和Lanczos双对角化算法(IRHLB)和隐式重新启动的精化调和Lanczos双对角化算法(IRRHLB).位移的合理选取是算法成功的关键之一,本文对精化算法提出了一种新的位移策略,称之为"精化调和位移".理论分析表明,精化调和位移比IRHLB中所用的调和位移要好,且可以廉价可靠地计算出来.数值实验表明,IRRHLB比IRHLB要显著优越,而且比目前常用的隐式重新启动的Lanczos双对角化方法(IRLB)和精化算法IRRLB更有效.     

An Arnoldi-type algorithm for computing page rank

We consider the problem of computing PageRank. The matrix involved is large and cannot be factored, and hence techniques based on matrix-vector products must be applied. A variant of the restarted refined Arnoldi method is proposed, which does not involve Ritz value computations. Numerical examples illustrate the performance and convergence behavior of the algorithm. AMS subject classification (2000) 65F15, 65C40     

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.     

Hermitian非自反矩阵的两类反问题

记J为一广义反射矩阵,HAJn×n为关于J的n阶Hermitian非自反矩阵的集合.本文考虑如下两个问题:问题Ⅰ给定X,B∈n×m,求A∈HAJn×n,使得‖AX-B‖=min.问题Ⅱ给定X∈n×m,B∈n×n,求A∈HAJn×n,使得XHAX=B.首先利用奇异值分解讨论问题Ⅰ的解的通式,然后利用广义奇异值分解得到了问题Ⅱ有解的充分必要条件和解的通式,最后给出问题Ⅰ和Ⅱ的逼近解的具体表达式.     

Solutions of symmetry‐constrained least‐squares problems

In this paper, two new matrix‐form iterative methods are presented to solve the least‐squares problem: and matrix nearness problem: where matrices and are given; ??₁ and ??₂ are the set of constraint matrices, such as symmetric, skew symmetric, bisymmetric and centrosymmetric matrices sets and S_XY is the solution pair set of the minimum residual problem. These new matrix‐form iterative methods have also faster convergence rate and higher accuracy than the matrix‐form iterative methods proposed by Peng and Peng (Numer. Linear Algebra Appl. 2006; 13 : 473–485) for solving the linear matrix equation AXB+CYD=E. Paige's algorithms, which are based on the bidiagonalization procedure of Golub and Kahan, are used as the framework for deriving these new matrix‐form iterative methods. Some numerical examples illustrate the efficiency of the new matrix‐form iterative methods. Copyright © 2008 John Wiley & Sons, Ltd.     

A block inverse-free preconditioned Krylov subspace method for symmetric generalized eigenvalue problems

The inverse-free preconditioned Krylov subspace method of Golub and Ye [G.H. Golub, Q. Ye, An inverse free preconditioned Krylov subspace method for symmetric generalized eigenvalue problems, SIAM J. Sci. Comp. 24 (2002) 312-334] is an efficient algorithm for computing a few extreme eigenvalues of the symmetric generalized eigenvalue problem. In this paper, we first present an analysis of the preconditioning strategy based on incomplete factorizations. We then extend the method by developing a block generalization for computing multiple or severely clustered eigenvalues and develop a robust black-box implementation. Numerical examples are given to illustrate the analysis and the efficiency of the block algorithm.     

Stability of solutions of a class of nonlinear fractional diffusion equations with respect to a pseudo‐differential operator

In this paper, we study the forward and the backward in time problems for a class of nonlinear diffusion equations with respect to the pseudo‐differential operator. Herein, we investigate the stability of the solution of the forward problem in relationship with parameters of the pseudo‐differential operator and initial data. Besides, as known, the backward in time problem is instability. Hence, we give a method to regularize the solution of the backward problem in the case of the parameters are perturbed.     

The quasi‐reversibility method for a final value problem of the time‐fractional diffusion equation with inhomogeneous source

This paper is devoted to discuss a multidimensional backward heat conduction problem for time‐fractional diffusion equation with inhomogeneous source. This problem is ill‐posed. We use quasi‐reversibility regularization method to solve this inverse problem. Moreover, the convergence estimates between regularization solution and the exact solution are obtained under the a priori and the a posteriori choice rules. Finally, the numerical examples for one‐dimensional and two‐dimensional cases are presented to show that our method is feasible and effective.     

Randomized algorithms for total least squares problems

Motivated by the recently popular probabilistic methods for low‐rank approximations and randomized algorithms for the least squares problems, we develop randomized algorithms for the total least squares problem with a single right‐hand side. We present the Nyström method for the medium‐sized problems. For the large‐scale and ill‐conditioned cases, we introduce the randomized truncated total least squares with the known or estimated rank as the regularization parameter. We analyze the accuracy of the algorithm randomized truncated total least squares and perform numerical experiments to demonstrate the efficiency of our randomized algorithms. The randomized algorithms can greatly reduce the computational time and still maintain good accuracy with very high probability.     

A simultaneous decomposition of a matrix triplet with applications

Researches on ranks of matrix expressions have posed a number of challenging questions, one of which is concerned with simultaneous decompositions of several given matrices. In this paper, we construct a simultaneous decomposition to a matrix triplet (A, B, C), where A=±A*. Through the simultaneous matrix decomposition, we derive a canonical form for the matrix expressions A?BXB*?CYC* and then solve two conjectures on the maximal and minimal possible ranks of A?BXB*?CYC* with respect to X=±X* and Y=±Y*. As an application, we derive a sufficient and necessary condition for the matrix equation BXB* + CYC*=A to have a pair of Hermitian solutions, and then give the general Hermitian solutions to the matrix equation. Copyright © 2010 John Wiley & Sons, Ltd.     

Hermitian‐type generalized singular value decomposition with applications

For a pair of given Hermitian matrix A and rectangular matrix B with the same row number, we reformulate a well‐known simultaneous Hermitian‐type generalized singular value decomposition (HGSVD) with more precise structure and parameters and use it to derive some algebraic properties of the linear Hermitian matrix function A?BXB* and Hermitian solution of the matrix equation BXB* = A, and the canonical form of a partitioned Hermitian matrix and some optimization problems on its inertia and rank. Copyright © 2012 John Wiley & Sons, Ltd.     

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

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