Minimax risk of matrix denoising by singular value thresholding

DOI10.1214/14-AOS1257zbMATH Open1310.62014MaRDI QIDQ482895FDOQ482895

Authors Matan Gavish, David Donoho

Publication date 6 January 2015

Published in The Annals of Statistics (Search for Journal in Brave)

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

zbMATH Keywords

phase transitionnuclear norm minimizationmatrix denoisingmatrix completion from Gaussian measurementsmonotonicity of power functions of multivariate testsoptimal thresholdsingular value thresholdingStein unbiased risk estimate

Mathematics Subject Classification ID

Factor analysis and principal components; correspondence analysis (62H25) Convex programming (90C25) Minimax procedures in statistical decision theory (62C20) Semidefinite programming (90C22)

Abstract: An unknown $m$ by $n$ matrix $X_0$ is to be estimated from noisy measurements $Y=X_0+Z$, where the noise matrix $Z$ has i.i.d. Gaussian entries. A popular matrix denoising scheme solves the nuclear norm penalization problem $operatorname{min}_X|Y-X{|}_F^2/2+lambda|X{|}_{\ast }$, where $|X{|}_{\ast }$ denotes the nuclear norm (sum of singular values). This is the analog, for matrices, of $el{l}_1$ penalization in the vector case. It has been empirically observed that if $X_0$ has low rank, it may be recovered quite accurately from the noisy measurement $Y$. In a proportional growth framework where the rank $r_n$, number of rows $m_n$ and number of columns $n$ all tend to $infty$ proportionally to each other ($r_n/m_{n}ightarrowho$, $$), we evaluate the asymptotic minimax MSE $$. Our formulas involve incomplete moments of the quarter- and semi-circle laws ($$, square case) and the Marv{c}enko-Pastur law ($$, nonsquare case). For finite $m$ and $n$, we show that MSE increases as the nonzero singular values of $X_0$ grow larger. As a result, the finite-$n$ worst-case MSE, a quantity which can be evaluated numerically, is achieved when the signal $X_0$ is "infinitely strong." The nuclear norm penalization problem is solved by applying soft thresholding to the singular values of $Y$. We also derive the minimax threshold, namely the value $lambd{a}^{\ast }(ho)$, which is the optimal place to threshold the singular values. All these results are obtained for general (nonsquare, nonsymmetric) real matrices. Comparable results are obtained for square symmetric nonnegative-definite matrices.

Recommendations

• The phase transition of matrix recovery from Gaussian measurements matches the minimax MSE of matrix denoising
• Nuclear-norm penalization and optimal rates for noisy low-rank matrix completion
• Generalized SURE for optimal shrinkage of singular values in low-rank matrix denoising
• Minimization of the difference of nuclear and Frobenius norms for noisy low rank matrix recovery
• High dimensional deformed rectangular matrices with applications in matrix denoising

Cites work

• scientific article; zbMATH DE number 409717 (Why is no real title available?)
• scientific article; zbMATH DE number 823379 (Why is no real title available?)
• Accurate Prediction of Phase Transitions in Compressed Sensing via a Connection to Minimax Denoising
• DISTRIBUTION OF EIGENVALUES FOR SOME SETS OF RANDOM MATRICES
• Estimation of high-dimensional low-rank matrices
• Estimation of the mean of a multivariate normal distribution
• Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization
• Minimax risk of matrix denoising by singular value thresholding
• Minimax risk over \(l_ p\)-balls for \(l_ q\)-error
• Monotonicity of the Power Functions of Some Tests of the Multivariate Linear Hypothesis
• Nonsmooth analysis of singular values. I: Theory
• Normalized iterative hard thresholding for matrix completion
• Nuclear-norm penalization and optimal rates for noisy low-rank matrix completion
• Null space conditions and thresholds for rank minimization
• Reconstruction of a low-rank matrix in the presence of Gaussian noise
• The Integral of a Symmetric Unimodal Function over a Symmetric Convex Set and Some Probability Inequalities
• The Optimal Hard Threshold for Singular Values is <inline-formula> <tex-math notation="TeX">\(4/\sqrt {3}\) </tex-math></inline-formula>
• The phase transition of matrix recovery from Gaussian measurements matches the minimax MSE of matrix denoising
• Unbiased Risk Estimates for Singular Value Thresholding and Spectral Estimators

Cited in

(41)

• Matrix denoising for weighted loss functions and heterogeneous signals
• Optimal singular value shrinkage for operator norm loss: extending to non-square matrices
• Optimal estimation of Schatten norms of a rectangular matrix
• Monte Carlo Simulation on the Stiefel Manifold via Polar Expansion
• Generalized SURE for optimal shrinkage of singular values in low-rank matrix denoising
• Dynamic mode decomposition with control
• Heteroskedastic PCA: algorithm, optimality, and applications
• Principal component analysis for zero-inflated compositional data
• Bridging convex and nonconvex optimization in robust PCA: noise, outliers and missing data
• The phase transition of matrix recovery from Gaussian measurements matches the minimax MSE of matrix denoising
• Euclidean Representation of Low-Rank Matrices and Its Geometric Properties
• High dimensional deformed rectangular matrices with applications in matrix denoising
• Statistical Inference, Learning and Models in Big Data
• Singular vector and singular subspace distribution for the matrix denoising model
• A Schatten-\(q\) low-rank matrix perturbation analysis via perturbation projection error bound
• Optimal prediction in the linearly transformed spiked model
• A general theory of singular values with applications to signal denoising
• Minimax risk of matrix denoising by singular value thresholding
• CGIHT: conjugate gradient iterative hard thresholding for compressed sensing and matrix completion
• Intelligent Initialization and Adaptive Thresholding for Iterative Matrix Completion: Some Statistical and Algorithmic Theory forAdaptive-Impute
• Edge statistics of large dimensional deformed rectangular matrices
• Rate-optimal perturbation bounds for singular subspaces with applications to high-dimensional statistics
• Entrywise limit theorems for eigenvectors of signal-plus-noise matrix models with weak signals
• scientific article; zbMATH DE number 7370563 (Why is no real title available?)
• On the non-asymptotic concentration of heteroskedastic Wishart-type matrix
• Low permutation-rank matrices: structural properties and noisy completion
• Normal approximation and confidence region of singular subspaces
• A cross-validation framework for signal denoising with applications to trend filtering, dyadic CART and beyond
• Matrix denoising with partial noise statistics: optimal singular value shrinkage of spiked F-matrices
• Low-rank matrix denoising for count data using unbiased Kullback-Leibler risk estimation
• Testing in high-dimensional spiked models
• A Zero-Inflated Logistic Normal Multinomial Model for Extracting Microbial Compositions
• Sharp MSE bounds for proximal denoising
• Conditions for equality in Anderson's theorem
• Research on a risk assessment method considering risk association
• Double bias correction for high-dimensional sparse additive hazards regression with covariate measurement errors
• Adaptive shrinkage of singular values
• A singular value thresholding with diagonal-update algorithm for low-rank matrix completion
• Optimal shrinkage of eigenvalues in the spiked covariance model
• \textit{ScreeNOT}: exact MSE-optimal singular value thresholding in correlated noise
• Multidimensional scaling of noisy high dimensional data

Describes a project that uses

Uses Software

• CVX

This page was built for publication: Minimax risk of matrix denoising by singular value thresholding

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