Optimal Shrinkage of Singular Values

DOI10.1109/TIT.2017.2653801MaRDI QIDQ5280888zbMATHOpenAlexFDO

Authors Matan Gavish, David Donoho

Publication date 27 July 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1405.7511

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Abstract: 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 $sigma$, the optimal nonlinearity for MSE loss simply shrinks each data singular value $y$ to $sqrt{y}^2-4nsigm{a}^2$ (or to 0 if $y<2sqrtnsigma$). This optimal nonlinearity guarantees an asymptotic MSE of $2nrsigm{a}^2$, which compares favorably with optimally tuned hard thresholding and optimally tuned soft thresholding, providing guarantees of $3nrsigm{a}^2$ and $6nrsigm{a}^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.

Cited in

(29)

• Matrix denoising for weighted loss functions and heterogeneous signals
• Optimal singular value shrinkage for operator norm loss: extending to non-square matrices
• Generalized SURE for optimal shrinkage of singular values in low-rank matrix denoising
• Heteroskedastic PCA: algorithm, optimality, and applications
• Bayesian simultaneous factorization and prediction using multi-omic data
• Ridge-type linear shrinkage estimation of the mean matrix of a high-dimensional normal distribution
• On approximating matrix norms in data streams
• Data-driven optimal shrinkage of singular values under high-dimensional noise with separable covariance structure with application
• High dimensional deformed rectangular matrices with applications in matrix denoising
• Smooth singular value thresholding algorithm for low-rank matrix completion problem
• Imputation and low-rank estimation with missing not at random data
• Optimal prediction in the linearly transformed spiked model
• Design-free estimation of integrated covariance matrices for high-frequency data
• Edge statistics of large dimensional deformed rectangular matrices
• Rapid evaluation of the spectral signal detection threshold and Stieltjes transform
• Bidimensional linked matrix factorization for pan-omics pan-cancer analysis
• Imputation of Mixed Data With Multilevel Singular Value Decomposition
• Structural variability from noisy tomographic projections
• Generalized Factor Model for Ultra-High Dimensional Correlated Variables with Mixed Types
• Consistency, breakdown robustness, and algorithms for robust improper maximum likelihood clustering
• OptShrink: An Algorithm for Improved Low-Rank Signal Matrix Denoising by Optimal, Data-Driven Singular Value Shrinkage
• High-dimensional change-point estimation: combining filtering with convex optimization
• Adaptive shrinkage of singular values
• Optimal scaling for p-norms and componentwise distance to singularity
• Log-determinant divergences revisited: alpha-beta and gamma log-det divergences
• Optimal shrinkage of eigenvalues in the spiked covariance model
• MIMCA: multiple imputation for categorical variables with multiple correspondence analysis
• Multidimensional scaling of noisy high dimensional data
• Selecting Regularization Parameters for Nuclear Norm--Type Minimization Problems

This page was built for publication: Optimal Shrinkage of Singular Values

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5280888)