Tim Netzer

We study different decompositions of positive semidefinite matrices and nonnegative tensors and examine their approximate ranks. For any rank and norm, we define an epsilon rank as the minimum rank of an element which is epsilon close to the original element with respect to the given norm. We prove that the separations between these ranks disappear for a large class of Schatten p-norms and all entrywise p-norms with p > 1. For the trace norm (i.e. p = 1), we obtain a dependence on the ambient dimension. Our main tool is an approximate version of Caratheodory’s Theorem. We also present a deterministic algorithm to find an approximate decomposition. This work implies that it must be possible to purify states approximately at a fixed cost, which shows that the positivity problem disappears in this case.