In matrix denoising, we estimate an unknown real m-by-n matrix X from a single noisy measurement Y=X+Z, where Z is assumed to have i.i.d normal entries. A popular matrix denoising scheme is Singular Value Thresholding (SVT), which applies soft thresholding (with a common threshold) to each of the singular values of the data matrix Y. I'll show an explicit formula for the minimax MSE of SVT over matrices of rank <= r, and the corresponding optimal location for the threshold of SVT. I will also compare the minimax MSE of SVT to the minimax MSE over all possible matrix denoisers. For example, for n=m, we will see that SVT is no more than a factor of 3 suboptimal. Matrix denoising is connected to compressed sensing of matrices: there is empirical evidence that the minimax formula I'll present accurately predicts the phase transition of matrix recovery from Gaussian measurements. Joint work with David Donoho.
Minimax Risk of Matrix Denoising by Singular Value Thresholding
Matan Gavish, Stanford University
Apr 10 2013 - 3:45pm
102A McDonnell Hall