Exploiting ideal-sparsity in the generalized moment problem with application to matrix factorization ranks

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F24%3A00370382" target="_blank" >RIV/68407700:21230/24:00370382 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1007/s10107-023-01993-x" target="_blank" >https://doi.org/10.1007/s10107-023-01993-x</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/s10107-023-01993-x" target="_blank" >10.1007/s10107-023-01993-x</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Exploiting ideal-sparsity in the generalized moment problem with application to matrix factorization ranks

Popis výsledku v původním jazyce

We explore a new type of sparsity for the generalized moment problem (GMP) that we call ideal-sparsity. In this setting, one optimizes over a measure restricted to be supported on the variety of an ideal generated by quadratic bilinear monomials. We show that this restriction enables an equivalent sparse reformulation of the GMP, where the single (high dimensional) measure variable is replaced by several (lower dimensional) measure variables supported on the maximal cliques of the graph corresponding to the quadratic bilinear constraints. We explore the resulting hierarchies of moment-based relaxations for the original dense formulation of GMP and this new, equivalent ideal-sparse reformulation, when applied to the problem of bounding nonnegative- and completely positive matrix factorization ranks. We show that the ideal-sparse hierarchies provide bounds that are at least as good (and often tighter) as those obtained from the dense hierarchy. This is in sharp contrast to the situation when exploiting correlative sparsity, as is most common in the literature, where the resulting bounds are weaker than the dense bounds. Moreover, while correlative sparsity requires the underlying graph to be chordal, no such assumption is needed for ideal-sparsity. Numerical results show that the ideal-sparse bounds are often tighter and much faster to compute than their dense analogs.

Název v anglickém jazyce

Exploiting ideal-sparsity in the generalized moment problem with application to matrix factorization ranks

Popis výsledku anglicky

We explore a new type of sparsity for the generalized moment problem (GMP) that we call ideal-sparsity. In this setting, one optimizes over a measure restricted to be supported on the variety of an ideal generated by quadratic bilinear monomials. We show that this restriction enables an equivalent sparse reformulation of the GMP, where the single (high dimensional) measure variable is replaced by several (lower dimensional) measure variables supported on the maximal cliques of the graph corresponding to the quadratic bilinear constraints. We explore the resulting hierarchies of moment-based relaxations for the original dense formulation of GMP and this new, equivalent ideal-sparse reformulation, when applied to the problem of bounding nonnegative- and completely positive matrix factorization ranks. We show that the ideal-sparse hierarchies provide bounds that are at least as good (and often tighter) as those obtained from the dense hierarchy. This is in sharp contrast to the situation when exploiting correlative sparsity, as is most common in the literature, where the resulting bounds are weaker than the dense bounds. Moreover, while correlative sparsity requires the underlying graph to be chordal, no such assumption is needed for ideal-sparsity. Numerical results show that the ideal-sparse bounds are often tighter and much faster to compute than their dense analogs.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10102 - Applied mathematics

Projekt

<a href="/cs/project/GJ20-11626Y" target="_blank" >GJ20-11626Y: Koncept Koopmanova operátoru pro řízení komplexních nelineárních dynamických systémů</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2024

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Mathematical Programming

ISSN

0025-5610

e-ISSN

1436-4646

Svazek periodika

205

Číslo periodika v rámci svazku

1-2

Stát vydavatele periodika

DE - Spolková republika Německo

Počet stran výsledku

42

Strana od-do

703-744

Kód UT WoS článku

001021517900001

EID výsledku v databázi Scopus

2-s2.0-85164161074