Semi definite programming approach for robust tracking

S. Shtern, A. Ben-Tal

Research output: Contribution to journalArticleScientificpeer-review

Abstract

Tracking problems are prevalent in the present day GPS and video systems. The problem of target tracking is a specific case of dynamic linear system estimation with additive noise. The most widely used filter for these systems is the Kalman filter (KF). The optimality of the KF and similar Bayesian filters is guaranteed under particular probabilistic assumptions. However, in practice, and specifically in applications such as tracking, these probabilistic assumptions are not realistic; indeed, the system noise is typically bounded and in fact might be adversarial. For such cases, robust estimation approaches, such as H∞ filtering and set-value estimation, were introduced with the aim of providing filters with guaranteed worst case performance. In this paper we present an innovative approximated set-value estimator (SVE) which is obtained through a semi-definite programming problem. We demonstrate that our problem is practically tractable even for long time horizons. The framework is extended to include the case of partially statistical noise, thus combining the KF and SVE frameworks. A variation of this filter which applies a rolling window approach is developed, achieving fixed computational cost per-iteration and coinciding with the classical SVE when window size is one. Finally, we present numerical results that show the advantages of this filter when dealing with adversarial noise and compare the performance of the various robust filters with the KF.
Original languageEnglish
Pages (from-to)615-656
JournalMathematical Programming
Volume156
Issue number1
DOIs
Publication statusPublished - Mar 2016
Externally publishedYes

Fingerprint

Semidefinite Programming
Kalman filters
Filter
Kalman Filter
Estimator
Additive noise
Target tracking
Linear systems
Global positioning system
Worst-case Performance
Robust Estimation
Target Tracking
Additive Noise
Dynamic Systems
Computational Cost
Horizon
Optimality
Filtering
Linear Systems
Iteration

Keywords

  • robust optimization
  • semidefinite programming
  • estimation of linear systems

Cite this

Shtern, S. ; Ben-Tal, A. / Semi definite programming approach for robust tracking. In: Mathematical Programming. 2016 ; Vol. 156, No. 1. pp. 615-656.
@article{c61652b6e8924d1f9863b9413806db53,
title = "Semi definite programming approach for robust tracking",
abstract = "Tracking problems are prevalent in the present day GPS and video systems. The problem of target tracking is a specific case of dynamic linear system estimation with additive noise. The most widely used filter for these systems is the Kalman filter (KF). The optimality of the KF and similar Bayesian filters is guaranteed under particular probabilistic assumptions. However, in practice, and specifically in applications such as tracking, these probabilistic assumptions are not realistic; indeed, the system noise is typically bounded and in fact might be adversarial. For such cases, robust estimation approaches, such as H∞ filtering and set-value estimation, were introduced with the aim of providing filters with guaranteed worst case performance. In this paper we present an innovative approximated set-value estimator (SVE) which is obtained through a semi-definite programming problem. We demonstrate that our problem is practically tractable even for long time horizons. The framework is extended to include the case of partially statistical noise, thus combining the KF and SVE frameworks. A variation of this filter which applies a rolling window approach is developed, achieving fixed computational cost per-iteration and coinciding with the classical SVE when window size is one. Finally, we present numerical results that show the advantages of this filter when dealing with adversarial noise and compare the performance of the various robust filters with the KF.",
keywords = "robust optimization, semidefinite programming, estimation of linear systems",
author = "S. Shtern and A. Ben-Tal",
year = "2016",
month = "3",
doi = "10.1007/s10107-015-0910-5",
language = "English",
volume = "156",
pages = "615--656",
journal = "Mathematical Programming",
issn = "0025-5610",
publisher = "Springer",
number = "1",

}

Semi definite programming approach for robust tracking. / Shtern, S.; Ben-Tal, A.

In: Mathematical Programming, Vol. 156, No. 1, 03.2016, p. 615-656.

Research output: Contribution to journalArticleScientificpeer-review

TY - JOUR

T1 - Semi definite programming approach for robust tracking

AU - Shtern, S.

AU - Ben-Tal, A.

PY - 2016/3

Y1 - 2016/3

N2 - Tracking problems are prevalent in the present day GPS and video systems. The problem of target tracking is a specific case of dynamic linear system estimation with additive noise. The most widely used filter for these systems is the Kalman filter (KF). The optimality of the KF and similar Bayesian filters is guaranteed under particular probabilistic assumptions. However, in practice, and specifically in applications such as tracking, these probabilistic assumptions are not realistic; indeed, the system noise is typically bounded and in fact might be adversarial. For such cases, robust estimation approaches, such as H∞ filtering and set-value estimation, were introduced with the aim of providing filters with guaranteed worst case performance. In this paper we present an innovative approximated set-value estimator (SVE) which is obtained through a semi-definite programming problem. We demonstrate that our problem is practically tractable even for long time horizons. The framework is extended to include the case of partially statistical noise, thus combining the KF and SVE frameworks. A variation of this filter which applies a rolling window approach is developed, achieving fixed computational cost per-iteration and coinciding with the classical SVE when window size is one. Finally, we present numerical results that show the advantages of this filter when dealing with adversarial noise and compare the performance of the various robust filters with the KF.

AB - Tracking problems are prevalent in the present day GPS and video systems. The problem of target tracking is a specific case of dynamic linear system estimation with additive noise. The most widely used filter for these systems is the Kalman filter (KF). The optimality of the KF and similar Bayesian filters is guaranteed under particular probabilistic assumptions. However, in practice, and specifically in applications such as tracking, these probabilistic assumptions are not realistic; indeed, the system noise is typically bounded and in fact might be adversarial. For such cases, robust estimation approaches, such as H∞ filtering and set-value estimation, were introduced with the aim of providing filters with guaranteed worst case performance. In this paper we present an innovative approximated set-value estimator (SVE) which is obtained through a semi-definite programming problem. We demonstrate that our problem is practically tractable even for long time horizons. The framework is extended to include the case of partially statistical noise, thus combining the KF and SVE frameworks. A variation of this filter which applies a rolling window approach is developed, achieving fixed computational cost per-iteration and coinciding with the classical SVE when window size is one. Finally, we present numerical results that show the advantages of this filter when dealing with adversarial noise and compare the performance of the various robust filters with the KF.

KW - robust optimization

KW - semidefinite programming

KW - estimation of linear systems

U2 - 10.1007/s10107-015-0910-5

DO - 10.1007/s10107-015-0910-5

M3 - Article

VL - 156

SP - 615

EP - 656

JO - Mathematical Programming

JF - Mathematical Programming

SN - 0025-5610

IS - 1

ER -