Recursive Smoother Type Variable Splitting Methods for State Estimation

Thumbnail Image
Journal Title
Journal ISSN
Volume Title
School of Electrical Engineering | Doctoral thesis (article-based) | Defence date: 2020-12-04
Degree programme
91 + app. 64
Aalto University publication series DOCTORAL DISSERTATIONS, 190/2020
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.
The public defense will be organized via remote technology. Follow defence on 4.12.2020 12:00 – 15:00:
Supervising professor
Särkkä, Simo, Prof., Aalto University, Department of Electrical Engineering and Automation, Finland
Thesis advisor
Särkkä, Simo, Prof., Aalto University, Department of Electrical Engineering and Automation, Finland
state estimation, sparsity, variable splitting, Bayesian filtering and smoothing, inequality constraint
Other note
  • [Publication 1]: Rui Gao, Filip Tronarp, Simo Särkkä. Iterated Extended Kalman Smoother-Based Variable Splitting for L1-Regularized State Estimation. IEEE Transactions on Signal Processing, Volume 67, Issue 19, pages 5078–5092, October 2019.
    DOI: 10.1109/TSP.2019.2935868 View at publisher
  • [Publication 2]: Rui Gao, Filip Tronarp, Simo Särkkä. Variable Splitting Methods for Constrained State Estimation in Partially Observed Markov Processes. IEEE Signal Processing Letters, Volume 27, pages 1305–1309, July 2020.
    DOI: 10.1109/LSP.2020.3010159 View at publisher
  • [Publication 3]: Rui Gao, Filip Tronarp, Zheng Zhao, Simo Särkkä. Regularized State Estimation And Parameter Learning Via Augmented Lagrangian Kalman Smoother Method. In IEEE 29th International Workshop on Machine Learning for Signal Processing (MLSP), Pittsburgh, PA, 6 pages, October 2019.
    DOI: 10.1109/MLSP.2019.8918821 View at publisher
  • DOI: 10.23919/Eusipco47968.2020.9287731 View at publisher
  • [Publication 5]: Rui Gao, Filip Tronarp, Simo Särkkä. Combined Analysis-L1 and Total Variation ADMM with Applications to MEG Brain Imaging and Signal Reconstruction. In 26th European Signal Processing Conference (EUSIPCO), Rome, Italy, pages 1930–1934, September 2018.
    DOI: 10.23919/EUSIPCO.2018.8553122 View at publisher
  • [Publication 6]: Rui Gao, Simo Särkkä, Rubén Claveria-Vega, Simon Godsill. Autonomous Tracking and State Estimation with Generalized Group Lasso. Submitted to IEEE Transactions on Cybernetics, 11 pages, July 2020.