Identifying parsimonious models is generically a "hard" nonconvex problem. Available approaches typically rely on relaxations such as Group Lasso or nuclear norm minimization. Moreover, incorporating stability and model order constraints into the formalism in such methods entails a substantial increase in computational complexity. Motivated by these challenges, in this paper we present algorithms for parsimonious linear time invariant system identification aimed at identifying low-complexity models which i) incorporate a priori knowledge on the system (e.g., stability), ii) allow for data with missing/nonuniform measurements, and iii) are able to use data obtained from several runs of the system with different unknown initial conditions. The randomized algorithms proposed are based on the concept of atomic norm and provide a numerically efficient way to identify sparse models from large amounts of noisy data.