On the minimal number of measurements in low-rank matrix recovery

In this paper we present a new way to obtain a bound on the number of measurements sampled from certain distributions that guarantee uniform stable and robust recovery of low-rank matrices. The recovery guarantees are characterized by a stable and robust version of the null space property and verifying this condition can be reduced to the problem of obtaining a lower bound for a quantity of the form inf_xϵT||Ax||2. Gordon´s escape through a mesh theorem provides such a bound with explicit constants for Gaussian measurements. Mendelson´s small ball method allows to cover the significantly more general case of measurements generated by independent identically distributed random variables with finite fourth moment.