A Counterexample for the Validity of Using Nuclear Norm as a Convex Surrogate of Rank

Hongyang Zhang, Zhouchen Lin, Chao Zhang

Rank minimization has attracted a lot of attention due to its robustness in data recovery. To overcome the computational difficulty, rank is often replaced with nuclear norm. For s…