Rank minimization or nuclear-norm minimization: Are we solving the right problem?

Low rank method or rank-minimization has received considerable attention from recent computer vision community. Due to the inherent computational complexity of rank problems, the non-convex rank function is often relaxed to its convex relaxation, ie the nuclear norm. Thanks to recent progress made in the filed of compressive sensing (CS), vision researchers who are practicing CS are fully aware, and conscious, of the convex relaxation gap, as well as under which condition (eg Restricted Isometry Property) the relaxation is tight (ie with nil gap). In this paper, we however wish to alert the potential users of the low-rank method that: focusing too much on the issue of relaxation gap and optimization may possibly adversely obscure the "big picture" of the original vision problem. In particular, this paper shows that for many commonly cited low-rank problems, nuclear norm minimization formulation of the original rank-minimization problem do not necessarily lead to the desired solution. Degenerate solutions and multiplicity seem often or always exist. Even if a certain nuclear-norm minimization solution is a provably tight relaxation, this solution can possibly be meaningless in its particular context. We therefore advocate that, in solving vision problems via nuclear norm minimization, special care must be given, and domain-dependent prior knowledge must be taken into account. This paper summarizes recent relevant theoretical results, provides original analysis, uses real examples to demonstrate the practical implications.