Biwhitening

Biwhitening separates signal from noise in a data matrix whose noise variance differs from entry to entry, as it does for counts. When the noise has constant variance, its eigenvalues follow the Marchenko–Pastur law, and components of the signal stand out above the edge of that law. Unequal variances change the noise spectrum in a way that depends on the unknown pattern of variances, so that no fixed threshold separates signal from noise. The method of Landa, Zhang, and Kluger (2022) restores the law by rescaling the data:

  1. Estimate the noise variance of each entry.
  2. Scale the rows and columns of the data so that the noise has average variance one in every row and every column.
  3. Count the singular values of the scaled matrix that exceed the largest singular value expected of noise. Their number estimates the rank of the signal.
  4. Estimate the signal from those components.

Unlike a variance-stabilizing transformation, the rescaling in step 2 leaves the rank of the signal unchanged; see Comparison with variance-stabilizing transformations.

The scaling of step 2 is computed by MatrixCovers.jl, whose documentation discusses how to estimate variances for several kinds of data.

Installation

using Pkg
Pkg.add(url="https://github.com/HolyLab/Biwhitening.jl")

A first example

The example simulates counts with Poisson noise around a matrix X of expected values. X has rank 5, and its rows and columns differ widely in scale, so the noise variance differs from entry to entry.

using Biwhitening, LinearAlgebra, Random

function poisson(rng, λ)        # one Poisson variable with mean λ
    k, t = 0, randexp(rng)
    while t < λ
        k += 1
        t += randexp(rng)
    end
    return k
end

rng = Xoshiro(1)
m, n, r = 400, 1200, 5
X = (rand(rng, m, r) * rand(rng, r, n)) .* (0.2 .+ 3 .* rand(rng, m)) .* (0.2 .+ 3 .* rand(rng, n))'
Y = [poisson(rng, x) for x in X]

biwhiten assumes Poisson noise unless told otherwise:

bw = biwhiten(Y)
Biwhitened{Float64} of a 400×1200 matrix
  rank: 5
  noise variance: 1.011
  Kolmogorov–Smirnov distance to the Marchenko–Pastur law: 0.0144

Five singular values of the scaled matrix exceed noise_edge, the largest singular value expected of noise:

round.(bw.S[1:8]; digits=1)', noise_edge(bw)
(adjoint([1333.5, 106.8, 99.1, 98.1, 95.1, 53.9, 53.6, 53.4]), 54.64101615137755)

The result holds the scales bw.a and bw.b, every singular value bw.S, and the singular vectors bw.U and bw.V of the components above the noise.

scaled(bw, Y) returns the scaled matrix itself.

Checking the variance model

The rank is meaningful only if the variances given to biwhiten describe the noise. Two numbers, both shown when a result is displayed, test this:

  • noise_variance is the noise variance of the scaled matrix, estimated from its median eigenvalue. It should be close to one. A larger value means that the noise exceeds what the model predicts, and the rank is then overestimated. When the estimate changes the count, the display adds the rank for noise of the estimated variance.
  • ks_distance is the Kolmogorov–Smirnov distance between the eigenvalues and the Marchenko–Pastur law. Each component of the signal contributes one eigenvalue that the law does not describe, so the distance is at least the rank divided by the number of eigenvalues (here 5/400).

Neither number replaces a look at the spectrum itself. With a Makie backend loaded, spectrumplot draws it:

using CairoMakie
spectrumplot(bw)
Example block output

On the right, the histogram of the singular values follows the Marchenko–Pastur law up to the noise edge, as it should when the variance model describes the noise. On the left, the five components of the signal stand well clear of the edge. Real data are seldom this clear: the singular values often descend into the bulk without a gap, and the count of components then depends on exactly where the edge lies. The plot shows how many components are in that position, and whether a change of slope sets some of them apart.

d =MarchenkoPastur(bw) is the law for the eigenvalues bw.S .^ 2 ./ q, where q is the larger dimension of the matrix, and Biwhitening.pdf(d, x) is its probability density, for drawing the comparison in another way.

Choosing the variance model

Counts from sequencing are often more variable than the Poisson distribution allows. A QuadraticVariance describes noise whose variance is a quadratic function of the expected value, a + b*x + c*x^2, and fit_variance chooses b and c by comparing the spectrum with the Marchenko–Pastur law.

The counts below have a negative binomial distribution with variance x + x^2 / 4. Under the Poisson model the noise variance is far from one and the rank is wrong:

gamma4(rng) = sum(randexp(rng) for _ in 1:4) / 4     # gamma variable, shape 4, mean 1
Ynb = [poisson(rng, x * gamma4(rng)) for x in X]
biwhiten(Ynb)
Biwhitened{Float64} of a 400×1200 matrix
  rank: 122 (20 if the noise has the estimated variance)
  noise variance: 1.837
  Kolmogorov–Smirnov distance to the Marchenko–Pastur law: 0.339

The fit tries several weights β for the quadratic term and keeps the one whose spectrum is closest to the law. It starts from a coarse grid and then halves the spacing around the best candidate twice:

fit = fit_variance(Ynb)
VarianceFit{Float64}: Var(y) = 1.007*x + 0.2517*x^2
      β       α      KS distance   rank
    0.0     1.837  0.0666        20
    0.1     1.276  0.0155        5
    0.15    1.119  0.0125        5
  * 0.2     1.006  0.0125        5
    0.25    0.9153 0.0125        5
    0.3     0.8422 0.0125        5
    0.4     0.7236 0.0194        6
    0.6     0.5682 0.0417        11
    0.8     0.4719 0.0554        18
    1.0     0.4037 0.0696        24
bwnb = biwhiten(Ynb, fit.model)
Biwhitened{Float64} of a 400×1200 matrix
  rank: 5
  noise variance: 1.0
  Kolmogorov–Smirnov distance to the Marchenko–Pastur law: 0.0125

The fitted coefficients are close to the true ones (b = 1, c = 0.25), the noise variance is close to one, and the rank is recovered.

Three caveats apply to the fit:

  • fit.scan lists every candidate. When the distance changes little over a range of β, the spectrum does not determine β within that range. The rank is then uncertain to the extent that the candidates in that range disagree about it. Above, the candidates from 0.15 to 0.3 share the smallest distance that five components allow, 5/400, and the fit takes the middle one.
  • The refinement assumes that the distance has a single minimum at the spacing of the coarse grid. To examine every element of a grid of your own, pass it as grid with refine=0.
  • Because the chosen candidate was selected for its small distance, that distance is biased downward. To assess the model without this bias, fit it on some of the rows, biwhiten the remaining rows with the fitted model, and compute their ks_distance.
  • With grid=[0], the fit keeps the variance proportional to the expected value and estimates only the constant of proportionality.

For data that are not counts, pass a matrix of variance estimates, of the same size as the data, as the second argument of biwhiten.

Estimating the signal

The singular values above the noise overestimate those of the signal, and the corresponding singular vectors are tilted away from the signal's. A Shrinker replaces each singular value by an estimate that accounts for both effects (Gavish and Donoho, 2017); shrink returns the estimates.

round.([bw.S[1:5] shrink(bw, OperatorShrinker()) shrink(bw, FrobeniusShrinker())]; digits=1)
5×3 Matrix{Float64}:
 1333.5  1332.9  1332.3
  106.8    98.8    90.9
   99.1    90.4    81.8
   98.1    89.2    80.5
   95.1    85.9    76.9

denoise rebuilds the matrix from the components with shrunk singular values and undoes the scaling. The result estimates the expected value of the data; below, its relative error is compared with that of the data themselves:

Xhat = denoise(bw)
norm(Xhat - X) / norm(X), norm(Y - X) / norm(X)
(0.05389402704815213, 0.3850437437555887)

scores gives coordinates of the rows or columns on the components, for visualization or clustering:

Z = scores(bw, 1)       # one row for each row of Y, one column for each component
size(Z)
(400, 5)

With the default HardThreshold these are the principal component scores of the scaled matrix. score_noise gives the noise variance of each column of the scores. It is close to one for a component well above the edge, where distances between rows are therefore in units of the noise, and it grows as a component approaches the edge, because the estimated singular vector then turns toward the noise:

round.(score_noise(bw, 1); digits=2)'
1×5 adjoint(::Vector{Float64}) with eltype Float64:
 1.0  1.26  1.32  1.32  1.35

The sum of these values is the expected squared length of the noise in one row of Z.

The rules differ in what they estimate best:

rulebest estimate of
FrobeniusShrinkerthe signal, by the sum of squared errors of its entries
OperatorShrinkereach singular value of the signal
NuclearShrinkerthe signal, by the sum of the singular values of the error
GramShrinkerinner products between rows, or between columns, of the signal
HardThresholdnone; the singular values are unchanged

Zeros, empty rows, and sparse data

biwhiten accepts sparse matrices and matrices of integers. Rows and columns without any nonzero variance estimate receive a scale of zero and are left out of the spectrum.

For some patterns of zeros no scaling exists: for example, a row whose nonzero entries lie in too few columns. biwhiten then throws an error that names the rows or columns responsible. Either remove them, or pass the keyword shrink=δ with a small positive δ. (This keyword is unrelated to the function shrink.) It mixes the variance estimates with those of a rank-one model, so that the scaling always exists. The MatrixCovers documentation describes the condition and the meaning of δ.

Comparison with variance-stabilizing transformations

A variance-stabilizing transformation equalizes noise variances in a different way: it applies a nonlinear function to each entry, such as the square root for Poisson counts or log(1 + y), so that the noise variance is approximately the same in every entry. Biwhitening equalizes only the average variance of each row and column. In exchange, it preserves linearity, on which matrix factorization depends.

Factorization methods such as principal component analysis represent the data as a sum of components, and the rank of the signal is the number of components needed. Biwhitening divides each entry by a constant, so the expected value of the scaled matrix, X ./ (a .* b'), has the same rank as the expected value X of the data (Landa, Zhang, and Kluger, 2022, eq. 2.3), and counts that add before scaling still add after it. A nonlinear transformation f preserves neither property: f.(X) generally has higher rank than X, and the expected value of f.(Y) is not f.(X). The components found in transformed data therefore need not correspond to those of the signal, and their number need not equal its rank.

Both approaches need a model of the noise variance: the square root stabilizes Poisson noise, for example, but not overdispersed noise. Variance-stabilizing transformations are also approximate, and least accurate for small expected values, which predominate in sparse counts. Biwhitening rests instead on an asymptotic theorem, which assumes that the noise is independent from entry to entry (Landa, Zhang, and Kluger, Theorem 2.2 and Proposition 4.1). Finally, because the scales weight rows and columns unequally, the singular vectors of the scaled matrix differ from those of the unscaled signal. denoise undoes the scaling, but scores are coordinates in the scaled matrix.

Cost

For an m × n matrix with m ≤ n, biwhiten forms the dense m × m Gram matrix of the scaled data and computes all of its eigenvalues. This takes memory proportional to m^2 and time proportional to m^2 * n + m^3, whether or not the data are sparse. fit_variance repeats this for every candidate, at most ten by default.

References

  • M. Gavish and D. L. Donoho, "Optimal shrinkage of singular values," IEEE Transactions on Information Theory 63 (2017) 2137–2152. doi:10.1109/TIT.2017.2653801
  • B. Landa, T. T. C. K. Zhang, and Y. Kluger, "Biwhitening reveals the rank of a count matrix," SIAM Journal on Mathematics of Data Science 4 (2022) 1420–1446. doi:10.1137/21M1456807