Accelerated low rank matrix approximate algorithms for matrix completion

In this paper, we propose two accelerated algorithms for the low-rank approximate method in Wang et al. (0000) for matrix completion. The main idea is to use the successive over-relaxation technique. Based on the successive over-relaxation method for the feasible matrices or projection matrices, the low-rank matrix approximate method is modified and accelerated. Meanwhile, we discuss the convergence of the over-relaxation algorithm for the feasible matrix. Finally, the numerical experiments show them to be effective.     

Textile fabric defect detection based on low-rank representation

In this paper, we propose a novel and robust fabric defect detection method based on the low-rank representation (LRR) technique. Due to the repeated texture structure we model a defects-free fabric image as a low-rank structure. In addition, because defects, if exist, change only the texture of fabric locally, we model them with a sparse structure. Based on the above idea, we represent a fabric image into the sum of a low-rank matrix which expresses fabric texture and a sparse matrix which expresses defects. Then, the LRR method is applied to obtain the corresponding decomposition. Especially, in order to make better use of low-rank structure characteristics we propose LRREB (low-rank representation based on eigenvalue decomposition and blocked matrix) method to improve LRR. LRREB is implemented by dividing a image into some corresponding blocked matrices to reduce dimensions and applying eigen-value decomposition (EVD) on blocked matrix instead of singular value decomposition (SVD) on original fabric image, which improves the accuracy and efficiency. No training samples are required in our methods. Experimental results show that the proposed fabric defect detection method is feasible, effective, and simple to be employed.

     

A novel segmentation algorithm for nucleus in white blood cells based on low-rank representation

White blood cells (WBCs) segmentation is a challenging problem in the study of automated morphological systems, due to both the complex nature of the cells and the uncertainty that is present in video microscopy. This paper investigates how to boost the effects of region-based nucleus segmentation in WBCs by means of optimal thresholding and low-rank representation. The main idea is firstly using optimal thresholding to obtain the possible uniform WBC regions in the input image. After that, a manifold-based low-rank representation technique is employed to infer a unified affinity matrix that implicitly encodes the segmentation of the pixels of possible WBC regions. This is achieved by separating the low-rank affinities from the feature matrix into a pair of sparse and low-rank matrices. The experiments show that the proposed method is possible to produce better segmentation results compared with existing approaches.

     

Low-rank matrix decomposition in L1-norm by dynamic systems

Low-rank matrix approximation is used in many applications of computer vision, and is frequently implemented by singular value decomposition under L₂-norm sense. To resist outliers and handle matrix with missing entries, a few methods have been proposed for low-rank matrix approximation in L₁ norm. However, the methods suffer from computational efficiency or optimization capability. Thus, in this paper we propose a solution using dynamic system to perform low-rank approximation under L₁-norm sense. From the state vector of the system, two low-rank matrices are distilled, and the product of the two low-rank matrices approximates to the given measurement matrix with missing entries, in L₁ norm. With the evolution of the system, the approximation accuracy improves step by step. The system involves a parameter, whose influences on the computational time and the final optimized two low-rank matrices are theoretically studied and experimentally valuated. The efficiency and approximation accuracy of the proposed algorithm are demonstrated by a large number of numerical tests on synthetic data and by two real datasets. Compared with state-of-the-art algorithms, the newly proposed one is competitive.     

A mixed-precision algorithm for the solution of Lyapunov equations on hybrid CPU-GPU platforms

We describe a hybrid Lyapunov solver based on the matrix sign function, where the intensive parts of the computation are accelerated using a graphics processor (GPU) while executing the remaining operations on a general-purpose multi-core processor (CPU). The initial stage of the iteration operates in single-precision arithmetic, returning a low-rank factor of an approximate solution. As the main computation in this stage consists of explicit matrix inversions, we propose a hybrid implementation of Gauß-Jordan elimination using look-ahead to overlap computations on GPU and CPU. To improve the approximate solution, we introduce an iterative refinement procedure that allows to cheaply recover full double-precision accuracy. In contrast to earlier approaches to iterative refinement for Lyapunov equations, this approach retains the low-rank factorization structure of the approximate solution. The combination of the two stages results in a mixed-precision algorithm, that exploits the capabilities of both general-purpose CPUs and many-core GPUs and overlaps critical computations. Numerical experiments using real-world data and a platform equipped with two Intel Xeon QuadCore processors and an Nvidia Tesla C1060 show a significant efficiency gain of the hybrid method compared to a classical CPU implementation.     

Computation of Sharp Rigorous Componentwise Error Bounds for the Approximate Solutions of Systems of Linear Equations

This paper is concerned with the problem of verifying the accuracy of approximate solutions of systems of linear equations. Recently, fast algorithms for calculating guaranteed error bounds of computed solutions of systems of linear equations have been proposed using the rounding mode controlled verification method and the residual iterative verification method. In this paper, a new verification method for systems of linear equations is proposed. Using this verification method, componentwise verified error bounds of approximate solutions of systems of linear equations can be calculated. Numerical results are presented to illustrate that it is possible to get very sharp error bounds of computed solutions of systems of linear equations whose coefficient matrices are symmetric and positive definite.     

A direct method for solving linear systems

In this work we propose a direct method for solving systems of linear equations which is based on a successive LU-decomposition of matrices of the form l + uv ^T . Simultaneously, the factors of an LU-decomposition of the coefficient matrix are obtained. A specific choice of the “rank-one decomposition” of the given matrix leads to a variant of the Gauss elimination process.     

Hierarchical matrix arithmetic with accumulated updates

Hierarchical matrices can be used to construct efficient preconditioners for partial differential and integral equations by taking advantage of low-rank structures in triangular factorizations and inverses of the corresponding stiffness matrices. The setup phase of these preconditioners relies heavily on low-rank updates that are responsible for a large part of the algorithm’s total run-time, particularly for matrices resulting from three-dimensional problems. This article presents a new algorithm that significantly reduces the number of low-rank updates and can shorten the setup time by 50% or more.

     

一个反求Bezier曲面控制点的算法

本文将反求m×n次Bezier曲面控制点问题,转化为求解m+1个n+1阶线性方程组和n+1个m+1阶线性方程组问题。这些线性方程组的系数矩阵是著名的Vandermonde矩阵。通过求解Vandermonde矩阵的逆矩阵,使CAD/CAM曲面造型中常常遇到的反求Bezier曲面控制点问题得到有效的解决。同时本文给出了一种求解Vandermonde矩阵的逆矩阵的方法。     

Dynamical low-rank approximation: applications and numerical experiments

Dynamical low-rank approximation is a differential-equation-based approach to efficiently compute low-rank approximations to time-dependent large data matrices or to solutions of large matrix differential equations. We illustrate its use in the following application areas: as an updating procedure in latent semantic indexing for information retrieval, in the compression of series of images, and in the solution of time-dependent partial differential equations, specifically on a blow-up problem of a reaction-diffusion equation in two and three spatial dimensions. In 3D and higher dimensions, space discretization yields a tensor differential equation whose solution is approximated by low-rank tensors, effectively solving a system of discretized partial differential equations in one spatial dimension.     

Fast solution of implicit methods for linear hyperbolic equations

A factorisation method is described for the fast numerical solution of constant tridiagonal Toeplitz linear systems which occur repeatedly in the solution of the implicit finite difference equations derived from linear first order hyperbolic equations, i.e. the Transport equation, under a variety of boundary conditions. In this paper, we show that such special linear systems can be solved efficiently by the factorisation of the coefficient matrix into two easily inverted matrices.     

New updates of incomplete LU factorizations and applications to large nonlinear systems

In this paper, we address the problem of preconditioning sequences of large sparse indefinite systems of linear equations and present two new strategies to construct approximate updates of factorized preconditioners. Both updates are based on the availability of an incomplete factorization for one matrix of the sequence and differ in the approximation of the so-called ideal update. For a general treatment, an incomplete LU (ILU) factorization is considered, but the proposed approaches apply to incomplete factorizations of symmetric matrices as well. The first strategy is an approximate diagonal update of the ILU factorization; the second strategy relies on banded approximations of the factors in the ideal update. The efficiency and reliability of the proposed preconditioners are shown in the solution of nonlinear systems of equations by preconditioned Newton–Krylov methods. Nearly matrix-free implementations of the updating strategy are provided, and numerical experiments are carried out on application problems.     

Fast QR factorization of low-rank changes of Vandermonde-like matrices

This paper is concerned with the solution of linear systems with coefficient matrices which are Vandermonde-like matrices modified by adding low-rank corrections. Hereafter we refer to these matrices as modified Vandermonde-like matrices. The solution of modified Vandermonde-like linear systems arises in approximation theory both when we use Remez algorithms for finding minimax approximations and when we consider least squares problems with constraints. Our approach relies on the computation of an inverse QR factorization. More specifically, we show that some classical orthogonalization schemes for m×n, m≥n, Vandermonde-like matrices can be extended to compute efficiently an inverse QR factorization of modified Vandermonde-like matrices. The resulting algorithm has a cost of O(mn) arithmetical operations. Moreover it requires O(m) storage since the matrices Q and R are not stored. Received: January 1997 / Accepted: November 1997     

Structural Identifiability in Low-Rank Matrix Factorization

In many signal processing and data mining applications, we need to approximate a given matrix Y with a low-rank product Y≈AX. Both matrices A and X are to be determined, but we assume that from the specifics of the application we have an important piece of a-priori knowledge: A must have zeros at certain positions. In general, different AX factorizations approximate a given Y equally well, so a fundamental question is whether the known zero pattern of A contributes to the uniqueness of the factorization. Using the notion of structural rank, we present a combinatorial characterization of uniqueness up to diagonal scaling (subject to a mild non-degeneracy condition on the factors), called structural identifiability of the model.     

Factorized Solution of Lyapunov Equations Based on Hierarchical Matrix Arithmetic

We investigate the numerical solution of large-scale Lyapunov equations with the sign function method. Replacing the usual matrix inversion, addition, and multiplication by formatted arithmetic for hierarchical matrices, we obtain an implementation that has linear-polylogarithmic complexity and memory requirements. The method is well suited for Lyapunov operators arising from FEM and BEM approximations to elliptic differential operators. With the sign function method it is possible to obtain a low-rank approximation to a full-rank factor of the solution directly. The task of computing such a factored solution arises, e.g., in model reduction based on balanced truncation. The basis of our method is a partitioned Newton iteration for computing the sign function of a suitable matrix, where one part of the iteration uses formatted arithmetic while the other part directly yields approximations to the full-rank factor of the solution. We discuss some variations of our method and its application to generalized Lyapunov equations. Numerical experiments show that the method can be applied to problems of order up to (10⁵) on workstations.     

求解低秩矩阵融合高动态范围图像

目的 利用低秩矩阵恢复方法可从稀疏噪声污染的数据矩阵中提取出对齐且线性相关低秩图像的优点,提出一种新的基于低秩矩阵恢复理论的多曝光高动态范围（HDR）图像融合的方法,以提高HDR图像融合技术的抗噪声与去伪影的性能。方法 以部分奇异值（PSSV）作为优化目标函数,可构建通用的多曝光低动态范围（LDR）图像序列的HDR图像融合低秩数学模型。然后利用精确增广拉格朗日乘子法,求解输入的多曝光LDR图像序列的低秩矩阵,并借助交替方向乘子法对求解算法进行优化,对不同的奇异值设置自适应的惩罚因子,使得最优解尽量集中在最大奇异值的空间,从而得到对齐无噪声的场景完整光照信息,即HDR图像。结果 本文求解方法具有较好的收敛性,抗噪性能优于鲁棒主成分分析（RPCA）与PSSV方法,且能适用于多曝光LDR图像数据集较少的场合。通过对经典的Memorial Church与Arch多曝光LDR图像序列的HDR图像融合仿真结果表明,本文方法对噪声与伪影的抑制效果较为明显,图像细节丰富,基于感知一致性（PU）映射的峰值信噪比（PSNR）与结构相似度（SSIM）指标均优于对比方法：对于无噪声的Memorial Church图像序列,RPCA方法的PSNR、SSIM值分别为28.117 dB与0.935,而PSSV方法的分别为30.557 dB与0.959,本文方法的分别为32.550 dB与0.968。当为该图像序列添加均匀噪声后,RPCA方法的PSNR、SSIM值为28.115 dB与0.935,而PSSV方法的分别为30.579 dB与0.959,本文方法的为32.562 dB与0.967。结论 本文方法将多曝光HDR图像融合问题与低秩最优化理论结合,不仅可以在较少的数据量情况下以较低重构误差获取到HDR图像,还能有效去除动态场景伪影与噪声的干扰,提高融合图像的质量,具有更好的鲁棒性,适用于需要记录场景真实光线变化的场合。     

Robust hashing for multi-view data: Jointly learning low-rank kernelized similarity consensus and hash functions

Learning hash functions/codes for similarity search over multi-view data is attracting increasing attention, where similar hash codes are assigned to the data objects characterizing consistently neighborhood relationship across views. Traditional methods in this category inherently suffer three limitations: 1) they commonly adopt a two-stage scheme where similarity matrix is first constructed, followed by a subsequent hash function learning; 2) these methods are commonly developed on the assumption that data samples with multiple representations are noise-free,which is not practical in real-life applications; and 3) they often incur cumbersome training model caused by the neighborhood graph construction using all N points in the database (O(N)). In this paper, we motivate the problem of jointly and efficiently training the robust hash functions over data objects with multi-feature representations which may be noise corrupted. To achieve both the robustness and training efficiency, we propose an approach to effectively and efficiently learning low-rank kernelized¹ hash functions shared across views. Specifically, we utilize landmark graphs to construct tractable similarity matrices in multi-views to automatically discover neighborhood structure in the data. To learn robust hash functions, a latent low-rank kernel function is used to construct hash functions in order to accommodate linearly inseparable data. In particular, a latent kernelized similarity matrix is recovered by rank minimization on multiple kernel-based similarity matrices. Extensive experiments on real-world multi-view datasets validate the efficacy of our method in the presence of error corruptions.We use kernelized similarity rather than kernel, as it is not a squared symmetric matrix for data-landmark affinity matrix.     

Efficient solutions of hierarchical systems of linear equations

Several methods have been developed in the past for the efficient solution of sparse systems of linear equations with Gaussian elimination. In [5] the generalized nested dissection method is introduced. This method finds an ordering of the rows and columns of the coefficient matrix that produces small fill-in. [6] exploits the hierarchical structure imposed on the coefficient matrix by nested dissection to circumvent the necessity for using general sparse matrix algorithms. He decomposes the matrix into submatrices, solves them and reassembles the solution. We take the approach of [6] one step further: In many engineering applications such as finite element problems and circuit analysis problems many of the submatrices are identical. We exploit this fact to drastically reduce the space requirements for solving systems of linear equations that are defined succinctly using hierarchical definitions. Furthermore, if only a few components of the solution vector are asked for, we can by the same token achieve drastic savings of computing time. We get our results by extending a method for hierarchical graph processing presented in [4] to matrix computation. Our approach generalizes special solutions given in [9, 10].     

Recovering shape and motion by a dynamic system for low-rank matrix approximation in L 1 norm

To recover motion and shape matrices from a matrix of tracking feature points on a rigid object under orthography, we can do low-rank matrix approximation of the tracking matrix with its each column minus the row mean vector of the matrix. To obtain the row mean vector, usually 4-rank matrix approximation is used to recover the missing entries. Then, 3-rank matrix approximation is used to recover the shape and motion. Obviously, the procedure is not convenient. In this paper, we build a cost function which calculates the shape matrix, motion matrix as well as the row mean vector at the same time. The function is in L ₁ norm, and is not smooth everywhere. To optimize the function, a continuous-time dynamic system is newly proposed. With time going on, the product of the shape and rotation matrices becomes closer and closer, in L ₁-norm sense, to the tracking matrix with each its column minus the mean vector. A parameter is implanted into the system for improving the calculating efficiency, and the influence of the parameter on approximation accuracy and computational efficiency are theoretically studied and experimentally confirmed. The experimental results on a large number of synthetic data and a real application of structure from motion demonstrate the effectiveness and efficiency of the proposed method. The proposed system is also applicable to general low-rank matrix approximation in L ₁ norm, and this is also experimentally demonstrated.     

Systems of linear difference equations with bounded and robustly bounded solutions

In this paper, we investigate higher-order systems of linear difference equations where the associated characteristic matrix polynomial is self-inversive. We consider classes of equations with bounded solutions. It is known that stability properties of higher-order systems of linear difference equations are determined by the characteristic values of the corresponding matrix polynomials. All solutions are bounded (in both time directions) if the spectrum of the corresponding matrix polynomial lies on the unit circle, and moreover if the characteristic values of modulus 1 are semisimple. If the corresponding matrix polynomial is self-inversive, then one can use the inner radius of the numerical range to obtain a criterion for boundedness of solutions. We show that all solutions are bounded if the inner radius is greater than 1. In the case of matrix polynomials with positive definite coefficient matrices, we derive a computable lower bound for the inner radius and we obtain a criterion for robust boundedness.