Correlation matrix nearness and completion under observation uncertainty

This paper introduces the paradigm of optimization under uncertainty for modelling and solving matrix nearness problems. In particular, it considers the concrete problem of recovering correlation matrices from uncertain observations by introducing two different approaches to tackling uncertainty. The first approach invokes the framework of robust optimization to construct low error solutions that are immune to worst-case uncertainty in the input. The second approach takes a less pessimistic view on uncertainty, and considers a situation where instead of the worst one, it suffices to use any matrix in the uncertainty set. We formulate both our approaches as convex (possibly nonsmooth) optimization problems. Thereafter, we show how to exploit problem structure to obtain efficient iterative first-order algorithms. We present several numerical results on both nearness and completion versions of the optimization problem; our results highlight the effectiveness of our proposed algorithmic techniques.