×

Nonnegative rank depends on the field. (English) Zbl 1465.15044

A real \(m\times n\) matrix is said to be nonnegative when its entries are nonnegative. We denote by rank\((A)\) the rank (i.e., the column space) of a matrix \(A\). Let \(A\) be a nonnegative matrix. The nonnegative rank of \(A\) is the smallest \(k\) for which \(A\) can be written as a product \(A=BC\) of two nonnegative matrices \(B\) and \(C\) of dimensions \( m\times k\) and \(k\times n \), respectively. Let \(\mathbb{F}\) be a subfield of \(\mathbb{R}\) and let \(\operatorname{rank}_{+}(A,\mathbb{F})\) denote the smallest integer \(k\) such that \(A\) can be written as a sum of \(k\) rank-one matrices with nonnegative entries in \(\mathbb{F}\). Note that \(\operatorname{rank}_{+}(A,\mathbb{R})\) corresponds to the nonnegative rank of \(A\).
The author provides an example of a subfield \(\mathbb{F\subset R}\) and a nonnegative matrix \(A\) with entries in \(\mathbb{F}\) such that \[ 5 = \operatorname{rank}(A) = \operatorname{rank}_{+}(A,\mathbb{R}) < \operatorname{rank}_{+}(A,\mathbb{F} ) = 6. \tag{\(\ast\)} \]
To show the existence of such a matrix \(A\), the author proves the following:
Theorem. There exists a field \(\mathbb{F\subset R}\) and polytopes \(P,Q\subset \mathbb{R}^{4}\) such that:
(1)
The vertices of both \(P\) and \(Q\) have coordinates in \(\mathbb{F}\);
(2)
\(\dim P=4\) and \(P\subset Q\);
(3)
There is a \(4\)-simplex \(\Delta \) satisfying \(P\subset \Delta \subset Q\);
(4)
Every such \(\Delta \) has a vertex where not all of whose coordinates belong to \(\mathbb{F}\).

The paper has five sections. In the introduction, the author gives a motivation and explains why the theorem above implies the existence of \(A\) as in (\(\ast\)). In Section 2, the author computes several numbers used in the description of the polytopes \(P\), \(Q,\) and \(\Delta \). In Section \(3\), the author describes these polytopes and proves items (1)–(3) of the above theorem. The author concludes the proof of the theorem in Section 4. Since the proof of the theorem requires some computer calculations, the author often refers in Sections 2–4 to given Wolfram Mathematica files attached to the current version of this paper on arXiv [the author, “Nonnegative rank depends on the field”, Preprint, arXiv:1505.01893]. The author concludes the paper with an open problem.

MathOverflow Questions:

Polynomial with two repeated roots

MSC:

15B48 Positive matrices and their generalizations; cones of matrices
15A03 Vector spaces, linear dependence, rank, lineability
15A23 Factorization of matrices
52B12 Special polytopes (linear programming, centrally symmetric, etc.)
52B40 Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.)

References:

[1] Chi, E.; Kolda, T., On tensors, sparsity, and nonnegative factorizations, SIAM J. Matrix Anal. A., 33, IV, 1272-1299 (2012) · Zbl 1262.15029 · doi:10.1137/110859063
[2] Chistikov, D.; Kiefer, S.; Marušić, I.; Shirmohammadi, M.; Worrell, J., Nonnegative matrix factorization requires irrationality, SIAM J. Appl. Algebra Geometry, 1, 285-307 (2017) · Zbl 1369.15020 · doi:10.1137/16M1078835
[3] Cohen, JE; Rothblum, UG, Nonnegative ranks, decompositions, and factorizations of nonnegative matrices, Linear Algebra Appl., 190, 149-168 (1993) · Zbl 0784.15001 · doi:10.1016/0024-3795(93)90224-C
[4] Eggermont, RH; Horobet, E.; Kubjas, K., Algebraic boundary of matrices of nonnegative rank at most three, Linear Algebra Appl., 508, 62-80 (2016) · Zbl 1350.13009 · doi:10.1016/j.laa.2016.06.036
[5] Févotte, C.; Bertin, N.; Durrieu, JL, Nonnegative matrix factorization with the Itakura-Saito divergence: with application to music analysis, Neural Comput., 21, III, 793-830 (2009) · Zbl 1156.94306 · doi:10.1162/neco.2008.04-08-771
[6] Fiorini, S.; Kaibel, V.; Pashkovich, K.; Theis, DO, Combinatorial bounds on nonnegative rank and extended formulations, Discrete Math., 313, 67-83 (2013) · Zbl 1259.90111 · doi:10.1016/j.disc.2012.09.015
[7] Fiorini, S., Massar, S., Pokutta, S., Tiwary, H. R., de Wolf, R.: Linear vs. semidefinite extended formulations: exponential separation and strong lower bounds, In: Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing, ACM (2012) · Zbl 1286.90125
[8] Gillis, N., The why and how of nonnegative matrix factorization, Regul. Optim. Kernels Support Vector Mach., 12, 257 (2014)
[9] Gillis, N.; Glineur, F., On the geometric interpretation of the nonnegative rank, Linear Algebra Appl., 437, 2685-2712 (2012) · Zbl 1258.65039 · doi:10.1016/j.laa.2012.06.038
[10] Krone, R., Kubjas, K.: Nonnegative rank four boundaries, preprint (2019) arXiv:1902.02868
[11] Kubjas, K.; Robeva, E.; Sturmfels, B., Fixed points of the EM algorithm and nonnegative rank boundaries, Ann. Stat., 43, I, 422-461 (2015) · Zbl 1308.62035 · doi:10.1214/14-AOS1282
[12] Lee, DD; Seung, HS, Learning the parts of objects by non-negative matrix factorization, Nature, 401, 788-791 (1999) · Zbl 1369.68285 · doi:10.1038/44565
[13] Moitra, A.: An almost optimal algorithm for computing nonnegative rank. In: Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM (2013) · Zbl 1422.68130
[14] Rote, G.: The algebraic conspiracy (joint work with M. Abrahamsen), In: Oberwolfach Reports, Volume 14, EMS Publishing House, pp. 1180-1182 (2017)
[15] Shitov, Y.: Nonnegative rank depends on the field, preprint (2015) arXiv:1505.01893v1
[16] Shitov, Y.: A universality theorem for nonnegative matrix factorizations, preprint (2016) arXiv:1606.09068
[17] Shitov, Y., The nonnegative rank of a matrix: Hard problems, easy solutions, SIAM Rev., 59, 794-800 (2017) · Zbl 1377.15003 · doi:10.1137/16M1080999
[18] Shitov, Y., Matrices of bounded psd rank are easy to detect, SIAM J. Optim., 28, 2067-2072 (2018) · Zbl 1395.68155 · doi:10.1137/17M1141345
[19] Speyer, D.: Re: Polynomial with two repeated roots, mathoverflow.net/a/13675
[20] Vavasis, SA, On the complexity of nonnegative matrix factorization, SIAM J. Optim., 20, III, 1364-1377 (2009) · Zbl 1206.65130
[21] Yannakakis, M., Expressing combinatorial optimization problems by linear programs, J. Comput. Syst. Sci., 43, III, 441-466 (1991) · Zbl 0748.90074 · doi:10.1016/0022-0000(91)90024-Y
[22] http://bit.ly/2sOl57M
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.