Properties of dimension witnesses and their semi-definite programming relaxations

In this paper we develop a method for investigating semi-device-independent randomness expansion protocols that was introduced in [Li et al., Phys. Rev. A $\mathbf{87}$, 020302(R) (2013)]. This method allows to lower-bound, with semi-definite programming, the randomness obtained from random number generators based on dimension witnesses. We also investigate the robustness of some randomness expanders using this method. We show the role of an assumption about the trace of the measurement operators and a way to avoid it. The method is also generalized to systems of arbitrary dimension, and for a more general form of dimension witnesses, than it the previous paper. Finally, we introduce a procedure of dimension witness reduction, which can be used to obtain from an existing witness a new one with higher amount of certifiable randomness. The presented methods finds an application for experiments [Ahrens et al., Phys. Rev. Lett. $\mathbf{112}$, 140401 (2014)].