OptShrink: An algorithm for improved low-rank signal matrix denoising by optimal, data-driven singular value shrinkage
arXiv:1306.6042 · doi:10.1109/TIT.2014.2311661
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.
arXiv commentPublished version. The algorithm can be downloaded from http://www.eecs.umich.edu/~rajnrao/optshrink
References in corpus (21)
- Rank-Sparsity Incoherence for Matrix Decomposition
- Matrix estimation by Universal Singular Value Thresholding
- Estimation of high-dimensional low-rank matrices
- Graph spectra and the detectability of community structure in networks
- Structured Sparse Principal Component Analysis
- Optimal Solutions for Sparse Principal Component Analysis
- Tracy--Widom limit for the largest eigenvalue of a large class of complex sample covariance matrices
- Regularization Techniques for Learning with Matrices
- High Dimensional Statistical Inference and Random Matrices
- Universality of covariance matrices
- Spectra of random graphs with arbitrary expected degrees
- Finding Dense Clusters via "Low Rank + Sparse" Decomposition
- The largest eigenvalues of sample covariance matrices for a spiked population: diagonal case
- Diagonal and Low-Rank Matrix Decompositions, Correlation Matrices, and Ellipsoid Fitting
- Extreme gaps between eigenvalues of random matrices
- A note on universality of the distribution of the largest eigenvalues in certain sample covariance matrices
- 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
- On determining the number of spikes in a high-dimensional spiked population model
- When are the most informative components for inference also the principal components?
Cited by in corpus (31)
- Matrix estimation by Universal Singular Value Thresholding
- 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
- Generalized SURE for optimal shrinkage of singular values in low-rank matrix denoising
- On Low-Rank Hankel 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
- High dimensional regression and matrix estimation without tuning parameters
- Adaptive Higher-order Spectral Estimators
- Adaptive Structure-constrained Robust Latent Low-Rank Coding for Image Recovery
- Adaptive Shrinkage of singular values
- Matrix Denoising with Partial Noise Statistics: Optimal Singular Value Shrinkage of Spiked F-Matrices
- Joint Covariance Estimation with Mutual Linear Structure
- Optimal singular value shrinkage for operator norm loss
- Empirical Bayes PCA in high dimensions
- Freeness over the diagonal and outliers detection in deformed random matrices with a variance profile
- A Fast Data Driven Shrinkage of Singular Values for Arbitrary Rank Signal Matrix Denoising
- Bi-cross-validation for factor analysis
- Augmented Robust PCA For Foreground-Background Separation on Noisy, Moving Camera Video
- Optimal Estimation of Schatten Norms of a rectangular Matrix
- Estimation of the number of spikes using a generalized spike population model and application to RNA-seq data