Newton's method for the common eigenvector problem

In El Ghazi et al. [Backward error for the common eigenvector problem, CERFACS Report TR/PA/06/16, Toulouse, France, 2006], we have proved the sensitivity of computing the common eigenvector of two matrices A and B, and we have designed a new approach to solve this problem based on the notion of the backward error.If one of the two matrices (saying A) has n eigenvectors then to find the common eigenvector we have just to write the matrix B in the basis formed by the eigenvectors of A. But if there is eigenvectors with multiplicity >1, the common vector belong to vector space of dimension >1 and such strategy would not help compute it.In this paper we use Newton's method to compute a common eigenvector for two matrices, taking the backward error as a stopping criteria.We mention that no assumptions are made on the matrices A and B.     

Optimal long-time $L_p}(0,T)$ stability and semidiscrete error estimates for the Volterra formulation of the linear quasistatic viscoelasticity problem

The purpose of this article is to show how the solution of the linear quasistatic (compressible) viscoelasticity problem, written in Volterra form with fading memory, may be sharply bounded in terms of the data if certain physically reasonable assumptions are satisfied. The bounds are derived by making precise assumptions on the memory term which then make it possible to avoid the Gronwall inequality, and use instead a comparison theorem which is more sensitive to the physics of the problem. Once the data-stability estimates are established we apply the technique also to deriving a priori error bounds for semidiscrete finite element approximations. Our bounds are derived for viscoelastic solids and fluids under the small strain assumption in terms of the eigenvalues of a certain matrix derived from the stress relaxation tensor. For isotropic materials we can be explicit about the form of these bounds, while for the general case we give a formula for their computation.     

COMPUTING EIGENVECTORS OF NORMAL MATRICES WITH SIMPLE INVERSE ITERATION

It is well-known that if we have an approximate eigenvalue λ- of a normal matrix A of order n,a good approximation to the corresponding eigenvector u can be computed by one inverse iteration provided the position,say kmax,of the largest component of u is known.In this paper we give a detailed theoretical analysis to show relations between the eigenvecor u and vector xk,k=1,…,n,obtained by simple inverse iteration,i.e.,the solution to the system(A-λI)x=ek with ek the kth column of the identity matrix I.We prove that under some weak conditions,the index kmax is of some optimal properties related to the smallest residual and smallest approximation error to u in spectral norm and Frobenius norm.We also prove that the normalized absolute vector v=|u|/||u||∞ of u can be approximated by the normalized vector of (||x1||2,…||xn||2)^T,We also give some upper bounds of |u(k)| for those “optimal“ indexeds such as Fernando‘s heuristic for kmax without any assumptions,A stable double orthogonal factorization method and a simpler but may less stable approach are proposed for locating the largest component of u.     

Error bounds for 2-regular mappings with Lipschitzian derivatives and their applications

We obtain local estimates of the distance to a set defined by equality constraints under assumptions which are weaker than those previously used in the literature. Specifically, we assume that the constraints mapping has a Lipschitzian derivative, and satisfies a certain 2-regularity condition at the point under consideration. This setting directly subsumes the classical regular case and the twice differentiable 2-regular case, for which error bounds are known, but it is significantly richer than either of these two cases. When applied to a certain equation-based reformulation of the nonlinear complementarity problem, our results yield an error bound under an assumption more general than b-regularity. The latter appears to be the weakest assumption under which a local error bound for complementarity problems was previously available. We also discuss an application of our results to the convergence rate analysis of the exterior penalty method for solving irregular problems. Received: February 2000 / Accepted: November 2000?Published online January 17, 2001     

Verified error bounds for eigenvalues of geometric multiplicity <Emphasis Type="Italic">q</Emphasis> and corresponding invariant subspaces

In this paper, we generalize the algorithm described by Rump and Graillat to compute verified and narrow error bounds such that a slightly perturbed matrix is guaranteed to have an eigenvalue with geometric multiplicity q within computed error bounds. The corresponding invariant subspace can be directly obtained by our algorithm. Our verification method is based on border matrix technique. We demonstrate the performance of our algorithm for matrices of dimension up to hundreds with non-defective and defective eigenvalues.     

On the extraction of weights from pairwise comparison matrices

We study properties of weight extraction methods for pairwise comparison matrices that minimize suitable measures of inconsistency, ‘average error gravity’ measures, including one that leads to the geometric row means. The measures share essential global properties with the AHP inconsistency measure. By embedding the geometric mean in a larger class of methods we shed light on the choice between it and its traditional AHP competitor, the principal right eigenvector. We also suggest how to assess the extent of inconsistency by developing an alternative to the Random Consistency Index, which is not based on random comparison matrices, but based on judgemental error distributions. We define and discuss natural invariance requirements and show that the minimizers of average error gravity generally satisfy them, except a requirement regarding the order in which matrices and weights are synthesized. Only the geometric row mean satisfies this requirement also. For weight extraction we recommend the geometric mean.     

Curvature notions on graphs

We survey some geometric and analytic results under the assumptions of combinatorial curvature bounds for planar/semiplanar graphs and curvature dimension conditions for general graphs.     

Bounds for geometric sums used for evaluation of reliability of regenerative models

The lifetime of a large repairable system can be decomposed into two parts. The first one is the cumulative time spent in the perfect state (all components are operating), and the second one is the restoration time when some components have failed. For highly reliable systems, the first time is close to the system lifetime, and it turns out that this approximation is accurate in many practical cases. Nevertheless, it is important to evaluate the error of such an approximation. Some bounds exist if each component has a constant failure rate. In this paper, using estimates of geometric sums, we get bounds for the general case. Proceedings of the Seminar on Stability Problems for Stochastic Models, Hajdúszoboszló, Hungary, 1997, Part III.     

Adiabatic approximation for the evolution generated by an <Emphasis Type="Italic">A</Emphasis>-uniformly pseudo-Hermitian Hamiltonian

We discuss an adiabatic approximation for the evolution generated by an A-uniformly pseudo-Hermitian Hamiltonian H(t). Such a Hamiltonian is a time-dependent operator H(t) similar to a time-dependent Hermitian Hamiltonian G(t) under a time-independent invertible operator A. Using the relation between the solutions of the evolution equations H(t) and G(t), we prove that H(t) and H^? (t) have the same real eigenvalues and the corresponding eigenvectors form two biorthogonal Riesz bases for the state space. For the adiabatic approximate solution in case of the minimum eigenvalue and the ground state of the operator H(t), we prove that this solution coincides with the system state at every instant if and only if the ground eigenvector is time-independent. We also find two upper bounds for the adiabatic approximation error in terms of the norm distance and in terms of the generalized fidelity. We illustrate the obtained results with several examples.     

Eigenvalue perturbation bounds for Hermitian block tridiagonal matrices

We derive new perturbation bounds for eigenvalues of Hermitian matrices with block tridiagonal structure. The main message of this paper is that an eigenvalue is insensitive to blockwise perturbation, if it is well-separated from the spectrum of the diagonal blocks nearby the perturbed blocks. Our bound is particularly effective when the matrix is block-diagonally dominant and graded. Our approach is to obtain eigenvalue bounds via bounding eigenvector components, which is based on the observation that an eigenvalue is insensitive to componentwise perturbation if the corresponding eigenvector components are small. We use the same idea to explain two well-known phenomena, one concerning aggressive early deflation used in the symmetric tridiagonal QR algorithm and the other concerning the extremal eigenvalues of Wilkinson matrices.     

Estimating a largest eigenvector by Lanczos and polynomial algorithms with a random start

We study Lanczos and polynomial algorithms with random start for estimating an eigenvector corresponding to the largest eigenvalue of an n × n large symmetric positive definite matrix. We analyze the two error criteria: the randomized error and the randomized residual error. For the randomized error, we prove that it is not possible to get distribution-free bounds, i.e., the bounds must depend on the distribution of eigenvalues of the matrix. We supply such bounds and show that they depend on the ratio of the two largest eigenvalues. For the randomized residual error, distribution-free bounds exist and are provided in the paper. We also provide asymptotic bounds, as well as bounds depending on the ratio of the two largest eigenvalues. The bounds for the Lanczos algorithm may be helpful in a practical implementation and termination of this algorithm. © 1998 John Wiley & Sons, Ltd.     

Backward errors for eigenvalue and singular value decompositions

Summary. We present bounds on the backward errors for the symmetric eigenvalue decomposition and the singular value decomposition in the two-norm and in the Frobenius norm. Through different orthogonal decompositions of the computed eigenvectors we can define different symmetric backward errors for the eigenvalue decomposition. When the computed eigenvectors have a small residual and are close to orthonormal then all backward errors tend to be small. Consequently it does not matter how exactly a backward error is defined and how exactly residual and deviation from orthogonality are measured. Analogous results hold for the singular vectors. We indicate the effect of our error bounds on implementations for eigenvector and singular vector computation. In a more general context we prove that the distance of an appropriately scaled matrix to its orthogonal QR factor is not much larger than its distance to the closest orthogonal matrix. Received July 19, 1993     

Tight global linear convergence rate bounds for Douglas–Rachford splitting

Recently, several authors have shown local and global convergence rate results for Douglas–Rachford splitting under strong monotonicity, Lipschitz continuity, and cocoercivity assumptions. Most of these focus on the convex optimization setting. In the more general monotone inclusion setting, Lions and Mercier showed a linear convergence rate bound under the assumption that one of the two operators is strongly monotone and Lipschitz continuous. We show that this bound is not tight, meaning that no problem from the considered class converges exactly with that rate. In this paper, we present tight global linear convergence rate bounds for that class of problems. We also provide tight linear convergence rate bounds under the assumptions that one of the operators is strongly monotone and cocoercive, and that one of the operators is strongly monotone and the other is cocoercive. All our linear convergence results are obtained by proving the stronger property that the Douglas–Rachford operator is contractive.     

一类算子矩阵特征值的代数指标和代数重数

自伴算子特征值的几何重数与代数重数相等,但对于非自伴算子不一定成立,这主要是特征值的代数指标起着决定性的作用.讨论了一类非自伴算子矩阵特征值的几何重数,代数指标与代数重数.     

Error for the modified secant method

New error bounds for the modified secant method are provided. We show that our error estimates are better than the ones already existing in the literature, under similar assumptions.     

Embeddings of Riemannian manifolds with finite eigenvector fields of connection Laplacian

We study the problem asking if one can embed manifolds into finite dimensional Euclidean spaces by taking finite number of eigenvector fields of the connection Laplacian. This problem is essential for the dimension reduction problem in manifold learning. In this paper, we provide a positive answer to the problem. Specifically, we use eigenvector fields to construct local coordinate charts with low distortion, and show that the distortion constants depend only on geometric properties of manifolds with metrics in the little Hölder space \(c^{2,\alpha }\). Next, we use the coordinate charts to embed the entire manifold into a finite dimensional Euclidean space. The proof of the results relies on solving the elliptic system and providing estimates for eigenvector fields and the heat kernel and their gradients. We also provide approximation results for eigenvector field under the \(c^{2,\alpha }\) perturbation.     

在常规故障条件下具有易损坏储备部件可修复系统的稳定性分析

讨论了在常规故障条件下具有易损坏储备部件可修复系统的渐进稳定性;证明了系统非负稳定解恰是系统算子0本征值对应的本征向量;系统算子的谱点均位于复平面的左半平面,且在虚轴上除0外无谱点;此外,证明了0的代数重数为1和求解了系统算子的共轭算子.     

Obtaining fast error rates in nonconvex situations

We show that under mild assumptions on the learning problem, one can obtain a fast error rate for every reasonable fixed target function even if the base class is not convex. To that end, we show that in such cases the excess loss class satisfies a Bernstein type condition.     

A convergence analysis of the iterative aggregation method with one parameter

A method for accelerating linear iterations in a Banach space is studied as a linear iterative method in an augmented space, and sufficient conditions for convergence are derived in the general case and in ordered Banach spaces. An acceleration of convergence takes place if an auxiliary functional is chosen sufficiently close to a dual eigenvector associated with a dominant simple eigenvalue of the iteration operator; in this case, the influence of this eigenvalue on the asymptotic rate of convergence is eliminated. Quantitative estimates and bounds on convergence are given.     

Parallel Algorithms and Probability of Large Deviation for Stochastic Convex Optimization Problems

We consider convex stochastic optimization problems under different assumptions on the properties of available stochastic subgradient. It is known that, if the value of the objective function is available, one can obtain, in parallel, several independent approximate solutions in terms of the objective residual expectation. Then, choosing the solution with the minimum function value, one can control the probability of large deviation of the objective residual. On the contrary, in this short paper, we address the situation, when the value of the objective function is unavailable or is too expensive to calculate. Under "‘light-tail"’ assumption for stochastic subgradient and in general case with moderate large deviation probability, we show that parallelization combined with averaging gives bounds for probability of large deviation similar to a serial method. Thus, in these cases, one can benefit from parallel computations and reduce the computational time without loss in the solution quality.