<link rel="stylesheet" href="styles.f3b1fba60ec7970c.css">

Publication:
Universal switching linear least squares prediction

Loading...
Thumbnail Image

Departments

School / College / Institute

Item type:Organizational Unit,

Program

Organization Authors

Co-Authors

Singer, Andrew C.

Date

Language

Embargo Status

N/A

Journal Title

Journal ISSN

Volume Title

Alternative Title

Abstract

In this paper, we consider sequential regression of individual sequences under the square-error loss. We focus on the class of switching linear predictors that can segment a given individual sequence into an arbitrary number of blocks within each of which a fixed linear regressor is applied. Using a competitive algorithm framework, we construct sequential algorithms that are competitive with the best linear regression algorithms for any segmenting of the data as well as the best partitioning of the data into any fixed number of segments, where both the segmenting of the data and the linear predictors within each segment can be tuned to the underlying individual sequence. The algorithms do not require knowledge of the data length or the number of piecewise linear segments used by the members of the competing class, yet can achieve the performance of the best member that can choose both the partitioning of the sequence as well as the best regressor within each segment. We use a transition diagram (F. M. J. Willems, 1996) to compete with an exponential number of algorithms in the class, using complexity that is linear in the data length. The regret with respect to the best member is O(ln(n)) per transition for not knowing the best transition times and O(ln(n)) for not knowing the best regressor within each segment, where n is the data length. We construct lower bounds on the performance of any sequential algorithm, demonstrating a form of min-max optimality under certain settings. We also consider the case where the members are restricted to choose the best algorithm in each segment from a finite collection of candidate algorithms. Performance on synthetic and real data are given along with a Matlab implementation of the universal switching linear predictor.

Source

Publisher

Ieee-Inst Electrical Electronics Engineers Inc

Citation

item.page.haspartof

Source

Ieee Transactions on Signal Processing

item.page.ispartofseries

item.page.edition

DOI

10.1109/TSP.2007.901161

item.page.datauri

item.page.link

Rights

N/A

Copyrights Note

Rights and licensing

N/A

Endorsement

Review

Supplemented By

Referenced By

Related Patent

Related Goal

Google Scholar
Scholar'da Ara ↗
Altmetric
Dimensions
PlumX Metrikleri
BIP! Indicators