21 results
Search Results
2. Verifying exactness of relaxations for robust semi-definite programs by solving polynomial systems
- Author
-
Dietz, S.G. and Scherer, C.W.
- Subjects
- *
POLYNOMIALS , *MATHEMATICAL analysis , *ALGORITHMS , *VECTOR spaces - Abstract
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]
- Published
- 2008
- Full Text
- View/download PDF
3. Robustness analysis of preconditioned successive projection algorithm for general form of separable NMF problem.
- Author
-
Mizutani, Tomohiko
- Subjects
- *
ROBUST statistics , *ALGORITHMS , *PROBLEM solving , *MATHEMATICAL analysis , *MATHEMATICAL functions - Abstract
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]
- Published
- 2016
- Full Text
- View/download PDF
4. On the inclusion matrix [formula omitted].
- Author
-
Ahmadi, M.H., Akhlaghinia, N., Khosrovshahi, G.B., and Maysoori, Ch.
- Subjects
- *
MATRICES (Mathematics) , *GAUSSIAN elimination , *ALGORITHMS , *MATHEMATICAL analysis , *CLASSIFICATION - Abstract
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]
- Published
- 2014
- Full Text
- View/download PDF
5. On the higher moments of TCP.
- Author
-
Schlote, A., Wirth, F., Berman, A., and Shorten, R.
- Subjects
- *
STOCHASTIC models , *ALGORITHMS , *TCP/IP , *MATHEMATICAL formulas , *MATHEMATICAL analysis , *NUMERICAL calculations , *AIMD algorithms - Abstract
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]
- Published
- 2013
- Full Text
- View/download PDF
6. Convergence of an algorithm for the largest singular value of a nonnegative rectangular tensor
- Author
-
Zhou, Guanglu, Caccetta, Louis, and Qi, Liqun
- Subjects
- *
STOCHASTIC convergence , *ALGORITHMS , *TENSOR algebra , *ITERATIVE methods (Mathematics) , *SINGULAR value decomposition , *MATHEMATICAL analysis - Abstract
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]
- Published
- 2013
- Full Text
- View/download PDF
7. The reconstruction of a special kind of periodic Jacobi matrices
- Author
-
Xu, Yinghong
- Subjects
- *
PERIODIC functions , *JACOBIAN matrices , *MATRICES (Mathematics) , *INVERSE problems , *NUMERICAL analysis , *ALGORITHMS , *MATHEMATICAL analysis - Abstract
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]
- Published
- 2012
- Full Text
- View/download PDF
8. Structured backward errors for generalized saddle point systems
- Author
-
Chen, Xiao Shan, Li, Wen, Chen, Xiaojun, and Liu, Jun
- Subjects
- *
ERROR analysis in mathematics , *METHOD of steepest descent (Numerical analysis) , *SYMMETRIC matrices , *PERTURBATION theory , *ALGORITHMS , *MATHEMATICAL formulas , *LINEAR algebra , *MATHEMATICAL analysis - Abstract
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]
- Published
- 2012
- Full Text
- View/download PDF
9. Nineteenth century roots of quasideterminants
- Author
-
Abeles, Francine F.
- Subjects
- *
NUMERICAL roots , *DETERMINANTS (Mathematics) , *RECURSION theory , *ALGORITHMS , *MATHEMATICAL analysis , *JACOBIAN matrices - Abstract
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]
- Published
- 2011
- Full Text
- View/download PDF
10. Factoring matrices with a tree-structured sparsity pattern
- Author
-
Druinsky, Alex and Toledo, Sivan
- Subjects
- *
SPARSE matrices , *FACTORIZATION , *TREE graphs , *ALGORITHMS , *MATHEMATICAL analysis , *NUMERICAL analysis - Abstract
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]
- Published
- 2011
- Full Text
- View/download PDF
11. Synthetic boundary conditions for image deblurring
- Author
-
Fan, Ying Wai (Daniel) and Nagy, James G.
- Subjects
- *
IMAGE reconstruction , *APPROXIMATION theory , *ALGORITHMS , *BOUNDARY value problems , *NUMERICAL analysis , *MATHEMATICAL analysis - Abstract
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]
- Published
- 2011
- Full Text
- View/download PDF
12. Some inequalities related to the Seysen measure of a lattice
- Author
-
Maze, Gérard
- Subjects
- *
MATHEMATICAL inequalities , *LATTICE theory , *ALGORITHMS , *GEOMETRIC measure theory , *MATRIX norms , *MATHEMATICAL analysis - Abstract
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]
- Published
- 2010
- Full Text
- View/download PDF
13. A note on “ Completely positive matrices”
- Author
-
Dong, Hongbo and Anstreicher, Kurt
- Subjects
- *
NONNEGATIVE matrices , *MATHEMATICAL transformations , *ALGEBRA , *ALGORITHMS , *MATHEMATICAL programming , *MATHEMATICAL analysis - Abstract
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]
- Published
- 2010
- Full Text
- View/download PDF
14. Face counting on an Acyclic Birkhoff polytope
- Author
-
Costa, Liliana, da Fonseca, C.M., and Martins, Enide Andrade
- Subjects
- *
POLYTOPES , *ALGORITHMS , *CHARTS, diagrams, etc. , *TREE graphs , *MATHEMATICAL analysis - Abstract
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]
- Published
- 2009
- Full Text
- View/download PDF
15. Algorithms for multidimensional spectral factorization and sum of squares
- Author
-
Avelli, D. Napp and Trentelman, H.L.
- Subjects
- *
ALGORITHMS , *LINEAR algebra , *MATHEMATICAL analysis , *DIFFERENTIAL geometry - Abstract
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]
- Published
- 2008
- Full Text
- View/download PDF
16. Sign-solvable linear complementarity problems
- Author
-
Kakimura, Naonori
- Subjects
- *
MATHEMATICAL analysis , *MATHEMATICAL programming , *MATRICES (Mathematics) , *ALGORITHMS - Abstract
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]
- Published
- 2008
- Full Text
- View/download PDF
17. Evaluation of minors associated to weighing matrices
- Author
-
Kravvaritis, Christos and Mitrouli, Marilena
- Subjects
- *
MATRICES (Mathematics) , *ALGORITHMS , *NUMERICAL analysis , *MATHEMATICAL analysis - Abstract
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]
- Published
- 2007
- Full Text
- View/download PDF
18. Orbits and critical components of matrices in max–min algebra
- Author
-
Semančı´ková, Blanka
- Subjects
- *
ALGORITHMS , *ALGEBRA , *MATRICES (Mathematics) , *MATHEMATICAL analysis - Abstract
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]
- Published
- 2007
- Full Text
- View/download PDF
19. A probabilistic algorithm for the secant defect of Grassmann varieties
- Author
-
McGillivray, Barbara
- Subjects
- *
GRASSMANN manifolds , *ALGORITHMS , *MATHEMATICAL optimization , *MATHEMATICAL analysis - Abstract
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]
- Published
- 2006
- Full Text
- View/download PDF
20. The skew-symmetric orthogonal solutions of the matrix equation AX=B
- Author
-
Meng, Chunjun, Hu, Xiyan, and Zhang, Lei
- Subjects
- *
SYMMETRIC matrices , *UNIVERSAL algebra , *ALGORITHMS , *MATHEMATICAL analysis - Abstract
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]
- Published
- 2005
- Full Text
- View/download PDF
21. A note on “Constructing matrices with prescribed off-diagonal submatrix and invariant polynomials”
- Author
-
Borobia, Alberto and Canogar, Roberto
- Subjects
- *
MATRICES (Mathematics) , *POLYNOMIALS , *ALGORITHMS , *MATHEMATICAL analysis - Abstract
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]
- Published
- 2008
- Full Text
- View/download PDF
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.