Exact solutions in low-rank approximation with zeros

Kaie Kubjas; Luca Sodomaco; Elias Tsigaridas

doi:10.1016/j.laa.2022.01.021

Exact solutions in low-rank approximation with zeros

Kaie Kubjas, Luca Sodomaco^*, Elias Tsigaridas

^*Tämän työn vastaava kirjoittaja

Tutkimustuotos: Lehtiartikkeli › Article › Scientific › vertaisarvioitu

Abstrakti

Low-rank approximation with zeros aims to find a matrix of fixed rank and with a fixed zero pattern that minimizes the Euclidean distance to a given data matrix. We study the critical points of this optimization problem using algebraic tools. In particular, we describe special linear, affine, and determinantal relations satisfied by the critical points. We also investigate the number of critical points and how this number is related to the complexity of nonnegative matrix factorization problem.

Alkuperäiskieli	Englanti
Sivut	67-97
Sivumäärä	31
Julkaisu	Linear Algebra and Its Applications
Vuosikerta	641
DOI - pysyväislinkit	https://doi.org/10.1016/j.laa.2022.01.021
Tila	Julkaistu - 15 toukok. 2022
OKM-julkaisutyyppi	A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä

Pääsy asiakirjaan

10.1016/j.laa.2022.01.021

https://arxiv.org/abs/2010.15636

Muut tiedostot ja linkit

Linkki julkaisuun Scopuksessa

-: Algebraic geometry of hidden variable models in statistics
Kubjas, K. (Vastuullinen tutkija)
01/09/2019 → 31/08/2023
Projekti: Academy of Finland: Other research funding

Science-IT
Hakala, M. (Manager)
Perustieteiden korkeakoulu
Laitteistot/tilat: Facility

Siteeraa tätä

@article{147fa5981a3e43d6b4f2d4b3b0be5609,

title = "Exact solutions in low-rank approximation with zeros",

abstract = "Low-rank approximation with zeros aims to find a matrix of fixed rank and with a fixed zero pattern that minimizes the Euclidean distance to a given data matrix. We study the critical points of this optimization problem using algebraic tools. In particular, we describe special linear, affine, and determinantal relations satisfied by the critical points. We also investigate the number of critical points and how this number is related to the complexity of nonnegative matrix factorization problem.",

keywords = "Euclidean distance degree, Nonnegative matrix factorization, Structured low-rank approximation, Zero patterns",

author = "Kaie Kubjas and Luca Sodomaco and Elias Tsigaridas",

note = "Funding Information: We thank Giorgio Ottaviani, Gr{\'e}goire Sergeant-Perthuis, Pierre-Jean Spaenlehauer, and Bernd Sturmfels for helpful discussions and suggestions. We thank two anonymous reviewers for insightful comments which improved the original manuscript. Kaie Kubjas and Luca Sodomaco are partially supported by the Academy of Finland Grant No. 323416 . Elias Tsigaridas is partially supported by ANR JCJC GALOP ( ANR-17-CE40-0009 ), the PGMO grant ALMA , and the PHC GRAPE . Publisher Copyright: {\textcopyright} 2022 Elsevier Inc.",

year = "2022",

month = may,

day = "15",

doi = "10.1016/j.laa.2022.01.021",

language = "English",

volume = "641",

pages = "67--97",

journal = "Linear Algebra and Its Applications",

issn = "1873-1856",

publisher = "Elsevier",

}

TY - JOUR

T1 - Exact solutions in low-rank approximation with zeros

AU - Kubjas, Kaie

AU - Sodomaco, Luca

AU - Tsigaridas, Elias

N1 - Funding Information: We thank Giorgio Ottaviani, Grégoire Sergeant-Perthuis, Pierre-Jean Spaenlehauer, and Bernd Sturmfels for helpful discussions and suggestions. We thank two anonymous reviewers for insightful comments which improved the original manuscript. Kaie Kubjas and Luca Sodomaco are partially supported by the Academy of Finland Grant No. 323416 . Elias Tsigaridas is partially supported by ANR JCJC GALOP ( ANR-17-CE40-0009 ), the PGMO grant ALMA , and the PHC GRAPE . Publisher Copyright: © 2022 Elsevier Inc.

PY - 2022/5/15

Y1 - 2022/5/15

N2 - Low-rank approximation with zeros aims to find a matrix of fixed rank and with a fixed zero pattern that minimizes the Euclidean distance to a given data matrix. We study the critical points of this optimization problem using algebraic tools. In particular, we describe special linear, affine, and determinantal relations satisfied by the critical points. We also investigate the number of critical points and how this number is related to the complexity of nonnegative matrix factorization problem.

AB - Low-rank approximation with zeros aims to find a matrix of fixed rank and with a fixed zero pattern that minimizes the Euclidean distance to a given data matrix. We study the critical points of this optimization problem using algebraic tools. In particular, we describe special linear, affine, and determinantal relations satisfied by the critical points. We also investigate the number of critical points and how this number is related to the complexity of nonnegative matrix factorization problem.

KW - Euclidean distance degree

KW - Nonnegative matrix factorization

KW - Structured low-rank approximation

KW - Zero patterns

UR - http://www.scopus.com/inward/record.url?scp=85123863641&partnerID=8YFLogxK

U2 - 10.1016/j.laa.2022.01.021

DO - 10.1016/j.laa.2022.01.021

M3 - Article

AN - SCOPUS:85123863641

SN - 1873-1856

VL - 641

SP - 67

EP - 97

JO - Linear Algebra and Its Applications

JF - Linear Algebra and Its Applications

ER -

Exact solutions in low-rank approximation with zeros

Abstrakti

Pääsy asiakirjaan

Muut tiedostot ja linkit

Sormenjälki

Projektit

-: Algebraic geometry of hidden variable models in statistics

Laitteet

Science-IT

Siteeraa tätä