Search

Abstract: In this paper, robust semi-definite programs are considered with the goal of verifying whether a particular LMI relaxation is exact. A procedure is presented showing that verifying exactness amounts to solving a polynomial system. The main contribution of the paper is a new algorithm to compute all isolated solutions of a system of polynomials. Standard techniques in computational algebra, often referred to as Stetter’s method [H.J. Stetter, Numerical Polynomial Algebra, SIAM, 2004], involve the computation of a Gröbner basis of the ideal generated by the polynomials and further require joint eigenvector computations in order to arrive at the zeros of the polynomial system. Our algorithm does neither require structural knowledge on the polynomial system, nor does it rely on the computation of joint eigenvectors. [Copyright &y& Elsevier]

Abstract: In this paper, we give necessary and sufficient conditions for a set of Jordan blocks to correspond to the peripheral spectrum of a nonnegative matrix. For each eigenvalue, , the -level characteristic (with respect to the spectral radius) is defined. The necessary and sufficient conditions include a requirement that the -level characteristic is majorized by the -height characteristic. An algorithm which has been implemented in MATLAB is given to determine when a multiset of Jordan blocks corresponds to the peripheral spectrum of a nonnegative matrix. The algorithm is based on the necessary and sufficient conditions given in this paper. [Copyright &y& Elsevier]

The successive projection algorithm (SPA) has been known to work well for separable nonnegative matrix factorization (NMF) problems arising in applications, such as topic extraction from documents and endmember detection in hyperspectral images. One of the reasons is in that the algorithm is robust to noise. Gillis and Vavasis showed in [8] that a preconditioner can further enhance its noise robustness. The proof rested on the condition that the dimension d and factorization rank r in the separable NMF problem coincide with each other. However, it may be unrealistic to expect that the condition holds in separable NMF problems appearing in actual applications; in such problems, d is usually greater than r . This paper shows, without the condition d = r , that the preconditioned SPA is robust to noise. [ABSTRACT FROM AUTHOR]

For a v -set X , W 23 ( v ) is a ( v 2 ) × ( v 3 ) inclusion matrix where rows and columns are indexed by pairs and triples of X , respectively, and for row T and column K , W 23 ( v ) ( T , K ) = 1 if T ⊆ K and zero otherwise. In this paper, we classify the basis elements of the null Z ( W 23 ( v ) ) , derived from the Gaussian elimination on W 23 ( v ) (called standard basis), into five classes. Then, we present a new algorithm to construct a ( 2 , 3 , v ) -halving for a feasible v , i.e. a nowhere zero T ( 2 , 3 , v ) -trade. [ABSTRACT FROM AUTHOR]

Abstract: In this paper we describe the moments of a stochastic model of the Additive Increase Multiplicative Decrease (AIMD) algorithm. AIMD is the algorithm that underpins the Transmission Control Protocol (TCP), which is used extensively in the internet. We prove that the Markov chain describing TCP has the remarkable property that all moments converge to their asymptotes at exactly the same rate. Further, we illustrate how a closed form solution can be obtained from the network properties, and this formula is explicitly calculated for the case of the third moment. [Copyright &y& Elsevier]

Abstract: In this paper, we present an iterative algorithm for computing the largest singular value of a nonnegative rectangular tensor. We establish the convergence of this algorithm for any irreducible nonnegative rectangular tensor. [Copyright &y& Elsevier]

Abstract: In this paper, we investigate the properties of a special kind of periodic Jacobi matrices. We show that the solution of the inverse problem for periodic Jacobi matrices is unique if and only if the matrix is of that special kind. Moreover, we present an algorithm to construct the solution of that inverse problem and give some illustrative examples. Finally, we perform a stability analysis of the algorithm. [Copyright &y& Elsevier]

Abstract: In this paper we investigate structured backward errors for three kinds of generalized saddle point systems where the matrix is not symmetric and its block is not zero and has perturbations. Computable formula of backward errors are derived. The expressions are useful for testing the stability of practical algorithms. [Copyright &y& Elsevier]

Abstract: In this expository paper I provide a complete record of the nineteenth century publications that bear on the development of quasideterminants in the twentieth century. Two important recursive feasible algorithms, Sylvester’s from 1851 and Dodgson’s from 1866 are discussed, and the antecedents of both are traced back to work by Jacobi. [Copyright &y& Elsevier]

Abstract: Let A be a matrix whose sparsity pattern is a tree with maximal degree . We show that if the columns of A are ordered using minimum degree on , then factoring A using a sparse LU with partial pivoting algorithm generates only fill, requires only operations, and is much more stable than LU with partial pivoting on a general matrix. We also propose an even more efficient and just-as-stable algorithm called sibling-dominant pivoting. This algorithm is a strict partial pivoting algorithm that modifies the column preordering locally to minimize fill and work. It leads to only O(n) work and fill. More conventional column pre-ordering methods that are based (usually implicitly) on the sparsity pattern of are not as efficient as the approaches that we propose in this paper. [Copyright &y& Elsevier]

Abstract: In this paper we introduce a new boundary condition that can be used when reconstructing an image from observed blurred and noisy data. Our approach uses information from the observed image to enforce boundary conditions that continue image features such as edges and texture across the boundary. Because of its similarity to methods used in texture synthesis, we call our approach synthetic boundary conditions. We provide an efficient algorithm for implementing the new boundary condition, and provide a linear algebraic framework for the approach that puts it in the context of more classical and well known image boundary conditions, including zero, periodic, reflective, and anti-reflective. Extensive numerical experiments show that our new synthetic boundary conditions provide a more accurate approximation of the true image scene outside the image boundary, and thus allow for better reconstructions of the unknown, true image scene. [Copyright &y& Elsevier]

Abstract: Given a lattice L, a basis B of L together with its dual , the orthogonality measure of B was introduced by Seysen (1993) . This measure (the Seysen measure in the sequel, also known as the Seysen metric) is at the heart of the Seysen lattice reduction algorithm and is linked with different geometrical properties of the basis . In this paper, we derive different expressions for this measure as well as new inequalities related to the Frobenius norm and the condition number of a matrix. [Copyright &y& Elsevier]

Abstract: In their paper “ Completely positive matrices”, Berman and Xu (2004) attempt to characterize which doubly nonnegative matrices are also completely positive. Most of the analysis in concerns a doubly nonnegative matrix A that has at least one off-diagonal zero component. To handle the case where A is componentwise strictly positive, Berman and Xu utilize an “edge-deletion” transformation of A that results in a matrix having an off-diagonal zero. Berman and Xu claim that A is completely positive if and only if there is such an edge-deleted matrix that is also completely positive. We show that this claim is false. We also show that two conjectures made in regarding completely positive matrices are both false. [Copyright &y& Elsevier]

Abstract: In this paper we present some algorithms allowing an exhaustive account on the number of edges and faces of the acyclic Birkhoff polytope. [Copyright &y& Elsevier]

Abstract: In this paper, algorithms are developed for the problems of spectral factorization and sum of squares of polynomial matrices with n indeterminates, and a natural interpretation of the tools employed in the algorithms is given using ideas from the theory of lossless and dissipative systems. These algorithms are based on the calculus of 2n-variable polynomial matrices and their associated quadratic differential forms, and share the common feature that the problems are lifted from the original n-variable polynomial context to a 2n-variable polynomial context. This allows to reduce the spectral factorization problem and the sum of squares problem to linear matrix inequalities (LMI’s), to the feasibility of a semialgebraic set or to a linear eigenvalue problem. [Copyright &y& Elsevier]

Abstract: This paper presents a connection between qualitative matrix theory and linear complementarity problems (LCPs). An LCP is said to be sign-solvable if the set of the sign patterns of the solutions is uniquely determined by the sign patterns of the given coefficients. We provide a characterization for sign-solvable LCPs such that the coefficient matrix has nonzero diagonals, which can be tested in polynomial time. This characterization leads to an efficient combinatorial algorithm to find the sign pattern of a solution for these LCPs. The algorithm runs in time, where is the number of the nonzero coefficients. [Copyright &y& Elsevier]

Abstract: In the present paper we focus our research on calculating minors of weighing matrices of order n and weight n − k, denoted by W(n, n − k). We provide analytical determinant computations, counting techniques for specifying the existence of certain submatrices inside a W(n, n − k) and an algorithm for computing the (n − j)×(n − j) minors of a W(n, n − k), which is realized with the notion of symbolic manipulation. These results are valid of general n. The ideas presented in this work can be used as the fundamental basis, on which the calculation of minors of other weighing matrices, and in general of orthogonal matrices, can be developed. An application of the derived formulas to an interesting problem of Numerical Analysis, the growth problem, is also presented. [Copyright &y& Elsevier]

Abstract: A speed-up of a known O(n 3) algorithm computing the period of a periodic orbit in max–min algebra is presented. If the critical components (or the transitive closure A +) of the transition matrix A are known, the computational complexity of the algorithm is O(n 2). This is achieved by using only those coordinates of the orbit that are related to the critical components. On the other hand, no critical component can be omitted. As the critical components are pairwise disjoint, the new formula is helpful also in solving the converse problem: generating an orbit with a prescribed period. This is demonstrated by examples. All parts of the paper are connected with the fact that the periodic regime of an orbit is encoded in its critical coordinates. We show that the non-critical coordinates of the state vector after n −1 steps can be ignored, how to generate a known periodic regime by using a small number of coordinates of the state vector and that the difference between the defect of an orbit and the quasidefect of its critical coordinates is small. The final part deals with the situation when the matrix is reduced after the orbit has reached its periodic regime. [Copyright &y& Elsevier]

Abstract: In this paper we study the higher secant varieties of Grassmann varieties in relation to the functional Waring’s problem for alternating tensors and to the Alexander–Hirschowitz theorem. We show how to identify defective higher secant varieties of Grassmannians using a probabilistic method involving Terracini’s lemma, and we describe an algorithm which can compute, by numerical methods, dim (S s G(k, n)) for n ⩽14. Our main result is that, except for Grassmannians of lines, if n ⩽14 and (if n =14 we have studied the case k ⩽5) there are only the four known defective cases: S 2 G(2,6), S 2 G(3,7), S 3 G(3,7) and S 3 G(2,8). [Copyright &y& Elsevier]

Abstract: An n×n real matrix X is said to be a skew-symmetric orthogonal matrix if XT=−X and XTX=I. Using the special form of the C–S decomposition of an orthogonal matrix with skew-symmetric k×k leading principal submatrix, this paper establishes the necessary and sufficient conditions for the existence of and the expressions for the skew-symmetric orthogonal solutions of the matrix equation AX=B. In addition, in corresponding solution set of the equation, the explicit expression of the nearest matrix to a given matrix in the Frobenius norm have been provided. Furthermore, the Procrustes problem of skew-symmetric orthogonal matrices is considered and the formula solutions are provided. Finally an algorithm is proposed for solving the first and third problems. Numerical experiments show that it is feasible. [Copyright &y& Elsevier]

Abstract: Let be any field and let B a matrix of . Zaballa found necessary and sufficient conditions for the existence of a matrix with prescribed similarity class and such that . In an earlier paper [A. Borobia, R. Canogar, Constructing matrices with prescribed off-diagonal submatrix and invariant polynomials, Linear Algebra Appl. 424 (2007) 615–633] we obtained, for fields of characteristic different from 2, a finite step algorithm to construct A when it exists. In this short note we extend the algorithm to any field. [Copyright &y& Elsevier]