Matan Gavish

Personnal website:
Other affiliations:

Matan Gavish created these companion sites

The Optimal Hard Threshold for Singular Values is 4/sqrt(3)
Abstract
We consider recovery of low-rank matrices from noisy data by hard thresholding of singular values, where singular values below a prescribed threshold \lambda are set to 0. We study the asymptotic MSE in a framework where the matrix size is large compared to the rank of the matrix to be recovered, and the signal-to-noise ratio of the low-rank piece stays constant. The AMSE-optimal choice of hard threshold, in the case of n-by-n matrix in noise level \sigma, is simply (4/\sqrt{3}) \sqrt{n}\sigma \approx 2.309 \sqrt{n}\sigma when \sigma is known, or simply 2.858\cdot y_{med} when \sigma is unknown, where y_{med} is the median empirical singular value. For nonsquare m by n matrices with m \neq n, these thresholding coefficients are replaced with different provided constants. In our asymptotic framework, this thresholding rule adapts to unknown rank and to unknown noise level in an optimal manner: it is always better than hard thresholding at any other value, no matter what the matrix is that we are trying to recover, and is always better than ideal Truncated SVD (TSVD), which truncates at the true rank of the low-rank matrix we are trying to recover. Hard thresholding at the recommended value to recover an n-by-n matrix of rank r guarantees an AMSE at most 3nr\sigma^2. In comparison, the guarantee provided by TSVD is 5nr\sigma^2, the guarantee provided by optimally tuned singular value soft thresholding is 6nr\sigma^2, and the best guarantee achievable by any shrinkage of the data singular values is 2nr\sigma^2. Empirical evidence shows that these AMSE properties of the 4/\sqrt{3} thresholding rule remain valid even for relatively small n, and that performance improvement over TSVD and other shrinkage rules is substantial, turning it into the practical hard threshold of choice.
Gavish, M., and D. Donoho, "The Optimal Hard Threshold for Singular Values is 4/sqrt(3)", Stanford University.
Authors: Donoho
Gavish
Coders: Gavish
Donoho
Last update
Thu May 30 02:46:00 CEST 2013
Ranking
9999
Runs
17
Visits
N.A.
The Phase Transition of Matrix Recovery from Gaussian Measurements Matches the Minimax MSE of Matrix Denoising
Abstract
Let X_0 be an unknown M by N matrix. In matrix recovery, one takes n < MN linear measurements y_1, ... , y_n of X_0, where y_i = Trace(a_i' X_0) and each a_i is a M by N matrix. For measurement matrices with Gaussian i.i.d entries, it known that if X_0 is of low rank, it is recoverable from just a few measurements. A popular approach for matrix recovery is Nuclear Norm Minimization (NNM): solving the convex optimization problem min ||X||_* subject to y_i=Trace(a_i' X) for all 1<= i<= n, where || . ||_* denotes the nuclear norm, namely, the sum of singular values. Empirical work reveals a phase transition curve, stated in terms of the undersampling fraction \delta(n,M,N) = n/(MN), rank fraction \rho=r/N and aspect ratio \beta=M/N. Specifically, a curve \delta^* = \delta^*(\rho;\beta) exists such that, if \delta > \delta^*(\rho;\beta), NNM typically succeeds, while if \delta < \delta^*(\rho;\beta), it typically fails. An apparently quite different problem is matrix denoising in Gaussian noise, where an unknown M by N matrix X_0 is to be estimated based on direct noisy measurements Y = X_0 + Z, where the matrix Z has iid Gaussian entries. It has been empirically observed that, if X_0 has low rank, it may be recovered quite accurately from the noisy measurement Y. A popular matrix denoising scheme solves the unconstrained optimization problem min || Y - X ||_F^2/2 + \lambda ||X||_*. When optimally tuned, this scheme achieves the asymptotic minimax MSE, M( \rho ) = \lim_{N-> \infty} \inf_\lambda \sup_{\rank(X) <= \rho * N} MSE(X,\hat{X}_\lambda). We report extensive experiments showing that the phase transition \delta^*(\rho) in the first problem (Matrix Recovery from Gaussian Measurements) coincides with the minimax risk curve M(\rho) in the second problem (Matrix Denoising in Gaussian Noise): \delta^*(\rho) = M(\rho), for any rank fraction 0 < \rho < 1. Our experiments considered matrices belonging to two constraint classes: real M by N matrices, of various ranks and aspect ratios, and real symmetric positive semidefinite N by N matrices, of various ranks. Different predictions M(\rho) of the phase transition location were used in the two different cases, and were validated by the experimental data.
Gavish, M., "The Phase Transition of Matrix Recovery from Gaussian Measurements Matches the Minimax MSE of Matrix Denoising", Stanford University.
Authors: Donoho
Gavish
Montanari
Coders: Gavish
Last update
Fri Feb 15 05:02:00 CET 2013
Ranking
9999
Runs
8
Visits
N.A.