Minimax Risk of Matrix Denoising by Singular Value Thresholding

Matan Gavish, Stanford University
Apr 10 2013 - 3:45pm
Event type: 
102A McDonnell Hall

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.