Optimal Singular Value Thresholding in Correlated Noise

Overview

Abstract

We consider the problem of recovering a low-rank signal matrix in the presence of a general, unknown additive noise; more specifically, noise where the eigenvalues of the sample covariance matrix have a general bulk distribution. We assume given an upper bound for the rank of the assumed orthogonally invariant signal, and develop a selector for hard thresholding of singular values, which adapts to the unknown correlation structure of the noise. Our selector asymptotically achieves the lowest squared error loss achievable by any hard threshold selector on the data at hand, namely the square error achievable by an oracle with access to the (in principle unknowable) low-rank signal matrix. This selector generalizes to the correlated noise case the 4/sqrt{3} threshold rule previously published for the case of white noise. Our approach develops stable and asymptotically unbiased empirical estimates of the noise bulk from signal+noise and shows that these estimates can be used inside formulas deriving from work by Benaych-Georges and Rao-Nadakuditi. This is assumed to be a mathematically sophisticated audience, so we'll spend more time on the arguments underlying the proofs than we would if we were discussing such things to end-users. This is joint work with Matan Gavish and Elad Romanov.

Brief Biography

David Donoho is Anne T. and Robert M. Bass Professor of Humanities and Sciences and Professor of Statistics at Stanford University. He previously was a Professor at UC Berkeley and held visiting positions at Universite de Paris (VII and XI), the University of Leiden, and the National University of Singapore.

He has also worked in the industry, in oil exploration (Western Geophysical), information technology (co-founding BigFix, Inc., which was acquired by IBM), and quantitative finance (Renaissance Technologies).

He received the AB in Statistics from Princeton summa cum laude, where his undergraduate thesis advisor was John Tukey. He earned a Ph.D. in Statistics from Harvard University, where his thesis advisor was Peter Huber. Donoho was awarded honorary degrees from the University of Chicago, Ecole Fédérale Polytechnique de Lausanne, University of Waterloo, and the Technion.

Donoho is a member of the American Academy of Arts and Sciences, the US National Academy of Sciences, and a Foreign Associate of the French Académie des Sciences. He has received a MacArthur Fellowship and the Committee of Presidents of Statistical Societies Presidents’ award. He was awarded the Norbert Wiener Prize of the American Mathematical Society and Society of Industrial and Applied Mathematics and the Gauss Prize of the International Mathematical Congress and German Mathematical Society. He received the 2013 Shaw Prize in Mathematical Sciences.