Special Seminar in Computing and Mathematical Sciences

In the common approach to low-rank matrix recovery, one uses the nuclear norm as a convex surrogate for rank. Geometric proof techniques like Tropp's Bowling scheme or Mendelson's small ball method bound the reconstruction error in terms of the descent cone of the norm at the matrix that is to be recovered. Moreover, these arguments suggest that the error would decrease if another convex function be used, which has a smaller descent cone at the set of matrices of interest. We construct such an improved convex function based on the diamond norm, a concept well-known in quantum information theory and operator theory. We demonstrate numerically that the diamond norm indeed outperforms the nuclear norm in a number of applications. The diamond norm is defined for matrices that can be interpreted as order-4 tensors and it turns out that the above condition depends crucially on that tensorial structure. In this sense, this work touches on an aspect of the notoriously difficult tensor completion problem.

This is joint work with Martin Kliesch (FU Berlin), Jens Eisert (FU Berlin) and David Gross (University of Cologne).