On lower bounds for singular values of matrix sums

It is pointed out by a counterexample that the result on lower bounds for the absolute singular values of sum of matrices given in [1] is not valid. Moreover, in this note a new result is established on such lower bounds.     

Equality conditions for lower bounds on the smallest singular value of a bidiagonal matrix

Several lower bounds have been proposed for the smallest singular value of a square matrix, such as Johnson’s bound, Brauer-type bound, Li’s bound and Ostrowski-type bound. In this paper, we focus on a bidiagonal matrix and investigate the equality conditions for these bounds. We show that the former three bounds give strict lower bounds if all the bidiagonal elements are non-zero. For the Ostrowski-type bound, we present an easily verifiable necessary and sufficient condition for the equality to hold.     

On choices of formulations of computing the generalized singular value decomposition of a large matrix pair

For the computation of the generalized singular value decomposition (GSVD) of a large matrix pair (A,B) of full column rank, the GSVD is commonly formulated as two mathematically equivalent generalized eigenvalue problems, so that a generalized eigensolver can be applied to one of them and the desired GSVD components are then recovered from the computed generalized eigenpairs. Our concern in this paper is, in finite precision arithmetic, which generalized eigenvalue formulation is numerically preferable to compute the desired GSVD components more accurately. We make a detailed perturbation analysis on the two formulations and show how to make a suitable choice between them. Numerical experiments illustrate the results obtained.

     

On efficient implementations of Kogbetliantz's algorithm for computing the singular value decomposition

Summary In this paper we compare several implementations of Kogbetliantz's algorithm for computing the SVD on sequential as well as on parallel machines. Comparisons are based on timings and on operation counts. The numerical accuracy of the different methods is also analyzed.     

On the quadratic convergence of Kogbetliantz's algorithm for computing the singular value decomposition

It is shown that the cyclic Kogbetliantz algorithm ultimately converges quadratically when no pathologically close singular values are present.     

Superquadratic convergence of DLASQ for computing matrix singular values

DLASQ is a routine in LAPACK for computing the singular values of a real upper bidiagonal matrix with high accuracy. The basic algorithm, the so-called dqds algorithm, was first presented by Fernando-Parlett, and implemented as the DLASQ routine by Parlett-Marques. DLASQ is now recognized as one of the most efficient routines for computing singular values. In this paper, we prove the asymptotic superquadratic convergence of DLASQ in exact arithmetic.     

An algorithm for computing the spectral structure of a singular linear matrix pencil

An algorithm is proposed for computing the structure of the Kronecker canonical form for a singular linear matrix pencil. Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Institute im. V. A. Steklova AN SSSR, Vol. 159, pp. 23–32, 1987.     

A lower bound for the smallest singular value of a matrix

For a matrix A which is diagonally dominant both by rows and by columns, we give bounds for 6A^-16₁ and 6A^-16_∞, which then can be used to give a lower bound for the smallest singular value. We also show that these bounds can be attained, and show how the result can be extended to block matrices.     

Differential equations for the analytic singular value decomposition of a matrix

Summary This paper is concerned with finding a smooth singular value decomposition for a matrix which is smoothly dependent on a parameter. A previous approach to this problem was based on minimisation techniques, here, in contrast, a system of ordinary differential equations is derived for the decomposition. It is shown that the numerical solution of an initial value problem associated with these differential equations provides a feasible approach to the solution of this problem. Particular consideration is given to the situation which arises with equal modulus singular values which lead to indeterminacies in the evaluations needed for the numerical solution. Examples which illustrate the behaviour of the method are included.     

An algorithm for a least absolute value regression problem with bounds on the parameters

This paper presents a special purpose linear programming algorithm to solve a least absolute value regression problem with upper and lower bounds on the parameters. The algorithm exploits the problem's special structure by maintaining a compact representation of the basis inverse and by allowing for the capability to combine several simplex iterations into one. Computational results with a computer code implementation of the algorithm are given.     

Smallest singular value of a random rectangular matrix

We prove an optimal estimate of the smallest singular value of a random sub‐Gaussian matrix, valid for all dimensions. For an N × n matrix A with independent and identically distributed sub‐Gaussian entries, the smallest singular value of A is at least of the order √N ? √n ? 1 with high probability. A sharp estimate on the probability is also obtained. © 2009 Wiley Periodicals, Inc.     

An Optimization algorithm computing the maximal singular number of a real matrix

The problem of calculating the maximal singular number of a given real matrix is considered. The existing solution methods are briefly surveyed. A new optimization-type algorithm for computing the maximal singular number is suggested and substantiated. Its rate of convergence is proved to be linear. A relationship between the row sums of the matrix and one of its singular numbers is established, and new localization theorems are proved. It is shown how the suggested algorithm is related to the Relay relation relaxation method. Exceptional situations in which the algorithm converges to a non-maximal singular number are described. A computational trick for avoiding such situations with fairly high reliability is suggested.     

Perturbation bounds in connection with singular value decomposition

LetA be anm ×n-matrix which is slightly perturbed. In this paper we will derive an estimate of how much the invariant subspaces ofA ^H A andAA ^H will then be affected. These bounds have the sin theorem for Hermitian linear operators in Davis and Kahan [1] as a special case. They are applicable to computational solution of overdetermined systems of linear equations and especially cover the rank deficient case when the matrix is replaced by one of lower rank.     

On the invertibility of a nearly singular matrix

Let z be a complex variable and let A and B be constant n × n matrices with complex elements. It is shown that A + zB is invertible for all z in a deleted neighborhood of zero if and only if there exist constant n × n matrices such that XA + YB = I and AX + BY = I. A related result is the alternate necessary and sufficient condition that there exist constant X, Y such that XA + YB = I, YAXB = XBYA = 0 and YA is nilpotent.     

An efficient and reliable algorithm for computing the singular subspace of a matrix,associated with its smallest singular values

In this paper, an improved algorithm PSVD for computing the singular subspace of a matrix corresponding to its smallest singular values is presented. As only a basis of the desired singular subspace is needed, the classical Singular Value Decomposition (SVD) algorithm can be modified in three ways. First, the Householder transformations of the bidiagonalization need only to be applied on the base vectors of the desired singular subspace. Second, the bidiagonal must only be partially diagonalized and third, the convergence rate of the iterative diagonalization can be improved by an appropriate choice between QR and QL iteration steps. An analysis of the operation counts, as well as computational results, show the relative efficiency of PSVD with respect to the classical SVD algorithm. Depending on the gap, the desired numerical accuracy and the dimension of the desired subspace, PSVD can be three times faster than the classical SVD algorithm while the same accuracy can be maintained. The new algorithm can be successfully used in total least squares applications, in the computation of the null space of a matrix and in solving (non) homogeneous linear equations. Based on PSVD a very efficient and reliable algorithm is also derived for solving nonhomogeneous equations.     

On optimal backward perturbation bounds for the linear least squares problem

Consider the linear least squares problem min _x ‖b?Ax‖₂ whereA is anm×n (m<n) matrix, andb is anm-dimensional vector. Lety be ann-dimensional vector, and let ηls(y) be the optimal backward perturbation bound defined by $$\eta _{LS} (y) = \inf \{ ||F||_F :y is a solution to \mathop {min}\limits_x ||b - (A + F)x||_2 \} .$$ . An explicit expression of ηls(y) (y≠0) has been given in [8]. However, if we define the optimal backward perturbation bounds ηmls(y) by $$\eta _{MLS} (y) = \inf \{ ||F||_F :y is the minimum 2 - norm solution to \mathop {min}\limits_x ||b - (A + F)x||_2 \} ,$$ , it may well be asked: How to derive an explicit expression of ηmls(y)? This note gives an answer. The main result is: Ifb≠0 andy≠0, then ηmls(y)=ηls (y).     

Integral methods for computing solutions of a class of singular two-point boundary value problems

In this paper, we establish three iteration methods to compute solutions for a class of (weakly) singular two-point boundary value problems (xy^′)^′=f(x,y), where x(0,1) and <2. We obtain the sufficient conditions for existence of a unique solution on . Finally, we given some numerical examples.