Minimizing the condition number of a positive definite matrix by completion

Summary. We consider the problem of minimizing the spectral condition number of a positive definite matrix by completion: \noindent where is an Hermitian positive definite matrix, a matrix and is a free Hermitian matrix. We reduce this problem to an optimization problem for a convex function in one variable. Using the minimal solution of this problem we characterize the complete set of matrices that give the minimum condition number. Received October 15, 1993     

$$S_{1/2}$$ regularization methods and fixed point algorithms for affine rank minimization problems

The affine rank minimization problem is to minimize the rank of a matrix under linear constraints. It has many applications in various areas such as statistics, control, system identification and machine learning. Unlike the literatures which use the nuclear norm or the general Schatten \(q~ (0<q<1)\) quasi-norm to approximate the rank of a matrix, in this paper we use the Schatten 1 / 2 quasi-norm approximation which is a better approximation than the nuclear norm but leads to a nonconvex, nonsmooth and non-Lipschitz optimization problem. It is important that we give a global necessary optimality condition for the \(S_{1/2}\) regularization problem by virtue of the special objective function. This is very different from the local optimality conditions usually used for the general \(S_q\) regularization problems. Explicitly, the global necessary optimality condition for the \(S_{1/2}\) regularization problem is a fixed point inclusion associated with the singular value half thresholding operator. Naturally, we propose a fixed point iterative scheme for the problem. We also provide the convergence analysis of this iteration. By discussing the location and setting of the optimal regularization parameter as well as using an approximate singular value decomposition procedure, we get a very efficient algorithm, half norm fixed point algorithm with an approximate SVD (HFPA algorithm), for the \(S_{1/2}\) regularization problem. Numerical experiments on randomly generated and real matrix completion problems are presented to demonstrate the effectiveness of the proposed algorithm.     

Minimal condition number for positive definite Hankel matrices using semidefinite programming

We present a semidefinite programming approach for computing optimally conditioned positive definite Hankel matrices of order n. Unlike previous approaches, our method is guaranteed to find an optimally conditioned positive definite Hankel matrix within any desired tolerance. Since the condition number of such matrices grows exponentially with n, this is a very good test problem for checking the numerical accuracy of semidefinite programming solvers. Our tests show that semidefinite programming solvers using fixed double precision arithmetic are not able to solve problems with n>30. Moreover, the accuracy of the results for 24?n?30 is questionable. In order to accurately compute minimal condition number positive definite Hankel matrices of higher order, we use a Mathematica 6.0 implementation of the SDPHA solver that performs the numerical calculations in arbitrary precision arithmetic. By using this code, we have validated the results obtained by standard codes for n?24, and we have found optimally conditioned positive definite Hankel matrices up to n=100.     

The conditioning of the maximum entropy covariance matrix and its inverse

The maximum entropy covariance matrix is positive definite even when the number of variables p exceeds the sample size n. However, the inverse of this matrix can have stability problems when p is close to n, although these problems tend to disappear as p increases beyond n. We analyze such problems using the variance of the latent roots in a particular metric as a condition number.     

Exact Matrix Completion via Convex Optimization

We consider a problem of considerable practical interest: the recovery of a data matrix from a sampling of its entries. Suppose that we observe m entries selected uniformly at random from a matrix M. Can we complete the matrix and recover the entries that we have not seen? We show that one can perfectly recover most low-rank matrices from what appears to be an incomplete set of entries. We prove that if the number m of sampled entries obeys $m\ge C\,n^{1.2}r\log n$ for some positive numerical constant C, then with very high probability, most n×n matrices of rank r can be perfectly recovered by solving a simple convex optimization program. This program finds the matrix with minimum nuclear norm that fits the data. The condition above assumes that the rank is not too large. However, if one replaces the 1.2 exponent with 1.25, then the result holds for all values of the rank. Similar results hold for arbitrary rectangular matrices as well. Our results are connected with the recent literature on compressed sensing, and show that objects other than signals and images can be perfectly reconstructed from very limited information.     

半监督距离度量学习内蕴加速投影梯度算法

考虑求解一类半监督距离度量学习问题. 由于样本集(数据库)的规模与复杂性的激增, 在考虑距离度量学习问题时, 必须考虑学习来的距离度量矩阵具有稀疏性的特点. 因此, 在现有的距离度量学习模型中, 增加了学习矩阵的稀疏约束. 为了便于模型求解, 稀疏约束应用了Frobenius 范数约束. 进一步, 通过罚函数方法将Frobenius范数约束罚到目标函数, 使得具有稀疏约束的模型转化成无约束优化问题. 为了求解问题, 提出了正定矩阵群上加速投影梯度算法, 克服了矩阵群上不能直接进行线性组合的困难, 并分析了算法的收敛性. 最后通过UCI数据库的分类问题的例子, 进行了数值实验, 数值实验的结果说明了学习矩阵的稀疏性以及加速投影梯度算法的有效性.     

A practical but rigorous approach to sum-of-ratios optimization in geometric applications

In this paper, we develop an algorithm for minimizing the L _q norm of a vector whose components are linear fractional functions, where q is an arbitrary positive integer. The problem is a kind of sum-of-ratios optimization problem, and often occurs in computer vision. In that case, it is characterized by a large number of ratios and a small number of variables. The algorithm we propose here exploits this feature and generates a globally optimal solution in a practical amount of computational time.     

Towards backward perturbation bounds for approximate dual Krylov subspaces

Given a matrix A,n by n, and two subspaces K and L of dimension m, we consider how to determine a backward perturbation E whose norm is as small as possible, such that k and L are Krylov subspaces of A+E and its adjoint, respectively. We first focus on determining a perturbation matrix for a given pair of biorthonormal bases, and then take into account how to choose an appropriate biorthonormal pair and express the Krylov residuals as a perturbation of the matrix A. Specifically, the perturbation matrix is globally optimal when A is Hermitian and K=L. The results show that the norm of the perturbation matrix can be assessed by using the norms of the Krylov residuals and those of the biorthonormal bases. Numerical experiments illustrate the efficiency of our strategy.     

Uniqueness in law for a class of degenerate diffusions with continuous covariance

We study the martingale problem associated with the operator $$ Lu(s, x) = \partial_su(s, x) + \frac{1}{2} \sum_{i,j=1}^{d_0} a^{ij}(s, x) \partial_{ij}u(s, x) + \sum_{i,j=1}^d B^{ij} x^j \partial_iu(s, x), $$ where d ₀ ≤  d. We show that the martingale problem is well-posed when the function a is continuous and strictly positive definite on ${\mathbb{R}^{d_0}}$ and the matrix B takes a particular lower-diagonal, block form. We then localize this result to show that the martingale problem remains well-posed when B is replaced by a sufficiently smooth vector field whose Jacobian matrix satisfies a nondegeneracy condition.     

Tropical hyperelliptic curves

We study the locus of tropical hyperelliptic curves inside the moduli space of tropical curves of genus g. We define a harmonic morphism of metric graphs and prove that a metric graph is hyperelliptic if and only if it admits a harmonic morphism of degree 2 to a metric tree. This generalizes the work of Baker and Norine on combinatorial graphs to the metric case. We then prove that the locus of 2-edge-connected genus g tropical hyperelliptic curves is a (2g?1)-dimensional stacky polyhedral fan whose maximal cells are in bijection with trees on g?1 vertices with maximum valence 3. Finally, we show that the Berkovich skeleton of a classical hyperelliptic plane curve satisfying a certain tropical smoothness condition is a standard ladder of genus g.     

Stopping criteria for the Ando-Li-Mathias and Bini-Meini-Poloni geometric means

We provide an upper bound for the number of iterations necessary to achieve a desired level of accuracy for the Ando-Li-Mathias [Linear Algebra Appl. 385 (2004) 305-334] and Bini-Meini-Poloni [Math. Comput. 79 (2010) 437-452] symmetrization procedures for computing the geometric mean of n positive definite matrices, where accuracy is measured by the spectral norm and the Thompson metric on the convex cone of positive definite matrices. It is shown that the upper bound for the number of iterations depends only on the diameter of the set of n matrices and the desired convergence tolerance. A striking result is that the upper bound decreases as n increases on any bounded region of positive definite matrices.     

Ricci Deformation of the Metric on Riemannian Orbifolds

In this note we generalize the Huisken’s (J Diff Geom 21:47–62, 1985) result to Riemannian orbifolds. We show that on any n-dimensional (n ≥ 4) orbifold of positive scalar curvature the metric can be deformed into a metric of constant positive curvature, provided the norm of the Weyl conformal curvature tensor and the norm of the traceless Ricci tensor are not large compared to the scalar curvature at each point, and therefore generalize 3-orbifolds result proved by Hamilton [Three- orbifolds with positive Ricci curvature. In: Cao HD, Chow B, Chu SC, Yau ST (eds) Collected Papers on Ricci Flow, Internat. Press, Somerville, 2003] to n-orbifolds (n ≥ 4).     

A solution to anisotropic suboptimal filtering problem by convex optimization

This paper considers a robust filtering problem for a linear discrete time invariant system with measured and estimated outputs. The system is exposed to random disturbances with imprecisely known distributions generated by an unknown stable shaping filter from the Gaussian white noise. The stochastic uncertainty of the input disturbance is measured by the mean anisotropy functional. The estimation error is quantified by the anisotropic norm which is a stochastic analogue of the H _∞ norm. A sufficient condition for an estimator to exist and ensure that the error is less than a given threshold value is derived in form of a convex inequality on the determinant of a positive definite matrix and two linear matrix inequalities. The suboptimal problem setting results to a set of the estimators ensuring the anisotropic norm of the error to be strictly bounded thereby providing some additional degree of freedom to impose some additional constraints on the estimator performance specification.     

On the stability of large matrices

The distance rstab(A) of a stable matrix A to the set of unstable matrices and the norm of the exponential of matrices constitute two important topics in stability theory. We treat in this note the case of large matrices. The method proposed partitions the matrix into two blocks: a small block in which the stability is studied and a large block whose field of values is located in the complex plane. Using the information on the blocks and some results on perturbation theory, we give sufficient conditions for the stability of the original matrix, a lower bound of rstab(A) and an upper bound on the norm of the exponential of A. We illustrate these theoretical bounds on a practical test problem.     

Retraction algorithms for solving variational inequalities,pseudomonotone equilibrium problems,and fixed-point problems in Banach spaces

In this paper, using sunny generalized nonexpansive retractions which are different from the metric projection and generalized metric projection in Banach spaces, we present new extragradient and line search algorithms for finding the solution of a J-variational inequality whose constraint set is the common elements of the set of fixed points of a family of generalized nonexpansive mappings and the set of solutions of a pseudomonotone J-equilibrium problem for a J -α-inverse-strongly monotone operator in a Banach space. To prove strong convergence of generated iterates in the extragradient method, we introduce a ? _?-Lipschitz-type condition and assume that the equilibrium bifunction satisfies this condition. This condition is unnecessary when the line search method is used instead of the extragradient method. Using FMINCON optimization toolbox in MATLAB, we give some numerical examples and compare them with several existence results in literature to illustrate the usability of our results.     

Damping optimization of parameter dependent mechanical systems by rational interpolation

We consider an optimization problem related to semi-active damping of vibrating systems. The main problem is to determine the best damping matrix able to minimize influence of the input on the output of the system. We use a minimization criteria based on the \(\mathcal {H}_{2}\) system norm. The objective function is non-convex and the associated optimization problem typically requires a large number of objective function evaluations. We propose an optimization approach that calculates ‘interpolatory’ reduced order models, allowing for significant acceleration of the optimization process. In our approach, we use parametric model reduction (PMOR) based on the Iterative Rational Krylov Algorithm, which ensures good approximations relative to the \(\mathcal {H}_{2}\) system norm, aligning well with the underlying damping design objectives. For the parameter sampling that occurs within each PMOR cycle, we consider approaches with predetermined sampling and approaches using adaptive sampling, and each of these approaches may be combined with three possible strategies for internal reduction. In order to preserve important system properties, we maintain second-order structure, which through the use of modal coordinates, allows for very efficient implementation. The methodology proposed here provides a significant acceleration of the optimization process; the gain in efficiency is illustrated in numerical experiments.     

Boundary Value Problems for the Elliptic Sine-Gordon Equation in a Semi-strip

We study boundary value problems posed in a semistrip for the elliptic sine-Gordon equation, which is the paradigm of an elliptic integrable PDE in two variables. We use the method introduced by one of the authors, which provides a substantial generalization of the inverse scattering transform and can be used for the analysis of boundary as opposed to initial-value problems. We first express the solution in terms of a 2×2 matrix Riemann–Hilbert problem whose “jump matrix” depends on both the Dirichlet and the Neumann boundary values. For a well posed problem one of these boundary values is an unknown function. This unknown function is characterised in terms of the so-called global relation, but in general this characterisation is nonlinear. We then concentrate on the case that the prescribed boundary conditions are zero along the unbounded sides of a semistrip and constant along the bounded side. This corresponds to a case of the so-called linearisable boundary conditions, however, a major difficulty for this problem is the existence of non-integrable singularities of the function q _y at the two corners of the semistrip; these singularities are generated by the discontinuities of the boundary condition at these corners. Motivated by the recent solution of the analogous problem for the modified Helmholtz equation, we introduce an appropriate regularisation which overcomes this difficulty. Furthermore, by mapping the basic Riemann–Hilbert problem to an equivalent modified Riemann–Hilbert problem, we show that the solution can be expressed in terms of a 2×2 matrix Riemann–Hilbert problem whose “jump matrix” depends explicitly on the width of the semistrip L, on the constant value d of the solution along the bounded side, and on the residues at the given poles of a certain spectral function denoted by h(λ). The determination of the function h remains open.     

Variational principles in non-metrizable spaces

We study generic variational principles in optimization when the underlying topological space X is not necessarily metrizable. It turns out that, to ensure the validity of such a principle, instead of having a complete metric which generates the topology in the space X (which is the case of most variational principles), it is enough that we dispose of a complete metric on X which is stronger than the topology in X and fragments the space X.     

Applications of gauge duality in robust principal component analysis and semidefinite programming

Gauge duality theory was originated by Freund (1987), and was recently further investigated by Friedlander et al. (2014). When solving some matrix optimization problems via gauge dual, one is usually able to avoid full matrix decompositions such as singular value and/or eigenvalue decompositions. In such an approach, a gauge dual problem is solved in the first stage, and then an optimal solution to the primal problem can be recovered from the dual optimal solution obtained in the first stage. Recently, this theory has been applied to a class of semidefinite programming (SDP) problems with promising numerical results by Friedlander and Macêdo (2016). We establish some theoretical results on applying the gauge duality theory to robust principal component analysis (PCA) and general SDP. For each problem, we present its gauge dual problem, characterize the optimality conditions for the primal-dual gauge pair, and validate a way to recover a primal optimal solution from a dual one. These results are extensions of Friedlander and Macêdo (2016) from nuclear norm regularization to robust PCA and from a special class of SDP which requires the coefficient matrix in the linear objective to be positive definite to SDP problems without this restriction. Our results provide further understanding in the potential advantages and disadvantages of the gauge duality theory.     

Condition numbers of rectangular systems and bounds for generalized inverses

A natural extension of the notion of condition number of a matrix to the class of all finite matrices is shown to enjoy properties similar to the classical condition number. For example, the relative distance to the set of all matrices of smaller rank is just the reciprocal of this generalized condition number. The question of whether a matrix with a small generalized condition number must also have a generalized inverse of small norm is then studied. The answer turns out to be norm dependent. In particular, only if p is 1 or 2 must an intrinsically well-conditioned full rank matrix in the l_p sense have a nicely bounded generalized inverse; in particular, in the l_∞ norm this need not be true. These facts are consequences of recent results in Banach space theory.