The bounds of restricted isometry constants for low rank matrices recovery

This paper discusses conditions under which the solution of linear system with minimal Schatten-p norm, 0 〈 p ≤ 1, is also the lowest-rank solution of this linear system. To study this problem, an important tool is the restricted isometry constant （RIC）. Some papers provided the upper bounds of RIC to guarantee that the nuclear-norm minimization stably recovers a low-rank matrix. For example, Fazel improved the upper bounds to δ4Ar 〈 0.558 and δ3rA 〈 0.4721, respectively. Recently, the upper bounds of RIC can be improved to δ2rA 〈 0.307. In fact, by using some methods, the upper bounds of RIC can be improved to δ2tA 〈 0.4931 and δrA 〈 0.309. In this paper, we focus on the lower bounds of RIC, we show that there exists linear maps A with δ2rA 〉1√2 or δrA 〉 1/3 for which nuclear norm recovery fail on some matrix with rank at most r. These results indicate that there is only a little limited room for improving the upper bounds for δ2rA and δrA.Furthermore, we also discuss the upper bound of restricted isometry constant associated with linear maps A for Schatten p （0 〈 p 〈 1） quasi norm minimization problem.

This paper discusses conditions under which the solution of linear system with minimal Schatten-p norm, 0 < p 1, is also the lowest-rank solution of this linear system. To study this problem, an important tool is the restricted isometry constant (RIC). Some papers provided the upper bounds of RIC to guarantee that the nuclear-norm minimization stably recovers a low-rank matrix. For example, Fazel improved the upper bounds to δA4r < 0.558 and δA3r < 0.4721, respectively. Recently, the upper bounds of RIC can be improved to δA2r < 0.307. In fact, by using some methods, the upper bounds of RIC can be improved to δA2r < 0.4931 and δ A r < 0.309. In this paper, we focus on the lower bounds of RIC, we show that there exists linear maps A with δA2r > 1/ 2^(1/2) or δAr > 1/3 for which nuclear norm recovery fail on some matrix with rank at most r. These results indicate that there is only a little limited room for improving the upper bounds for δA2r and δAr . Furthermore, we also discuss the upper bound of restricted isometry constant associated with linear maps A for Schatten p (0 < p < 1) quasi norm minimization problem.