Worst-case results for positive semidefinite rank (Q745690): Difference between revisions

From MaRDI portal
Set OpenAlex properties.
Normalize DOI.
 
(3 intermediate revisions by 3 users not shown)
Property / DOI
 
Property / DOI: 10.1007/s10107-015-0867-4 / rank
Normal rank
 
Property / arXiv ID
 
Property / arXiv ID: 1305.4600 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4210476 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Approximation Limits of Linear Programs (Beyond Hierarchies) / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the Existence of 0/1 Polytopes with High Semidefinite Extension Complexity / rank
 
Normal rank
Property / cites work
 
Property / cites work: Nonnegative ranks, decompositions, and factorizations of nonnegative matrices / rank
 
Normal rank
Property / cites work
 
Property / cites work: Lower bounds on nonnegative rank via nonnegative nuclear norms / rank
 
Normal rank
Property / cites work
 
Property / cites work: Combinatorial bounds on nonnegative rank and extended formulations / rank
 
Normal rank
Property / cites work
 
Property / cites work: Linear vs. semidefinite extended formulations / rank
 
Normal rank
Property / cites work
 
Property / cites work: Extended formulations for polygons / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the geometric interpretation of the nonnegative rank / rank
 
Normal rank
Property / cites work
 
Property / cites work: Lifts of Convex Sets and Cone Factorizations / rank
 
Normal rank
Property / cites work
 
Property / cites work: Polytopes of minimum positive semidefinite rank / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4044675 / rank
 
Normal rank
Property / cites work
 
Property / cites work: An Almost Optimal Algorithm for Computing Nonnegative Rank / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the computational complexity and geometry of the first-order theory of the reals. I: Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the reals / rank
 
Normal rank
Property / cites work
 
Property / cites work: An upper bound for nonnegative rank / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the Complexity of Nonnegative Matrix Factorization / rank
 
Normal rank
Property / cites work
 
Property / cites work: Handbook of semidefinite programming. Theory, algorithms, and applications / rank
 
Normal rank
Property / cites work
 
Property / cites work: Expressing combinatorial optimization problems by linear programs / rank
 
Normal rank
Property / DOI
 
Property / DOI: 10.1007/S10107-015-0867-4 / rank
 
Normal rank

Latest revision as of 02:55, 10 December 2024

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