Low-rank matrix recovery via regularized nuclear norm minimization

Abstract In this paper, we theoretically investigate the low-rank matrix recovery problem in the context of the unconstrained regularized nuclear norm minimization (RNNM) framework. Our theoretical findings show that, the RNNM method is able to provide a robust recovery of any matrix X (not necessary to be exactly low-rank) from its few noisy measurements b = A ( X ) + n with a bounded constraint ‖ n ‖ 2 ≤ ϵ , provided that the tk-order restricted isometry constant (RIC) of A satisfies a certain constraint related to t > 0 . Specifically, the obtained recovery condition in the case of t > 4 / 3 is found to be same with the sharp condition established previously by Cai and Zhang (2014) to guarantee the exact recovery of any rank-k matrix via the constrained nuclear norm minimization method. More importantly, to the best of our knowledge, we are the first to establish the tk-order RIC based coefficient estimate of the robust null space property in the case of 0 t ≤ 1 .