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

^*Corresponding author for this work

Research output: Contribution to journal › Article › Scientific › peer-review

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.

Original language	English
Pages (from-to)	67-97
Number of pages	31
Journal	Linear Algebra and Its Applications
Volume	641
DOIs	https://doi.org/10.1016/j.laa.2022.01.021
Publication status	Published - 15 May 2022
MoE publication type	A1 Journal article-refereed

Keywords

Euclidean distance degree
Nonnegative matrix factorization
Structured low-rank approximation
Zero patterns

Access to Document

10.1016/j.laa.2022.01.021

https://arxiv.org/abs/2010.15636

Cite this

@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

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

-: Algebraic geometry of hidden variable models in statistics

Science-IT

Cite this

Exact solutions in low-rank approximation with zeros

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Projects

-: Algebraic geometry of hidden variable models in statistics

Equipment

Science-IT

Cite this