面向矩阵秩函数准确估计的自表示子空间聚类方法

传统子空间聚类方法通常使用矩阵核范数代替矩阵秩函数进行低秩矩阵恢复,然而在目标优化过程中主要关注低秩矩阵大奇异值的影响,容易导致矩阵秩估计不准确的问题。为此,在分析矩阵奇异值长尾分布特点基础上,提出使用基于截断Schatten-p范数的低秩子空间聚类模型。该模型充分考虑小奇异值对低秩矩阵恢复过程的贡献,利用小奇异值信息拟合矩阵奇异值的长尾分布,通过对矩阵秩函数进行准确估计以提升子空间聚类性能。实验结果表明,与现有加权核范数子空间聚类WNNM-LRR和近邻约束子空间聚类BDR算法相比,在Extended Yale B数据集上的聚类准确性分别提升了11%和8%,所提方法能够更好地拟合数据奇异值分布以及生成准确的相似度矩阵。     

Parallel algorithms for certain matrix computations

The complexity of performing matrix computations, such as solving a linear system, inverting a nonsingular matrix or computing its rank, has received a lot of attention by both the theory and the scientific computing communities. In this paper we address some “nonclassical” matrix problems that find extensive applications, notably in control theory. More precisely, we study the matrix equations AX + XA^T = C and AX − XB = C, the “inverse” of the eigenvalue problem (called pole assignment), and the problem of testing whether the matrix [B AB … Aⁿ⁻¹ B] has full row rank. For these problems we show two kinds of PRAM algorithms: on one side very fast, i.e. polylog time, algorithms and on the other side almost linear time and processor efficient algorithms. In the latter case, the algorithms rely on basic matrix computations that can be performed efficiently also on realistic machine models.     

A new block algorithm for full-rank solution of the Sylvester-observer equation

A new block algorithm for computing a full rank solution of the Sylvester-observer equation arising in state estimation is proposed. The major computational kernels of this algorithm are: 1) solutions of standard Sylvester equations, in each case of which one of the matrices is of much smaller order than that of the system matrix and (furthermore, this small matrix can be chosen arbitrarily), and 2) orthogonal reduction of small order matrices. There are numerically stable algorithms for performing these tasks including the Krylov-subspace methods for solving large and sparse Sylvester equations. The proposed algorithm is also rich in Level 3 Basic Linear Algebra Subroutine (BLAS-3) computations and is thus suitable for high performance computing. Furthermore, the results on numerical experiments on some benchmark examples show that the algorithm has better accuracy than that of some of the existing block algorithms for this problem.     

可验证的大规模矩阵满秩分解的安全外包

针对矩阵满秩分解的外包算法没有对原始矩阵中零元素的个数进行保护且没有对云返回结果的正确性进行验证的问题,提出了一个可验证的矩阵满秩分解的安全外包方案。首先,在加密阶段,结合Sherman-Morrison公式构造出一个稠密的可逆矩阵来进行加密。其次,在云计算阶段,一方面,要求云计算加密矩阵的满秩分解;另一方面,在得到满秩分解的结果（一个列满秩矩阵和一个行满秩矩阵）后,要求分别云计算列满秩矩阵的左逆和行满秩矩阵的右逆。接下来,在验证阶段,用户不仅要分别验证返回的两个矩阵是否满足行满秩和列满秩,还要验证这两个矩阵相乘是否等于加密矩阵。最后,如果验证通过,则用户可以利用私钥进行解密。在协议分析中,证明了所提方案满足正确性、安全性、高效性和可验证性。同时,当选择的原始矩阵的维度是512×512时,无论怎样改变矩阵中非零元素的密度,所提方案计算得到的加密矩阵的熵恒等于18,说明方案确实可以有效保护零元素的个数。实验结果表明所提方案具有较高的效率。     

A Symbolic-Numerical Method for Finding a Real Solution of an Arbitrary System of Nonlinear Algebraic Equations

In this paper, the author presents a new method for iteratively finding a real solution of an arbitrary system of nonlinear algebraic equations, where the system can be overdetermined or underdetermined and its Jacobian matrix can be of any (positive) rank. When the number of equations is equal to the number of variables and the Jacobian matrix of the system is nonsingular, the method is similar to the well-known Newton's method.The method is a hybrid symbolic-numerical method, in that we utilize some extended procedures from classical computer algebra together with ideas and algorithmic techniques from numerical computation, namely Newton's method and pseudoinverse matrices. First the symbolic techniques are used to transform an arbitrary system of algebraic equations into a set of regular systems. By regular system we mean a system whose Jacobian matrix is of full row rank. Newton-like numerical techniques are then used to find a real solution for each regular system obtained from the symbolic part of the method.The method has a wide range of applicability. It is especially useful for applications in which we need to find some particular solutions from a nonzero-dimensional manifold of real solutions of a system of equations, i.e. the system has infinitely many solutions.We find some mild conditions for the asymptotic convergence of the numerical part of our method. We prove that the asymptotic convergence of the new method is still quadratic while the robustness of the numerical part can be enhanced by techniques like damping as in the regular case. The method has been implemented in Maple andMathematica . Several examples are presented to show that the method works nicely.     

On the existence of an optimal observer in singular measurement systems

An essential stage in each of the existing methods for singular optimal estimation is to obtain a nonsingular measurement vector which is a linear combination of the original measurement vector and a finite number of its derivatives. A necessary and sufficient condition for the existence of such a nonsingular measurement is presented. If this condition is satisfied, then the existence of an optimal observer is guaranteed. The new condition is shown to be considerably simpler and of much wider applicability than a recently published condition which is just a sufficient one. The new condition requires just a rank check of a single composite matrix consisting of the system and noise matrices. Unlike the other condition, the existence of an optimal estimator is determined here without carrying out the complex procedures for singular optimal estimation.     

Stochastic P-type/D-type iterative learning control algorithms

This paper presents stochastic algorithms that compute optimal and sub-optimal learning gains for a P-type iterative learning control algorithm (ILC) for a class of discrete-time-varying linear systems. The optimal algorithm is based on minimizing the trace of the input error covariance matrix. The state disturbance, reinitialization errors and measurement errors are considered to be zero-mean white processes. It is shown that if the product of the input-output coupling matrices C ( t + 1 ) B ( t ) is full column rank, then the input error covariance matrix converges to zero in presence of uncorrelated disturbances. Another sub-optimal P-type algorithm, which does not require the knowledge of the state matrix, is also presented. It is shown that the convergence of the input error covariance matrices corresponding to the optimal and sub-optimal P-type and D-type algorithms are equivalent, and all converge to zero at a rate inversely proportional to the number of learning iterations. A transient-response performance comparison, in the domain of learning iterations, for the optimal and sub-optimal P- and D-type algorithms is investigated. A numerical example is added to illustrate the results.     

Representing Weighted Pseudoinverse Matrices with Mixed Weights in Terms of Other Pseudoinverses

The paper considers weighted pseudoinverse where both weighted matrices are symmetric and one of them is positive definite matrix and the other is nonsingular and indefinite. Formulas are obtained to represent these matrices in terms of the Moore–Penrose pseudoinverse matrix and other weighted pseudoinverses.     

Recursion based parallelization of exact dense linear algebra routines for Gaussian elimination

We present block algorithms and their implementation for the parallelization of sub-cubic Gaussian elimination on shared memory architectures. Contrarily to the classical cubic algorithms in parallel numerical linear algebra, we focus here on recursive algorithms and coarse grain parallelization. Indeed, sub-cubic matrix arithmetic can only be achieved through recursive algorithms making coarse grain block algorithms perform more efficiently than fine grain ones. This work is motivated by the design and implementation of dense linear algebra over a finite field, where fast matrix multiplication is used extensively and where costly modular reductions also advocate for coarse grain block decomposition. We incrementally build efficient kernels, for matrix multiplication first, then triangular system solving, on top of which a recursive PLUQ decomposition algorithm is built. We study the parallelization of these kernels using several algorithmic variants: either iterative or recursive and using different splitting strategies. Experiments show that recursive adaptive methods for matrix multiplication, hybrid recursive–iterative methods for triangular system solve and tile recursive versions of the PLUQ decomposition, together with various data mapping policies, provide the best performance on a 32 cores NUMA architecture. Overall, we show that the overhead of modular reductions is more than compensated by the fast linear algebra algorithms and that exact dense linear algebra matches the performance of full rank reference numerical software even in the presence of rank deficiencies.     

An Algorithm for the Generalized Singular Value Decomposition on Massively Parallel Computers

A new algorithm for computing the generalized singular value decomposition that diagonalizes two matrices is introduced. First, two existing algorithms are studied, one due to Paige and the other to Han and Veselic. The former requires only orthogonal plane transformations, resulting in two matrices with parallel rows. The latter employs nonsingular (not necessarily orthogonal) transformations to directly diagonalize the two data matrices. For many applications, it is preferable to be given both the diagonal matrices and the transformation matrices explicitly. Our algorithm has the advantages that the nonsingular transformation is readily available, computation of transformations is simple, and the convergence test is efficient in a parallel computing environment. We present implementation results, obtained on a Connection Machine 2, to compare our new algorithm with that of Paige.     

非线性控制系统中的相对阶概念在线性系统中的反映

相对阶(Relative Degree)概念是非线性系统控制中一个有用的概念,本文探讨了它在 线性系统中的反映.用Markov参数矩阵的方法证明了它与一致秩(Uniform Rank)、级数 指标、系统传递函数阵中元素的分母阶次与分子阶次之差、以及元素的极零点数之差的关系. 证明了线性系统的相对阶对于任意状态反馈常值阵K和任意满秩的前馈常值阵F是一个不变 量.当系统存在相对阶r=[r1,…,rm]r时,可通过K和F进行积分解耦而具有传递矩阵 diag{s-r1,…,s-1m}.     

Block TERM factorization of block matrices

Duetothelimitationofcomputationalprecisionandstoragecapacity,transformsusedinlosslessdatacompressionshouldbeequivalentlyinteger-reversible.Reversibleintegertransform(orintegermapping)issuchatypeoftransformthatmapsintegerstointegersandrealizesperfectreconstruction(PR).Peoplestartedtoworkinthisarealongago,andtheirearlywork,suchasStransform[1],TStransform[2],S+Ptransform[3],andcolorspacetransforms[4],suggestedapromisingfutureofreversibleintegermappinginimagecompression,region-of-interest(ROI)…     

Fast robust regression algorithms for problems with Toeplitz structure

The problem of computing an approximate solution of an overdetermined system of linear equations is considered. The usual approach to the problem is least squares, in which the 2-norm of the residual is minimized. This produces the minimum variance unbiased estimator of the solution when the errors in the observations are independent and normally distributed with mean 0 and constant variance. It is well known, however, that the least squares solution is not robust if outliers occur, i.e., if some of the observations are contaminated by large error. In this case, alternate approaches have been proposed which judge the size of the residual in a way that is less sensitive to these components. These include the Huber M-function, the Talwar function, the logistic function, the Fair function, and the ?₁ norm. New algorithms are proposed to compute the solution to these problems efficiently, in particular, when the matrix A has small displacement rank. Matrices with small displacement rank include matrices that are Toeplitz, block-Toeplitz, block-Toeplitz with Toeplitz blocks, Toeplitz plus Hankel, and a variety of other forms. For exposition, only Toeplitz matrices are considered, but the ideas apply to all matrices with small displacement rank. Algorithms are also presented to compute the solution efficiently when a regularization term is included to handle the case when the matrix of the coefficients is ill-conditioned or rank-deficient. The techniques are illustrated on a problem of FIR system identification.     

广义区间动力系统稳定的充分条件

本文讨论了连续广义系统在系统矩阵为区间矩阵时的稳定性问题。通过使用Gershgorin圆盘定理，在假设广义区间动力系统满足系统矩阵A主对角线元素均为负区间数的约束条件情况下，给出了一个使广义区间动力系统正则、无脉冲膜、稳定的充分条件。并针对系统对应的Gershgorin圆盘半径较大的情况做了进一步的讨论，使上述充分条件能够适用于更一般的情况。文中举出实例说明此方法的正确性。同时，本文还给出了一个判别区间矩阵为非奇异的充分必要条件。     

基于聚类数的评分矩阵恢复算法

评分矩阵（rating matrix）的特点是高维、稀疏、低秩,对其研究的主要方法是低秩矩阵恢复。对这些算法而言,不同评分矩阵的秩,会得到不同的恢复精度。但目前没有理论来研究评分矩阵秩的估计,从而影响了这些算法的应用。从理论上分析了用户聚类数与评分矩阵秩的关系,给出用户聚类数的计算方法,并在此基础上提出一种基于聚类数的秩1矩阵恢复（Clusters Number Rank-1 Matrix Completion,CN-R1MC）算法来恢复评分矩阵。通过在多个推荐系统数据集上的实验证明：用户聚类数能较好地近似评分矩阵的秩,这对提高评分矩阵的恢复精度有重要的作用。所提出的算法有较好的应用价值。     

常用Fisher判别函数的判别矩阵研究

在线性判别分析(Linear discriminant analysis, LDA)中, 比迹函数、比值函数和迹比函数是三种常用的Fisher判别函数, 每一个判别函数都可得到一个正交判别(Orthogonal discriminant, OD)矩阵和一个不相关判别(Uncorrelated discriminant, UD)矩阵. 本文的主要目的是对这6种判别矩阵的获取方法及其性质进行系统分析, 拟期更清楚地认识它们的联系与区别. 当类内协方差阵非奇异时, 比迹、比值函数的判别矩阵和迹比函数的OD矩阵的获取方法及性质已有研究, 本文对迹比函数的UD矩阵的获取方法及性质进行了补充研究, 得到了迹比函数的UD矩阵与比迹、比值函数的UD矩阵是同一矩阵以及迹比函数的UD矩阵的判别函数值不超过它的OD矩阵的结论. 当类内协方差阵奇异时, 6种判别矩阵的获取方法遇到了困难, 为克服这一困难, 本文首先用极限的思想重新定义了这三种判别函数, 然后采用求极限的方法得到了6种判别矩阵的获取方法. 从所得的获取方法可以看出, 当所需的判别向量均在类内协方差阵的零空间中时, 6个判别矩阵是同一矩阵.     

GATO: An MHD stability code for axisymmetric plasmas with internal separatrices

The GATO code computes the growth rate of ideal magnetohydrodynamic instabilities in axisymmetric geometries with internal separatrices such as doublet and expanded spheromak. The basic method, which uses a variational principle and a Galerkin procedure to obtain a matrix eigenvalue problem, is common to the ERATO and PEST codes. A new coordinate system has been developed to handle the internal separatrix. Efficient algorithms have been developed to solve the matrix eigenvalue problem for matrices of rank as large as 40 000. Further improvement is expected using graph theoretical techniques to reorder the matrices. Using judicious mesh repartition, the marginal point can be determined with great precision. The code has been extensively used to optimize doublet and general tokamak plasmas.     

Zur Berechnung von Lösungen konsistenter linearer Gleichungssysteme mit singulärer Koeffizientenmatrix

Based on a roundoff error analysis, it is shown how to modify the well-known iterative refinement algorithm for nonsingular linear algebraic systems to get an algorithm for computing one of the solutions of a consistent system with quadratic singular matrix. The algorithm is given explicitly for symmetric matrices.     

动态反馈解耦规范型时域结构特征分析及变换矩阵的构造

从可解耦线性多输入多输出(Multi-input multi-output, MIMO)系统的结构特性指数出发, 根据此类系统解耦后系统的可观测矩阵与基本向量矩阵的秩的关系, 提出了按照这种关系将解耦规范型划分为4大类的观点, 同时给出了一种针对各类积分型解耦系统构造相应的非奇异变换矩阵的构造方法. 分析了解耦规范型及其变换矩阵的时域结构形式, 通过一系列定理的证明,从一般意义上解释了解耦规范型的结构与变换矩阵的关系, 并通过一个数值实例验证了所提出方法的正确性及可行性.     

SVD based initialization: A head start for nonnegative matrix factorization

We describe Nonnegative Double Singular Value Decomposition (NNDSVD), a new method designed to enhance the initialization stage of nonnegative matrix factorization (NMF). NNDSVD can readily be combined with existing NMF algorithms. The basic algorithm contains no randomization and is based on two SVD processes, one approximating the data matrix, the other approximating positive sections of the resulting partial SVD factors utilizing an algebraic property of unit rank matrices. Simple practical variants for NMF with dense factors are described. NNDSVD is also well suited to initialize NMF algorithms with sparse factors. Many numerical examples suggest that NNDSVD leads to rapid reduction of the approximation error of many NMF algorithms.