Linear rank and corank preserving maps on (H) and an application to *-semigroup isomorphisms of operator ideals

We characterize linear rank-k nonincreasing, rank-k preserving, and corank-k preserving maps on B(H), the algebra of all bounded linear operators on the Hilbert space H. This unifies and extends finite-dimensional results and results on linear rank-1 non-increasing and rank-1 preserving maps in the infinite-dimensional case. We conclude with an application to *-semigroup isomorphisms of operator ideals.     

Accurate downdating of a modified Gram-Schmidt QR decomposition

A new algorithm for downdating a QR decomposition is presented. We show that, when the columns in the Q factor from the Modified Gram-Schmidt QR decomposition of a matrixX are exactly orthonormal, the Gram-Schmidt downdating algorithm for the QR decomposition ofX is equivalent to downdating the full Householder QR decomposition of the matrixX augmented by ann ×n zero matrix on top. Using this relation, we derive an algorithm that improves the Gram-Schmidt downdating algorithm when the columns in the Q factor are not orthonormal. Numerical test results show that the new algorithm produces far more accurate results than the Gram-Schmidt downdating algorithm for certain ill-conditioned problems.This work was partially supported in part by the National Science Foundation grants CCR-9209726 and CCR-9509085.     

On systolic arrays for updating the Cholesky factorization

We have considered the systolic implementation of several methods for updating the Cholesky factorization. For positive rank-k changes there are simple one-pass arrays that implement algorithms based on elimination and plane rotations. In the case of negative rank-one changes, we do not feel that the standard algorithm [2] has a practical implementation. We have introduced a new algorithm for the case of a negative rank-k change and provided an attractive two-pass systolic implementation.     

DC-NMF: nonnegative matrix factorization based on divide-and-conquer for fast clustering and topic modeling

The importance of unsupervised clustering and topic modeling is well recognized with ever-increasing volumes of text data available from numerous sources. Nonnegative matrix factorization (NMF) has proven to be a successful method for cluster and topic discovery in unlabeled data sets. In this paper, we propose a fast algorithm for computing NMF using a divide-and-conquer strategy, called DC-NMF. Given an input matrix where the columns represent data items, we build a binary tree structure of the data items using a recently-proposed efficient algorithm for computing rank-2 NMF, and then gather information from the tree to initialize the rank-k NMF, which needs only a few iterations to reach a desired solution. We also investigate various criteria for selecting the node to split when growing the tree. We demonstrate the scalability of our algorithm for computing general rank-k NMF as well as its effectiveness in clustering and topic modeling for large-scale text data sets, by comparing it to other frequently utilized state-of-the-art algorithms. The value of the proposed approach lies in the highly efficient and accurate method for initializing rank-k NMF and the scalability achieved from the divide-and-conquer approach of the algorithm and properties of rank-2 NMF. In summary, we present efficient tools for analyzing large-scale data sets, and techniques that can be generalized to many other data analytics problem domains along with an open-source software library called SmallK.     

Perturbation and error analyses for block downdating of a Cholesky decomposition

A new perturbation result is presented for the problem of block downdating a Cholesky decompositionX ^T X = R ^T R. Then, a condition number for block downdating is proposed and compared to other downdating condition numbers presented in literature recently. This new condition number is shown to give a tighter bound in many cases. Using the perturbation theory, an error analysis is presented for the block downdating algorithms based on the LINPACK downdating algorithm and stabilized hyperbolic transformations. An error analysis is also given for block downdating using Corrected Seminormal Equations (CSNE), and it is shown that for ill-conditioned downdates this method gives more accurate results than the algorithms based on the LINPACK downdating algorithm or hyperbolic transformations. We classify the problems for which the CSNE downdating method produces a downdated upper triangular matrix which is comparable in accuracy to the upper triangular factor obtained from the QR decomposition by Householder transformations on the data matrix with the row block deleted.Dedicated to Ji-guang Sun in honour of his 60th birthdayThe work of the second author was supported in part by the National Science Foundation grant CCR-9209726.     

Subtracting a best rank-1 approximation may increase tensor rank

It has been shown that a best rank-R approximation of an order-k tensor may not exist when R?2 and k?3. This poses a serious problem to data analysts using tensor decompositions. It has been observed numerically that, generally, this issue cannot be solved by consecutively computing and subtracting best rank-1 approximations. The reason for this is that subtracting a best rank-1 approximation generally does not decrease tensor rank. In this paper, we provide a mathematical treatment of this property for real-valued 2×2×2 tensors, with symmetric tensors as a special case. Regardless of the symmetry, we show that for generic 2×2×2 tensors (which have rank 2 or 3), subtracting a best rank-1 approximation results in a tensor that has rank 3 and lies on the boundary between the rank-2 and rank-3 sets. Hence, for a typical tensor of rank 2, subtracting a best rank-1 approximation increases the tensor rank.     

Structured multi-way arrays and their applications

Based on the structure of the rank-1 matrix and the different unfolding ways of the tensor, we present two types of structured tensors which contain the rank-1 tensors as special cases. We study some properties of the ranks and the best rank-r approximations of the structured tensors. By using the upper-semicontinuity of the matrix rank, we show that for the structured tensors, there always exist the best rank-r approximations. This can help one to better understand the sequential unfolding singular value decomposition (SVD) method for tensors proposed by J. Salmi et al. [IEEE Trans Signal Process, 2009, 57(12): 4719–4733] and offer a generalized way of low rank approximations of tensors. Moreover, we apply the structured tensors to estimate the upper and lower bounds of the best rank-1 approximations of the 3rd-order and 4th-order tensors, and to distinguish the well written and non-well written digits.     

Sufficient descent nonlinear conjugate gradient methods with conjugacy condition

In this paper, by the use of Gram-Schmidt orthogonalization, we propose a class of modified conjugate gradient methods. The methods are modifications of the well-known conjugate gradient methods including the PRP, the HS, the FR and the DY methods. A common property of the modified methods is that the direction generated by any member of the class satisfies g_k^Td_k=-||g_k||²g_{k}^{T}d_k=-\|g_k\|^2. Moreover, if line search is exact, the modified method reduces to the standard conjugate gradient method accordingly. In particular, we study the modified YT and YT+ methods. Under suitable conditions, we prove the global convergence of these two methods. Extensive numerical experiments show that the proposed methods are efficient for the test problems from the CUTE library.     

The rank of a 2 × 2 × 2 tensor

As computing power increases, many more problems in engineering and data analysis involve computation with tensors, or multi-way data arrays. Most applications involve computing a decomposition of a tensor into a linear combination of rank-1 tensors. Ideally, the decomposition involves a minimal number of terms, i.e. computation of the rank of the tensor. Tensor rank is not a straight-forward extension of matrix rank. A constructive proof based on an eigenvalue criterion is provided that shows when a 2?×?2?×?2 tensor over ? is rank-3 and when it is rank-2. The results are extended to show that n?×?n?×?2 tensors over ? have maximum possible rank n?+?k where k is the number of complex conjugate eigenvalue pairs of the matrices forming the two faces of the tensor cube.     

Solution of augmented linear systems using orthogonal factorizations

We consider solvingx+Ay=b andA ^T x=c for givenb, c andm ×n A of rankn. This is called the augmented system formulation (ASF) of two standard optimization problems, which include as special cases the minimum 2-norm of a linear underdetermined system (b=0) and the linear least squares problem (c=0), as well as more general problems. We examine the numerical stability of methods (for the ASF) based on the QR factorization ofA, whether by Householder transformations, Givens rotations, or the modified Gram-Schmidt (MGS) algorithm, and consider methods which useQ andR, or onlyR. We discuss the meaning of stability of algorithms for the ASF in terms of stability of algorithms for the underlying optimization problems.We prove the backward stability of several methods for the ASF which useQ andR, inclusing a new one based on MGS, and also show under what circumstances they may be regarded as strongly stable. We show why previous methods usingQ from MGS were not backward stable, but illustrate that some of these methods may be acceptable-error stable. We point out that the numerical accuracy of methods that do not useQ does not depend to any significant extent on which of of the above three QR factorizations is used. We then show that the standard methods which do not useQ are not backward stable or even acceptable-error stable for the general ASF problem, and discuss how iterative refinement can be used to counteract these deficiencies.Dedicated to Carl-Eric Fröberg on the occasion of his 75th birthdayThis research was partially supported by NSERC of Canada Grant No. A9236.     

Low-rank Orthogonal Decompositions for Information Retrieval Applications

Current methods to index and retrieve documents from databases usually depend on a lexical match between query terms and keywords extracted from documents in a database. These methods can produce incomplete or irrelevant results due to the use of synonyms and polysemus words. The association of terms with documents (or implicit semantic structure) can be derived using large sparse {\it term-by-document} matrices. In fact, both terms and documents can be matched with user queries using representations in k-space (where 100 ≤ k ≤ 200) derived from k of the largest approximate singular vectors of these term-by-document matrices. This completely automated approach called latent semantic indexing or LSI, uses subspaces spanned by the approximate singular vectors to encode important associative relationships between terms and documents in k-space. Using LSI, two or more documents may be closeto each other in k-space (and hence meaning) yet share no common terms. The focus of this work is to demonstrate the computational advantages of exploiting low-rank orthogonal decompositions such as the ULV (or URV) as opposed to the truncated singular value decomposition (SVD) for the construction of initial and updated rank-k subspaces arising from LSI applications.     

Fast Kalman Filtering and Forward–Backward Smoothing via a Low-Rank Perturbative Approach

Kalman filtering-smoothing is a fundamental tool in statistical time-series analysis. However, standard implementations of the Kalman filter-smoother require O(d³) time and O(d²) space per time step, where d is the dimension of the state variable, and are therefore impractical in high-dimensional problems. In this article we note that if a relatively small number of observations are available per time step, the Kalman equations may be approximated in terms of a low-rank perturbation of the prior state covariance matrix in the absence of any observations. In many cases this approximation may be computed and updated very efficiently (often in just O(k²d) or O(k²d + kdlog?d) time and space per time step, where k is the rank of the perturbation and in general k ? d), using fast methods from numerical linear algebra. We justify our approach and give bounds on the rank of the perturbation as a function of the desired accuracy. For the case of smoothing, we also quantify the error of our algorithm because of the low-rank approximation and show that it can be made arbitrarily low at the expense of a moderate computational cost. We describe applications involving smoothing of spatiotemporal neuroscience data. This article has online supplementary material.     

Splitting Methods for Convex Clustering

Clustering is a fundamental problem in many scientific applications. Standard methods such as k-means, Gaussian mixture models, and hierarchical clustering, however, are beset by local minima, which are sometimes drastically suboptimal. Recently introduced convex relaxations of k-means and hierarchical clustering shrink cluster centroids toward one another and ensure a unique global minimizer. In this work, we present two splitting methods for solving the convex clustering problem. The first is an instance of the alternating direction method of multipliers (ADMM); the second is an instance of the alternating minimization algorithm (AMA). In contrast to previously considered algorithms, our ADMM and AMA formulations provide simple and unified frameworks for solving the convex clustering problem under the previously studied norms and open the door to potentially novel norms. We demonstrate the performance of our algorithm on both simulated and real data examples. While the differences between the two algorithms appear to be minor on the surface, complexity analysis and numerical experiments show AMA to be significantly more efficient. This article has supplementary materials available online.     

Modifiable low‐rank approximation to a matrix

A truncated ULV decomposition (TULVD) of an m×n matrix X of rank k is a decomposition of the form X = ULV^T+E, where U and V are left orthogonal matrices, L is a k×k non‐singular lower triangular matrix, and E is an error matrix. Only U,V, L, and ∥E∥_F are stored, but E is not stored. We propose algorithms for updating and downdating the TULVD. To construct these modification algorithms, we also use a refinement algorithm based upon that in (SIAM J. Matrix Anal. Appl. 2005; 27 (1):198–211) that reduces ∥E∥_F, detects rank degeneracy, corrects it, and sharpens the approximation. Copyright © 2009 John Wiley & Sons, Ltd.     

Parallelization Strategies for Rollout Algorithms

Rollout algorithms are innovative methods, recently proposed by Bertsekas et al. [3], for solving NP-hard combinatorial optimization problems. The main advantage of these approaches is related to their capability of magnifying the effectiveness of any given heuristic algorithm. However, one of the main limitations of rollout algorithms in solving large-scale problems is represented by their computational complexity. Innovative versions of rollout algorithms, aimed at reducing the computational complexity in sequential environments, have been proposed in our previous work [9]. In this paper, we show that a further reduction can be accomplished by using parallel technologies. Indeed, rollout algorithms have very appealing characteristics that make them suitable for efficient and effective implementations in parallel environments, thus extending their range of relevant practical applications.We propose two strategies for parallelizing rollout algorithms and we analyze their performance by considering a shared-memory paradigm. The computational experiments have been carried out on a SGI Origin 2000 with 8 processors, by considering two classical combinatorial optimization problems. The numerical results show that a good reduction of the execution time can be obtained by exploiting parallel computing systems.     

Modified Gram-Schmidt-based methods for block downdating the Cholesky factorization

The hyperbolic modified Gram-Schmidt (HMGS) method is proposed for block downdating the Cholesky factorization. The method might be unsatisfactory due to rounding errors. A modified version based on the MGS process is presented and is shown to be mixed stable. Numerical tests show that the new method has the same numerical properties as the generalized LINPACK-type algorithm, and can work better than the Householder-based algorithm given by Bojanczyk and Steinhardt (1991) [9].     

Preconditioned Krylov subspace method for the solution of least-squares problems

We consider preconditioned Krylov subspace iteration methods, e.g., CG, LSQR and GMRES, for the solution of large sparse least-squares problems min ∥Ax – b ∥₂, with A ∈ R ^m×n, based on the Krylov subspaces K_k (BA, Br) and K_k (AB, r), respectively, where B ∈ R ^n×m is the preconditioning matrix. More concretely, we propose and implement a class of incomplete QR factorization preconditioners based on the Givens rotations and analyze in detail the efficiency and robustness of the correspondingly preconditioned Krylov subspace iteration methods. A number of numerical experiments are used to further examine their numerical behaviour. It is shown that for both overdetermined and underdetermined least-squares problems, the preconditioned GMRES methods are the best for large, sparse and ill-conditioned matrices in terms of both CPU time and iteration step. Also, comparisons with the diagonal scaling and the RIF preconditioners are given to show the superiority of the newly-proposed GMRES-type methods. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Cut problems in graphs with a budget constraint

We study budgeted variants of classical cut problems: the Multiway Cut problem, the Multicut problem, and the k-Cut problem, and provide approximation algorithms for these problems. Specifically, for the budgeted multiway cut and the k-cut problems we provide constant factor approximation algorithms. We show that the budgeted multicut problem is at least as hard to approximate as the sparsest cut problem, and we provide a bi-criteria approximation algorithm for it.