Necessary and Sufficient Null Space Condition for Nuclear Norm
  Minimization in Low-Rank Matrix Recovery
  Low-rank matrix recovery has found many applications in science and
engineering such as machine learning, signal processing, collaborative
filtering, system identification, and Euclidean embedding. But the low-rank
matrix recovery problem is an NP hard problem and thus challenging. A commonly
used heuristic approach is the nuclear norm minimization. In [12,14,15], the
authors established the necessary and sufficient null space conditions for
nuclear norm minimization to recover every possible low-rank matrix with rank
at most r (the strong null space condition). In addition, in [12], Oymak et al.
established a null space condition for successful recovery of a given low-rank
matrix (the weak null space condition) using nuclear norm minimization, and
derived the phase transition for the nuclear norm minimization. In this paper,
we show that the weak null space condition in [12] is only a sufficient
condition for successful matrix recovery using nuclear norm minimization, and
is not a necessary condition as claimed in [12]. In this paper, we further give
a weak null space condition for low-rank matrix recovery, which is both
necessary and sufficient for the success of nuclear norm minimization. At the
core of our derivation are an inequality for characterizing the nuclear norms
of block matrices, and the conditions for equality to hold in that inequality.
