Search

Nonnegative matrix factorization (NMF) is a popular model in the field of pattern recognition. The aim is to find a low rank approximation for nonnegative matrix M by a product of two nonnegative matrices W and H. In general, NMF is NP-hard to solve while it can be solved efficiently under a separability assumption, which requires that the columns of the factor matrix are some columns of the input matrix M. In this paper, we generalize the separability assumption based on 3-factor NMF (M = P1SP2), and require that S is a submatrix of the input matrix M. We refer to this NMF as a Coseparable NMF (CoS-NMF). In the paper, we discuss and study mathematical properties of CoS-NMF, and present its relationships with other matrix factorizations such as generalized separable NMF, tri-symNMF, biorthogonal trifactorization and CUR decomposition. An optimization method for CoS-NMF is proposed, and an alternating fast gradient method is employed to determine the rows and the columns of M for the submatrix S. Numerical experiments on synthetic data sets, document data sets, and facial data sets are conducted to verify the effectiveness of the proposed CoS-NMF model. By comparison with state-of-the-art methods, the CoS-NMF model performs very well in a coclustering task by finding useful features, and keeps a good approximation to the input data matrix as well. [ABSTRACT FROM AUTHOR]

In this paper, we first give new model formulations for computing arbitrary generalized singular value of a Grassmann matrix pair or a real matrix pair. In these new formulations, we need to solve matrix optimization problems with unitary constraints or orthogonal constraints. We propose a geometric inexact Newton--conjugate gradient (Newton-CG) method for solving the resulting matrix optimization problems. Under some mild assumptions, we establish the global and quadratic convergence of the proposed method for the complex case. Some numerical examples are given to illustrate the effectiveness and high accuracy of the proposed method. [ABSTRACT FROM AUTHOR]

In practical applications, incremental tensors are very common: only a portion of tensor data is available, and new data are arriving in the next time step or continuously over time. To handle this type of tensors time-saving algorithms are required for online computation. In this paper, we consider incremental CP ( CANDECOMP/PARAFAC ) decomposition, which requires one to update the CP decomposition after new tensor data, together with the exiting tensor, are ready for analysis. There exist several incremental CP decomposition algorithms, but almost all of these algorithms assume that the number of CP decomposition components remains fixed in the incremental process. The main contribution of this paper is the study of how to add components in the incremental CP decomposition. We derive the coordinate representation of the incremental CP decomposition with respect to a special basis and show related properties of tensor rank and the uniqueness of such incremental CP decomposition. Under the framework of this representation, the proposed method can be solved by using an alternating minimization algorithm. Numerical examples are presented to show the good performance of the proposed algorithms in terms of computational time and data fitting compared with existing methods. [ABSTRACT FROM AUTHOR]

The main aim of this paper is to develop the quaternion generalized minimal residual method (QGMRES) for solving quaternion linear systems. Quaternion linear systems arise fromthree-dimensional or color imaging filtering problems. The proposed quaternion Arnoldi procedure can preserve quaternion Hessenberg form during the iterations. The main advantage is that the storage of the proposed iterative method can be reduced by comparing with the Hessenberg form constructed by the classical GMRES iterations for the real representation of quaternion linear systems. The convergence of the proposed QGMRES is also established. Numerical examples are presented to demonstrate the effectiveness of the proposed QGMRES compared with the traditional GMRES in terms of storage and computing time [ABSTRACT FROM AUTHOR]

In this paper, we consider an inverse problem with quasi-boundary value regularization for recovering a source term of the time fractional diffusion equations from the final observation data. In particular, a two-by-two block linear system arising from the problem is studied. We propose a fast preconditioning technique by approximating the Schur complement in the system using a product of some factors, motivated by an approximate diagonalization of one of the blocks. The eigenvalues of the preconditioned system are shown to be clustered around 1, and the fast convergence of the methods is guaranteed theoretically. We also present an approach for selecting the regularization parameter of the quasi-boundary value method. Numerical experiments are carried out to demonstrate the effectiveness of our method. [ABSTRACT FROM AUTHOR]

In this paper, we study orthogonal nonnegative matrix factorization. We demonstrate the coefficient matrix can be sparse and low-rank in the orthogonal nonnegative matrix factorization. By using these properties, we propose to use a sparsity and nuclear norm minimization for the factorization and develop a convex optimization model for finding the coefficient matrix in the factorization. Numerical examples including synthetic and real-world data sets are presented to illustrate the effectiveness of the proposed algorithm and demonstrate that its performance is better than other testing methods. [ABSTRACT FROM AUTHOR]

We study the eigenvalue bounds of block two-by-two nonsingular and symmetric indefinite matrices whose (1, 1) block is symmetric positive definite and Schur complement with respect to its (2, 2) block is symmetric indefinite. A constraint preconditioner for this matrix is constructed by simply replacing the (1, 1) block by a symmetric and positive definite approximation, and the spectral properties of the preconditioned matrix are discussed. Numerical results show that, for a suitably chosen (1, 1) block-matrix, this constraint preconditioner outperforms the blockdiagonal and the block-tridiagonal ones in iteration step and computing time when they are used to accelerate the GMRES method for solving these block two-by-two symmetric positive indefinite linear systems. The new results extend the existing ones about block two-by-two matrices of symmetric negative semidefinite (2, 2) blocks to those of general symmetric (2, 2) blocks. [ABSTRACT FROM AUTHOR]

In this paper we consider the solution of Hermitian positive definite block-Toeplitz systems with small size blocks. We propose and study block diagonal and Schur complement preconditioners for such block-Toeplitz matrices. We show that for some block-Toeplitz matrices, the spectra of the preconditioned matrices are uniformly bounded except for a fixed number of outliers where this fixed number depends only on the size of the block. Hence, conjugate gradient type methods, when applied to solving these preconditioned block-Toeplitz systems with small size blocks, converge very fast. Recursive computation of such block diagonal and Schur complement preconditioners is considered by using the nice matrix representation of the inverse of a block-Toeplitz matrix. Applications to block-Toeplitz systems arising from least squares filtering problems and queueing networks are presented. Numerical examples are given to demonstrate the effectiveness of the proposed method. [ABSTRACT FROM AUTHOR]

We consider the iterative solution of weighted Toeplitz least squares problems. Our approach is based on an augmented system formulation. We focus our attention on two types of preconditioners: a variant of constraint preconditioning, and the Hermitian/skew-Hermitian splitting (HSS) preconditioner. Bounds on the eigenvalues of the preconditioned matrices are given in terms of problem and algorithmic parameters, and numerical experiments are used to illustrate the performance of the preconditioners. [ABSTRACT FROM AUTHOR]

Many image processing applications require computing approximate solutions of very large, ill-conditioned linear systems. Physical assumptions of the imaging system usually dictate that the matrices in these linear systems have exploitable structure. The specific structure depends on (usually simplifying) assumptions of the physical model and other considerations such as boundary conditions. When reflexive (Neumann) boundary conditions are used, the coefficient matrix is a combination of Toeplitz and Hankel matrices. Kronecker products also occur, but this structure is not obvious from measured data. In this paper we discuss a scheme for computing a (possibly approximate) Kronecker product decomposition of structured matrices in image processing, which extends previous work by Kamm and Nagy [SIAM J. Matrix Anal. Appl., 22 (2000), pp. 155–172] to a wider class of image restoration problems. [ABSTRACT FROM AUTHOR]

We consider linear systems of equations arising from the sinc method of boundary value problems which are typically nonsymmetric and dense. For the solutions of these systems we propose Krylov subspace methods with banded preconditioners. We prove that our preconditioners are invertible and discuss the convergence behavior of the conjugate gradient method for normal equations (CGNE). In particular, we show that the solution of an n-by-n discrete sinc system arising from the model problem can be obtained in O(n log² n) operations by using the preconditioned CGNE method. Numerical results are given to illustrate the effectiveness of our fast iterative solvers. [ABSTRACT FROM AUTHOR]

Quaternion matrices are employed successfully in many color image processing applications. In particular, a pure quaternion matrix can be used to represent red, green, and blue channels of color images. A low-rank approximation for a pure quaternion matrix can be obtained by using the quaternion singular value decomposition. However, this approximation is not optimal in the sense that the resulting low-rank approximation matrix may not be pure quaternion, i.e., the low-rank matrix contains a real component which is not useful for the representation of a color image. The main contribution of this paper is to find an optimal rank-r pure quaternion matrix approximation for a pure quaternion matrix (a color image). Our idea is to use a pro jection on a low-rank quaternion matrix manifold and a projection on a quaternion matrix with zero real component, and develop an alternating pro jections algorithm to find such optimal low-rank pure quaternion matrix approximation. The convergence of the pro jection algorithm can be established by showing that the low-rank quaternion matrix manifold and the zero real component quaternion matrix manifold has a nontrivial intersection point. Numerical examples on synthetic pure quaternion matrices and color images are presented to illustrate the pro jection algorithm can find optimal low-rank pure quaternion approximation for pure quaternion matrices or color images. [ABSTRACT FROM AUTHOR]

In this paper, we study the Birkhoff-von Neumann theorem for a class of multistochastic tensors. In particular, we give a necessary and sufficient condition such that a multistochastic tensor is a convex combination of finitely many permutation tensors. It is well-known that extreme points in the set of doubly stochastic matrices are just permutation matrices. However, we find that extreme points in the set of multistochastic tensors are not just permutation tensors. We provide the other types of tensors contained in the set of extreme points. [ABSTRACT FROM AUTHOR]

Let Z be an n X n complex matrix. A decomposition Z = U̅MUH is called an antitriangular Schur decomposition of Z if U is an n x n unitary matrix and M is an n x n antitriangular matrix. The antitriangular Schur decomposition is a useful tool for solving palindromic eigenvalue problems. However, there is no perturbation result for an antitriangular Schur decomposition in the literature. The main contribution of this paper is to give a perturbation bound of such decomposition and show that the bound depends inversely on Due to image rights restrictions, multiple line equation(s) cannot be graphically displayed., where XL and XU are the strictly lower triangular and upper triangular parts of X, XN = XL + XU, and Aup(Y) denotes the strictly upper antitriangular part of Y. The quantity √2/f(M) can be used to characterize the condition number of the decomposition, i.e., when √2/f(M) is large (or small), the decomposition problem is ill-conditioned (or well-conditioned). Numerical examples are presented to illustrate the theoretical result. [ABSTRACT FROM AUTHOR]

Linear discriminant analysis (LDA) is one of the most popular approaches for feature extraction and dimension reduction to overcome the curse of the dimensionality of the high-dimensional data in many applications of data mining, machine learning, and bioinformatics. In this paper, we made two main contributions to an important LDA scheme, the generalized Foley–Sammon transform (GFST) [Foley and Sammon, IEEE Trans. Comput., 24 (1975), pp. 281–289; Guo et al., Pattern Recognition Lett., 24 (2003), pp. 147–158] or a trace ratio model [Wang et al., Proceedings of the International Conference on Computer Vision and Pattern Recognition, 2007, pp. 1–8] and its regularized GFST (RGFST), which handles the undersampled problem that involves small samples size n, but with high number of features N (N > n) and arises frequently in many modern applications. Our first main result is to establish an equivalent reduced model for the RGFST which effectively improves the computational overhead. The iteration method proposed by Wang et al. is applied to solve the GFST or the reduced RGFST. It has been proven by Wang et al. that this iteration converges globally and fast convergence was observed numerically, but there is no theoretical analysis on the convergence rate thus far. Our second main contribution completes this important and missing piece by proving the quadratic convergence even under two kinds of inexact computations. Practical implementations, including computational complexity and storage requirements, are also discussed. Our experimental results on several real world data sets indicate the efficiency of the algorithm and the advantages of the GFST model in classification. [ABSTRACT FROM AUTHOR]

Examines efficient iterative methods for the large sparse non-Hermitian positive definite systems of linear equations based on the Hermitian and skew-Hermitian splitting of the coefficient matrix. Demonstration that the Hermitian/skew-Hermitian splitting iteration method converges unconditionally to the unique solution of the system of linear equations.