Streaming Hard-Assignment Dictionaries That Grow and Shrink

Dictionary learning represents each small image patch as a combination of a few columns, called atoms, taken from a learned matrix. The fast streaming method for this, Online dictionary learning for sparse coding, is the workhorse here. It needs the number of atoms fixed in advance, and when atoms go unused it swaps them out for random incoming patches. Bayesian nonparametric dictionaries choose their own size: Non-Parametric Bayesian Dictionary Learning uses a Beta Process prior and infers 34 atoms under heavy noise and 196 under light noise. They pay for this with Gibbs sampling over the whole dataset. Small-variance asymptotics bridges the two. This technique takes a Bayesian model's most-probable-solution objective, sends the noise variance to zero, and gets a fast deterministic objective whose prior has turned into explicit penalties. It has been used for clustering and binary features, but not for continuous, overcomplete, streaming dictionaries.

We propose to take this zero-noise limit of the Beta-Bernoulli-Gaussian dictionary model and run the result as a single-pass streaming algorithm. The resulting objective has one cost per active coefficient and one cost per atom. Under that objective, adding an atom and deleting an atom become moves that provably lower the same surrogate the online learner already minimizes. Deletion can be decided exactly from the two small running summary matrices the online method keeps. Combined with exponential forgetting of those summaries, stale atoms die and new ones are born by rule, with no ad hoc replacement. Because both penalties come out in units of the noise variance, the method can set them on its own from the measured reconstruction error.

Core Claim

Let $x_t \in \mathbb{R}^P$ be the patch arriving at time $t$, $D \in \mathbb{R}^{P\times K}$ the current dictionary with $K$ atoms, and $w_t$ its sparse code. Taking the small-variance limit of the Beta-Bernoulli-Gaussian model, with the Beta Process mass parameters scaled jointly with the noise variance $\sigma^2$ as in the BP-means derivation of MAD-Bayes, yields

$$ \min_{K,\,D,\,\{w_t\}} \;\sum_t \|x_t - D w_t\|_2^2 \;+\; \sigma^2\Big(\beta\sum_t \|w_t\|_0 + \gamma K\Big). $$

Here $\beta$ is the cost of switching on one coefficient and $\gamma$ is the cost of keeping one atom in existence. Both are dimensionless log-odds that the limiting prior inherits. The continuous Gaussian weight prior drops out in the limit, which is why the continuous version stays tractable. What the derivation contributes over BP-means is that the codes are real-valued, not binary.

We make three claims. The first is that a Mairal-style quadratic surrogate built from the summaries $A=\sum_t \rho^{T-t} w_t w_t^\top$ and $B=\sum_t \rho^{T-t} x_t w_t^\top$, with forgetting factor $\rho\le 1$, admits birth and death moves that never increase the surrogate. The second is that the resulting atom count tracks noise level and signal complexity the way the full Beta Process posterior does. The third is that writing $\beta,\gamma$ in units of $\sigma^2$ lets an online estimate of $\sigma^2$ calibrate the penalties. That calibration addresses the fixed-penalty problem left open by every small-variance method in the file.

Research Program

The first step is the derivation and the move rules. Sparse coding of each new patch minimizes an $\ell_0$-penalized least-squares problem with threshold $\sigma^2\beta$, solved greedily by orthogonal matching pursuit with a stopping rule. A birth fires when the remaining residual $r_t$ satisfies $\|r_t\|^2 > \sigma^2(\gamma+\beta)$. In that case the normalized residual becomes a new atom whose coefficient is $\|r_t\|$. This is the dictionary analogue of the DP-means rule for opening a new cluster (Kulis et al.).

Death works directly on the summaries. Hold the stored codes fixed and remove atom $k$, by zeroing its row and column in $A$ and its column in $B$ and refitting the remaining atoms through the usual block-coordinate update. This gives a surrogate that upper-bounds the true objective after deletion. We delete $k$ when

$$ \Delta_k \;=\; \hat f_{-k}(D) - \hat f(D) \;<\; \sigma^2\gamma, $$

where $\hat f$ is the surrogate and $\hat f_{-k}$ is its value without atom $k$. The test costs $O(PK)$ per atom using quantities the algorithm already stores. Forgetting matters here: when a pattern stops appearing, the atom's diagonal entry in $A$ decays geometrically, so $\Delta_k$ shrinks and the atom eventually dies. This is our principled replacement for patch-swapping.

The second step is analysis. We will prove that each move does not increase the forgetting-weighted surrogate. We will then extend Mairal's stationary-point argument to the case where $K$ changes only finitely often on a stationary stream. The atom cost $\gamma$ bounds $K$ by the total objective divided by $\sigma^2\gamma$, which restores the compactness that convergence theory needs.

The third step is calibration. When $\sigma^2$ is unknown, we estimate it as a forgetting-weighted mean of $\|r_t\|^2/(P-\|w_t\|_0)$. This is circular, because the residuals depend on the penalties, so we treat it as a fixed-point iteration and test empirically whether it converges or drifts.

Baselines

The naive reference point is a fixed analytic basis (an overcomplete DCT) with $\ell_0$ coding at the same sparsity threshold. It tells us how much any learning buys.

The strongest practical competitor is online dictionary learning (Mairal et al.) with its atom-replacement heuristic. It is the throughput standard, reported to learn from 7 million patches in 500 seconds on an 8-core workstation. We will run it at $K\in\{64,128,256,512\}$, with the oracle-best $K$ chosen on held-out data and reported separately so that it is generous to the baseline. We will use the same patches, mini-batch size, and single pass, plus a matched grid-search budget over its sparsity weight. We count as beating it if our method matches its oracle-$K$ PSNR without being told $K$ and beats every fixed $K$ on the noise-mismatch and drift streams.

The quality ceiling is the Gibbs-sampled Beta Process dictionary (Zhou et al.). It reports 34.44 dB on House under mismatched noise, against 30.67 dB for K-SVD, and 29.31 dB on New Orleans with 80% of pixels missing. We do not expect to beat it. Success means coming within roughly 0.5 dB while running orders of magnitude faster, in line with the roughly 1,000× speedup of BP-means over IBP Gibbs sampling reported in MAD-Bayes.

The streaming nonparametric competitor is the Recursive Indian Buffet Process of Streaming Inference for Infinite Feature Models. We run it on its own MNIST and Omniglot streams, scored by negative log predictive likelihood. No reported result was found on Lacuna for R-IBP's numeric scores, so we will rerun it ourselves.

Two ablations isolate what is new. The first keeps our birth rule but removes the death test. The second replaces the derived thresholds with a residual-threshold birth plus usage-count death whose two thresholds are freely tuned with the same budget.

Why not just…?

Why not just run online dictionary learning with a large $K$ and let the sparsity penalty leave extra atoms unused? This is the most serious threat. Oversized dictionaries under an $\ell_1$ penalty often do reasonably well. The evidence against fixed capacity is the noise-mismatch gap in Zhou et al.: K-SVD at 30.67 dB versus 34.44 dB for the adaptive Beta Process. That gap comes from batch K-SVD, though, not from the online method. Our mismatched-noise and drift experiments test this directly against the oracle-$K$ and largest-$K$ runs. If large-$K$ online learning matches us, the case for our method shrinks to memory savings and calibration, and we will report that.

Why not just add a residual-threshold birth rule to the online method by hand? Our birth rule is close to exactly such a heuristic, so this alternative is almost our method without the theory. The tuned-heuristic ablation decides it. If freely tuned thresholds match the derived ones at equal tuning budget, the contribution is the monotonicity proof and the self-calibration, not accuracy. Calibration is where we expect a difference: the derived penalties transfer across noise levels without retuning, while tuned heuristic thresholds should need retuning at each level. We will test transfer by tuning at one noise level and evaluating at others.

Why not just use streaming variational inference (R-IBP)? R-IBP is a forward filter that its authors say cannot revise features after a distribution shift. It is also evaluated on binary and linear-Gaussian features, not on restoration tasks. Its authors also show that its zero-noise limit is BP-means, so our method is the continuous, prunable endpoint of the same family. The drift stream and the MNIST/Omniglot comparison test whether discarding uncertainty costs predictive quality.

Why not just rerun batch BP-means or DP-space over sliding windows? Each window restarts optimization and scrambles atom identities between windows. Campbell et al. showed this kind of flicker for windowed clustering of video color. We measure it here as atom-matching stability across windows, and as wall-clock time per patch.

Proposed Experiments

On House denoising, we apply the mismatched-noise protocol of Zhou et al. across several true noise levels. We report PSNR and inferred $K$, checking whether $K$ moves from tens of atoms toward the hundreds as noise falls. On New Orleans, we run inpainting with 80% of pixels missing, coding only the observed pixels. On Castle we run compressive sensing, comparing our method with the "Online BP" variant.

For scale, we stream 7 million patches from a 12-megapixel image and Berkeley Segmentation Dataset patches. We report wall-clock time against the online method's 500 seconds, peak memory, and surrogate-cost curves.

For drift, we build a stream that concatenates BSDS patches with text-overlay patches and then switches back. We report PSNR on the current regime over time, how fast atoms die and are born, and the final $K$, comparing $\rho<1$ against $\rho=1$.

The decisive checks are three. First, the method must match oracle-$K$ online dictionary learning without being told $K$. Second, it must beat the tuned heuristic when penalties are transferred across noise levels. Third, on the stationary stream, the surrogate must decrease monotonically through every birth and death event.