OptShrink: An algorithm for improved low-rank signal matrix denoising by optimal, data-driven singular value shrinkage

Abstract

The truncated singular value decomposition (SVD) of the measurement matrix is the optimal solution to the_representation_ problem of how to best approximate a noisy measurement matrix using a low-rank matrix. Here, we consider the (unobservable)_denoising_ problem of how to best approximate a low-rank signal matrix buried in noise by optimal (re)weighting of the singular vectors of the measurement matrix. We exploit recent results from random matrix theory to exactly characterize the large matrix limit of the optimal weighting coefficients and show that they can be computed directly from data for a large class of noise models that includes the i.i.d. Gaussian noise case. Our analysis brings into sharp focus the shrinkage-and-thresholding form of the optimal weights, the non-convex nature of the associated shrinkage function (on the singular values) and explains why matrix regularization via singular value thresholding with convex penalty functions (such as the nuclear norm) will always be suboptimal. We validate our theoretical predictions with numerical simulations, develop an implementable algorithm (OptShrink) that realizes the predicted performance gains and show how our methods can be used to improve estimation in the setting where the measured matrix has missing entries.

Published version. The algorithm can be downloaded from http://www.eecs.umich.edu/~rajnrao/optshrink

References in corpus (11)

• Graph spectra and the detectability of community structure in networks
• Structured Sparse Principal Component Analysis
• High Dimensional Statistical Inference and Random Matrices
• Spectra of random graphs with arbitrary expected degrees
• Finding Dense Clusters via "Low Rank + Sparse" Decomposition
• Diagonal and Low-Rank Matrix Decompositions, Correlation Matrices, and Ellipsoid Fitting
• Learning mixtures of spherical Gaussians: moment methods and spectral decompositions
• Isotropic Local Laws for Sample Covariance and Generalized Wigner Matrices
• Risk estimation for matrix recovery with spectral regularization
• When are the most informative components for inference also the principal components?
• On determining the number of spikes in a high-dimensional spiked population model

Cited by in corpus (30)

• Enhanced Low-Rank Matrix Approximation
• Low-rank and Adaptive Sparse Signal (LASSI) Models for Highly Accelerated Dynamic Imaging
• Asymptotic performance of PCA for high-dimensional heteroscedastic data
• Deterministic parallel analysis: An improved method for selecting factors and principal components
• Downlink Precoding with Mixed Statistical and Imperfect Instantaneous CSI for Massive MIMO Systems
• Improved Sparse Low-Rank Matrix Estimation
• Efficient Computation of Limit Spectra of Sample Covariance Matrices
• ScreeNOT: Exact MSE-Optimal Singular Value Thresholding in Correlated Noise
• Is your data alignable? Principled and interpretable alignability testing and integration of single-cell data
• Optimal spectral shrinkage and PCA with heteroscedastic noise
• On Low-Rank Hankel Matrix Denoising
• Generalized SURE for optimal shrinkage of singular values in low-rank matrix denoising
• Denoising Click-evoked Otoacoustic Emission Signals by Optimal Shrinkage
• Spiked separable covariance matrices and principal components
• How to reduce dimension with PCA and random projections?
• PCA from noisy, linearly reduced data: the diagonal case
• Adaptive Higher-order Spectral Estimators
• High dimensional regression and matrix estimation without tuning parameters
• Adaptive Shrinkage of singular values
• Optimal singular value shrinkage for operator norm loss
• Matrix Denoising with Partial Noise Statistics: Optimal Singular Value Shrinkage of Spiked F-Matrices
• Empirical Bayes PCA in high dimensions
• Adaptive Structure-constrained Robust Latent Low-Rank Coding for Image Recovery
• Freeness over the diagonal and outliers detection in deformed random matrices with a variance profile
• Joint Covariance Estimation with Mutual Linear Structure
• A Fast Data Driven Shrinkage of Singular Values for Arbitrary Rank Signal Matrix Denoising
• Bi-cross-validation for factor analysis
• Optimal Estimation of Schatten Norms of a rectangular Matrix
• Augmented Robust PCA For Foreground-Background Separation on Noisy, Moving Camera Video
• Estimation of the number of spikes using a generalized spike population model and application to RNA-seq data