Projected Gradient Methods for NMF

Why Projected Gradient for NMF?

Non-negative matrix factorization (NMF) seeks nonnegative factors whose product approximates a nonnegative data matrix. The earlier material on Alternating Nonnegative Least Squares explains how one factor can be optimized while the other is held fixed. Projected gradient offers another way to perform those block updates: take a gradient step, then project the result back onto the nonnegative constraint set.

The projection is simple, but it does not make step-size choice optional. A step that is too large can increase the reconstruction error or make iterates oscillate. A step that is unnecessarily small can make progress very slow. The useful feature is that, with the appropriate step size for a fixed block, a standard descent guarantee is available.

Definition: Let $X\in\mathbb{R}^{m\times n}$ be a data matrix and let $r$ be the chosen factorization rank. NMF approximates $X$ by $WH$, where $W\in\mathbb{R}^{m\times r}$ and $H\in\mathbb{R}^{r\times n}$ have nonnegative entries. For the Frobenius-norm objective, define $$ F(W,H)=\frac{1}{2}\|X-WH\|_F^2. $$ For a matrix $Z$, the projection onto the nonnegative orthant is elementwise: $[Z]_+=\max(Z,0)$, where each entry is replaced by its maximum with zero.

The factorization problem is not jointly convex in $W$ and $H$. However, if either factor is fixed, $F$ is a convex quadratic function of the other factor over a nonnegative constraint set. Projected-gradient updates use this blockwise structure. The factorization rank and the starting values still matter; a descent step does not guarantee a globally best factorization.

Gradients and Block Updates

With $W$ fixed, the gradient with respect to $H$ is $W^\mathsf{T}(WH-X)$. With $H$ fixed, the gradient with respect to $W$ is $(WH-X)H^\mathsf{T}$. A projected-gradient step subtracts a positive step size times the relevant gradient, then clips negative entries to zero.

H^{+}=[H-\alpha_H W^\mathsf{T}(WH-X)]_+,\qquad W^{+}=[W-\alpha_W(WH-X)H^\mathsf{T}]_+.

Here $\alpha_H$ and $\alpha_W$ are positive step sizes. Each update uses the factor values held fixed in that block’s subproblem. In an alternating implementation, one may update $H$ using the current $W$, then update $W$ using the new $H$. This is a blockwise algorithm, not a simultaneous update using two gradients calculated from a changing pair of factors.

Definition: For fixed $W$, the gradient of the $H$-subproblem has Lipschitz constant $L_H=\|W^\mathsf{T}W\|_2$. For fixed $H$, the gradient of the $W$-subproblem has Lipschitz constant $L_W=\|HH^\mathsf{T}\|_2$. Here $\|A\|_2$ is the spectral norm, the largest singular value of $A$. If the corresponding constant is positive, the conventional safe choice $0<\alpha\leq 1/L$ ensures nonincrease of that block’s objective. A zero constant means the block objective has zero curvature; it should be handled as a degenerate subproblem rather than by dividing by zero.

The constants follow from the linear change in the gradient. For example, at two candidate $H$ matrices $H_1,H_2$, the gradient difference is $W^\mathsf{T}W(H_1-H_2)$. Its Frobenius norm is at most $\|W^\mathsf{T}W\|_2\|H_1-H_2\|_F$. The same argument gives the stated $W$-block constant.

Why the Step-Size Bound Gives Descent

For a differentiable function with $L$-Lipschitz gradient, the smoothness inequality gives $f(Y)\leq f(U)+\langle\nabla f(U),Y-U\rangle+\tfrac{L}{2}\|Y-U\|_F^2$. For projected gradient, $Y$ is the projection of $U-\alpha\nabla f(U)$ onto the feasible set. Since $U$ is feasible, the defining property of Euclidean projection yields $\langle\nabla f(U),Y-U\rangle\leq-\|Y-U\|_F^2/\alpha$. Combining these inequalities gives a direct descent bound.

f(Y)\leq f(U)-\left(\frac{1}{\alpha}-\frac{L}{2}\right)\|Y-U\|_F^2.

When $0<\alpha\leq 1/L$, the multiplier in parentheses is at least $L/2$, so the objective cannot increase. This argument applies to either fixed-factor subproblem because each is a smooth quadratic with the corresponding Lipschitz constant. It does not establish that alternating updates find a global minimum of the original jointly nonconvex problem.

Choosing and Checking a Step Size

When a block’s spectral norm is available, a straightforward choice is $\alpha=1/L$, or a smaller positive value. For large matrices, the largest eigenvalue of $W^\mathsf{T}W$ or $HH^\mathsf{T}$ can be estimated numerically, for example by power iteration. A conservative upper bound can also be used, though it may produce slower steps.

A backtracking rule is useful when a reliable value of $L$ is inconvenient. Start from a trial step size, form the projected candidate, and evaluate the block objective. If it increases, reduce the step size and try again; continue until a descent condition holds. The objective must be computed for the same fixed-factor subproblem used to form that candidate. A trial step that happens to decrease the objective is not, by itself, proof of a general convergence guarantee.

Worked Example: One Projected Update of H

Suppose the hypothetical matrices are $X=\begin{bmatrix}2&1\\1&2\end{bmatrix}$, $W=\begin{bmatrix}1\\1\end{bmatrix}$, and $H=\begin{bmatrix}1&1\end{bmatrix}$. Compute one update of $H$ with $\alpha_H=0.4$.

First, $WH=\begin{bmatrix}1&1\\1&1\end{bmatrix}$, so $WH-X=\begin{bmatrix}-1&0\\0&-1\end{bmatrix}$. The gradient is $$ \nabla_H F=W^\mathsf{T}(WH-X) =\begin{bmatrix}1&1\end{bmatrix} \begin{bmatrix}-1&0\\0&-1\end{bmatrix} =\begin{bmatrix}-1&-1\end{bmatrix}. $$

The block Lipschitz constant is $L_H=\|W^\mathsf{T}W\|_2=\|[2]\|_2=2$. Thus $1/L_H=0.5$, and the selected step $0.4$ satisfies the safe bound. The unprojected candidate is $$ H-\alpha_H\nabla_H F =\begin{bmatrix}1&1\end{bmatrix}-0.4\begin{bmatrix}-1&-1\end{bmatrix} =\begin{bmatrix}1.4&1.4\end{bmatrix}. $$

Both entries are nonnegative, so projection leaves them unchanged: $H^+=\begin{bmatrix}1.4&1.4\end{bmatrix}$. Before the update, $F=\tfrac12(1+0+0+1)=1$. Afterward, the residual is $WH^+-X=\begin{bmatrix}-0.6&0.4\\0.4&-0.6\end{bmatrix}$, giving $F(W,H^+)=\tfrac12(0.36+0.16+0.16+0.36)=0.52$. The fixed-$W$ objective therefore decreases from 1 to 0.52.

Projection at the Boundary

Projection is entrywise, but it has an important optimization interpretation. A positive factor entry at a constrained optimum must have zero partial derivative; an entry at zero must have a nonnegative partial derivative. A negative gradient at a zero entry points into the feasible region, so a projected step can make that entry positive. A positive gradient at zero points outside the feasible region, so the unconstrained step is negative and projection keeps the entry at zero.

Key condition: For a differentiable objective $f$ minimized over nonnegative entries, the first-order conditions are $U_{ij}\geq 0$, $\nabla f(U)_{ij}\geq 0$, and $U_{ij}\nabla f(U)_{ij}=0$ for every entry at a constrained stationary point. Equivalently, a projected-gradient mapping $G_\alpha(U)=(U-[U-\alpha\nabla f(U)]_+)/\alpha$ is zero exactly when these entrywise conditions hold.

The condition distinguishes a constrained optimum from an arbitrary zero. A zero entry with a negative gradient is not stationary: the next projected step can move it above zero. This is one reason projected gradient can avoid the zero-locking behavior possible in multiplicative updates. It does not mean every zero will be revived: if its gradient points outward or is zero, projection can leave it at zero.

Worked Example: A Zero Entry Can Move Into the Feasible Region

Consider a one-entry fixed-factor problem with $W=[1]$, $X=[2]$, and current $H=[0]$. The objective is $f(H)=\tfrac12(2-H)^2$, with gradient $H-2$. At $H=0$, the gradient is $-2$, so the negative-gradient direction is positive and feasible. The block Lipschitz constant is $L_H=1$. Take $\alpha_H=0.25$, which is no larger than $1/L_H=1$.

The update is $$ H^+=[0-0.25(-2)]_+=[0.5]_+=0.5. $$

The objective falls from $f(0)=\tfrac12(2)^2=2$ to $f(0.5)=\tfrac12(1.5)^2=1.125$. Thus clipping negative values does not itself trap a zero: this zero becomes positive because the gradient points into the nonnegative region.

What an Excessive Step Can Do

Worked Example: Step-Size Overshoot

Take a fixed $W=\begin{bmatrix}1\\1\end{bmatrix}$, $X=\begin{bmatrix}2\\2\end{bmatrix}$, and a scalar factor $H=[0]$. The objective is $f(H)=\tfrac12\{(2-H)^2+(2-H)^2\}$, and its gradient is $2H-4$. Here $L_H=W^\mathsf{T}W=2$, so the safe bound is $\alpha_H\leq0.5$.

If $\alpha_H=1.2$, then $H^+=[0-1.2(-4)]_+=4.8$. The objective increases from $f(0)=\tfrac12(4+4)=4$ to $f(4.8)=\tfrac12(2.8^2+2.8^2)=7.84$. The result is feasible, but it is a worse fit.

With $\alpha_H=0.4$, the update is $H^+=[0-0.4(-4)]_+=1.6$, and $f(1.6)=\tfrac12(0.4^2+0.4^2)=0.16$. The comparison shows why nonnegative projection alone does not make an arbitrary step safe.

Diagnostics, Alternatives, and Limitations

Monitor the reconstruction objective after each block update, not just after a full cycle. With valid step sizes, each exact projected-gradient block step for this objective should not increase its fixed-block objective. Unexpected increases can indicate an overly large step, a gradient or transpose error, or that the comparison did not hold the intended block fixed. Very small steps, little change in the projected-gradient mapping, or repeated oscillation are also useful warning signs. A small mapping indicates approximate first-order stationarity for the block, not necessarily a good global factorization.

Projected gradient and alternating nonnegative least squares both optimize one factor while fixing the other, but their block subproblem steps differ. Alternating nonnegative least squares solves each constrained least-squares subproblem, whereas projected gradient takes a step based on the gradient and its step size. Multiplicative updates use an elementwise ratio update; they can be convenient, but exact zeros can remain locked at zero. These methods are not interchangeable in every numerical setting, and none removes the joint nonconvexity of NMF.

Method	Block operation	Practical consideration
Projected gradient	Gradient step followed by projection	Requires a suitable step size; can move a zero entry when its gradient points inward
Alternating nonnegative least squares	Solves a constrained least-squares block subproblem	Can make stronger block progress, but each subproblem solve has computational cost
Multiplicative updates	Multiplies entries by a nonnegative ratio	Simple to implement; an exact zero can remain zero in subsequent updates

Projected gradient also has limitations. Poor scaling or an ill-conditioned block can make a single global step conservative for some directions and inadequate for others. The algorithm can converge to a stationary point that depends on initialization, and the nonnegative factors may not be uniquely determined. A decreasing objective is evidence of optimization progress, not proof that the selected rank or resulting components are scientifically appropriate.

Common mistake: “The update is projected onto nonnegative values, so the objective must decrease.” Projection guarantees feasibility, not descent. A large step can produce a nonnegative factor and still increase the loss, as the overshoot example shows. Check the block Lipschitz bound or use a suitable backtracking rule, and monitor the objective.

Check Your Understanding

Answer each question; concise solutions follow.

For fixed $W$, what is the gradient with respect to $H$, and what is its Lipschitz constant?
If $W^\mathsf{T}W=[5]$, what is the conventional maximum safe step size for the $H$-block?
For a scalar constrained factor $h=0$, what gradient sign allows a projected-gradient step to move $h$ above zero?
Suppose a projected block update increases the objective. Name two possible explanations or checks.
Does a decreasing NMF objective establish that the algorithm found the global minimum? Why or why not?

Solutions. (1) $\nabla_H F=W^\mathsf{T}(WH-X)$, with $L_H=\|W^\mathsf{T}W\|_2$. (2) $L_H=5$, so $1/L_H=0.2$; choose $0<\alpha_H\leq0.2$ for the stated guarantee. (3) A negative gradient makes the unprojected step positive, so projection can retain a positive value. (4) Check whether the step exceeds the Lipschitz bound and verify the gradient, matrix dimensions, transpose, and fixed-block objective calculation. (5) No. The joint problem is nonconvex, so descent does not rule out convergence to a non-global stationary point.