Optimal Shrinkage of Singular Values

DOI10.1109/TIT.2017.2653801zbMATH Open1366.94100arXiv1405.7511OpenAlexW2962946304MaRDI QIDQ5280888FDOQ5280888

Authors: Matan Gavish, David Donoho 

Publication date: 27 July 2017

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

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.

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

Mathematics Subject Classification ID

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

Cited In (29)

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

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)