Critical points and Euclidean distance degrees of low-rank approximation with zeros: the Kubjas–Sodomaco–Tsigaridas conjectures

Low-rank approximation with zeros asks for a matrix of rank at most $r$ whose entries vanish on a prescribed set $S$ of positions and which minimizes the Frobenius (entrywise Euclidean) distance to a data matrix $U$. Its complex critical points govern exact algebraic solution methods, and their generic number — the Euclidean distance degree (ED degree) of the variety $\mathcal{L}_r^S$ of bounded-rank matrices with zero pattern $S$ — measures the algebraic complexity of writing the exact optimizer as a function of $U$. Kubjas, Sodomaco and Tsigaridas (Linear Algebra Appl. 2022) proved that the critical points always lie in an explicit linear "critical space" $H_U^S$ and computed many ED degrees, but left their central statements open. This problem asks to settle them: the conjecture that the critical points span the critical space exactly when $\mathcal{L}_r^S$ is irreducible (Conjecture 4.4); the conjectured determinantal affine relations satisfied by critical points of irreducible sections (Conjecture 4.15); the conjectural closed-form ED-degree formulas for diagonal zero patterns in general, square, and symmetric formats (Conjectures 5.1, 5.2, 5.4, 5.6); and the question of which zero patterns can occur at best nonnegative rank-two approximations (Question 6.3). No resolution of these statements is known in the literature to date.

Background

The best rank-$r$ approximation problem asks for a matrix of rank at most $r$ minimizing the squared Frobenius distance $d_U(X)=\sum_{i,j}(x_{ij}-u_{ij})^2$ to a given data matrix $U$. The classical Eckart–Young theorem solves it: the optimum is the truncated singular value decomposition (SVD) of $U$, and every complex critical point of $d_U$ on the variety $\mathcal{X}_r$ of matrices of rank at most $r$ is a sum of $r$ spectral components of $U$; for generic $U$ of rank $k$ there are $\binom{k}{r}$ of them, they all lie in the span of the rank-one spectral components, and each is a $\{0,1\}$-combination of a fixed basis of that span.

Kubjas, Sodomaco and Tsigaridas (2022) studied the structured variant in which a prescribed set of entries is forced to be zero. For a zero pattern $S\subset[m]\times[n]$ (where $[k]=\{1,\dots,k\}$ for a positive integer $k$), let $\mathcal{L}^S=\{X : x_{ij}=0\ \text{for}\ (i,j)\in S\}$ be the coordinate subspace and $\mathcal{L}_r^S=\mathcal{X}_r\cap\mathcal{L}^S$ the variety of bounded-rank matrices with zeros at $S$; the optimization problem is minimizing $d_U$ over $\mathcal{L}_r^S$. Unlike the generic linear sections treated by Ottaviani–Spaenlehauer–Sturmfels (2014), coordinate sections are non-generic: $\mathcal{L}_r^S$ is typically singular and often reducible (a complex algebraic variety is irreducible when it cannot be written as a union of two proper closed subsets), so the available intersection-theoretic tools fail. For generic complex $U$, the number of complex critical points of $d_U$ on $\mathcal{L}_r^S$ is constant; it is the Euclidean distance degree $\mathrm{EDdegree}(\mathcal{L}_r^S)$, an invariant introduced by Draisma–Horobet–Ottaviani–Sturmfels–Thomas that measures the algebraic complexity of writing the optimal solution as a function of $U$.

For rank one the problem becomes combinatorial: critical points correspond to the minimal covers of the zero pattern (equivalently, minimal vertex covers of the bipartite graph with an edge for each entry of $S$, i.e. each position forced to zero), and counting them is #P-complete in general. For rank $r\ge 2$ the paper proves two structural results. First (Theorem 4.3), the linear span $\langle Z_{U,r}^S\rangle$ of the set $Z_{U,r}^S$ of critical points of $d_U$ on $\mathcal{L}_r^S$ is always contained in a linear space $H_U^S$, the critical space, cut out by explicit linear equations: the row relations $r_U^{(i,j)}(X)=(XU^T-UX^T)_{ij}=0$ for pairs of rows whose corresponding rows in the mask matrix of $S$ (the 0/1 indicator matrix of the zero pattern) coincide, the analogous column relations, and the vanishing coordinates $x_{ij}$ for $(i,j)\in S$. Second (Corollary 4.8), the codimension of $H_U^S$ is given by an explicit combinatorial formula. In the unstructured case $S=\emptyset$ this containment is an equality, the rank-one critical points form a basis of $H_U$, and the rank-$r$ critical points have coefficients in $\{0,1\}$; with zeros there are generally too few rank-one critical points, and whether the rank-$r$ critical points span all of $H_U^S$ becomes a genuine question. The paper also studies affine relations: in the unstructured square case the critical points satisfy $\langle X, C(U)\rangle_F - r\det(U)=0$, where $C(U)$ is the cofactor matrix and $\langle\cdot,\cdot\rangle_F$ is the Frobenius inner product; the structured analogue is conjectural.

The problem is motivated by nonnegative matrix factorization (NMF): a matrix has nonnegative rank at most $r$ when it factors as a product of two nonnegative matrices, and the best nonnegative rank-$r$ approximation of $U$ is found among the critical points of $d_U$ on $\mathcal{L}_r^S$ over all zero patterns $S$ (an optimum is either an interior critical point or lies on the boundary, where entries vanish). For $3\times 3$ matrices and $r=2$ the paper shows that a finite list of 756 critical points suffices to compute the best nonnegative rank-2 approximation exactly, and a 100,000-sample experiment suggests that optimal nonnegative approximations have at most two zeros, never aligned in one row or column.

Problem Statement

Settle the conjectures and questions that Kubjas–Sodomaco–Tsigaridas left open on the critical points of low-rank approximation with zeros — that is, prove or refute each of the following statements, correcting it with explicit counterexamples and corrected hypotheses where it is false. Throughout we adopt the source's convention $m\le n$ (the case $m>n$ being obtained by transposition), so that the rank range in (1) is binding and the index set $I$ in (2) is non-vacuous. Parts (1)-(4) are independent objectives: each is settled on its own, and a correct settlement of any one part (whether by proof or by counterexample with corrected hypotheses) is a self-contained result, while a full resolution of the task settles all four.

(1) (Conjecture 4.4) For every zero pattern $S\subset[m]\times[n]$, every $U\in\mathbb{R}^{m\times n}$ and every $r\in[m-1]$, the linear span of the critical points of $d_U$ on $\mathcal{L}_r^S$ equals the critical space, $\langle Z_{U,r}^S\rangle=H_U^S$, if and only if the variety $\mathcal{L}_r^S$ is irreducible.

(2) (Conjecture 4.15) If $\mathcal{L}_r^S$ is irreducible, then for every subset $I\subset[n]$ with $|I|=m$, the complex critical points $X$ of $d_U$ on $\mathcal{L}_r^S$ satisfy the affine relation $\langle X_{[m],I},\,C(U_{[m],I})\rangle_F-r\det(U_{[m],I})=0$ if and only if $S\cap([m]\times I)=\emptyset$, where $X_{[m],I}$ and $U_{[m],I}$ are the $m\times m$ submatrices on all rows and the columns $I$, and $C$ denotes the cofactor matrix.

(3) (ED-degree formulas, diagonal zero patterns $S=\{(1,1),\dots,(s,s)\}$): (Conjecture 5.1) $\mathrm{EDdegree}(\mathcal{L}_{n-1}^S)=5(n-1)-2$ for $s=1$ in $n\times n$ matrices; (Conjecture 5.2) for $\mathcal{L}_2^S\subset\mathbb{C}^{m\times n}$, $s\in[4]$, $l=\min(m,n)$: $\mathrm{EDdegree}(\mathcal{L}_2^S)=3(l-1)^2-2(l-1)$ if $s=1$; $18(l-2)^2+6(l-2)+1$ if $s=2$ and $m\ne n$; $18(l-2)^2+10(l-2)+1$ if $s=2$ and $m=n$; $108(l-3)^2+144(l-3)+30$ if $s=3$ and $m=n$; $648(l-4)^2+1600(l-4)+488$ if $s=4$ and $m=n$; (Conjecture 5.4) for square formats and $s\ge2$: $\mathrm{EDdegree}(\mathcal{L}_2^S)=3^s\,2^{s-1}(n-s)^2+s^{s-1}(s+1)^{\lceil s/2\rceil}(n-s)+c$ for some constant $c$; (Conjecture 5.6) for symmetric $n\times n$ matrices: $\mathrm{EDdegree}(\mathcal{L}_2^S)=3(n-1)-2$, $9(n-2)-2$, $27(n-3)+4$, $81(n-4)+28$ for $s=1,2,3,4$ respectively.

(4) (Question 6.3, nonnegative approximation) (1) Do the experimental observations (a) that no best nonnegative rank-2 approximation of a nonnegative $3\times3$ matrix has three zeros or two zeros in the same row or column, and (b) that whenever the best nonnegative rank-2 approximation has zero pattern $S$ the best rank-2 approximation given by the SVD has negative entries in $S$, hold for every nonnegative $U\in\mathbb{R}^{3\times3}_{\ge0}$? (2) Does the sign relation (b) hold for nonnegative matrices of every format $m\times n$? (3) Characterize the pairs (zero pattern $S\subset[m]\times[n]$, rank $r\in[m-1]$) for which there exists a full-rank nonnegative matrix $U\in\mathbb{R}^{m\times n}_{\ge0}$ whose best nonnegative rank-$r$ approximation has zero pattern $S$.

These components serve one objective — a complete exact-solution theory for low-rank approximation with zeros: (1) and (2) describe where the critical points lie (linear and affine structure), (3) counts them, and (4) locates the global optimum of the nonnegative variant, which is selected among exactly these critical points.

References

1. Kaie Kubjas, Luca Sodomaco, Elias Tsigaridas. Exact solutions in low-rank approximation with zeros. Linear Algebra and its Applications 641 (2022) 67–97. DOI: 10.1016/j.laa.2022.01.021; arXiv:2010.15636. https://arxiv.org/abs/2010.15636; Zbl 1485.14101
2. Laurenţiu G. Maxim, Jose Israel Rodriguez, Botong Wang. Euclidean distance degree defect of singular projective varieties. Preprint, 2026. arXiv:2605.13726. https://arxiv.org/abs/2605.13726
3. Jan Draisma, Emil Horobet, Giorgio Ottaviani, Bernd Sturmfels, Rekha R. R. Thomas. The Euclidean distance degree of an algebraic variety. Foundations of Computational Mathematics 16 (2016) 99–149. DOI: 10.1007/s10208-014-9240-x; arXiv:1309.0049. https://arxiv.org/abs/1309.0049
4. Giorgio Ottaviani, Pierre-Jean Spaenlehauer, Bernd Sturmfels. Exact solutions in structured low-rank approximation. SIAM Journal on Matrix Analysis and Applications 35 (2014) 1521–1542. DOI: 10.1137/13094520X; arXiv:1311.2376. https://arxiv.org/abs/1311.2376
5. Carl Eckart, Gale Young. The approximation of one matrix by another of lower rank. Psychometrika 1 (1936) 211–218. DOI: 10.1007/BF02288367. https://doi.org/10.1007/BF02288367
6. Luca Sodomaco, Ettore Teixeira Turatti. The span of singular tuples of a tensor beyond the boundary format. Journal of Symbolic Computation 120 (2024), article 102230. DOI: 10.1016/j.jsc.2023.102230; arXiv:2206.08606. https://arxiv.org/abs/2206.08606
7. Ettore Teixeira Turatti, Emanuele Ventura. On defective spans of singular vector tuples beyond the boundary format. Preprint, 2026. arXiv:2605.22118. https://arxiv.org/abs/2605.22118
8. Khazhgali Kozhasov, Alan Muniz, Yang Qi, Luca Sodomaco. On the minimal algebraic complexity of the rank-one approximation problem for general inner products. Mathematics of Computation (2025). DOI: 10.1090/mcom/4176; arXiv:2309.15105. https://arxiv.org/abs/2309.15105
9. Etna Lindy, Vanni Noferini, Paul Van Dooren. On rank-2 Nonnegative Matrix Factorizations and their variants. Preprint, 2025. arXiv:2507.20612. https://arxiv.org/abs/2507.20612