Well-posedness and Stability of Nuclear Norm Minimization Problems

Nghia T. A. Tran
Oakland University

A nuclear norm minimization (NNM) problem minimizing a nuclear norm over an affine constraint has many applications in recommendation systems, computer vision, and multivariate linear regression. It is especially efficient in recovering a low-rank matrix with known linear sampling measurements. The theory of such recovery usually requires well-posedness and robustness on the corresponding NNM problem, which are very likely when the number of sampling measurements is big enough. In this talk, I will provide new results in this direction. Particularly, geometric characterizations of well-posedness are obtained via the radial/tangent cones and numerically verified. This allows us to derive the smallest bound for the number of sampling measurements in exact recovery. Unique solutions of NNM problems are categorized into two groups: sharp minimizers and strong minimizers. When the number of measurements is not big enough, unique solutions of NNM problems happen to be strong minimizers. Robust recovery and Lipschitz stability of NNM problems are also studied when the sampling measurements are disrupted by small noises.