Polynomial Instances of the Positive Semidefinite and Euclidean Distance Matrix Completion Problems

DOI10.1137/S0895479899352689zbMath0981.05071MaRDI QIDQ2706294

Monique Laurent

Publication date: 19 March 2001

Published in: SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)

zbMATH Keywords

matrix completionpolynomial algorithmchordal graphpositive semidefinite matrixEuclidean distance matrixminimum fill-inbit modelnumber model

Mathematics Subject Classification ID

Convex programming (90C25) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Positive matrices and their generalizations; cones of matrices (15B48) Hermitian, skew-Hermitian, and related matrices (15B57)

Related Items (14)

Completion problem with partial correlation vines ⋮ Phase retrieval of complex and vector-valued functions ⋮ On the uniqueness of Euclidean distance matrix completions. ⋮ An efficient algorithm for maximum entropy extension of block-circulant covariance matrices ⋮ Positive semidefinite matrix completion, universal rigidity and the strong Arnold property ⋮ A new graph parameter related to bounded rank positive semidefinite matrix completions ⋮ Semidefinite programming for discrete optimization and matrix completion problems ⋮ On the uniqueness of Euclidean distance matrix completions: the case of points in general position ⋮ Euclidean Distance Matrices and Applications ⋮ Efficient algorithms for network localization using cores of underlying graphs ⋮ A maximum entropy approach to the realizability of spin correlation matrices ⋮ Approximate and exact completion problems for Euclidean distance matrices using semidefinite programming ⋮ Complexity of the Positive Semidefinite Matrix Completion Problem with a Rank Constraint ⋮ Coordinate Shadows of Semidefinite and Euclidean Distance Matrices

This page was built for publication: Polynomial Instances of the Positive Semidefinite and Euclidean Distance Matrix Completion Problems