Uniqueness in Nuclear Norm Minimization: Flatness of the Nuclear Norm Sphere and Simultaneous Polarization.

In this paper, we establish necessary and sufficient conditions for the existence of line segments (or flats) in the sphere of the nuclear norm via the notion of simultaneous polarization and a refined expression for the subdifferential of the nuclear norm. This is then leveraged to provide (point-based) necessary and sufficient conditions for uniqueness of solutions for minimizing the nuclear norm over an affine subspace. We further establish an alternative set of sufficient conditions for uniqueness, based on the interplay of the subdifferential of the nuclear norm and the range of the problem-defining linear operator. Finally, we show how to transfer the uniqueness results for the original problem to a whole class of nuclear norm-regularized minimization problems with a strictly convex fidelity term. [ABSTRACT FROM AUTHOR]