Least-Squares Solution of Inverse Problem for Hermitian Anti-reflexive Matrices and Its Appoximation

In this paper, we first consider the least-squares solution of the matrix inverse problem as follows： Find a hermitian anti-reflexive matrix corresponding to a given generalized reflection matrix J such that for given matrices X, B we have minA ｜｜AX - B｜｜. The existence theorems are obtained, and a general representation of such a matrix is presented. We denote the set of such matrices by SE. Then the matrix nearness problem for the matrix inverse problem is discussed. That is： Given an arbitrary A^＊, find a matrix A E SE which is nearest to A^＊ in Frobenius norm. We show that the nearest matrix is unique and provide an expression for this nearest matrix.     

Positive definite matrix approximation with condition number constraint

Positive definite matrix approximation with a condition number constraint is an optimization problem to find the nearest positive definite matrix whose condition number is smaller than a given constant. We demonstrate that this problem can be converted to a simpler one when we use a unitary similarity invariant norm as a metric. We can especially convert it to a univariate piecewise convex optimization problem when we use the Ky Fan p-k norm. We also present an analytical solution to the problem whose metric is the spectral norm and the trace norm.     

Computing the nearest Euclidean distance matrix with low embedding dimensions

Euclidean distance embedding appears in many high-profile applications including wireless sensor network localization, where not all pairwise distances among sensors are known or accurate. The classical Multi-Dimensional Scaling (cMDS) generally works well when the partial or contaminated Euclidean Distance Matrix (EDM) is close to the true EDM, but otherwise performs poorly. A natural step preceding cMDS would be to calculate the nearest EDM to the known matrix. A crucial condition on the desired nearest EDM is for it to have a low embedding dimension and this makes the problem nonconvex. There exists a large body of publications that deal with this problem. Some try to solve the problem directly and some are the type of convex relaxations of it. In this paper, we propose a numerical method that aims to solve this problem directly. Our method is strongly motivated by the majorized penalty method of Gao and Sun for low-rank positive semi-definite matrix optimization problems. The basic geometric object in our study is the set of EDMs having a low embedding dimension. We establish a zero duality gap result between the problem and its Lagrangian dual problem, which also motivates the majorization approach adopted. Numerical results show that the method works well for the Euclidean embedding of Network coordinate systems and for a class of problems in large scale sensor network localization and molecular conformation.     

A note on the m-center problem with rectilinear distances

Given n demand points on a plane, the problem we consider is to locate a given number, m, of facilities on the plane so that the maximum of the set of rectilinear distances of each demand point to its nearest facility is minimized. This problem is known as the m-center problem on the plane. A related problem seeks to determine, for a given r, the minimum number of facilities and their locations so as to ensure that every point is within r units of rectilinear distance from its nearest facility. We formulate the latter problem as a problem of covering nodes by cliques of an intersection graph. Certain bounds are established on the size of the problem. An efficient algorithm is provided to generate this set-covering problem. Computational results with this approach are summarized.     

A minimum norm approach for low-rank approximations of a matrix

The problems of calculating a dominant eigenvector or a dominant pair of singular vectors, arise in several large scale matrix computations. In this paper we propose a minimum norm approach for solving these problems. Given a matrix, A, the new method computes a rank-one matrix that is nearest to A, regarding the Frobenius matrix norm. This formulation paves the way for effective minimization techniques. The methods proposed in this paper illustrate the usefulness of this idea. The basic iteration is similar to that of the power method, but the rate of convergence is considerably faster. Numerical experiments are included.     

On the low rank solution of the Q‐weighted nearest correlation matrix problem

The low rank solution of the Q‐weighted nearest correlation matrix problem is studied in this paper. Based on the property of Q‐weighted norm and the Gramian representation, we first reformulate the Q‐weighted nearest correlation matrix problem as a minimization problem of the trace function with quadratic constraints and then prove that the solution of the minimization problem the trace function is the stationary point of the original problem if it is rank‐deficient. Finally, the nonmonotone spectral projected gradient method is constructed to solve them. Numerical examples illustrate that the new method is feasible and effective. Copyright © 2015 John Wiley & Sons, Ltd.     

The solvability conditions for inverse eigenproblem of symmetric and anti‐persymmetric matrices and its approximation

The problem of generating a matrix A with specified eigen‐pair, where A is a symmetric and anti‐persymmetric matrix, is presented. An existence theorem is given and proved. A general expression of such a matrix is provided. We denote the set of such matrices by ??????_Eⁿ. The optimal approximation problem associated with ??????_Eⁿ is discussed, that is: to find the nearest matrix to a given matrix A* by A∈??????_Eⁿ. The existence and uniqueness of the optimal approximation problem is proved and the expression is provided for this nearest matrix. Copyright © 2002 John Wiley & Sons, Ltd.     

Hermite-广义反Hamilton矩阵的一类反问题

给定矩阵X和B,利用矩阵的广义奇异值分解,得到了矩阵方程X~HAX=B有Hermite-广义反Hamiton解的充分必要条件及有解时解的—般表达式.用S_E表示此矩阵方程的解集合,证明了S_E中存在唯一的矩阵(?),使得(?)与给定矩阵A的差的Frobenius范数最小,并且给出了矩阵(?)的表达式;同时也证明了S_E中存在唯一的矩阵A_o,使得A_o是此矩阵方程的极小Frobenius范数Hermite-广义反Hamilton解,并且给出了矩阵A_o的表达式.     

Minimisation of functions of a positive semidefinite matrix A subject to AX = 0

A common problem in multivariate analysis is that of minimising or maximising a function f of a positive semidefinite matrix A subject possibly to AX = 0. Typically A is a variance-covariance matrix. Using the theory of nearest point projections in Hilbert spaces, it is shown that the solution satisfies the equation f′(A) + M ? A = 0, where A = P₀(M) and P₀ is a certain projection operator.     

Optimized projections for compressed sensing via rank-constrained nearest correlation matrix

Optimizing the acquisition matrix is useful for compressed sensing of signals that are sparse in overcomplete dictionaries, because the acquisition matrix can be adapted to the particular correlations of the dictionary atoms. In this paper a novel formulation of the optimization problem is proposed, in the form of a rank-constrained nearest correlation matrix problem. Furthermore, improvements for three existing optimization algorithms are introduced, which are shown to be particular instances of the proposed formulation. Simulation results show notable improvements and superior robustness in sparse signal recovery.     

Algorithms for projecting a point onto a level surface of a continuous function on a compact set

Given an equation f(x) = 0, the problem of finding its solution nearest to a given point is considered. In contrast to the authors’ previous works dealing with this problem, exact algorithms are proposed assuming that the function f is continuous on a compact set. The convergence of the algorithms is proved, and their performance is illustrated with test examples.     

Solving Hankel matrix approximation problem using semidefinite programming

Positive semidefinite Hankel matrices arise in many important applications. Some of their properties may be lost due to rounding or truncation errors incurred during evaluation. The problem is to find the nearest matrix to a given matrix to retrieve these properties. The problem is converted into a semidefinite programming problem as well as a problem comprising a semidefined program and second-order cone problem. The duality and optimality conditions are obtained and the primal–dual algorithm is outlined. Explicit expressions for a diagonal preconditioned and crossover criteria have been presented. Computational results are presented. A possibility for further improvement is indicated.     

On approximating the nearest Ω‐stable matrix

In this paper, we consider the problem of approximating a given matrix with a matrix whose eigenvalues lie in some specific region Ω of the complex plane. More precisely, we consider three types of regions and their intersections: conic sectors, vertical strips, and disks. We refer to this problem as the nearest Ω‐stable matrix problem. This includes as special cases the stable matrices for continuous and discrete time linear time‐invariant systems. In order to achieve this goal, we parameterize this problem using dissipative Hamiltonian matrices and linear matrix inequalities. This leads to a reformulation of the problem with a convex feasible set. By applying a block coordinate descent method on this reformulation, we are able to compute solutions to the approximation problem, which is illustrated on some examples.     

The calculation of the distance to a nearby defective matrix

The distance of a matrix to a nearby defective matrix is an important classical problem in numerical linear algebra, as it determines how sensitive or ill‐conditioned an eigenvalue decomposition of a matrix is. The concept has been discussed throughout the history of numerical linear algebra, and the problem of computing the nearest defective matrix first appeared in Wilkinsons famous book on the algebraic eigenvalue problem. In this paper, a new fast algorithm for the computation of the distance of a matrix to a nearby defective matrix is presented. The problem is formulated following Alam and Bora introduced in (2005) and reduces to finding when a parameter‐dependent matrix is singular subject to a constraint. The solution is achieved by an extension of the implicit determinant method introduced by Spence and Poulton in (2005). Numerical results for several examples illustrate the performance of the algorithm. Copyright © 2013 John Wiley & Sons, Ltd.     

Fast computation of eigenvalues of companion,comrade, and related matrices

The class of eigenvalue problems for upper Hessenberg matrices of banded-plus-spike form includes companion and comrade matrices as special cases. For this class of matrices a factored form is developed in which the matrix is represented as a product of essentially 2×2 matrices and a banded upper-triangular matrix. A non-unitary analogue of Francis’s implicitly-shifted QR algorithm that preserves the factored form and consequently computes the eigenvalues in O(n ²) time and O(n) space is developed. Inexpensive a posteriori tests for stability and accuracy are performed as part of the algorithm. The results of numerical experiments are mixed but promising in certain areas. The single-shift version of the code applied to companion matrices is much faster than the nearest competitor.     

On a general class of matrix nearness problems

The problem is considered of finding the nearest rank-deficient matrix to a given rectangular matrix. For a wide class of matrix norms, and arbitrary sparsity imposed on the matrix of perturbations, it is shown that when a solution exists, it can be calculated from the solution of a simpler problem involving fewer variables and only vector norms. Some numerical results are given for a special case involving the Frobenius norm.Communicated by Charles Micchelli.     

Anderson acceleration of the alternating projections method for computing the nearest correlation matrix

In a wide range of applications it is required to compute the nearest correlation matrix in the Frobenius norm to a given symmetric but indefinite matrix. Of the available methods with guaranteed convergence to the unique solution of this problem the easiest to implement, and perhaps the most widely used, is the alternating projections method. However, the rate of convergence of this method is at best linear, and it can require a large number of iterations to converge to within a given tolerance. We show that Anderson acceleration, a technique for accelerating the convergence of fixed-point iterations, can be applied to the alternating projections method and that in practice it brings a significant reduction in both the number of iterations and the computation time. We also show that Anderson acceleration remains effective, and indeed can provide even greater improvements, when it is applied to the variants of the nearest correlation matrix problem in which specified elements are fixed or a lower bound is imposed on the smallest eigenvalue. Alternating projections is a general method for finding a point in the intersection of several sets and ours appears to be the first demonstration that this class of methods can benefit from Anderson acceleration.     

A matrix lower bound

Four essentially different interpretations of a lower bound for linear operators are shown to be equivalent for matrices (involving inequalities, convex sets, minimax problems, and quotient spaces). Properties stated by von Neumann in a restricted case are satisfied by the lower bound. Applications are made to rank reduction, s-numbers, condition numbers, and pseudospectra. In particular, the matrix lower bound is the distance to the nearest matrix with strictly contained row or column spaces, and it occurs in a condition number formula for any consistent system of linear equations, including those that are underdetermined.     

On some methods for entropy maximization and matrix scaling

We describe and survey in this paper iterative algorithms for solving the discrete maximum entropy problem with linear equality constraints. This problem has applications e.g. in image reconstruction from projections, transportation planning, and matrix scaling. In particular we study local convergence and asymptotic rate of convergence as a function of the iteration parameter. For the trip distribution problem in transportation planning and the equivalent problem of scaling a positive matrix to achieve a priori given row and column sums, it is shown how the iteration parameters can be chosen in an optimal way. We also consider the related problem of finding a matrix X, diagonally similar to a given matrix, such that corresponding row and column norms in X are all equal. Reports of some numerical tests are given.     

Ill-Conditionedness Need not be Componentwise Near to Ill-Posedness for Least Squares Problems

The condition number of a problem measures the sensitivity of the answer to small changes in the input, where small refers to some distance measure. A problem is called ill-conditioned if the condition number is large, and it is called ill-posed if the condition number is infinity. It is known that for many problems the (normwise) distance to the nearest ill-posed problem is proportional to the reciprocal of the condition number. Recently it has been shown that for linear systems and matrix inversion this is also true for componentwise distances. In this note we show that this is no longer true for least squares problems and other problems involving rectangular matrices. Problems are identified which are arbitrarily ill-conditioned (in a componentwise sense) whereas any componentwise relative perturbation less than 1 cannot produce an ill-posed problem. Bounds are given using additional information on the matrix.