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

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