Fast Robust Methods for Singular State-Space Models
This work provides a robust and efficient solution for time series analysis in fields like navigation and ARMA modeling, though it is incremental as it builds on existing optimization formulations for outlier-robust estimation.
The paper tackled the problem of estimating state-space models with singular innovations or error covariances, which arise in navigation and time series analysis, by reformulating them as constrained convex optimization problems and developing an efficient algorithm; the result is a method that outperforms state-of-the-art interior point approaches in run-time comparisons, with a locally linear convergence rate independent of problem conditioning.
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.