Search

The Eigendecomposition of quadratic forms (symmetric matrices) guaranteed by the spectral theorem is a foundational result in applied mathematics. Motivated by a shared structure found in inferential problems of recent interest---namely orthogonal tensor decompositions, Independent Component Analysis (ICA), topic models, spectral clustering, and Gaussian mixture learning---we generalize the eigendecomposition from quadratic forms to a broad class of "orthogonally decomposable" functions. We identify a key role of convexity in our extension, and we generalize two traditional characterizations of eigenvectors: First, the eigenvectors of a quadratic form arise from the optima structure of the quadratic form on the sphere. Second, the eigenvectors are the fixed points of the power iteration. In our setting, we consider a simple first order generalization of the power method which we call gradient iteration. It leads to efficient and easily implementable methods for basis recovery. It includes influential Machine Learning methods such as cumulant-based FastICA and the tensor power iteration for orthogonally decomposable tensors as special cases. We provide a complete theoretical analysis of gradient iteration using the structure theory of discrete dynamical systems to show almost sure convergence and fast (super-linear) convergence rates. The analysis also extends to the case when the observed function is only approximately orthogonally decomposable, with bounds that are polynomial in dimension and other relevant parameters, such as perturbation size. Our perturbation results can be considered as a non-linear version of the classical Davis-Kahan theorem for perturbations of eigenvectors of symmetric matrices., 69 pages

We state and prove an analogue of the Daleckii--Krein theorem, thus obtaining an explicit formula for the Frechet derivative of generalized matrix functions. Moreover, we prove the differentiability of generalized matrix functions of real matrices under very mild assumptions. For complex matrices, we argue that, under the same assumptions, generalized matrix functions are real-differentiable but generally not complex-differentiable. Finally, we discuss the application of our results to the study of the condition number of generalized matrix functions. Along our way, we also derive generalized matrix functional analogues of a few classical theorems on polynomial interpolation of classical matrix functions and their derivatives.

Given an arbitrary square matrix $A$, we obtain the leading terms of the asymptotic expansions in the small, real parameter $\varepsilon$ of multiplicative perturbations $\widehat{A}(\varepsilon)=(I+\varepsilon\,B)A(I+\varepsilon\,C)$ of $A$ for arbitrary matrices $B$ and $C$. The analysis is separated into two rather different cases, depending on whether the unperturbed eigenvalue is zero or not. It is shown that in either case the leading exponents are obtained from the partial multiplicities of the eigenvalue of interest, and the leading coefficients generically involve only appropriately normalized left and right eigenvectors of $A$ associated with that eigenvalue, with no need of generalized eigenvectors. Similar results are obtained for multiplicative perturbation of singular values as well.

In this paper, we study the analyticity of the semisimple eigenvalue and the corresponding eigenvector functions of general analytic matrix-valued functions which are very important in many engineering applications such as the optimum design of dynamical structures, model updating, damage detecting, quantum mechanics, diffraction grating theory, medical imaging, and social network theory. We establish some new sufficient conditions on existence of analytic eigenvalue and eigenvector functions corresponding to semisimple eigenvalues of general analytic matrix-valued functions, which relaxes the condition in [P. Lancaster, A. S. Markus, and F. Zhou, SIAM J. Matrix Anal. Appl., 25 (2003), pp. 606--626]. We also present a numerical method to compute the derivatives of the eigenvalue and eigenvector functions. Numerical performance of the method is illustrated by some numerical examples.

A max-plus matrix $A$ is called weakly stable if the sequence (orbit) $x,A\otimes x,A^{2}\otimes x,\ldots$ does not reach an eigenvector of $A$ for any $x$ unless $x$ is an eigenvector. This is in contrast to previously studied strongly stable (robust) matrices for which the orbit reaches an eigenvector with any nontrivial starting vector. Max-plus matrices are used to describe multiprocessor interactive systems for which reachability of a steady regime is equivalent to reachability of an eigenvector by a matrix orbit. We prove that an irreducible matrix is weakly stable if and only if its critical graph is a Hamiltonian cycle in the associated graph. We extend this condition to reducible matrices. These criteria can be checked in polynomial time.

A normalized eigenvector, or, more interestingly, an invariant subspace, is localized if its significant entries are defined by just part(s) of the matrix and negligible elsewhere. This paper presents two new procedures to detect such localization in eigenvectors of a symmetric tridiagonal matrix. The procedures are intended for use before the actual eigenvector computation. If localization is found, one may reduce costs by computing the vectors just from the relevant matrix regions. Practical eigensolvers from numerical libraries such as LAPACK and ScaLAPACK already inspect a given tridiagonal $T$ for off-diagonal entries that are of small magnitude relative to the matrix norm. These so-called splitting points indicate that $T$ breaks into smaller blocks, each one defining a subset of eigenvalues and localized eigenvectors. However, localization can occur even when none of the off-diagonals is particularly small. Our study investigates this more complicated phenomenon in the context of invariant subspaces belonging to isolated eigenvalue clusters.

We present methods to compute verified square roots of a square matrix $A$. Given an approximation $X$ to the square root, obtained by a classical floating point algorithm, we use interval arithmetic to find an interval matrix which is guaranteed to contain the error of $X$. Our approach is based on the Krawczyk method, which we modify in two different ways in such a manner that the computational complexity for an $n\times n$ matrix is reduced to $n^3$. The methods are based on the spectral decomposition or, in the case that the eigenvector matrix is ill conditioned, on a similarity transformation to block diagonal form. Numerical experiments prove that our methods are computationally efficient and that they yield narrow enclosures provided $X$ is a good approximation. This is particularly true for symmetric matrices, since their eigenvector matrix is perfectly conditioned.

A regular network is a network with one kind of node and one kind of coupling. We show that a codimension one bifurcation from a synchronous equilibrium in a regular network is at linear level isomorphic to a generalized eigenspace of the adjacency matrix of the network, at least when the dimension of the internal dynamics of each node is greater than 1. We also introduce the notion of a product network—a network where the nodes of one network are replaced by copies of another network. We show that generically the center subspace of a bifurcation in product networks is the tensor product of eigenspaces of the adjacency matrices of the two networks.

This paper generalizes the well-known identity which relates the last components of the eigenvectors of a symmetric matrix A to the eigenvalues of A and of the matrix An-1, obtained by deleting the last row and column of A. The generalizations relate to matrices and to Sturm--Liouville equations.

This paper shows how the set of nonnegative matrices can be seen as the union of smaller-dimensional sets called slices. For $2\times 2$ matrices a model is drawn and it is shown how the model can be used to study the eigenvector behavior of a perturbed matrix.

We construct a generalization of affine-scaling vector fields for matrix linear programming problems. We discuss various properties of these vector fields and suggest a generalization of a path-following algorithm that is due to C. Gonzaga [SIAM Rev., 34 (1992), pp. 493--513].

Let $M$ be an upper block triangular matrix with $A$ and $B$ singular diagonal blocks. It is known that $\max\{\index (A), \index (B)\} \le \index (M) \le \index (A) + \index (B)$. Recently, a necessary and sufficient condition has been given so that $\index (M) = \index (A) + \index (B)$. In this paper we find various characterizations for $\index (M)$ to take any specific values between $\max\{\index (A), \index (B)\}$ and $\index (A) + \index (B)$ which generalize previous results.

A bounded sesquilinear form, $a( \cdot , \cdot )$, defined on a Hilbert space X is called a weak perturbation of a Hermitian form, $h( \cdot , \cdot )$, if an operator associated with $a( \cdot , \cdot )$ is a weak perturbation, in the sense of Krei˘n, of a selfadjoint operator associated with $h( \cdot , \cdot )$. Under suitable hypotheses on the forms $a( \cdot , \cdot )$ and $h( \cdot , \cdot )$, it is shown that $a( \cdot , \cdot )$ is a weak perturbation of $h( \cdot , \cdot )$. In this case, results of Keldys and Krei˘n on the spectral properties of weakly perturbed selfadjoint operators are applied to the eigenvalue problem, $a(u,v) = \lambda (u,v)$, where $( \cdot , \cdot )$ is the inner product on X. In particular, the completeness in X of the space of generalized eigenvectors and various results on the localization and distribution of eigenvalues are demonstrated. Applications of these results to three different kinds of elliptic differential eigenvalue problems are included. Among these applica...

We obtain solutions for the shape of the free surface on the upper and lower boundaries of an initially rectangular, incompressible linearly viscoelastic block when the block is sheared at the vertical sidewall. To solve the problem when the vertical displacement of the sidewall is prescribed we use biorthogonal series of the Fadle–Papkovich type. The series has a point of novelty in that zero is an algebraically double but geometrically simple eigenvalue. To expand arbitrary vector fields with two components it is necessary to include in the series the proper and generalized eigenvectors belonging to zero.

The properties of the generalized inverse of an arbitrary incidence matrix are examined in connection with the properties of the corresponding directed graph. (Author)

when solutions exist, is possessed by every matrix Ag which satisfies (1). The condition for solutions to exist is AAgy = y and when this is satisfied x = Agy is a particular solution of (5). Ag is a generalized inverse (g.i.) of A. A matrix A' which satisfies (1) and (2) is a reflexive g.i. A matrix A' which satisfies (1), (2) and (3) is a normalized g.i. Aw satisfying (1), (2) and (4) is a weak g.i. while the unique solution At of all four equations is the pseudoinverse or Moore-Penrose inverse. It is the purpose of this note to show that the classification can be made geometrically and that the various forms in which the different inverses can be expressed are given by making suitable choices of base vectors.

We consider the numerical calculation of several matrix eigenvalue problems which require some manipulation before the standard algorithms may be used. This includes finding the stationary values of a quadratic form subject to linear constraints and determining the eigenvalues of a matrix which is modified by a matrix of rank one. We also consider several inverse eigenvalue problems. This includes the problem of determining the coefficients for the Gauss–Radau and Gauss–Lobatto quadrature rules. In addition, we study several eigenvalue problems which arise in least squares.