Matrix estimation by Universal Singular Value Thresholding

By Sourav Chatterjee. 2012

572 citations recorded by the source corpus.

Consider the problem of estimating the entries of a large matrix, when the observed entries are noisy versions of a small random fraction of the original entries. This problem has received widespread attention in recent times, especially after the pioneering works of Emmanuel Cand\`{e}s and collaborators. This paper introduces a simple estimation procedure, called Universal Singular Value Thresholding (USVT), that works for any matrix that has "a little bit of structure." Surprisingly, this simple estimator achieves the minimax error rate up to a constant factor. The method is applied to solve problems related to low rank matrix estimation, blockmodels, distance matrix completion, latent space models, positive definite matrix completion, graphon estimation and generalized Bradley--Terry models for pairwise comparison.

Subfields: Computational Mechanics, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/e655546e7133b5c97647da066a90b112fe3c9aeb

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Statistics and Probability

Citations in the corpus

The Optimal Hard Threshold for Singular Values is $4/\sqrt {3}$ (2014, background): ““ Keeping in mind that the scope of [17] is much broader than the one considered here, we would like to evaluate this proposal, in the setting of low rank matrix in white noise, and specifically in our asymptotic framework.”
Using Synthetic Controls: Feasibility, Data Requirements, and Methodological Aspects (2021, methodology): “, wJ+1 using pre-intervention data only, in the inferential procedure of Chernozhukov et al. (2019a) the synthetic control weights are estimated under the null hypothesis, τT0+1 = aT0+1, . . . , τT = aT , using data on Y N it = Yit− at for all periods, including the periods after the intervention. F”
Data-Enabled Predictive Control: In the Shallows of the DeePC (2018, background): “eful that it can also be applied beyond deterministic LTI systems. To apply the algorithm to such systems, we propose some preliminary though insightful regularizations (e.g., low-rank approximations [39], and introduction of auxiliary slack variables [40]), and reason as to why these regularization”
Estimation from Pairwise Comparisons: Sharp Minimax Bounds with Topology Dependence (2015, methodology): “In future work we would like to investigate more ﬂexible semi-parametric and non-parametric pairwise comparison models (see, for instance, Chatterjee (2014); Braverman and Mossel (2008)).”
On matrix estimation under monotonicity constraints (2015, background): “Two such examples are: (1) the estimation of graphons under monotonicity constraints (see Chatterjee and Mukherjee [10]), and (2) the nonparametric Bradley–Terry model (see Chatterjee [7], Shah et al. [20]).”
On Adaptive Attacks to Adversarial Example Defenses (2020, methodology): “We thus tried to apply BPDA only to the USVT procedure, and backpropagate through the random mask.”
Rate-Optimal Perturbation Bounds for Singular Subspaces with Applications to High-Dimensional Statistics (2016, methodology): “…Yang et al., 2014; Donoho and Gavish, 2014), matrix completion (Candès and Recht, 2009; Candès and Tao, 2010; Keshavan et al., 2010; Gross, 2011; Chatterjee, 2014), principle component analysis (Anderson, 2003; Johnstone and Lu, 2009; Cai et al., 2013, 2015b), canonical correlation analysis…”
Weighted low rank approximations with provable guarantees (2016, background): “This is given in the full version of the paper.”
Rejoinder on: Minimal penalties and the slope heuristics: a survey. (2019, unknown): “Universal singular value thresholding (USVT; Chatterjee, 2015) is another procedure related to minimal-penalty algorithms, not mentioned in the survey.”
Optimal rates of statistical seriation (2016, background): “In his celebrated paper on matrix estimation [23], Sourav Chatterjee describes several noisy matrix models involving unknown latent permutations.”
Statistical Inference on Random Dot Product Graphs: a Survey (2017, methodology): “With FlashGraph, we adjacency spectral embed the Friendster adjacency matrix into R(14)—where D̂ = 14 is chosen using universal singular value thresholding on the partial SCREE plot [18].”
Asymptotically perfect seeded graph matching without edge correlation (and applications to inference) (2025, unknown): “In practice, we select d using an automatic dimensionality selection method (locating an appropriate elbow of the SCREE plot) based on [63], [64].”