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

DOI10.1109/TIT.2014.2323359MaRDI QIDQ2986241zbMATH OpenOpenAlexFDO

Authors Matan Gavish, David Donoho

Publication date 16 May 2017

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

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

Mathematics Subject Classification ID

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

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.

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

Cited in

(64)

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

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)