Recursive Smoother Type Variable Splitting Methods for State Estimation

Abstract

Many real-world applications in signal processing, such as target tracking, indoor positioning, and dynamic tomographic reconstruction, can be treated as state estimation problems for recovering the hidden states given a set of incomplete measurements. Mathematically, these problems can be formalized as a class of optimization problems which require minimization of composite functions, for example, the sum of quadratic functions and extra regularizers. A well-established way to solve the resulting problem is to decompose the composite function into separate sub-functions. Variable splitting methods such as the alternating direction method of multipliers are powerful batch optimization methods with such decomposition properties. However, the methods do not take the inherently temporal nature of the problems into account, which leads to bad computational and memory scaling when the number of time steps (e.g., millions) is in extreme scale. This thesis is concerned with studying recursive smoother-based variable splitting methods for solving regularized or constrained state-estimation problems. This thesis first establishes the equivalences between recursive smoothers and batch Bayesian maximum a posteriori estimates, which then enables the use of recursive smoothers to solve the subproblems arising in variable splitting iterations. Since recursive smoothing methods are suitable for problems exhibiting an inherent temporal structure and batch variable splitting methods have the decomposition property, the proposed methods gain the benefits of both. In the main part of the thesis, using synthesis and analysis sparsity, an L1-regularized state estimation problem is solved. Based on variable splitting, the general algorithmic framework is proposed. Instead of using direct batch methods, the iterative steps involving minimization of linear or nonlinear quadratic terms are computed efficiently by recursive smoothing methods. The proposed methods have low per-iteration time complexity, which makes them suitable for solving large-scale state estimation problems. The convergence of these methods is established. Additionally, introducing structured sparsity, a generalized L2-regularized state estimation problem is addressed. Motivated by the equivalences mentioned above, three new methods based on multi-block alternating direction method of multipliers are proposed which use recursive smoothers on augmented state-space models to compute the primal variable. The performance of the approach is illustrated in simulated data as well as in many real-world applications, such as tomographic reconstruction, audio restoration, marine vessel tracking, and urban car tracking. Furthermore, a class of efficient, accurate, and general methods is proposed to solve state-estimation problems with equality and inequality constraints. The advantage of our methods is highlighted by the fact that they can efficiently solve constrained state-estimation problems with extremely large numbers of time steps.