Minimax risk of matrix denoising by singular value thresholding

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

Authors: Matan Gavish, David Donoho 

Publication date: 6 January 2015

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

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{|}_{*}$, where $|X{|}_{*}$ 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}^{*}(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.

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

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

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)

Cites Work

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

Cited In (37)

• Dynamic mode decomposition with control
• A Schatten-\(q\) low-rank matrix perturbation analysis via perturbation projection error bound
• Matrix denoising with partial noise statistics: optimal singular value shrinkage of spiked F-matrices
• Conditions for equality in Anderson's theorem
• A singular value thresholding with diagonal-update algorithm for low-rank matrix completion
• Title not available (Why is that?)
• Rate-optimal perturbation bounds for singular subspaces with applications to high-dimensional statistics
• Monte Carlo Simulation on the Stiefel Manifold via Polar Expansion
• Testing in high-dimensional spiked models
• Statistical Inference, Learning and Models in Big Data
• On the non-asymptotic concentration of heteroskedastic Wishart-type matrix
• Normal approximation and confidence region of singular subspaces
• Adaptive shrinkage of singular values
• Minimax risk of matrix denoising by singular value thresholding
• Entrywise limit theorems for eigenvectors of signal-plus-noise matrix models with weak signals
• Optimal estimation of Schatten norms of a rectangular matrix
• Principal component analysis for zero-inflated compositional data
• Sharp MSE bounds for proximal denoising
• Research on a risk assessment method considering risk association
• 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
• Bridging convex and nonconvex optimization in robust PCA: noise, outliers and missing data
• A Zero-Inflated Logistic Normal Multinomial Model for Extracting Microbial Compositions
• Matrix Denoising for Weighted Loss Functions and Heterogeneous Signals
• Optimal prediction in the linearly transformed spiked model
• Double bias correction for high-dimensional sparse additive hazards regression with covariate measurement errors
• Euclidean Representation of Low-Rank Matrices and Its Geometric Properties
• Intelligent Initialization and Adaptive Thresholding for Iterative Matrix Completion: Some Statistical and Algorithmic Theory forAdaptive-Impute
• Low Permutation-rank Matrices: Structural Properties and Noisy Completion
• Low-rank matrix denoising for count data using unbiased Kullback-Leibler risk estimation
• Optimal shrinkage of eigenvalues in the spiked covariance model
• Heteroskedastic PCA: algorithm, optimality, and applications
• CGIHT: conjugate gradient iterative hard thresholding for compressed sensing and matrix completion
• Edge statistics of large dimensional deformed rectangular matrices
• Singular vector and singular subspace distribution for the matrix denoising model
• A cross-validation framework for signal denoising with applications to trend filtering, dyadic CART and beyond
• Multidimensional scaling of noisy high dimensional data

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)