Half thresholding eigenvalue algorithm for semidefinite matrix completion

The semidefinite matrix completion(SMC) problem is to recover a low-rank positive semidefinite matrix from a small subset of its entries. It is well known but NP-hard in general. We first show that under some cases, SMC problem and S1/2relaxation model share a unique solution. Then we prove that the global optimal solutions of S1/2regularization model are fixed points of a symmetric matrix half thresholding operator. We give an iterative scheme for solving S1/2regularization model and state convergence analysis of the iterative sequence.Through the optimal regularization parameter setting together with truncation techniques, we develop an HTE algorithm for S1/2regularization model, and numerical experiments confirm the efficiency and robustness of the proposed algorithm.     

Exploiting sparsity in linear and nonlinear matrix inequalities via positive semidefinite matrix completion

A basic framework for exploiting sparsity via positive semidefinite matrix completion is presented for an optimization problem with linear and nonlinear matrix inequalities. The sparsity, characterized with a chordal graph structure, can be detected in the variable matrix or in a linear or nonlinear matrix-inequality constraint of the problem. We classify the sparsity in two types, the domain-space sparsity (d-space sparsity) for the symmetric matrix variable in the objective and/or constraint functions of the problem, which is required to be positive semidefinite, and the range-space sparsity (r-space sparsity) for a linear or nonlinear matrix-inequality constraint of the problem. Four conversion methods are proposed in this framework: two for exploiting the d-space sparsity and the other two for exploiting the r-space sparsity. When applied to a polynomial semidefinite program (SDP), these conversion methods enhance the structured sparsity of the problem called the correlative sparsity. As a result, the resulting polynomial SDP can be solved more effectively by applying the sparse SDP relaxation. Preliminary numerical results on the conversion methods indicate their potential for improving the efficiency of solving various problems.     

Exploiting sparsity in semidefinite programming via matrix completion II: implementation and numerical results

 In Part I of this series of articles, we introduced a general framework of exploiting the aggregate sparsity pattern over all data matrices of large scale and sparse semidefinite programs (SDPs) when solving them by primal-dual interior-point methods. This framework is based on some results about positive semidefinite matrix completion, and it can be embodied in two different ways. One is by a conversion of a given sparse SDP having a large scale positive semidefinite matrix variable into an SDP having multiple but smaller positive semidefinite matrix variables. The other is by incorporating a positive definite matrix completion itself in a primal-dual interior-point method. The current article presents the details of their implementations. We introduce new techniques to deal with the sparsity through a clique tree in the former method and through new computational formulae in the latter one. Numerical results over different classes of SDPs show that these methods can be very efficient for some problems. Received: March 18, 2001 / Accepted: May 31, 2001 Published online: October 9, 2002 RID="⋆" ID="⋆"The author was supported by The Ministry of Education, Culture, Sports, Science and Technology of Japan. Key Words. semidefinite programming – primal-dual interior-point method – matrix completion problem – clique tree – numerical results Mathematics Subject Classification (2000): 90C22, 90C51, 05C50, 05C05     

A nonconvex approach to low‐rank matrix completion using convex optimization

This paper deals with the problem of recovering an unknown low‐rank matrix from a sampling of its entries. For its solution, we consider a nonconvex approach based on the minimization of a nonconvex functional that is the sum of a convex fidelity term and a nonconvex, nonsmooth relaxation of the rank function. We show that by a suitable choice of this nonconvex penalty, it is possible, under mild assumptions, to use also in this matrix setting the iterative forward–backward splitting method. Specifically, we propose the use of certain parameter dependent nonconvex penalties that with a good choice of the parameter value allow us to solve in the backward step a convex minimization problem, and we exploit this result to prove the convergence of the iterative forward–backward splitting algorithm. Based on the theoretical results, we develop for the solution of the matrix completion problem the efficient iterative improved matrix completion forward–backward algorithm, which exhibits lower computing times and improved recovery performance when compared with the best state‐of‐the‐art algorithms for matrix completion. Copyright © 2016 John Wiley & Sons, Ltd.     

Logarithmic geometry and algebraic stacks

We construct algebraic moduli stacks of log structures and give stack-theoretic interpretations of K. Kato's notions of log flat, log smooth, and log étale morphisms. In the last section we describe the local structure of these moduli stacks in terms of toric stacks.     

Baxter's equations and algebraic geometry

Functional Analysis and Its Applications -     

Symplectic packings and algebraic geometry

Oblatum 9-XI-1992 & 17-VI-1993     

Unitary matrix digraphs and minimum semidefinite rank

For an undirected simple graph G, the minimum rank among all positive semidefinite matrices with graph G is called the minimum semidefinite rank (msr) of G. In this paper, we show that the msr of a given graph may be determined from the msr of a related bipartite graph. Finding the msr of a given bipartite graph is then shown to be equivalent to determining which digraphs encode the zero/nonzero pattern of a unitary matrix. We provide an algorithm to construct unitary matrices with a certain pattern, and use previous results to give a lower bound for the msr of certain bipartite graphs.     

Positive semidefinite matrix completions on chordal graphs and constraint nondegeneracy in semidefinite programming

Let G=(V,E) be a graph. In matrix completion theory, it is known that the following two conditions are equivalent: (i) G is a chordal graph; (ii) Every G-partial positive semidefinite matrix has a positive semidefinite matrix completion. In this paper, we relate these two conditions to constraint nondegeneracy condition in semidefinite programming and prove that they are each equivalent to (iii) For any G-partial positive definite matrix that has a positive semidefinite completion, constraint nondegeneracy is satisfied at each of its positive semidefinite matrix completions.     

The tetrahedron equation and algebraic geometry

The tetrahedron equation arises as a generalization of the famous Yang-Baxter equation to the2+1-dimensional quantum field theory and three-dimensional statistical mechanics. Not much is known about its solutions. In the present paper, a systematic method of constructing nontrivial solutions to the tetrahedron equation with spin-like variables on the links is described. The essence of this method is the use of the so-called tetrahedral Zamolodchikov algebras. Bibliography:12 titles. Published inZapiski Nauchnykh Seminarov POMI, Vol. 209, 1994, pp. 137–149. Translated by I. G. Korepanov.     

Porosity and unique completion in strictly convex spaces

We are concerned in this paper with topological and stochastic properties of the family ${\mathcal G}$ of all closed convex sets with a unique extension to a complete set. With the help of a strengthened version of a lemma by Groemer we show that, in Minkowski spaces with a strictly convex norm, ${\mathcal G}$ is lower porous. This improves a previous result from Groemer (Geom. Dedicata 20:319?C334, 1986) where, in the same context, ${\mathcal G}$ was proved to be nowhere dense. In contrast to this fact we show that, in these spaces, there is a stochastic construction procedure which provides a complete set with probability one. This generalizes an earlier result of Bavaud (Trans. Amer. Math. Soc. 333(1):315?C324, 1992) proved for the particular case of the Euclidean plane.     

On monotone and convex approximation by algebraic polynomials

The following results are obtained: If >0, 2, [3, 4], andf is a nondecreasing (convex) function on [–1, 1] such thatE _n (f) n ^– for any n>, then E _n ⁽¹⁾ (f)Cn ^– (E _n ⁽²⁾ (f)Cn ^–) for n>, where C=C(), E_n(f) is the best uniform approximation of a continuous function by polynomials of degree (n–1), and E _n ⁽¹⁾ (f) (E _n ⁽²⁾ (f)) are the best monotone and convex approximations, respectively. For =2 ( [3, 4]), this result is not true.Published in Ukrainskii Matematicheskii Zhurnal, Vol. 46, No. 9, pp. 1266–1270, September, 1994.     

Equations and algebraic geometry over profinite groups

The notion of an equation over a profinite group is defined, as well as the concepts of an algebraic set and of a coordinate group. We show how to represent the coordinate group as a projective limit of coordinate groups of finite groups. It is proved that if the set π(G) of prime divisors of the profinite period of a group G is infinite, then such a group is not Noetherian, even with respect to one-variable equations. For the case of Abelian groups, the finiteness of a set π(G) gives rise to equational Noetherianness. The concept of a standard linear pro-p-group is introduced, and we prove that such is always equationally Noetherian. As a consequence, it is stated that free nilpotent pro-p-groups and free metabelian pro-p-groups are equationally Noetherian. In addition, two examples of equationally non-Noetherian pro-p-groups are constructed. The concepts of a universal formula and of a universal theory over a profinite group are defined. For equationally Noetherian profinite groups, coordinate groups of irreducible algebraic sets are described using the language of universal theories and the notion of discriminability.     

Hermitian semidefinite matrix means and related matrix inequalities—an introduction

A survey of matrix means and matrix inequalities is presented with the work of Ando, Anderson and Duffin being showcased. The classical Arithmetic-Geometric-Harmonic Mean for two Hermitian positive semidefinite matrices is given. Other classical means such as the Gaussian Mean, power means and the symmetric function means are also discussed.     

Multiplier ideal sheaves in complex and algebraic geometry

The application of the method of multiplier ideal sheaves to effective problems in algebraic geometry is briefly discussed. Then its application to the deformational invari-ance of plurigenera for general compact algebraic manifolds is presented and discussed. Finally its application to the conjecture of the finite generation of the canonical ring is explored, and the use of complex algebraic geometry in complex Neumann estimates is discussed.     

Multiplier ideal sheaves in complex and algebraic geometry

The application of the method of multiplier ideal sheaves to effective problems in algebraic geometry is briefly discussed. Then its application to the deformational invariance of plurigenera for general compact algebraic manifolds is presented and discussed. Finally its application to the conjecture of the finite generation of the canonical ring is explored, and the use of complex algebraic geometry in complex Neumann estimates is discussed.