PaperlayerView exact revision on arXiv

Source-linked AI summary

Optimal Shrinkage of Singular Values

Matan Gavish, David L. Donoho

arXiv:1405.7511v3math.ST

TL;DR

The paper asks how to recover low-rank matrices from noisy observations using singular-value shrinkage under different loss functions. It develops an asymptotic framework and a general method for finding optimal univariate shrinkers. The resulting shrinkers are asymptotically unique admissible for the studied losses, with explicit formulas for several norms and numerical evaluation for Schatten-p losses.

  • Problem

    The paper seeks a simple, natural singular-value shrinkage nonlinearity for low-rank matrix recovery, recognizing that the appropriate rule depends on the loss function and assumptions on X.

  • Method

    The paper analyzes univariate singular-value shrinkage in an asymptotic low-rank white-noise framework and develops a general method for deriving optimal shrinkers analytically or numerically.

  • Results

    For each studied loss, the framework produces an asymptotically unique admissible shrinker, including explicit formulas for Frobenius, operator, and nuclear norm losses.

  • Takeaways & Limitations

    The framework provides a single loss-specific shrinkage choice and extends numerical optimal-shrinker evaluation to Schatten-p losses when closed-form formulas are unavailable.

  • Takeaways & Limitations

    The optimality guarantee is among conservative shrinkers and is described as an artifact of the proof method rather than a definitive summary of optimality properties.

Abstract

from arXiv · show

We consider recovery of low-rank matrices from noisy data by shrinkage of singular values, in which a single, univariate nonlinearity is applied to each of the empirical singular values. We adopt an asymptotic framework, in which the matrix size is much larger than the rank of the signal matrix to be recovered, and the signal-to-noise ratio of the low-rank piece stays constant. For a variety of loss functions, including Mean Square Error (MSE - square Frobenius norm), the nuclear norm loss and the operator norm loss, we show that in this framework there is a well-defined asymptotic loss that we evaluate precisely in each case. In fact, each of the loss functions we study admits a unique admissible shrinkage nonlinearity dominating all other nonlinearities. We provide a general method for evaluating these optimal nonlinearities, and demonstrate our framework by working out simple, explicit formulas for the optimal nonlinearities in the Frobenius, nuclear and operator norm cases. For example, for a square low-rank n-by-n matrix observed in white noise with level $σ$, the optimal nonlinearity for MSE loss simply shrinks each data singular value $y$ to $\sqrt{y^2-4nσ^2 }$ (or to 0 if $y<2\sqrt{n}σ$). This optimal nonlinearity guarantees an asymptotic MSE of $2nrσ^2$, which compares favorably with optimally tuned hard thresholding and optimally tuned soft thresholding, providing guarantees of $3nrσ^2$ and $6nrσ^2$, respectively. Our general method also allows one to evaluate optimal shrinkers numerically to arbitrary precision. As an example, we compute optimal shrinkers for the Schatten-p norm loss, for any p>0.

1 Introduction

The paper studies low-rank matrix recovery from noisy observations using univariate singular-value shrinkage, whose choice depends on the loss function. In an asymptotic low-rank framework, it establishes optimal shrinkers for several losses and compares their performance with thresholding methods.

  • Low-rank matrix recovery observes Y = X + σZ and estimates X under a chosen loss, with noise entries assumed independent, standardized, and finite-fourth-moment.
  • Singular-value shrinkage applies a scalar nonlinearity to each data singular value, offering a simpler estimator than the broader class of bi-orthogonally invariant estimators.
  • For each studied loss, the asymptotic framework yields a single admissible shrinker that offers equal or better asymptotic loss at every low-rank model.
  • The framework explicitly derives optimal nonlinearities for Frobenius, operator, and nuclear norm losses, while also supporting numerical evaluation for other losses.
  • For Frobenius loss, the optimal shrinker has worst-case asymptotic MSE 2r at noise level 1/√n, versus 3r for optimally tuned hard thresholding and 6r for soft thresholding.

2 Preliminaries

The paper defines an asymptotic low-rank matrix-denoising framework and formalizes optimal singular-value shrinkers for broad loss families under white-noise assumptions.

  • The model uses matrices X_n observed as Y_n = X_n + σZ_n, with fixed-rank signals and white noise having zero mean, unit variance, and finite fourth moment.
  • The matrix dimensions grow with m_n/n → β, where 0 < β ≤ 1, while the nonzero signal singular values remain fixed across n.
  • The signal singular vectors are unknown and arbitrary, although distinct nonzero singular values simplify the analysis without being necessary.
  • The denoiser applies a univariate nonlinearity to each data singular value, within a broader class of bi-orthogonally invariant estimators.
  • The asymptotic loss is well-defined for a large class of nonlinearities, and an optimal shrinker is one whose loss is no worse than any competing shrinker across admissible signals.
  • The paper establishes optimal shrinkers for Frobenius, operator, and nuclear losses, gives a general construction framework, and supports numerical evaluation when closed forms are unavailable.

3 The Asymptotic Picture

The asymptotic picture separates signal-related singular values from a noise bulk, whose edge determines when observed singular values carry recoverable signal information.

  • In the null case X_n ≡ 0, the empirical singular values of Y_n = Z_n/√n converge to a generalized quarter-circle distribution with upper edge β+.
  • The noise-only singular values form the bulk, with the largest singular value converging to the bulk edge.
  • The analysis uses prior results on asymptotic singular-value locations, singular-vector angles, and noise-bulk behavior.
  • A signal singular value x produces an asymptotically separated data singular value y(x) when x ≥ β^1/4, with y(β^1/4) = β+.
  • For x ≥ β^1/4, c(x) and c̃(x) give the asymptotic cosines between the signal and corresponding data left and right singular vectors.

4 Optimal Shrinker for Frobenius Loss

For Frobenius loss, the paper derives an asymptotic lower bound from singular-value locations and singular-vector alignments, then identifies a shrinker that attains it.

  • The Frobenius-loss analysis begins by expanding the matrix loss for a general singular-value shrinker and deriving a lower bound.
  • The asymptotic lower bound depends on the limiting data singular values and the left and right singular-vector angles.
  • The candidate shrinker η* minimizes the asymptotic lower-bound terms associated with each signal singular value.
  • A successful shrinker must set to zero data singular values that do not correspond to signal, including values inside the noise bulk.
  • Conservative shrinkers impose a safety margin above the bulk edge, ensuring that noise-originating singular values are removed asymptotically.
  • The optimal Frobenius shrinker is continuous but not strictly conservative, and its asymptotic loss matches the lower bound while remaining no worse than other continuous shrinkers.

5 A Framework for Finding Optimal Shrinkers

The framework reduces optimal singular-value shrinkage to asymptotic loss minimization for orthogonally invariant, decomposable loss families. It combines atomic loss decomposition with a crossing-point rule that yields a shrinker dominating conservative alternatives.

  • Optimal shrinkers exist for a variety of loss families and are given by simple formulas among conservative shrinkers.
  • Orthogonally invariant losses are unchanged by simultaneous orthogonal transformations of both matrix arguments.
  • Frobenius and nuclear losses are sum-decomposable, whereas operator loss is max-decomposable.
  • For decomposable losses, asymptotic loss separates into identical atomic terms across signal singular values.
  • The zero shrinker is optimal below x = β^1/4, while above that threshold the method minimizes a specific 2-by-2 loss function.
  • Concatenating the nonzero shrinker with the zero shrinker at their loss-crossing point produces a shrinker whose asymptotic loss dominates every conservative shrinker.
  • The general recipe evaluates the local loss, solves for its minimizer, computes the minimum, finds the crossing point, and composes the resulting shrinker with x(y).
  • The limiting asymptotic loss is obtained by taking limits of the atomic units as matrix dimensions grow.

6 Finding Optimal Shrinkers Analytically: Frobenius, Operator & Nuclear Losses

The framework yields explicit optimal shrinkers for Frobenius, operator, and nuclear norm losses. These formulas arise by optimizing the associated 2-by-2 error loss and comparing it with the zero shrinker.

  • Theorem 1 provides explicit optimal singular-value shrinkers for Frobenius, operator, and nuclear norm losses.
  • The derivations use eigenvalue and singular-value identities for a 2-by-2 error matrix, including trace, determinant, and derivative relations.
  • Frobenius norm loss: The Frobenius optimal shrinker is recovered by simplifying the general transformation from signal location x to observed singular value y.
  • Frobenius norm loss: For Frobenius loss, the intermediate minimizer is η**(x) = x c(x) c̃(x), and the crossing occurs at x0 = β^1/4.
  • Operator norm loss: For operator loss, the intermediate minimizer is η**(x) = x, so the optimal shrinker maps each data singular value back to its corresponding signal location.
  • Operator norm loss: The operator-norm shrinker is discontinuous at y(β^1/4) = 1 + √β, yet its asymptotic loss exists and dominates conservative shrinkers.

7 Finding Optimal Shrinkers Numerically: Schatten norm losses

The framework can compute optimal shrinkers numerically for Schatten-p losses when closed-form optimization is unwieldy. The resulting figures cover both norm and quasi-norm regimes across two aspect ratios.

  • When closed-form solutions are complicated, the optimization reduces to numerical minimization of a univariate function.
  • For Schatten-p loss, the method evaluates selected observed singular values, transforms them to signal locations, and numerically minimizes F(η, x).
  • Figures 4 and 5 show numerically computed optimal shrinkers for Schatten-p losses over selected values of p.
  • Schatten-p norm losses: For p ≥ 1, the plotted cases include p = 1, p = 2, and p = 10000, with the last nearly indistinguishable from operator loss.
  • The figures compare square matrices, β = 1, with matrices having four times as many columns as rows, β = 0.25.

8 Extensions

The paper extends the framework to general noise levels, unknown noise, and non-orthogonally invariant i.i.d. noise. The latter extension requires a generic random orientation of the signal matrix.

  • The extensions cover known or unknown noise levels and i.i.d. noise distributions that are not necessarily orthogonally invariant.
  • When the noise level is known, an optimal shrinker can be recalibrated from the natural 1/√n scaling to another noise level.
  • When the noise level is unknown, the method estimates it using a robust estimator based on a median singular value and the Marcenko–Pastur median.
  • The formal results assume orthogonally invariant noise, although Gaussian noise satisfies this assumption while many common white-noise distributions do not.
  • General white noise: For general white noise, the results extend when the signal has uniformly distributed singular vectors and a fixed rank and aspect ratio.
  • General white noise: Under that alternative framework, the results depend on specifying signal singular values and using a generic signal matrix with those singular values.

9 Simulation

Two simulation studies evaluated how well the asymptotic analysis matches finite-matrix behavior and compared the optimal shrinker with tuned thresholding methods.

  • The simulations examined finite matrices to assess asymptotic-loss accuracy and compare the optimal shrinker with optimally tuned hard and soft thresholding.The studies used empirical losses from noisy low-rank matrix observations.
  • The first study used n-by-n matrices with exactly r identical nonzero singular values and focused on asymptotic Frobenius loss.It compared (n, r) = (20, 1), (100, 1), (50, 2), and (50, 4) across Gaussian, uniform, and Student-t noise.
  • The second study used rank-1 20-by-20 matrices with i.i.d. Gaussian noise to compare brute-force optimal shrinkage against asymptotically optimal shrinkers.Brute-force shrinkers were obtained by grid search over η and averaging empirical loss over 10 Monte Carlo draws for Frobenius, nuclear, and operator losses.

10 Conclusion

The conclusion presents a general framework for finding optimal shrinkers and clarifies both its scope and remaining limitations. Simulations compare asymptotic and empirical behavior across matrix sizes, ranks, noise distributions, and loss functions.

  • 10 Conclusion: The framework finds optimal shrinkers analytically or numerically for a variety of loss functions.
  • 10 Conclusion: Theorem 1 guarantees asymptotic unique admissibility only among conservative shrinkers, so it should be viewed as a method for finding good shrinkers rather than a definitive optimality statement.
  • 10 Conclusion: The simulations compare asymptotic and empirically observed Frobenius losses for n = 20, 100 and r = 1.
  • 10 Conclusion: For Gaussian noise, controlling the cumulative effect of null singular values requires loss functions with a Lipschitz regularity property in addition to decomposability and orthogonal invariance.
  • 10 Conclusion: Closed-form optimal shrinkers for Schatten-p losses and a generalization to Ky-Fan norms remain open problems for further study.
  • 10 Conclusion: The simulations also compare asymptotic and empirically observed Frobenius losses for n = 50 and r = 2, 4.
  • 10 Conclusion: Figure 8 compares brute-force optimal shrinkage with asymptotically optimal shrinkers for β = 1.

Reproducible Research

The code supplement provides software for computing optimal singular-value shrinkage and scripts for reproducing the paper’s figures and numerical shrinker evaluations.

  • The supplement includes a Matlab function that calculates optimal singular-value shrinkage for Frobenius, operator, and nuclear norm losses.It supports both known and unknown noise levels.
  • The supplement includes scripts that generate each figure in the paper.
  • The scripts for Figures 4 and 5 include an example of numerical evaluation of optimal shrinkers.
Loading 1405.7511v3…