Tight Recovery Thresholds and Robustness Analysis for Nuclear Norm Minimization

Nuclear norm minimization (NNM) has recently gained significant attention for its use in rank minimization problems. Using null space characterizations, recovery thresholds for NNM have been previously studied for the case of Gaussian measurements as matrix dimensions tend to infinity. However simulations show that the thresholds are far from optimal, especially in the low rank region. In this paper we apply the recent analysis of Stojnic for ℓ_1-minimization to the null space conditions of NNM. The results are significantly better and in particular our weak threshold appears to match with simulation results. Further, our closed form bounds suggest for any rank growing linearly with matrix size n one needs only three times of oversampling (the model complexity) for weak recovery and eight times for strong recovery. Additionally, the results for robustness analysis are given which indicate with slightly more measurements recovery guarantees for approximately low rank matrices can be given