Subspace identification for predictive state representation by nuclear norm minimization

Predictive State Representations (PSRs) are dynamical systems models that keep track of the system´s state using predictions of future observations. In contrast to other models of dynamical systems, such as partially observable Markov decision processes, PSRs produces more compact models and can be consistently learned using statistics of the execution trace and spectral decomposition. In this paper we make a connection between rank minimization problems and learning PSRs. This allows us to derive a new algorithm based on nuclear norm minimization. In addition to estimate automatically the dimension of the system, our algorithm compares favorably with the state of art on randomly generated realistic problems of different sizes.