Learning a stable Linear Dynamical System (LDS) from data involves creating\nmodels that both minimize reconstruction error and enforce stability of the\nlearned representation. We propose a novel algorithm for learning stable LDSs.\nUsing a recent characterization of stable matrices, we present an optimization\nmethod that ensures stability at every step and iteratively improves the\nreconstruction error using gradient directions derived in this paper. When\napplied to LDSs with inputs, our approach---in contrast to current methods for\nlearning stable LDSs---updates both the state and control matrices, expanding\nthe solution space and allowing for models with lower reconstruction error. We\napply our algorithm in simulations and experiments to a variety of problems,\nincluding learning dynamic textures from image sequences and controlling a\nrobotic manipulator. Compared to existing approaches, our proposed method\nachieves an orders-of-magnitude improvement in reconstruction error and\nsuperior results in terms of control performance. In addition, it is provably\nmore memory-efficient, with an O(n^2) space complexity compared to O(n^4) of\ncompeting alternatives, thus scaling to higher-dimensional systems when the\nother methods fail.\n