Experimental study of Pac-Man conditions for learn-ability of discrete linear dynamical systems

Abstract

In this work, we are going to reconstruct parameters of a discrete dynamical system with a hidden layer, given by a quadruple of matrices (𝐴,𝐵,𝐶,𝐷), from system’s past behaviour. First, we reproduced experimentally the well-known result of Hardt et al. that the reconstruction can be made under some conditions, called Pac-Man conditions. Then we demonstrated experimentally that the system approaches the global minimum even if an input 𝑥 is a sequence of i.i.d. random variables with a nongaussian distribution. We also formulated hypotheses beyond Pac-Man conditions that Gradient Descent solves the problem if the operator norm (or alternatively, the spectral radius) of transition matrix 𝐴 is bounded by 1 and obtained the negative result, i.e. a counterexample to those conjectures.