Simplicial faces of the set of correlation matrices

DOI10.1007/S00454-017-9961-0MaRDI QIDQ1991097zbMATH OpenOpenAlexWikidataFDO

Authors Joel A. Tropp

Publication date 30 October 2018

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1801.00749, https://authors.library.caltech.edu/84074/

zbMATH Keywords

correlation matrixcut polytopeelliptopefacematrix concentrationprobabilistic method

Mathematics Subject Classification ID

Positive matrices and their generalizations; cones of matrices (15B48) Convex sets in (n) dimensions (including convex hypersurfaces) (52A20) Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Combinatorial optimization (90C27)

Abstract: This paper concerns the facial geometry of the set of $nimesn$ correlation matrices. The main result states that almost every set of $r$ vertices generates a simplicial face, provided that $rleqsqrtmathrmcn$, where $mathrmc$ is an absolute constant. This bound is qualitatively sharp because the set of correlation matrices has no simplicial face generated by more than $sqrt2n$ vertices.

Recommendations

• On the Facial Structure of the Set of Correlation Matrices
• Extremal correlation matrices
• Correlation polytopes: Their geometry and complexity
• Cartesian and polar coordinates for the N-dimensional elliptope
• Three-by-three correlation matrices: its exact shape and a family of distributions

Cites work

• An introduction to matrix concentration inequalities
• Analysis of Boolean Functions
• Bounding the smallest singular value of a random matrix without concentration
• Convex Analysis
• Convex Recovery of a Structured Signal from Independent Random Linear Measurements
• Grothendieck-type inequalities in combinatorial optimization
• Grothendieck’s Theorem, past and present
• scientific article; zbMATH DE number 1667417 (Why is no real title available?)
• scientific article; zbMATH DE number 3124239 (Why is no real title available?)
• scientific article; zbMATH DE number 967931 (Why is no real title available?)
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Lectures on modern convex optimization. Analysis, algorithms, and engineering applications
• On a positive semidefinite relaxation of the cut polytope
• On the Facial Structure of the Set of Correlation Matrices
• Reducibility among combinatorial problems
• Semidefinite relaxation and nonconvex quadratic optimization
• Solving the max-cut problem using eigenvalues
• Strong converse for identification via quantum channels
• The lower tail of random quadratic forms with applications to ordinary least squares
• The performance of an eigenvalue bound on the max-cut problem in some classes of graphs
• Two proposals for robust PCA using semidefinite programming
• User-friendly tail bounds for sums of random matrices

Cited in

(10)

• Correlation polytopes: Their geometry and complexity
• On generating random Gaussian graphical models
• Cut polytope has vertices on a line
• Geodesics and curvature of the quotient-affine metrics on full-rank correlation matrices
• On the Facial Structure of the Set of Correlation Matrices
• Clustering in Hilbert's projective geometry: the case studies of the probability simplex and the elliptope of correlation matrices
• COMPATIBILITY AND ATTAINABILITY OF MATRICES OF CORRELATION-BASED MEASURES OF CONCORDANCE
• Binary component decomposition. I: The positive-semidefinite case
• Introduction to correlation networks: interdisciplinary approaches beyond thresholding
• Quotient geometry of bounded or fixed-rank correlation matrices

This page was built for publication: Simplicial faces of the set of correlation matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1991097)