Collapsing One Side of the Factorization: Rank Selection for Partially Observed Matrices

Many models explain a data matrix as the product of two smaller matrices, and the size of the shared inner dimension, the rank, is the number of hidden factors. Bayesian versions of these models can choose the rank on their own. Each factor carries its own scale, and the inference procedure shrinks the scales of useless factors to zero. For fully observed matrices this behavior is understood exactly. Global Analytic Solution for Variational Bayesian Matrix Factorization solves variational Bayesian matrix factorization in closed form, and Implicit Regularization in Variational Bayesian Matrix Factorization shows that it acts as a shrinkage rule with a sharp threshold: singular values below a noise level are set to zero. Both results break when entries are missing, and missing entries are the normal case in recommendation data and in genomics. What remains is iterative optimization of a two-sided product. Analysis of Variational Bayesian Factorizations for Sparse and Low-Rank Estimation shows that this "bilinear" variational factorization behaves like a log-determinant rank penalty with many local minima. A factor whose scale reaches zero is permanently trapped, and the failure is worst when the true factors are correlated.

We propose to fix this with collapsed variational inference. The method integrates some unknowns out exactly before making any independence assumption about the rest. Here the integrated-out quantity is one entire factor matrix. Given the other factor, each column of the data is a Gaussian linear model in its own coefficients, even when only some of its rows are observed, so that side can be marginalized exactly and cheaply for any pattern of missing data. The claim is that collapsing one side changes which penalty the optimizer sees. Instead of the trapping bilinear penalty, it sees an evidence-type penalty of the "Gaussian scale mixture" kind, which Wipf shows is smooth, invariant to linear transformations, and free of the trapping minima. The practical payoff is a rank-selection method for partially observed matrices that keeps the reliability of the fully observed analytic theory without needing its closed form.

Core Claim

Let $X$ be a $D\times N$ matrix, and let $O_j$ be the set of observed rows in column $j$. The model writes $X \approx UV^\top$ plus Gaussian noise of variance $\sigma^2$. Here $U$ is $D\times K$, and each coefficient vector $v_j$ has prior $\mathcal N(0,\Gamma)$ with $\Gamma=\mathrm{diag}(\gamma_1,\dots,\gamma_K)$, one scale per factor. Integrating out $V$ exactly gives

$$ \log p(X\mid U,\Gamma,\sigma^2)=\sum_{j=1}^N \log \mathcal N\!\left(x_{O_j,j};\,0,\;U_{O_j}\Gamma U_{O_j}^\top+\sigma^2 I\right), $$

where $U_{O_j}$ keeps only the rows of $U$ observed in column $j$. We place a Gaussian variational distribution $q(U)$ over the rows of $U$ and maximize the collapsed bound $\mathbb E_{q(U)}[\log p(X\mid U,\Gamma,\sigma^2)]-\mathrm{KL}(q(U)\,\|\,p(U))$. The expectation is estimated with reparameterized samples of $U$. The Woodbury identity reduces each column's term to a $K\times K$ solve. Factors whose $\gamma_k$ is driven to zero are removed.

For a fixed $q(U)$, this bound is at least as tight as the uncollapsed bound that uses an independent $q(U)q(V)$. The reason is that the collapsed bound effectively uses the exact conditional distribution of $V$ given $U$ rather than a distribution over $V$ that ignores $U$. This is the same argument A Collapsed Variational Bayesian Inference Algorithm for Latent Dirichlet Allocation makes for topic models.

The testable claims are these:

  1. Rank recovery under missing data and correlated factors should be markedly more reliable than uncollapsed variational factorization.
  2. On fully observed matrices, the method should reproduce the rank chosen by Nakajima et al.'s analytic empirical solution.
  3. A factor whose scale has shrunk toward zero should still be able to re-enter when the data support it, which is the escape Wipf's analysis says the bilinear form lacks.

Relation to Prior Work

Two collapsed-inference papers motivate the mechanism and show that collapsing changes pruning behavior in practice. Collapsed Variational Bounds for Bayesian Neural Networks integrates out weight-prior means and variances and finds that this stops mean-field inference from over-pruning. BasisVAE integrates out mixture weights so that surplus clusters prune cleanly. Neither addresses matrix rank, and Tomczak et al. explicitly list factor-matrix formulations as untreated.

The closest bridging work is Collapsed Variational Inference for Nonparametric Bayesian Group Factor Analysis. It integrates out beta-process parameters in a sparse factor model $G=Z\odot W$ and chooses $K$ through binary indicators. It collapses the process parameters, not a factor matrix, and it does not treat arbitrary missing entries. We differ by collapsing a full side of the product so that the optimization landscape itself changes.

Wipf's analysis supplies the prediction we test. It diagnoses the two landscapes and shows the bilinear one traps factors, but it proposes no algorithm and does not handle missing data. Nakajima et al.'s analytic solution acts as a constraint and a sanity check: our method must agree with it where it applies.

The nonparametric line is a different design choice. Variational Inference for the Indian Buffet Process uses truncated variational inference over an infinite feature model. Variational Russian Roulette for Deep Bayesian Nonparametrics uses unbiased stochastic truncation. Both are uncollapsed. The Russian Roulette estimator also has high variance. We keep a fixed upper bound on $K$ and argue that a well-behaved landscape matters more than an open-ended truncation. This is a bet, and one experiment below checks it.

Research Program

Build. We will implement the collapsed bound with minibatches over columns. There will be two treatments of the per-factor scales. The first learns $\Gamma$ by empirical Bayes. The second integrates it out under a Gamma hyperprior in the style of Tomczak et al., which reintroduces a single hyper-hyperparameter; we will report sensitivity to that constant. The cost is $O(S\sum_j |O_j|K^2 + SNK^3)$ per epoch with $S$ samples, which is feasible for $K$ in the tens to low hundreds.

Analyze. We will analyze the collapsed objective near $\gamma_k=0$. The goal is to state conditions on the observed-data residual under which the gradient pushes a vanished factor back out. We will compare those conditions to the absorbing zero state of the bilinear form. We will also check whether, under full observation, the stationary points reduce to the positive-part James–Stein threshold $\gamma_h^2 < M\sigma^2/n$.

Test. The experiments map where the collapsed method wins or ties across three dimensions: the fraction of entries missing, the correlation between true factors, and signal strength relative to that threshold.

Baselines

Do nothing. The naive reference fixes $K$ at the upper bound and fits point estimates with an $\ell_2$ penalty. It shows what automatic pruning buys at all.

Uncollapsed variational factorization. The primary competitor is uncollapsed variational factorization with per-factor scales: an independent Gaussian $q(U)q(V)$ with the same scale parameters, fitted by coordinate ascent on observed entries only. This is the bilinear factorization that Wipf and Nakajima analyze, and it is the standard way rank selection is done with missing data. It will use the same initialization, the same upper bound on $K$, the same noise model, and the same wall-clock budget. Hyperparameter search will get an equal number of trials.

Impute-then-shrink. The strongest competitor is a hybrid we construct from Nakajima et al.'s closed-form empirical solution, applied inside an impute-and-repeat loop: fill missing entries, apply analytic shrinkage, refill, and repeat. It inherits the analytic method's trapping-free behavior on complete data.

Reported numbers. No reported result was found on Lacuna for any of these methods on partially observed rank recovery. The group factor analysis paper reports only qualitative Sparse and Dense Stability Index comparisons against BASS and sGFA, with no scalar values. All baseline numbers will therefore be produced in our runs.

Criterion for beating the baselines. Beating a baseline means lower held-out reconstruction error on masked entries, together with a higher fraction of runs recovering the true rank on synthetic data. Both must hold across five or more seeds and be outside seed-to-seed variation.

Ablations. The key ablation isolates collapsing. It compares collapsing $V$, collapsing $U$ (which is equivalent up to transposition, as a symmetry check), and collapsing neither, with the same $q$ family for the remaining side. A second ablation replaces sampled $q(U)$ with a point estimate. This separates the benefit of the collapsed landscape from the benefit of uncertainty over $U$.

Why not just…?

Why not just grid-search $K$ with held-out likelihood? This is honest and often works when the signal is strong. It costs one fit per candidate rank, and each fit still uses a bilinear optimizer that can trap factors, so the chosen $K$ inherits those failures. We will run it with the same total compute. If it matches our rank recovery at equal cost, the claim narrows to efficiency and stability rather than accuracy.

Why not just impute the missing entries and apply the closed-form shrinkage? This is the most serious threat. At low missingness it may well tie us. The concern is that imputation feeds the method's own low-rank guess back in as data. That biases the singular values that the threshold acts on, and the bias should grow with the missing fraction. The missingness sweep will show where, if anywhere, the two methods separate. If they never separate, we will report that.

Why not just use a nonparametric prior with stochastic truncation? The Russian Roulette approach removes the upper bound on $K$ but stays uncollapsed, and its authors report high gradient variance. Removing the upper bound does not address trapping inside the bound. We include an experiment where the true rank is near our upper bound to check whether the bound itself ever becomes the limitation.

Proposed Experiments

Synthetic study. We will generate rank-$r$ matrices with factor correlation varied from zero to high, which is Wipf's failure regime. Missing fractions will range from 0 to 90 percent, and signal strengths will span the James–Stein threshold. We will measure three things: exact-rank recovery rate, held-out error on masked entries, and the fraction of runs in which a true factor's scale vanishes and never returns.

Decisive checks. First, at full observation, our chosen rank must agree with Nakajima et al.'s analytic empirical solution. Second, in the correlated, high-missingness corner, the collapsed method's trapping rate must be clearly below that of the uncollapsed bilinear baseline. If the second check fails, the core claim is wrong.

Real data. We will use the Hyman and Pollack cancer genomics matrices, which pair gene expression with copy-number variation, from the group factor analysis study. Entries will be masked at controlled rates, and we will report held-out error and the stability of the selected rank across masks and seeds.

Group sparsity extension. Finally, we will extend the collapsed-side construction to the multi-view $Z\odot W$ setting and rerun the synthetic Sparse and Dense Stability Index benchmark, with the group factor analysis method as the reference.