Rank, Reconstruction Error, and Approximation

Rank as a Limit on Representation

In non-negative matrix factorization (NMF), a nonnegative data matrix is represented approximately as a product of two nonnegative factor matrices. The selected rank sets the number of component patterns available to reconstruct the data. A low rank gives a compact representation, but it may be unable to capture distinct patterns; a higher rank can fit more detail, including noise.

Let \(X\) be an \(m\times n\) matrix with nonnegative entries. In an omics setting, its rows might represent specimens and its columns features; the orientation does not change the mathematics. For a chosen rank \(r\), NMF seeks nonnegative matrices \(W\) and \(H\) with dimensions \(m\times r\) and \(r\times n\), respectively. Their product \(\widehat{X}=WH\) is the reconstruction of \(X\). This tutorial focuses on what the rank permits and how to measure approximation error, not on how a numerical algorithm obtains the factors.

Each column of \(W\) gives the weights of one component across rows; the corresponding row of \(H\) gives that component's pattern across columns. Their product adds the \(r\) component contributions. Thus, rank \(r\) allows at most \(r\) such patterns in the representation. An exact factorization with rank \(r\) also implies that the ordinary matrix rank of \(X\) is at most \(r\), because the columns of \(X=WH\) lie in the column space of \(W\). The converse need not hold: a factorization using signed values can be possible at a smaller rank than one constrained to be nonnegative. In particular, ordinary rank and nonnegative rank are not interchangeable.

Measuring Reconstruction Error

A common way to summarize the discrepancy between the observed matrix and its reconstruction is the Frobenius norm. It aggregates squared entrywise residuals, so large discrepancies contribute more than small ones. The error is measured in the same units as the entries of \(X\).

For a fixed dataset and this error measure, the best attainable error cannot increase when the allowed rank increases. Any rank-\(r\) factorization can be represented at rank \(r+1\) by adding a zero column to \(W\) and a zero row to \(H\); the product is unchanged. The rank-\((r+1)\) choices therefore include all rank-\(r\) choices, so minimizing over the larger set cannot give a larger minimum. This is a statement about the best attainable fit, not a promise that a particular numerical fitting procedure will find it.

Here \(\mathcal{F}_r\) is the set of reconstructions allowed at rank at most \(r\), and \(E^*_r\) is the smallest Frobenius error over that set. The inequality describes training reconstruction error. It does not say that predictive performance improves, that the additional component is scientifically meaningful, or that a fitted factorization is unique.

A Rank Trade-Off in a Small Matrix

An exact fit may require more than one component. The identity matrix below has two distinct nonnegative patterns, one on each diagonal entry. A rank-one reconstruction must combine them and leave a nonzero residual.

A helpful justification of the general monotonicity result is the zero-padding construction. Given any rank-\(r\) factors \(W,H\), form \(W'=[W\ \ 0]\) by appending a zero column and \(H'=\begin{bmatrix}H\\0\end{bmatrix}\) by appending a zero row. Then \(W'H'=WH\), so the residual and its Frobenius norm are unchanged. Since the expanded model can reproduce every old reconstruction as well as potentially other reconstructions, its best error is no greater. This argument relies only on allowing nonnegative factors and rank at most \(r\), not on a particular fitting algorithm.

Known Low-Rank Structure and Approximation

Synthetic examples with known structure are useful because they distinguish a component pattern built into the data from a pattern introduced only to reduce residual error. In practice, measurements may also include noise, background signal, and preprocessing effects. A rank that reproduces an ideal noiseless construction need not be the rank that best describes an observed dataset.

Choosing Rank: Complexity, Diagnostics, and Alternatives

For an \(m\times n\) matrix, the factor entries number \(mr+rn=r(m+n)\) before accounting for constraints and redundancies. Thus larger rank generally means more parameters available to adapt to the observed matrix. Increasing rank cannot worsen the best training error, but it can make the model less compact and more able to capture idiosyncratic noise. A practical rank decision balances fit against complexity and the intended use of the reconstruction.

Several checks help reveal when a rank choice or fit is questionable:

• Inspect residuals by entry and structure. A small total error can conceal a systematic residual pattern, such as a group of features consistently under-reconstructed. Plot or summarize residuals in the context of rows and columns rather than relying only on one total.
• Compare ranks on data not used for fitting. If the purpose is prediction or reconstruction of held-out entries, assess that purpose directly. Training error alone is guaranteed to be nonincreasing with allowed rank.
• Check sensitivity and stability. If small changes in the data or fitting start lead to very different component patterns, avoid treating a particular high-rank decomposition as a uniquely established biological structure.
• Look for boundary cases. A rank larger than needed may yield components with negligible contribution, while a rank that is too small may force visibly distinct patterns into one component. Neither symptom alone determines the correct rank.
• Check data suitability. NMF requires nonnegative entries. A matrix containing negative values cannot be factored under the stated nonnegative model without a principled transformation or a different model; shifting values changes their interpretation and can change the approximation problem.

A truncated singular value decomposition is a key alternative for unconstrained low-rank approximation under squared Frobenius error. It permits positive and negative factor values, whereas NMF constrains both factors to be nonnegative. Consequently, the best unconstrained low-rank error is a lower bound on the best NMF error at the same rank, but its components can be harder to interpret as additive nonnegative patterns. Rank selection may also use validation error or explicit complexity penalties. These approaches answer somewhat different questions; none makes a rank automatically biologically meaningful.

The introductory material on Non-Negative Matrix Factorization as a Data Model establishes the basic additive-factor interpretation; here the central additional point is that rank controls the available number of patterns. The error-versus-rank curve is informative, but it must be read alongside model complexity, residual structure, and stability. In particular, zero training error can mean that a matrix is exactly representable at the chosen rank, not that the same rank is appropriate for noisy data or future observations.