Worst-case results for positive semidefinite rank (Q745690)

From MaRDI portal
Revision as of 16:40, 18 April 2024 by Importer (talk | contribs) (‎Changed an Item)
scientific article
Language Label Description Also known as
English
Worst-case results for positive semidefinite rank
scientific article

    Statements

    Worst-case results for positive semidefinite rank (English)
    0 references
    0 references
    0 references
    0 references
    14 October 2015
    0 references
    The positive semidefinite rank is an extension of the notion of the nonnegative rank of a matrix. The nonnegative rank of a matrix is the smallest possible integer \(k\) such that each entry \((i,j)\) of the matrix can be written as the inner product of two vectors \(a_i\) and \(b_j\) in the cone of nonnegative vectors of size \(k\). The positive semidefinite rank is the smallest possible integer \(k\) such that each entry \((i,j)\) of the matrix can be written as the inner product of two matrices \(A_i\) and \(B_j\) in the cone of positive semidefinite matrices of size \(k\). These ranks can be interpreted as a measure of complexity of a polytope, in the sense that they encode the size of a sparse representation of a polytope through a factorization of its matrix description. The paper under review reports on state-of-the-art results on lower bounds on the positive semidefinite rank, both for generic polytopes and for specific polytopes.
    0 references
    representations of polytopes
    0 references
    matrix factorization
    0 references
    semidefinite programming
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references