The Optimal Hard Threshold for Singular Values is <inline-formula> <tex-math notation="TeX">4/ 3 </tex-math></inline-formula>

DOI10.1109/TIT.2014.2323359zbMATH Open1360.94071arXiv1305.5870OpenAlexW2963780177MaRDI QIDQ2986241FDOQ2986241

Authors: Matan Gavish, David Donoho 

Publication date: 16 May 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 hard thresholding of singular values, where singular values below a prescribed threshold $lambda$ are set to 0. We study the asymptotic MSE in a framework where the matrix size is large compared to the rank of the matrix to be recovered, and the signal-to-noise ratio of the low-rank piece stays constant. The AMSE-optimal choice of hard threshold, in the case of n-by-n matrix in noise level sigma, is simply $(4/sqrt3)sqrtnsigmaapprox2.309sqrtnsigma$ when $sigma$ is known, or simply $2.858cdot{y}_{med}$ when $sigma$ is unknown, where $y_{med}$ is the median empirical singular value. For nonsquare $m$ by $n$ matrices with $meqn$, these thresholding coefficients are replaced with different provided constants. In our asymptotic framework, this thresholding rule adapts to unknown rank and to unknown noise level in an optimal manner: it is always better than hard thresholding at any other value, no matter what the matrix is that we are trying to recover, and is always better than ideal Truncated SVD (TSVD), which truncates at the true rank of the low-rank matrix we are trying to recover. Hard thresholding at the recommended value to recover an n-by-n matrix of rank r guarantees an AMSE at most $3nrsigm{a}^2$. In comparison, the guarantee provided by TSVD is $5nrsigm{a}^2$, the guarantee provided by optimally tuned singular value soft thresholding is $6nrsigm{a}^2$, and the best guarantee achievable by any shrinkage of the data singular values is $2nrsigm{a}^2$. Empirical evidence shows that these AMSE properties of the $4/sqrt3$ thresholding rule remain valid even for relatively small n, and that performance improvement over TSVD and other shrinkage rules is substantial, turning it into the practical hard threshold of choice.

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

Recommendations

• The real structured singular value is hardly approximable
• A parameterized lower bound for the smallest singular value
• Determination of singular value truncation threshold for regularization in ill-posed problems
• Lower bounds for the smallest singular value
• A lower bound for the smallest singular value
• A lower bound for the smallest singular value
• Optimal Gersgorin-style estimation of the singular value
• A new lower bound for the smallest singular value
• Further lower bounds for the smallest singular value
• Two new lower bounds for the smallest singular value

Mathematics Subject Classification ID

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

Cited In (64)

• Dynamic mode decomposition of deformation fields in elastic and elastic-plastic solids
• WSN optimization for sampling-based signal estimation using semi-binarized variational autoencoder
• Automated nonlinear feedforward controller identification applied to engine air path output tracking
• \textit{ScreeNOT}: exact MSE-optimal singular value thresholding in correlated noise
• Optimal estimation and computational limit of low-rank Gaussian mixtures
• Biwhitening Reveals the Rank of a Count Matrix
• Data‐driven identification of the spatiotemporal structure of turbulent flows by streaming dynamic mode decomposition
• Optimal estimation of Schatten norms of a rectangular matrix
• Empirical Bayes Poisson matrix completion
• Sparse and integrative principal component analysis for multiview data
• Spiked singular values and vectors under extreme aspect ratios
• Data-driven optimal shrinkage of singular values under high-dimensional noise with separable covariance structure with application
• A Schatten-\(q\) low-rank matrix perturbation analysis via perturbation projection error bound
• Adaptive singular value shrinkage estimate for low rank tensor denoising
• Selecting Regularization Parameters for Nuclear Norm--Type Minimization Problems
• Combining dynamic mode decomposition with ensemble Kalman filtering for tracking and forecasting
• Matrix denoising for weighted loss functions and heterogeneous signals
• Ridge-type linear shrinkage estimation of the mean matrix of a high-dimensional normal distribution
• Reducing subspace models for large‐scale covariance regression
• Rate-optimal perturbation bounds for singular subspaces with applications to high-dimensional statistics
• Deterministic parallel analysis: an improved method for selecting factors and principal components
• Matrix estimation by universal singular value thresholding
• Nonlinear model order reduction via dynamic mode decomposition
• Modes of homogeneous gradient flows
• Variable projection methods for an optimized dynamic mode decomposition
• Efficient computation of limit spectra of sample covariance matrices
• Low-rank approximation and completion of positive tensors
• Time-delay observables for Koopman: theory and applications
• Adaptive shrinkage of singular values
• Detection and prediction of equilibrium states in kinetic plasma simulations via mode tracking using reduced-order dynamic mode decomposition
• Time-resolved denoising using model order reduction, dynamic mode decomposition, and Kalman filter and smoother
• Minimax risk of matrix denoising by singular value thresholding
• A novel coupling of noise reduction algorithms for particle flow simulations
• Exploring dimension learning via a penalized probabilistic principal component analysis
• Classification of spatiotemporal data via asynchronous sparse sampling: application to flow around a cylinder
• Iterative procedure for network inference
• Comparative numerical analysis using reduced-order modeling strategies for nonlinear large-scale systems
• On the structure of time-delay embedding in linear models of non-linear dynamical systems
• Compressed sensing and dynamic mode decomposition
• Model and data reduction for data assimilation: particle filters employing projected forecasts and data with application to a shallow water model
• Multiresolution dynamic mode decomposition
• A machine learning approach to optimal Tikhonov regularization. I: Affine manifolds
• Randomized Dynamic Mode 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
• An improved criterion to select dominant modes from dynamic mode decomposition
• SINDy-PI: a robust algorithm for parallel implicit sparse identification of nonlinear dynamics
• Estimation of the Number of Spiked Eigenvalues in a Covariance Matrix by Bulk Eigenvalue Matching Analysis
• Detecting regime transitions in time series using dynamic mode decomposition
• Intelligent Initialization and Adaptive Thresholding for Iterative Matrix Completion: Some Statistical and Algorithmic Theory forAdaptive-Impute
• Bi-cross-validation for factor analysis
• Low-rank matrix denoising for count data using unbiased Kullback-Leibler risk estimation
• Optimal shrinkage of eigenvalues in the spiked covariance model
• Shared subspace models for multi-group covariance estimation
• Randomized model order reduction
• Analysis of the onset and evolution of a dynamic stall vortex on a periodic plunging aerofoil
• Discovering governing equations from data by sparse identification of nonlinear dynamical systems
• Centering data improves the dynamic mode decomposition
• Forecasting of nonlinear dynamics based on symbolic invariance
• Statistical Methods for Minimax Estimation in Linear Models with Unknown Design Over Finite Alphabets
• Estimation of Monge matrices
• Adaptive reduced basis method for the reconstruction of unsteady vortex-dominated flows
• Multidimensional scaling of noisy high dimensional data

This page was built for publication: The Optimal Hard Threshold for Singular Values is <inline-formula> <tex-math notation="TeX">\(4/\sqrt {3}\) </tex-math></inline-formula>

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