  State-space models are used in a wide range of time series analysis
formulations. Kalman filtering and smoothing are work-horse algorithms in these
settings. While classic algorithms assume Gaussian errors to simplify
estimation, recent advances use a broader range of optimization formulations to
allow outlier-robust estimation, as well as constraints to capture prior
information.
  Here we develop methods on state-space models where either innovations or
error covariances may be singular. These models frequently arise in navigation
(e.g. for `colored noise' models or deterministic integrals) and are ubiquitous
in auto-correlated time series models such as ARMA. We reformulate all
state-space models (singular as well as nonsinguar) as constrained convex
optimization problems, and develop an efficient algorithm for this
reformulation. The convergence rate is {\it locally linear}, with constants
that do not depend on the conditioning of the problem.
  Numerical comparisons show that the new approach outperforms competing
approaches for {\it nonsingular} models, including state of the art interior
point (IP) methods. IP methods converge at superlinear rates; we expect them to
dominate. However, the steep rate of the proposed approach (independent of
problem conditioning) combined with cheap iterations wins against IP in a
run-time comparison. We therefore suggest that the proposed approach be the
{\it default choice} for estimating state space models outside of the Gaussian
context, regardless of whether the error covariances are singular or not.
