Gemma De las Cuevas

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.

We introduce a notion of a learning agent whose interaction with the environment is governed by a simulation-based projection, which allows the agent to project itself into future situations before it takes real action. Projective simulation is based on a random walk through a network of clips, which are elementary patches of episodic memory. The network of clips changes dynamically, both due to new perceptual input and due to certain compositional principles of the simulation process. During simulation, the clips are screened for specific features which trigger factual action of the agent. While the scheme works entirely classically, it also provides a natural route for generalization to quantum-mechanical operation.