Optimal Shrinkage of Singular Values

DOI10.1109/TIT.2017.2653801MaRDI QIDQ5280888zbMATH OpenOpenAlexFDO

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

(40)

• Design-free estimation of integrated covariance matrices for high-frequency data
• Edge statistics of large dimensional deformed rectangular matrices
• Heteroskedastic PCA: algorithm, optimality, and applications
• Bidimensional linked matrix factorization for pan-omics pan-cancer analysis
• Optimal prediction in the linearly transformed spiked model
• Ridge-type linear shrinkage estimation of the mean matrix of a high-dimensional normal distribution
• Imputation and low-rank estimation with missing not at random data
• Rapid evaluation of the spectral signal detection threshold and Stieltjes transform
• High dimensional deformed rectangular matrices with applications in matrix denoising
• High-dimensional change-point estimation: combining filtering with convex optimization
• Optimal shrinkage of eigenvalues in the spiked covariance model
• Multidimensional scaling of noisy high dimensional data
• Optimal singular value shrinkage for operator norm loss: extending to non-square matrices
• Adaptive shrinkage of singular values
• Log-determinant divergences revisited: alpha-beta and gamma log-det divergences
• OptShrink: An Algorithm for Improved Low-Rank Signal Matrix Denoising by Optimal, Data-Driven Singular Value Shrinkage
• Imputation of Mixed Data With Multilevel Singular Value Decomposition
• Generalized SURE for optimal shrinkage of singular values in low-rank matrix denoising
• Consistency, breakdown robustness, and algorithms for robust improper maximum likelihood clustering
• Structural variability from noisy tomographic projections
• Optimal scaling for p-norms and componentwise distance to singularity
• Selecting Regularization Parameters for Nuclear Norm--Type Minimization Problems
• Matrix denoising for weighted loss functions and heterogeneous signals
• MIMCA: multiple imputation for categorical variables with multiple correspondence analysis
• On approximating matrix norms in data streams
• Generalized Factor Model for Ultra-High Dimensional Correlated Variables with Mixed Types
• Smooth singular value thresholding algorithm for low-rank matrix completion problem
• Bayesian simultaneous factorization and prediction using multi-omic data
• Data-driven optimal shrinkage of singular values under high-dimensional noise with separable covariance structure with application
• Optimal clustering by Lloyd's algorithm for low-rank mixture model
• Distribution-free online change detection for low-rank images
• Spectral properties of elementwise-transformed spiked matrices
• The Dyson equalizer: adaptive noise stabilization for low-rank signal detection and recovery
• Deflated HeteroPCA: overcoming the curse of ill-conditioning in heteroskedastic PCA
• Multivariate sensitivity-adaptive polynomial chaos expansion for high-dimensional surrogate modeling and uncertainty quantification
• Comments on: ``Data integration via analysis of subspaces (DIVAS)
• Data integration via analysis of subspaces (DIVAS)
• Optimal eigenvalue shrinkage in the semicircle limit
• Multifaceted neuroimaging data integration via analysis of subspaces
• Bayesian joint additive factor models for multiview learning

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)