Accelerating large partial EVD/SVD calculations by filtered block Davidson methods

Partial eigenvalue decomposition (PEVD) and partial singular value decomposition (PSVD) of large sparse matrices are of fundamental importance in a wide range of applications, including latent semantic indexing, spectral clustering, and kernel methods for machine learning. The more challenging problems are when a large number of eigenpairs or singular triplets need to be computed. We develop practical and efficient algorithms for these challenging problems. Our algorithms are based on a filter-accelerated block Davidson method. Two types of filters are utilized, one is Chebyshev polynomial filtering, the other is rational-function filtering by solving linear equations. The former utilizes the fastest growth of the Chebyshev polynomial among same degree polynomials; the latter employs the traditional idea of shift-invert, for which we address the important issue of automatic choice of shifts and propose a practical method for solving the shifted linear equations inside the block Davidson method. Our two filters can efficiently generate high-quality basis vectors to augment the projection subspace at each Davidson iteration step, which allows a restart scheme using an active projection subspace of small dimension. This makes our algorithms memory-economical, thus practical for large PEVD/PSVD calculations. We compare our algorithms with representative methods, including ARPACK, PROPACK, the randomized SVD method, and the limited memory SVD method. Extensive numerical tests on representative datasets demonstrate that, in general, our methods have similar or faster convergence speed in terms of CPU time, while requiring much lower memory comparing with other methods. The much lower memory requirement makes our methods more practical for large-scale PEVD/PSVD computations.     

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

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

Algebraic Method for Inequality Constrained Quaternion Least Squares Problem

In this paper, we introduce a kind of complex representation of quaternion matrices (or quaternion vectors) and quaternion matrix norms, study quaternionic least squares problem with quadratic inequality constraints (LSQI) by means of generalized singular value decomposition of quaternion matrices (GSVD), and derive a practical algorithm for finding solutions of the quaternionic LSQI problem in quaternionic quantum theory.     

一四元数矩阵方程组的最佳逼近解

利用四元数矩阵的广义Frobenius范数和弱圈积,建立一个关于四元数矩阵的实函数并简洁表征其极小值.再用四元数矩阵的奇异值分解和广义Frobenius范数的性质,讨论四元数矩阵方程组[AX,XB]=[C,D]的最小二乘解,得到了解的具体表达式.最后在该方程组的解集合中导出了与给定矩阵的最佳逼近解的表达式.     

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

本文提出了一般实矩阵奇异值分解问题重分析的摄动法.这是一种简捷、高效的快速重分析方法,对于提高各种需要反复进行矩阵奇异值分解的迭代分析问题的计算效率具有较重要的实用价值.文中导出了奇异值和左、右奇异向量的直到二阶摄动量的渐近估计算式.文末指出了将这种振动分析方法直接推广到一般复矩阵情况的途径.     

四元数矩阵方程AXAH=B的最小二乘解

引入了四元数矩阵范数的概念，通过使用四无数矩阵的奇异值分解，给出了四元数矩阵方程AXA^H＝B在最小二乘意义下的Hermitian解以及Skew-Hermitian解．     

具有奇异值分解性质的代数

设F为一个域,R为一个带有对合的F-代数,如果R上每一个矩阵都有奇异值分解(简称SVD),则称R为一个有SVD性质的F-代数.本文指出:R为一个有SVD性质的F-代数的充要条件是:R同构于R~+,或R~+上二次扩域,或R~+上四元数体((-1,-1)/R~+),其中R~+为R的对称元集合,并且R~+为一个Galois序闭域.     

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

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

Factorization of matrices of quaternions

We review known factorization results for quaternion matrices. Specifically, we derive the Jordan canonical form, polar decomposition, singular value decomposition, and QR factorization. We prove that there is a Schur factorization for commuting matrices, and from this derive the spectral theorem. We do not consider algorithms, but do point to some of the numerical literature.     

四元数广义奇异值分解及其应用

This paper derives a theorem of generalized singular value decomposition of quaternion matrices(QGSVD),studies the solution of general quaternion matrix equation AXB-CYD=E,and obtains quaternionic Roth's theorem.This paper also suggestssufficient and necessary conditions for the existence and uniqueness of solutions and explicit forms of the solutions of the equation.     

四元数矩阵的加权广义逆

利用四元数矩阵的加权奇异值分解 ,给出了四元数矩阵加权广义逆的显式表达 ,简化了应瓦金给出的相应结果 ,同时解答了有关的公开问题 .     

A Sparse Singular Value Decomposition Method for High-Dimensional Data

We present a new computational approach to approximating a large, noisy data table by a low-rank matrix with sparse singular vectors. The approximation is obtained from thresholded subspace iterations that produce the singular vectors simultaneously, rather than successively as in competing proposals. We introduce novel ways to estimate thresholding parameters, which obviate the need for computationally expensive cross-validation. We also introduce a way to sparsely initialize the algorithm for computational savings that allow our algorithm to outperform the vanilla singular value decomposition (SVD) on the full data table when the signal is sparse. A comparison with two existing sparse SVD methods suggests that our algorithm is computationally always faster and statistically always at least comparable to the better of the two competing algorithms. Supplementary materials for the article are available in an online appendix. An R package ssvd implementing the algorithms introduced in this article is available on CRAN.     

QUATERNION GENERALIZED SINGULAR VALUE DECOMPOSITION AND ITS APPLICATIONS

This paper derives a theorem of generalized singular value decomposition of quaternion matrices （QGSVD）,studies the solution of general quaternion matrix equation AXB -CYD= E,and obtains quaternionic Roth＇s theorem. This paper also suggests sufficient and necessary conditions for the existence and uniqueness of solutions and explicit forms of the solutions of the equation.     

The structured total least‐squares approach for non‐linearly structured matrices

In this paper, an extension of the structured total least‐squares (STLS) approach for non‐linearly structured matrices is presented in the so‐called ‘Riemannian singular value decomposition’ (RiSVD) framework. It is shown that this type of STLS problem can be solved by solving a set of Riemannian SVD equations. For small perturbations the problem can be reformulated into finding the smallest singular value and the corresponding right singular vector of this Riemannian SVD. A heuristic algorithm is proposed. Some examples of Vandermonde‐type matrices are used to demonstrate the improved accuracy of the obtained parameter estimator when compared to other methods such as least squares (LS) or total least squares (TLS). Copyright © 2002 John Wiley & Sons, Ltd.     

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

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.     

四元数体上一类矩阵方程的极小范数最小二乘解

借助于四元数体上自共轭矩阵的奇异值分解,给出了四元数矩阵方程AX＋XB＋CXD=F的极小范数最小二乘解.同时,在有解的条件下给出了Hermite最小二乘解及其通解的表达形式.     

An efficient rank detection procedure for modifying the ULV decomposition

The ULV decomposition (ULVD) is an important member of a class of rank-revealing two-sided orthogonal decompositions used to approximate the singular value decomposition (SVD). The problem of adding and deleting rows from the ULVD (called updating and downdating, respectively) is considered. The ULVD can be updated and downdated much faster than the SVD, hence its utility. When updating or downdating the ULVD, it is necessary to compute its numerical rank. In this paper, we propose an efficient algorithm which almost always maintains rank-revealing structure of the decomposition after an update or downdate without standard condition estimation. Moreover, we can monitor the accuracy of the information provided by the ULVD as compared to the SVD by tracking exact Frobenius norms of the two small blocks of the lower triangular factor in the decomposition.     

Robust tensor completion using transformed tensor singular value decomposition

In this article, we study robust tensor completion by using transformed tensor singular value decomposition (SVD), which employs unitary transform matrices instead of discrete Fourier transform matrix that is used in the traditional tensor SVD. The main motivation is that a lower tubal rank tensor can be obtained by using other unitary transform matrices than that by using discrete Fourier transform matrix. This would be more effective for robust tensor completion. Experimental results for hyperspectral, video and face datasets have shown that the recovery performance for the robust tensor completion problem by using transformed tensor SVD is better in peak signal‐to‐noise ratio than that by using Fourier transform and other robust tensor completion methods.     

关于矩阵的奇异值偏序

研究矩阵的奇异值偏序,给出了矩阵的奇异值偏序的等价刻画和性质,指出了相关文献关于矩阵*序刻画不真,利用强同时奇异值分解给出了矩阵*-序的刻画.