At first glance, linear optimization and machine learning matrix factorizations seem to belong to different worlds. One deals with minimizing linear functions over geometric shapes called polytopes; the other deals with breaking down data matrices into interpretable, non-negative components.
Yet, a profound mathematical bridge connects them: slack matrix factorization. This framework reveals that the difficulty of solving an optimization problem and the feasibility of decomposing a dataset are two sides of the same geometric coin. By translating algebraic rank into spatial containment, this paradigm explains not just what makes an optimization or factorization problem hard, but why.
The Geometry of Slack
To understand this connection, we must first visualize a polytope—a high-dimensional generalization of a polygon or polyhedron. A polytope can be defined in two ways:
- From the inside out (Vertices): As the convex hull of its extreme points or corners ($x_1, x_2, \dots, x_n$).
- From the outside in (Facets): As the intersection of half-spaces or flat boundaries defined by linear inequalities ($A_i x \le b_i$).
For any valid polytope, every vertex must lie on the correct side of every facet. If you measure the distance from a specific vertex $j$ to a specific facet $i$, you get a non-negative number called the slack:
$$S_{ij} = b_i - A_i x_j \ge 0$$
If we compute this distance for every pair of facets and vertices, we get a large, non-negative matrix $S$, known as the slack matrix.
Vertices (Columns)
x₁ x₂ x₃ x₄
┌─────────────────┐
f₁ │ 0 4 2 0 │ <- A vertex on the facet
Facets │ 3 0 1 5 │ has a slack of 0.
(Rows) │ 1 2 0 3 │
f₄ │ 0 1 5 2 │
└─────────────────┘
The slack matrix completely encodes the geometric structure of the polytope. If a vertex rests exactly on a facet, their corresponding entry is zero. If it lies deep inside the polytope, the entry is large. Because every entry is greater than or equal to zero, $S$ is inherently a non-negative matrix.
Extended Formulations: The Power of Lifting
Why do we care about factorizing a slack matrix? The answer lies in a powerful geometric trick called an extended formulation or a lift.
Imagine a complex polygon in a two-dimensional plane—say, a regular 20-gon. Describing this shape requires 20 distinct linear inequalities, one for each side. However, if you look at a three-dimensional cube and tilt it just right, its shadow (projection) onto the table can form a complex polygon. The 3D cube is much simpler to describe mathematically than its complex 2D shadow.
In optimization, "lifting" a complicated polytope into a higher-dimensional space can drastically reduce the number of inequalities needed to define it. If we can represent a complex polytope as a projection of a simpler, higher-dimensional shape, we can solve optimization problems over it much faster.
This is where matrix factorization enters the picture. As established by Samuel Fiorini et al. in Linear vs. Semidefinite Extended Formulations: Exponential Separation and Strong Lower Bounds, the non-negative rank of a polytope's slack matrix is exactly equal to the minimum number of facets required to represent that polytope in an extended formulation.
If you can factorize the slack matrix $S$ into two non-negative matrices $W$ and $H$ such that $S = WH$ with an inner dimension $r$, you have effectively proven that the polytope can be "lifted" into a space where it only requires $r$ facets. The authors of Lifting for Simplicity: Concise Descriptions of Convex Sets demonstrate that finding a concise higher-dimensional representation is completely equivalent to this algebraic decomposition.
This equivalence allowed theoretical computer scientists to settle long-standing open problems. For decades, researchers tried to find clever linear programming (LP) relaxations to solve NP-hard problems like the Traveling Salesman Problem (TSP). By proving that the slack matrix of the TSP polytope has an exponential non-negative rank, Samuel Fiorini et al. proved unconditionally that no polynomial-sized linear program can ever solve or perfectly approximate TSP. Similarly, Gábor Braun et al. utilized this connection in The matching polytope does not admit fully-polynomial size relaxation schemes to rule out efficient linear relaxation schemes for the matching problem.
From Linear to Semidefinite Extensions
The power of slack factorization extends beyond standard linear programming. If we change the constraints on the factors of our slack matrix, we can analyze even more powerful optimization paradigms.
Instead of factorizing the slack matrix into non-negative vectors, what if we factorize each entry into the inner product of two positive semidefinite (PSD) matrices?
$$S_{ij} = \text{Tr}(A_i B_j)$$
This defines the positive semidefinite rank (PSD rank). In Positive semidefinite rank, João Gouveia et al. proved that the PSD rank of a slack matrix determines the size of the smallest Semidefinite Program (SDP) needed to represent the polytope.
Because SDPs allow for curved, spectrally constrained feasible regions (spectrahedra), they can compress geometric complexity far better than LPs. As Gábor Braun et al. show in Affine reductions for LPs and SDPs, the non-negative rank dictates LP complexity, while the PSD rank dictates SDP complexity.
To see this compression in action, consider a regular polygon with $n$ sides. Representing it via a standard linear extended formulation requires a number of constraints that scales heavily with $n$. However, by developing numerical algorithms for PSD factorization, Arnaud Vandaele et al. in Algorithms for positive semidefinite factorization provided evidence that the PSD rank of regular polygons scales logarithmically ($\sim \log_2 n$). A shape with thousands of sides can be represented in an SDP using only a handful of dimensions.
The Machine Learning Mirror: The Nested Polytope Problem
While optimization researchers use slack matrices to find lower bounds on complexity, machine learning practitioners encounter the exact same geometry in reverse when using Non-negative Matrix Factorization (NMF).
In NMF, we are given a data matrix $V$ and want to find non-negative latent factors $W$ and $H$ such that $V \approx WH$. François Glineur established a unifying geometric perspective in On the geometric interpretation of the nonnegative rank, proving that computing the non-negative rank of any matrix is equivalent to the Nested Polytope Problem (NPP).
Imagine your data points as vectors in space. Because they are non-negative, they all live inside an outer boundary: the positive orthant (the "outer polytope"). The data points themselves span a smaller, tighter shape (the "inner polytope").
Finding an NMF of rank $r$ means finding an intermediate, nested polytope with exactly $r$ vertices that sandwiches perfectly between the two:
$$\text{Inner Polytope (Data)} \subseteq \text{Intermediate Polytope (Factors)} \subseteq \text{Outer Polytope (Non-negativity)}$$
▲ Outer Polytope (Positive Orthant)
│
│ ┌──────────────┐
│ │ ▲ │
│ │ / \ │
│ │/ \ │
│ │───── Intermediate Polytope (r vertices)
│ /│ \
│ / └───────┘\
│ / Inner \
│ / Polytope \
│ / (Data Hull) \
└────────────────────────►
This geometric "sandwich" explains why NMF behaves so differently from standard linear algebra. For instance, the standard rank of a matrix is identical whether you calculate it using rational numbers or real numbers. But because NMF is governed by the rigid spatial boundaries of nested polytopes, Dmitry Chistikov et al. demonstrated in Nonnegative Matrix Factorization Requires Irrationality that a perfectly rational data matrix can sometimes force its unique intermediate nested polytope to have vertices with irrational coordinates.
Why It Works: Identifiability and Conical Hulls
This geometric interpretation answers the most critical question in unsupervised learning: When is a learned decomposition unique and correct?
If an NMF solution is not unique, an algorithm might output arbitrary, uninterpretable combinations of features instead of the true underlying "parts" of the data. In their seminal paper, David L. Donoho et al. proved in When Does Non-Negative Matrix Factorization Give a Correct Decomposition into Parts? that NMF yields a unique, identifiable solution when the data points are sufficiently "spread out" to tightly pin down the boundaries of the intermediate simplicial cone.
When the data includes points that lie exactly on the extreme rays of this cone—a condition known as separability—the intermediate polytope's vertices are directly exposed as actual columns in our dataset. Abhishek Kumar et al. turned this geometric insight into highly scalable algorithms in Fast Conical Hull Algorithms for Near-separable Non-negative Matrix Factorization. Instead of solving heavy optimization problems, their approach treats NMF as an iterative geometric search to locate the extreme rays of the data's conical hull.
Even when the entire matrix cannot be uniquely decomposed, the nested polytope framework allows us to find pockets of certainty. As Nicolas Gillis et al. showed in Partial Identifiability for Nonnegative Matrix Factorization, if certain facets of the inner data polytope intersect or align perfectly with the outer non-negativity boundaries, specific latent features become locked into place. This guarantees that individual columns of the decomposition are physically meaningful ground truths, even if the rest of the system remains geometrically ambiguous.
Key Foundational Work
When Does Non-Negative Matrix Factorization Give a Correct Decomposition into Parts? (2003) — contributed 1 concept elements to this direction.
Group theoretical investigations of daylight spectra (2004) — contributed 1 concept elements to this direction.