KKT Conditions for Constrained NMF

Why KKT Conditions Matter in NMF

Nonnegative matrix factorization (NMF) represents a nonnegative data matrix using two elementwise nonnegative factors. With the Frobenius loss, the factors are chosen to make their product approximate the data. The nonnegativity constraints change the optimization problem: at a boundary value of zero, a factor cannot move in every direction. The Karush–Kuhn–Tucker (KKT) conditions describe the first-order behavior that a constrained local minimum must satisfy.

The earlier material on deriving the Frobenius-norm NMF objective motivates the loss considered here. The focus now is its constrained stationarity conditions. These conditions are important for checking whether a candidate solution is locally stationary and for understanding algorithms that seek such a solution. They do not, by themselves, establish that a candidate is the best factorization among all feasible factors.

Model, Assumptions, and Notation

Let \(X\) be an \(n\times p\) data matrix, and fix a factorization rank \(r\). The factors are \(W\in\mathbb{R}^{n\times r}\) and \(H\in\mathbb{R}^{r\times p}\); thus \(WH\) has the same dimensions as \(X\). In standard NMF, \(X\) is elementwise nonnegative, and both factors are constrained to be elementwise nonnegative. The differentiable objective is

F(W,H)=\frac{1}{2}\|X-WH\|_F^2,\qquad W\geq 0,\quad H\geq 0.

The inequality on a matrix means that every entry satisfies the inequality. The factor \(1/2\) is a convenient scaling: it does not change the minimizers, and it cancels the factor of two in the derivative of a squared norm. Write \(R=WH-X\) for the residual using this sign convention. The derivation below requires only that \(F\) is differentiable; the nonnegative-data assumption is standard for NMF but is not needed to calculate its gradient.

Definition: For a constrained differentiable objective, the KKT conditions consist of primal feasibility, dual feasibility, stationarity of the Lagrangian, and complementary slackness. For elementwise nonnegativity in NMF, these conditions require \(W,H\geq0\), nonnegative constraint multipliers, \(\nabla_W F\) and \(\nabla_H F\) to equal those multipliers, and each factor entry to have zero product with its corresponding gradient entry.

Deriving the Gradients and KKT Conditions

The Frobenius norm is the square root of the sum of squared entries, so \(F=\frac{1}{2}\sum_{i,j}R_{ij}^2\). A small change \(dW\) changes \(WH\) by \(dW H\), and a small change \(dH\) changes \(WH\) by \(W dH\). Therefore,

dF=\langle R,dW H+W dH\rangle_F =\langle R H^T,dW\rangle_F+\langle W^T R,dH\rangle_F,

where \(\langle A,B\rangle_F=\sum_{i,j}A_{ij}B_{ij}\) is the Frobenius inner product. In the second equality, factors are rearranged inside the corresponding scalar trace. By the definition of a gradient under this inner product, the gradients are

\nabla_W F=(WH-X)H^T,\qquad \nabla_H F=W^T(WH-X).

To set the signs of the KKT conditions, write the constraints as \(-W_{ik}\leq0\) and \(-H_{kj}\leq0\). Let \(\Lambda_W\) and \(\Lambda_H\) be their multiplier matrices, with the same dimensions as \(W\) and \(H\). The Lagrangian is

\mathcal{L}(W,H,\Lambda_W,\Lambda_H) =F(W,H)-\langle\Lambda_W,W\rangle_F-\langle\Lambda_H,H\rangle_F.

Stationarity with respect to the two factors gives \(\nabla_W F-\Lambda_W=0\) and \(\nabla_H F-\Lambda_H=0\). Dual feasibility requires \(\Lambda_W,\Lambda_H\geq0\); complementary slackness requires \(W\odot\Lambda_W=0\) and \(H\odot\Lambda_H=0\), where \(\odot\) denotes entrywise multiplication. Substituting the stationarity equations for the multipliers yields the NMF KKT conditions:

\begin{aligned} &W\geq0,\qquad H\geq0,\\ &(WH-X)H^T\geq0,\qquad W^T(WH-X)\geq0,\\ &W\odot\big((WH-X)H^T\big)=0,\\ &H\odot\big(W^T(WH-X)\big)=0. \end{aligned}

Entry by entry, a positive factor entry must have zero corresponding gradient, while a zero factor entry may have a positive gradient. A negative gradient at a zero factor entry violates dual feasibility: moving that entry a small amount into the feasible region can decrease the objective to first order.

For a smooth objective with inequality constraints, KKT conditions are necessary at a local minimum when a suitable constraint qualification holds. Here the constraints are linear coordinate inequalities, and the standard constraint qualification holds at feasible points of the nonnegative orthant. Thus, any local minimum of the joint problem must satisfy these conditions. The objective is not jointly convex in \(W,H\), however, so the conditions are not generally sufficient for a local or global minimum.

Worked Example: Checking Joint KKT Conditions at a Boundary Point

Consider the hypothetical data matrix and rank-one factors

X=\begin{bmatrix}1&0\\0&1\end{bmatrix},\qquad W=\begin{bmatrix}1\\0\end{bmatrix},\qquad H=\begin{bmatrix}1&0\end{bmatrix}.

The factors are nonnegative and their product is \(WH=\begin{bmatrix}1&0\\0&0\end{bmatrix}\). Hence

R=WH-X=\begin{bmatrix}0&0\\0&-1\end{bmatrix}, \qquad F=\frac12\left(0^2+0^2+0^2+(-1)^2\right)=0.5.

The gradients are

\nabla_W F=RH^T =\begin{bmatrix}0&0\\0&-1\end{bmatrix} \begin{bmatrix}1\\0\end{bmatrix} =\begin{bmatrix}0\\0\end{bmatrix}, \qquad \nabla_H F=W^TR =\begin{bmatrix}1&0\end{bmatrix} \begin{bmatrix}0&0\\0&-1\end{bmatrix} =\begin{bmatrix}0&0\end{bmatrix}.

Both gradients are nonnegative, and their entrywise products with the factors are zero. Primal feasibility also holds, so this candidate satisfies the joint KKT conditions. The check establishes first-order stationarity only; it does not, on its own, prove global optimality.

Worked Example: Detecting a KKT Violation

For a one-entry example, let \(X=[4]\), \(W=[0]\), and \(H=[1]\). These factors are feasible, and \(WH=[0]\). The objective is

F(W,H)=\frac12(4-0)^2=8.

Here \(R=WH-X=[-4]\), so

\nabla_W F=RH^T=[-4],\qquad \nabla_H F=W^TR=[0].

Although \(W\odot\nabla_W F=[0]\) and \(H\odot\nabla_H F=[0]\), the \(W\)-gradient is negative. Dual feasibility fails, so the point does not satisfy KKT. This has a direct optimization interpretation: holding \(H=1\) and increasing \(W\) slightly from zero changes the loss to \(\frac12(4-W)^2\), which decreases for \(0<W<4\). Checking complementary slackness alone would have missed this violation.

Complementary Slackness in a Fixed-Factor Problem

A useful way to interpret a positive gradient at a zero factor entry is to fix one factor and optimize the other. For fixed \(H\), the objective is a quadratic function of \(W\). Its Hessian is positive semidefinite, so the resulting constrained problem is convex, and its KKT conditions are sufficient for a global minimum of that subproblem. This differs from optimizing both factors jointly.

Worked Example: A Zero Coefficient With Positive Gradient

Suppose the hypothetical data row is \(X=[0,1]\), and hold the following two-component \(H\) fixed:

H=\begin{bmatrix}1&1\\10&0\end{bmatrix},\qquad W=\begin{bmatrix}0.5&0\end{bmatrix}.

The reconstruction is \(WH=[0.5,0.5]\), so \(R=[0.5,-0.5]\). The objective is

F=\frac12\left((0-0.5)^2+(1-0.5)^2\right) =\frac12(0.25+0.25)=0.25.

For this fixed \(H\), the gradient with respect to \(W\) is

\nabla_W F=RH^T =\begin{bmatrix}0.5&-0.5\end{bmatrix} \begin{bmatrix}1&10\\1&0\end{bmatrix} =\begin{bmatrix}0&5\end{bmatrix}.

Both gradient entries are nonnegative. The first coefficient is positive and has zero gradient; the second coefficient is zero and has positive gradient. Thus both stationarity and complementary slackness hold for the \(W\)-subproblem. Its Hessian is \(HH^T=\begin{bmatrix}2&10\\10&100\end{bmatrix}\), which is positive definite because its leading entry is positive and its determinant is \(2(100)-10(10)=100>0\). The objective is therefore strictly convex in \(W\), making these KKT conditions sufficient for the unique constrained minimum of this fixed-\(H\) subproblem. This check does not establish joint KKT conditions for \(H\), which was held fixed.

Diagnostics, Alternatives, and Limitations

For a computed pair of factors, a direct KKT diagnostic is to calculate both gradients and inspect their signs and entrywise products. In exact arithmetic, primal feasibility, nonnegative gradients, and zero complementary products are the required checks. In numerical work, small deviations are expected, so tolerances should be specified relative to the scale of the factors, gradients, and objective rather than treating every floating-point discrepancy as substantive.

Negative gradient at a zero entry: dual feasibility fails and indicates a feasible direction of first-order decrease.
Nonzero gradient at a positive entry: stationarity fails; an interior coordinate can move in either direction locally.
Nonzero factor-gradient product: complementary slackness fails, even if the signs appear plausible.
Large violations after fitting: may indicate inadequate convergence, an implementation or gradient-sign error, or a candidate that is not stationary.

The KKT conditions are not an optimization algorithm. For a fixed factor, nonnegative least squares or an active-set method can solve the corresponding convex subproblem. Projected-gradient methods and multiplicative-update methods are alternatives for seeking solutions to the constrained factorization; their convergence behavior and implementation details are separate questions. Regardless of the approach, a small reconstruction error is not itself a KKT check, and KKT stationarity is not a global-optimality certificate for joint NMF.

Another limitation is that NMF has multiple feasible factorizations and the joint objective is generally nonconvex. Different starts can lead to different stationary solutions. Therefore, KKT diagnostics should be interpreted alongside the objective value, reconstruction residuals, and sensitivity to initialization, not as evidence that a unique scientifically meaningful factorization has been found.

Key takeaway: For Frobenius-loss NMF, the two factor gradients must be elementwise nonnegative, and each must have zero entrywise product with its factor. These are necessary first-order conditions at a joint local minimum under the stated constraints, but they do not generally guarantee a global solution.

Check Your Understanding

Answer each question, then compare your reasoning with the solutions below.

For \(F(W,H)=\frac12\|X-WH\|_F^2\), state the gradients with respect to \(W\) and \(H\), using \(R=WH-X\).
In the scalar problem \(X=2\), \(W=0\), and \(H=1\), calculate both gradients and decide whether the KKT conditions hold.
At a KKT point, can a zero entry of \(W\) have a strictly positive corresponding gradient? Explain.
Why do joint KKT conditions not generally establish global optimality for NMF?

Solutions. (1) \(\nabla_W F=RH^T\) and \(\nabla_H F=W^TR\), by differentiating the half-squared Frobenius loss. (2) \(R=-2\), so \(\nabla_W F=-2\) and \(\nabla_H F=0\). The negative \(W\)-gradient violates dual feasibility, so KKT fails. (3) Yes. Complementary slackness requires the product of the factor entry and gradient entry to be zero; a zero factor entry can therefore have a positive gradient, provided the gradient is nonnegative. (4) The objective is not generally jointly convex in \(W,H\). KKT conditions are first-order necessary conditions under the constraint qualification, not a guarantee that no better feasible factorization exists.