Nonnegative matrix factorization (NMF) is the problem of decomposing a given nonnegative n × m matrix M into a product of a nonnegative n × d matrix W and a nonnegative d × m matrix H. Restricted NMF requires in addition that the column spaces of M and W coincide. Finding the minimal inner dimension d is known to be NP-hard, both for NMF and restricted NMF. We show that restricted NMF is closely related to a question about the nature of minimal probabilistic automata, posed by Paz in his seminal 1971 textbook. We use this connection to answer Paz's question negatively, thus falsifying a positive answer claimed in 1974. Furthermore, we investigate whether a rational matrix M always has a restricted NMF of minimal inner dimension whose factors W and H are also rational. We show that this holds for matrices M of rank at most 3 and we exhibit a rank-4 matrix for which W and H require irrational entries.  ACM Subject Classification Nonnegative matrix factorization (NMF) is the task of factoring a matrix of nonnegative real numbers M (henceforth a nonnegative matrix) as a product M = W · H such that matrices W and H are also nonnegative. The smallest inner dimension of any such factorization is called the nonnegative rank of M , written rank + (M ). In machine learning, NMF was popularized by the seminal work of Lee and Seung [14] as a tool for finding features in facial-image databases. Since then, NMF has found a broad range of applications-including document clustering, topic modelling, computer vision, recommender systems, bioinformatics, and acoustic signal processing [5, 4, 7, 19, 21, 22]. In applications, matrix M can typically be seen as a matrix of data points: each column of M corresponds to a data point and each row to a feature. Then, computing a nonnegative factorization M = W · H corresponds to expressing the data points (columns of M ) as convex combinations of latent factors (columns of W ), i.e., as linear combinations of latent factors with nonnegative coefficients (columns of H). * Present address: Department of Computer Science, University of Oxford, UK. 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016  From a computational perspective, perhaps the most basic problem concerning NMF is whether a given nonnegative matrix of rational numbers M admits an NMF with inner dimension at most a given number k. Formally, the NMF problem asks whether rank + (M ) ≤ k. In practical applications, various heuristics and local-search algorithms are used to compute an approximate nonnegative factorization, but little is known in terms of their theoretical guarantees. The NMF problem under the separability assumption of Donoho and Stodden [9] is tractable: an NMF M = W · H is called separable if every column of W is also a column of M . In 2012, Arora et al. [2] showed that it is decidable in polynomial time whether a given matrix admits a separable NMF with a given inner dimension. Further progress was made recently, with several efficient algorithms for computing near-separable NMFs [13, 12] . Vavasis [20] showed that the problem of deciding whether the rank of a nonnegative matrix is equal to its nonnegative rank is NP-hard. This result implies that generalizations of this problem, such as the aforementioned NMF problem, the problem of computing the factors W, H (in both exact and approximate versions), and nonnegative rank determination, are also NP-hard. It is not known whether any of these problems are in NP. Vavasis [20] notes that the difficulty in proving membership in NP lies in the fact that a certificate for a positive answer to the NMF problem seems to require the sought factors: a pair of nonnegative matrices W, H such that M = W · H. Related to this, Cohen and Rothblum [8] posed the question of whether, given a nonnegative matrix of rational numbers M , there always exists an NMF M = W · H of inner dimension equal to rank + (M ) such that both W and H are also matrices of rational numbers. A natural route to proving membership of the NMF problem in NP would be to give a positive answer to the question of Cohen and Rothblum (as well as a polynomial bound on the bit-length of the factors W and H). However, the question remains open. Currently the best complexity bound for the NMF problem is membership in PSPACE, which is obtained by translation into the existential theory of real-closed fields [2] . Such a translation shows that one can always choose the entries of W and H to be algebraic numbers. In this work, we focus on the so-called restricted NMF (RNMF) problem, introduced by Gillis and Glineur [11] . The RNMF problem is defined as the NMF problem, except that the column spaces of M and W are required to coincide. (Note that for any NMF, the column space of M is a subspace of the column space of W .) This problem has a natural geometric interpretation as the nested polytope problem (NPP): the problem of finding a minimum-vertex polytope nested between two given convex polytopes. In more detail, for a rank-r matrix M , finding an RNMF with inner dimension d is known to correspond exactly to finding a nested polytope with d vertices in an (r − 1)-dimensional NPP. Our contributions are as follows. We establish a tight connection between NMF and the coverability relation in labelled Markov chains (LMCs). (i, j) th entry. The column space (resp., row space) of M , written Col(M ) (resp., Row(M )), is the vector space spanned by the columns (resp., rows) of M . A matrix is called nonnegative (resp., zero or rational) if so are all its entries. A nonnegative matrix is column-stochastic (resp., row-stochastic) if the element sum of each of its columns (resp., rows) is one. Let F be an ordered field, such as the reals R or the rationals Q. Given a nonnegative matrix M ∈ F such that M is equal to their sum. The nonnegative rank over R will henceforth simply be called nonnegative rank, and will be denoted by rank + (M ). For any nonnegative matrix M ∈ R n×m + , it is easy to see that rank , by removing the zero columns of M and dividing each remaining column by the sum of its elements, we obtain a column-stochastic matrix M with equal nonnegative rank. Similarly, if M = W · H then after removing zero columns in W and multiplying with a suitable diagonal matrix D, H is column-stochastic as well. Thus, without loss of generality one can consider NMFs of column-stochastic matrices into column-stochastic matrices [8, Theorem 3.2]. The NMF problem is NP-hard, even for k = rank(M ) (see [20] ). On the other hand, it is reducible to the existential theory of the reals, hence by [6, 16] it is in PSPACE. For a matrix M ∈ Q n×m + , its nonnegative rank over Q is clearly at least rank + (M ). While those ranks are equal if rank(M ) ≤ 2, a longstanding open question by Cohen and Rothblum asks whether they are always equal [8] . In other words, it is conceivable that there exists a rational matrix M ∈ Q n×m + with rank + (M ) = d that has no rational NMF with inner dimension d. Recently, Shitov [17] exhibited a nonnegative matrix (with irrational entries) whose nonnegative rank over a subfield of R is different from its nonnegative rank over R. if rank(M ) = rank(W ). As we know Col(M ) ⊆ Col(W ) holds for all NMF instances, the condition rank(M ) = rank(W ) is then equivalent to Col(M ) = Col(W ). The restricted nonnegative rank over F of M is the smallest number d ∈ N 0 such that there exists a d-dimensional restricted nonnegative factorization over F of M . Unless indicated otherwise, henceforth we will assume F = R when speaking of the restricted nonnegative rank of M , and denote it by rrank + (M ). We have the following basic properties. Thus, with the above-mentioned NP-hardness result, it follows that the RNMF problem is also NP-hard and in PSPACE. For a matrix M ∈ Q n×m + , its restricted nonnegative rank over Q is clearly at least rrank + (M ). As with nonnegative rank, in general it is not known whether the restricted nonnegative ranks of M over R and over Q are equal. By [8, Theorem 4.1] and Lemma 1, this is true when rank(M ) ≤ 2. RNMF has the following geometric interpretation. For a dimension ∈ N, the convex combination of a set {v 1 , . A set is a polytope if and only if it is a bounded polyhedron. A polytope is full-dimensional (i.e., has volume) if the matrix (A b) ∈ R n×( +1) has rank + 1. Let S ⊆ P be a full-dimensional polytope described by spanning points. The nested polytope problem (NPP) asks, given A, b, S and a number k ∈ N, whether there exist k points that span a polytope Q with S ⊆ Q ⊆ P . Such a polytope Q is called nested between P and S. The following proposition appears as Theorem 1 in [11] . Proposition 2. The RNMF problem and the NPP are interreducible in polynomial time. More specifically, the reductions are as follows. 1. Given a nonnegative matrix M ∈ Q n×m + of rank r, one can compute in polynomial time A ∈ Q n×(r−1) and b ∈ Q n such that P = { x ∈ R r−1 | Ax + b ≥ 0 } is a full-dimensional polytope, and m rational points that span a full-dimensional polytope S ⊆ P such that (a) any d-dimensional RNMF (rational or irrational) of M determines d points that span a polytope Q with S ⊆ Q ⊆ P , and (b) any d points (rational or irrational) that span a polytope Q with Importantly, the correspondences (a) and (b) preserve rationality. In Appendix A we detail the reduction from point 2 above, thereby filling in a small gap in the proof of [11] . Using the geometric interpretation of restricted nonnegative rank it follows easily that, in general, we may have rank(M ) < rank + (M ) < rrank + (M ). Let 3D-cube NPP be the NPP instance where the inner and outer polytope are the standard 3D cube, i.e., The only nested polytope is Q = P . The corresponding restricted NMF problem consists of the following matrix M ∈ R n×n specifies the transition matrices and is such that σ∈Σ µ(σ) is a row-stochastic matrix. The intuitive behaviour of the LMC M is as follows: When M is in state i ∈ [n], it emits label σ and moves to state j, with probability µ(σ) i,j . We extend the function µ to words by defining µ(ε) := I n and µ(σ 1 . . . , it emits w and moves to state j in |w| steps, with probability µ(w) i,j . For i ∈ [n] and w ∈ Σ * , we write pr for the probability that, starting in state i, M emits word w. For example, in Figure 1 we have pr More generally, for a given initial distribution π on the set of states [n] (viewed as a stochastic row vector), we write pr (n) for the probability that M emits word w starting from state distribution π. We omit the superscript M from pr LMCs can be seen as a special case of stochastic sequential machines, a class of probabilistic automata introduced and studied by Paz [15] . More specifically, they are stochastic sequential machines with a singleton input alphabet and Σ as output alphabet. Assuming Proposition 6 we can prove Theorem 5: 6×8 be the matrix from Example 3. Let M = (10, Σ, µ) be the associated LMC from Proposition 6. Since M = I 6 · M is an NMF with inner dimension 6, by Proposition 6 (a) there is an LMC M = (8, Σ, µ ) with M ≥ M. Towards a contradiction, suppose the answer to Question 4 were yes. Then M is also covered by some n * -state LMC M * , where n * ≤ 9, such that M * and M have the same rank. The last sentence of Proposition 6 then implies that rrank + (M ) ≤ 7. But this contradicts the equality rrank + (M ) = 8 from Example 3. Hence, the answer to Question 4 is no. To prove Proposition 6 we adapt a reduction from NMF to the trace-refinement problem in Markov decision processes [10] . Proof sketch of Proposition 6. Let M ∈ Q n×m + be a nonnegative matrix of rank r. As argued in Section 2.1, without loss of generality we may assume that M is column-stochastic and consider factorizations of M into column-stochastic matrices only. We define an LMC M = (m + 2, Σ, µ) with m + 2 states {0, 1, . . . , m, m + 1}. The alphabet is Σ = {a 1 , . . . , a m } ∪ {b 1 , . . . , b n } ∪ { } and the function µ, for all i ∈ [m] and all j ∈ [n], is defined by: and all other entries of µ(a i ), µ(b j ), and µ( ) are 0. See Figure 1 for an example. We have:  and all other entries of µ (a i ), µ (b j ), and µ ( ) are 0. From the NMF M = W · H it follows that we can factor Back M as follows: where the left factor is row-stochastic (as H is column-stochastic), and the right factor equals Back M . It follows that M ≥ M. In this section we consider rational matrices of rank at most 3. We show that for such matrices the restricted nonnegative ranks over R and Q are equal and we give a polynomial-time algorithm that computes a minimal-dimension RNMF over Q.  Using reduction 1 of Proposition 2, we can reduce in polynomial time the RNMF problem for rank-3 matrices to the 2-dimensional NPP, i.e., the nested polygon problem in the plane. As noted in Section 2.2, the correspondence between restricted nonnegative factorizations and nested polygons preserves rationality. Thus to prove Theorem 7 it suffices to prove: Theorem 8. Given polygons S ⊆ P ⊆ R 2 with rational vertices, there exists a minimumvertex polygon Q nested between P and S that also has rational vertices. Moreover there is an algorithm that, given P and S, computes such a polygon in polynomial time in the Turing machine model. In fact, Aggarwal et al. [1] give an algorithm for the 2-dimensional NPP and prove that it runs in polynomial time in the RAM model with unit-cost arithmetic. However, they freely use trigonometric functions and do not address the rationality of the output of the algorithm nor its complexity in the Turing model. To prove Theorem 8 we show that, by adopting a suitable representation of the vertices of a nested polygon, the algorithm in [1] can be adapted so that it runs in polynomial time in the Turing model. We furthermore use this representation to prove that the minimum-vertex nested polygon identified by the resulting algorithm has rational vertices. The remainder of the section is devoted to the proof of Theorem 8. We first recall some terminology from [1] and describe their algorithm. A supporting line segment is a directed line segment, with its initial and final points on the boundary of the outer polygon P , that touches the inner polygon S on its left. A nested polygon with vertices on the boundary of P is said to be supporting if all but at most one of its edges are supporting line segments. A polygon nested between P and S is called minimal if it has the minimum number of vertices among all polygons nested between P and S. It is shown in [1, Lemma 4] that there is always a supporting polygon that is also minimal, and the algorithm given therein outputs such a polygon. Let k be the number of vertices of a minimal nested polygon. Given a vertex v on the boundary of P , there is a uniquely defined supporting polygon Q v with at most k + 1 vertices. To determine Q v one computes the supporting line segments v 1 v 2 , . . . , v k v k+1 , where v 1 = v; see Figure 2 . Then Q v is either the polygon with vertices v 1 , . . . , v k or the polygon with vertices v 1 , . . . , v k+1 . In the first case, Q v is minimal. The idea behind the algorithm of [1] is to search along the boundary of P for an initial vertex v such that Q v is minimal. As a central ingredient for our proof of Theorem 8, we choose a convenient representation of the vertices of supporting polygons. To this end, we assume that the edges of P are oriented counter-clockwise, and we represent a vertex v on an edge pq of P by the unique λ ∈ [0, 1] such that v = (1 − λ)p + λq. We call this the convex representation of v. Similar to [1], we associate with each supporting line segment uv a ray function r, such that if λ is the convex representation of u then r(λ) is the convex representation of v. The same ray function applies for supporting line segments u v with u in a small enough interval containing u. In the following, when we say polynomial time, we mean polynomial time in the Turing model. To obtain a polynomial time bound, the key lemma is as follows: Next we show that if such a solution exists, then there exists a rational solution, which, moreover, can be computed in polynomial time. To this end, let λ * ∈ I be such that s(λ * ) ≥ 0. If λ * is on the boundary of I, then λ * ∈ Q. If λ * is not on the boundary and is not an isolated solution, then there exists a rational solution in its neighbourhood. Lastly, let λ * be an isolated solution not on the boundary. Then, λ * is a root of both s and its derivative s . For every λ ∈ I, we have Taking the derivative of the above equation with respect to λ, we get Since s(λ * ) = s (λ * ) = 0, from (1)  Restricted NMF Requires Irrationality Here we show that the restricted nonnegative ranks over R and Q are, in general, different. Since rank(M ) = rank(W ) = 4, the NMF M = W · H is restricted. This RNMF has been obtained by reducing, according to Proposition 2, an NPP instance, which we now describe. Figure 3 shows the outer 3-dimensional polytope P with 6 faces. The polytope P is the intersection of the following half-spaces: y ≥ 0 (blue), z ≥ 0 (brown), x ≥ 0 (pink), −x + Figure 4 Detailed view of the xy-plane. The outer quadrilateral is one of 6 faces of P , the brown face in Figure 3 . The points s1, s2, s3 are among the 6 points that span the inner polytope S. The points q * 1 , q * 2 , q * 3 are among the 5 points that span the nested polytope Q. The area around q * 1 is zoomed in on the right-hand side. The picture illustrates that q * 1 cannot be moved left on the x-axis without increasing the number of vertices of the nested polytope: A dotted ray from a point slightly to the left of q * 1 is drawn through s1. Its intersection with the line x = 1 is slightly below q * 2 . Following the algorithm of [1], the dotted ray is continued in a similar fashion, "wrapping around" s2 and s3, and ending on the x-axis at around x ≈ 0.2, far left of the starting point. On the other hand, the dashed line illustrates that q * 1 could be moved right (considering only this face). (transparent front). The figure also indicates an interior polytope S spanned by 6 points (black dots): s 1 = ( ) . In the following we discuss possible locations of 5 points q 1 , q 2 , q 3 , q 4 , q 5 that span a nested polytope Q. Since s 1 , s 2 , s 3 all lie on the (brown) face on the xy-plane, but not on a common line, at least 3 of the q i must lie on the xy-plane. A similar statement holds for s 4 , s 5 , s 6 and the xz-plane. So at least one q i , say q 1 , must lie on the x-axis. Suppose another q i , say q 2 , lies on the x-axis. Without loss of generality we can take q 1 = (0, 0, 0) and q 2 = (1, 0, 0) , as all points in P on the x-axis are enclosed by these q 1 , q 2 . Figure 4 provides a detailed view of the xy-plane. To enclose s 2 , some q ∈ {q 3 , q 4 , q 5 } must also lie on the xy-plane and to the right of the line that connects q 2 = (1, 0, 0) and s 2 . To enclose s 3 , some q ∈ {q 3 , q 4 , q 5 } must also lie on the xy-plane and to the left of the line that connects q 1 = (0, 0, 0) and s 3 . If q and q were identical then they would lie outside P -a contradiction. Hence 4 points (namely, q 1 , q 2 , q, q ) are on the xy-plane. This leaves only one point, say q , that is not on the xy-plane. To enclose s 4 (see Figure 9 in Appendix D), point q must lie on the xz-plane and must lie to the right of the line that connects q 2 = (1, 0, 0) and s 4 . To enclose s 6 , point q must lie to the left of the line that connects q 1 = (0, 0, 0) and s 6 . Hence q lies outside P -a contradiction. Hence we have shown that only one point, say q 1 , lies on the x-axis, and two points besides q 1 , say q 2 , q 3 , lie on the xy-plane, and two points besides q 1 , say q 4 , q 5 , lie on the xz-plane. that the x-coordinate of q * 1 must be at least 2 − √ 2. Figure 5 illustrates how to prove the same fact more formally, using the concept of a slack function (see Section 4): The slack function s(λ) for the interval containing 2 − √ 2 has a zero at λ = 2 − √ 2, with a sign change from negative to positive. An inspection of the intervals (of the partition I from Section 4) to the "left" of 2 − √ 2 reveals that none of the corresponding slack functionss satisfiess(λ) ≥ 0 for λ < 2 − √ 2. Similarly, the x-coordinate of q * 1 must be at most 2 −  6 We have shown that an optimal restricted nonnegative factorization of a rational matrix may require factors that have irrational entries. An outstanding open problem is whether the same holds for general nonnegative factorizations. An answer to this question will likely shed light on the issue of whether the nonnegative rank can be computed in NP. Another contribution of the paper has been to develop connections between nonnegative matrix factorization and probabilistic automata, thereby answering an old question concerning the latter. Pursuing this connection, and closely related to the above-mentioned open problem, one can ask whether, given a probabilistic automaton with rational transition probabilities, one can always find a minimal equivalent probabilistic automaton that also has rational transition probabilities. Acknowledgements. The authors would like to thank Michael Benedikt for stimulating discussions, and anonymous referees for their helpful suggestions.
The common part of REF and the present paper finds, in the restricted setting (i.e., where the columns of W and M span the same vector space), a rigid structure that exhibits irrationality.
On Restricted Nonnegative Matrix Factorization
ArXiv
ArXiv
Mathematics Computer Science