PaperlayerView exact revision on arXiv

Source-linked AI summary

Bi-cross-validation of the SVD and the nonnegative matrix factorization

Art B. Owen, Patrick O. Perry

arXiv:0908.2062v1stat.AP

TL;DR

The paper addresses how to choose rank in outer-product approximations without relying on unreliable tests, visual elbows, or known noise levels. It develops bi-cross-validation by holding out rows and columns, proves a self-consistency residual result, and studies its behavior for SVD and NMF. The analysis and simulations indicate a trade-off between overfitting and underfitting as holdout size changes, with half-row and half-column holdouts performing well.

  • Problem

    Choosing the rank of low-rank matrix approximations is difficult because larger SVD ranks improve fit while increasing exposure to noise and overfitting.

  • Method

    The paper generalizes bi-cross-validation to rectangular row-and-column holdouts and outer-product models, using low-rank operations on retained data and NMF as a detailed example.

  • Results

    Large holdouts reduce overfitting but make it harder to select a sufficiently high rank, while extreme aspect ratios make both problems more difficult.

  • Takeaways & Limitations

    Bi-cross-validation extends rank cross-validation to outer-product and unsupervised-learning settings, including SVD and NMF.

  • Takeaways & Limitations

    For inherently nonunique NMFs, the conforming residual may be nonzero even when both X and the retained submatrix have k-term NMFs.

Abstract

from arXiv · show

This article presents a form of bi-cross-validation (BCV) for choosing the rank in outer product models, especially the singular value decomposition (SVD) and the nonnegative matrix factorization (NMF). Instead of leaving out a set of rows of the data matrix, we leave out a set of rows and a set of columns, and then predict the left out entries by low rank operations on the retained data. We prove a self-consistency result expressing the prediction error as a residual from a low rank approximation. Random matrix theory and some empirical results suggest that smaller hold-out sets lead to more over-fitting, while larger ones are more prone to under-fitting. In simulated examples we find that a method leaving out half the rows and half the columns performs well.

1. Introduction.

The paper develops bi-cross-validation for selecting rank in outer-product matrix approximations, addressing overfitting and extending the approach beyond the SVD to models such as NMF.

  • Outer-product models approximate large data matrices as LR, with the SVD, NMF, and k-means providing important examples.NMF constrains factors to be nonnegative, while k-means imposes binary structure on one factor.
  • Choosing the SVD rank is difficult because larger ranks improve fit but can overfit noise.At k = min(m,n), the fitted matrix equals X, so noise can influence the approximation more strongly as k increases.
  • Cross-validation selects k by minimizing a numerical criterion without requiring known noise levels or visual identification of a singular-value elbow.The paper contrasts this with selecting the last large gap or matching residual error to a known noise level.
  • The paper generalizes Gabriel’s row-and-column holdout from single entries to r × s blocks and extends it to outer-product models, using NMF as a detailed example.The resulting (h × ℓ)-fold BCV parallels k-fold cross-validation while making larger holdouts feasible for large problems.
  • The proposed BCV provides cross-validation for unsupervised learning, including NMF viewed as bi-clustering of rows and columns.
  • The paper analyzes BCV’s self-consistency, random-matrix behavior, and relation to prior rank-selection and imputation methods.Its setting lets both matrix dimensions grow and does not require rows or columns to be i.i.d.; retained data are rectangular submatrices rather than missing-value inputs.

2. Background matrix algebra.

This section establishes matrix-algebra facts used later, especially generalized-inverse identities for rank-deficient factorizations and the singular value decomposition.

  • The Moore–Penrose inverse X+ generalizes matrix inversion and reduces to 1/x for nonzero scalars, while assigning 0 to x = 0.
  • Unlike ordinary inverses, generalized inverses do not generally satisfy the reverse-order law (AB)+ = B+A+.A special reverse-order case is attributed to MacDuffee and further sufficient conditions are noted.
  • MacDuffee’s theorem gives a reverse-order identity when X = LR and both factors have rank k.The proof uses explicit formulas for L+ and R+ and verifies the defining properties of the Moore–Penrose inverse.
  • The skinny SVD writes X = UΣV′ with orthonormal singular-vector factors and nonincreasing nonnegative singular values.It also provides the explicit generalized-inverse formula X+ = VΣ+U′.
  • The SVD yields the closest rank-k approximation to X in Frobenius norm.

3. Cross-validating the SVD.

The paper develops row-and-column holdout cross-validation for SVD rank selection, derives its residual interpretation, and relates it to principal-components regression while identifying failure cases.

  • 3. Cross-validating the SVD.: Cross-validating the SVD holds out matrix entries, fits a low-rank model to retained data, and predicts the held-out portion.
  • 3. Cross-validating the SVD.: Parameter-counting methods and some rank tests are unreliable, motivating numerical cross-validation criteria for SVD rank selection.One reported test rejects 66% of the time when the nominal rejection rate is 5%, while other tests become too conservative for k > 0.
  • 3. Cross-validating the SVD.: Gabriel’s method leaves out a row and column simultaneously and produces reasonable nonmonotonic cross-validated errors, unlike separate row and column deletion.Eastment–Krzanowski’s method also has sign ambiguity and does not completely hold out the target entry.
  • 3. Cross-validating the SVD.: For an r × s held-out block, BCV partitions rows and columns, then predicts the block through a low-rank operation involving the retained submatrix’s generalized inverse.The residual construction is based on A − B(bD(k))+C and can be organized as (h × ℓ)-fold BCV.
  • 3. Cross-validating the SVD.: If X and the retained submatrix D both have rank k, self-consistency gives A − BD+C = 0, with related residual constructions remaining zero under rank-k replacement.The paper interprets these residuals as errors relative to a rank-k SVD model.
  • 3. Cross-validating the SVD.: Conditionally on held-out columns, generalized Gabriel BCV is ordinary cross-validation of principal-components regression using the first k principal components.BCV additionally varies the held-out columns and changes the regression rank to k; the regression analogue is statistically simpler because its inverted matrix is nonrandom.

4. Exceptions.

BCV’s self-consistency can fail when the retained submatrix loses rank or when the held-out block contains a localized signal. These exceptions expose both robustness benefits and cases where BCV may underestimate rank.

  • Spike matrices: A rank-1 spike matrix can become rank 0 after excluding its sole nonzero entry, making rank-0 and rank-1 fits equally inaccurate.The retained submatrix cannot reconstruct the held-out 1, so BD+C equals zero.
  • Spike matrices: The spike exception provides robustness because predicting an isolated 1 from surrounding zeros is not reasonably possible.
  • Stripe matrices: Stripe matrices create ambiguous predictions because row continuation and column continuation imply different values for the held-out entry.Such additive patterns may be absorbed by regression terms in crop-science applications but remain plausible elsewhere.
  • Arrow matrices: An arrow matrix can have rank 2 while BD+C still predicts its held-out entry incorrectly, because multiplicative and additive explanations disagree.The multiplicative model suggests 1, whereas an additive model suggests 2.
  • Conditions for self-consistency: Exact self-consistency requires the retained SVD factors to remain nondegenerate, with the relevant columns of U2 and V2 linearly independent.
  • Localized signals: Holding out r rows and s columns can miss features affecting fewer than r+1 rows or s+1 columns, causing BCV to underrepresent localized factors.With many small tight clusters or near-duplicate rows, BCV might underestimate k.

5. Cross-validating the NMF and other outer product decompositions.

The paper extends bi-cross-validation from the SVD to NMF and related outer-product decompositions, using held-out row-column blocks and residuals tailored to nonnegative factors.

  • NMF formulation: NMF approximates X by WH with nonnegative factors W and H, whose rows can represent sparsely supported prototypes.The factors are chosen by minimizing squared Frobenius error subject to nonnegativity.
  • NMF formulation: Alternating constrained least squares estimates H given W and W given H, but unlike the SVD it need not attain the desired global optimum.Each alternating step solves a nonnegative least-squares problem.
  • Bi-cross-validation residuals: When X = WH and the retained submatrix D has rank k, the NMF bi-cross-validation prediction follows from the self-consistency lemma and MacDuffee’s theorem.The retained block’s rank condition is required for the reconstruction argument.
  • Bi-cross-validation residuals: The simple residual vanishes when a k-term NMF holds for both X and D, while the conforming residual estimates the held-out block using constrained nonnegative factors.The conforming residual is formed through a constrained least-squares replacement of the ordinary factor estimate.
  • Bi-cross-validation residuals: Conforming residuals can depend on the factorization of D and may be nonzero when a k-term NMF is inherently nonunique.They are zero when the NMF of D is unique up to permutation and scaling.
  • Extensions: The NMF BCV process evaluates row-column holdouts, while analogous procedures can respect binary constraints in k-means and sign constraints in semi-discrete decompositions.The paper also notes that clusters smaller than the held-out row set could be missed in bi-cross-validated k-means.

6. Random matrix distribution theory.

The section analyzes BCV rank selection using random matrix theory for pure noise and rank-1 signal-plus-noise models. It finds that larger holdouts improve separation against overfitting, while signal detectability and aspect ratio affect rank-selection accuracy.

  • True rank 0: For pure noise, the true rank-0 model has no larger expected cross-validated error than a fitted rank-1 model.The comparison considers fitting ranks 0 and 1 when the true rank is 0.
  • True rank 0: Larger holdouts increase the expected separation between BCV(1) and BCV(0), making overfitting easier to avoid.This result is derived for proportional holdouts, where the holdout fractions r/m and s/n increase together.
  • Rank 1 plus noise: Rank-1 signal recovery depends on a critical signal-strength threshold d1 = κ2/n > √c, with c determined by the matrix aspect ratio.Above the threshold, the largest sample eigenvalue separates from the noise spectrum; below it, the analysis gives a negative result.
  • Rank 1 plus noise: When the signal is sufficiently strong, the first singular value scales as a multiple of κ, and its relative bias becomes small for large δ.The weak-factor limit retains non-negligible bias, whereas increasing δ reduces that bias.
  • Summary: The summary analysis concludes that large holdouts reduce overfitting but increase underfitting risk, while extreme aspect ratios make both problems more difficult.Extreme aspect ratios reduce rank-0 versus rank-1 error separation and can make estimated ranks less reliable; large holdouts can also raise the rank-1 error bound through η.

7. Examples for the truncated SVD.

Simulations compare rank-selection methods for truncated SVD under binary and geometric singular-value patterns, varying signal strength and BCV holdout size. Generalized Gabriel BCV performs well overall, with 500×500 holdouts attaining the best regret across the 60 large-matrix simulations, while real-data examples produce ranks 14 and 41.

  • Simulation design: The simulations construct Gaussian-noise matrices with prescribed binary or geometric singular values, including equal signal and expected noise magnitude.The optimal rank is known from the signal matrix in each realization.
  • Small simulated example: In the 50 × 40 binary case, the oracle always selected k = 10, while Eastment–Krzanowski selected ranks near 20 and Gabriel selected slightly-too-large ranks.For the geometric case, the best rank was always 3 or 4, and Gabriel remained below rank 20.
  • Small simulated example: Generalized Gabriel holdouts with r ∈{1,2,5,10} had good relative performance in both small-example settings, with holdout size favoring smaller values for binary signals and larger values for geometric signals.Type I residuals were at least as effective as type II, while replication helped slightly for binary signals but hurt somewhat for geometric signals.
  • Large simulated examples: Large holdouts better detected unnecessarily high ranks, while small holdouts better avoided selecting ranks below the binary optimum k = 50.For the binary medium-signal setting, 200×200 holdouts approached the true rank but had the worst squared errors among the six methods.
  • Large simulated examples: 500×500 BCV holdouts attained the minimum regret in all 60 large-matrix simulations.Smaller holdouts struggled with medium-strength binary signals, whereas larger holdouts struggled with medium-strength geometric signals.
  • Real data examples: On additional data, BCV selected rank 14 for standardized student-test data and rank 41 for a microarray data set with aspect ratio c > 300.The microarray BCV curves were very flat, unlike the reported Gaussian simulations with extreme aspect ratios.

8. NMF

The NMF experiments apply BCV to simulated and educational-testing data, assessing rank selection under different residual criteria and holdout schemes. On synthetic Classic3 data, smaller BCV holdouts recover the rank-3 signal, while larger holdouts select rank 4 despite higher error.

  • Synthetic Classic3 data: The simulated data combine three topic-specific rank-1 NMFs into a nonnegative rank-3 signal, then add Poisson noise through µ = ε + WH.The signal WH has rank 3, while the additive noise raises the rank of µ to 4.
  • Synthetic Classic3 data: The true error for the synthetic NMF approximation is minimized at k = 3.
  • Synthetic Classic3 data: (5 × 5)-fold BCV selects k = 4, although the true rank has about 50% higher MSE.
  • Educational-testing data: On educational-testing data, BCV compares truncated SVD with NMF using plain and nonnegative-factor held-out predictions.
  • Educational-testing data: The educational-testing comparison normalizes BCV squared error by the rank-0 error and finds better holdout error for plain SVD than for NMF.The comparison suggests that unconstrained factors predict this data better despite potentially going out of bounds.

9. Discussion.

The discussion generalizes BCV from single-element holdouts to rectangular holdouts and compares its model-selection behavior with CV, AIC, and BIC. It identifies a holdout-size trade-off and recommends small block-fold schemes pending better theory.

  • Generalization: BCV generalizes Gabriel’s holdout-one method for truncated SVD rank selection to r × s holdouts and other outer product models.
  • Holdout-size trade-off: Smaller holdouts appear more prone to overfitting, whereas larger holdouts are more prone to underfitting.The underfitting concern is strongest when important outer-product terms are not small relative to the held-in dimensions.
  • Holdout-size trade-off: The authors recommend (2 × 2)-fold or (3 × 3)-fold BCV while the optimal holdout size remains unresolved.They report that (2 × 2)-BCV gave the most accurate recovery of µ in their examples, except in a small case described subsequently.
  • Model selection: BCV behaves similarly to CV: its criterion decreases toward a minimum as model complexity rises, then increases more slowly.
  • Model selection: CV and AIC are described as better than BIC for choosing a model when the true model is not necessarily among those considered.BIC is better at finding the true model when it is one of the candidates.
  • Resampling context: In crossed random-effects settings, cited work finds resampling matrix elements seriously incorrect, while independently resampling rows and columns is approximately correct.
  • Generalization: Leaving out an r × s submatrix permits simpler algorithms on the retained (m−r) × (n−s) submatrix.
Loading 0908.2062v1…