HOPS: A Fast Algorithm for Segmenting Piecewise Polynomials of Arbitrary Orders

The segmentation of piecewise polynomial signals arises in a variety of scientific and engineering fields. When a signal is modeled as a piecewise polynomial, the key then becomes the detection of breakpoints followed by curve fitting and parameter estimation. This paper proposes HOPS, a fast High-O...

Description complète

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Junbo Duan, Qing Wang, Yu-Ping Wang
Format:	article
Langue:	EN
Publié:	IEEE 2021
Sujets:	Piecewise polynomials breakpoint detection segmentation curve fitting sparse modeling Electrical engineering. Electronics. Nuclear engineering TK1-9971
Accès en ligne:	https://doaj.org/article/05e4a3fc584e4cc1a738e960034db8c4
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

id	oai:doaj.org-article:05e4a3fc584e4cc1a738e960034db8c4
record_format	dspace
spelling	oai:doaj.org-article:05e4a3fc584e4cc1a738e960034db8c42021-12-01T00:00:33ZHOPS: A Fast Algorithm for Segmenting Piecewise Polynomials of Arbitrary Orders2169-353610.1109/ACCESS.2021.3128902https://doaj.org/article/05e4a3fc584e4cc1a738e960034db8c42021-01-01T00:00:00Zhttps://ieeexplore.ieee.org/document/9618954/https://doaj.org/toc/2169-3536The segmentation of piecewise polynomial signals arises in a variety of scientific and engineering fields. When a signal is modeled as a piecewise polynomial, the key then becomes the detection of breakpoints followed by curve fitting and parameter estimation. This paper proposes HOPS, a fast High-Order Polynomial Segmenter, which is based on <inline-formula> <tex-math notation="LaTeX">$\ell _{0}$ </tex-math></inline-formula>-penalized least-square regression. While the least-squares regression ensures fitting fidelity, the <inline-formula> <tex-math notation="LaTeX">$\ell _{0}$ </tex-math></inline-formula> penalty takes the number of breakpoints into account. We show that dynamic programming can be applied to find the optimal solution to this problem and that a pruning strategy and matrix factorization can be utilized to accelerate the execution speed. Finally, we provide some illustrative examples, and compare the proposed method with state-of-the-art alternatives.Junbo DuanQing WangYu-Ping WangIEEEarticlePiecewise polynomialsbreakpoint detectionsegmentationcurve fittingsparse modelingElectrical engineering. Electronics. Nuclear engineeringTK1-9971ENIEEE Access, Vol 9, Pp 155977-155987 (2021)
institution	DOAJ
collection	DOAJ
language	EN
topic	Piecewise polynomials breakpoint detection segmentation curve fitting sparse modeling Electrical engineering. Electronics. Nuclear engineering TK1-9971
spellingShingle	Piecewise polynomials breakpoint detection segmentation curve fitting sparse modeling Electrical engineering. Electronics. Nuclear engineering TK1-9971 Junbo Duan Qing Wang Yu-Ping Wang HOPS: A Fast Algorithm for Segmenting Piecewise Polynomials of Arbitrary Orders
description	The segmentation of piecewise polynomial signals arises in a variety of scientific and engineering fields. When a signal is modeled as a piecewise polynomial, the key then becomes the detection of breakpoints followed by curve fitting and parameter estimation. This paper proposes HOPS, a fast High-Order Polynomial Segmenter, which is based on <inline-formula> <tex-math notation="LaTeX">$\ell _{0}$ </tex-math></inline-formula>-penalized least-square regression. While the least-squares regression ensures fitting fidelity, the <inline-formula> <tex-math notation="LaTeX">$\ell _{0}$ </tex-math></inline-formula> penalty takes the number of breakpoints into account. We show that dynamic programming can be applied to find the optimal solution to this problem and that a pruning strategy and matrix factorization can be utilized to accelerate the execution speed. Finally, we provide some illustrative examples, and compare the proposed method with state-of-the-art alternatives.
format	article
author	Junbo Duan Qing Wang Yu-Ping Wang
author_facet	Junbo Duan Qing Wang Yu-Ping Wang
author_sort	Junbo Duan
title	HOPS: A Fast Algorithm for Segmenting Piecewise Polynomials of Arbitrary Orders
title_short	HOPS: A Fast Algorithm for Segmenting Piecewise Polynomials of Arbitrary Orders
title_full	HOPS: A Fast Algorithm for Segmenting Piecewise Polynomials of Arbitrary Orders
title_fullStr	HOPS: A Fast Algorithm for Segmenting Piecewise Polynomials of Arbitrary Orders
title_full_unstemmed	HOPS: A Fast Algorithm for Segmenting Piecewise Polynomials of Arbitrary Orders
title_sort	hops: a fast algorithm for segmenting piecewise polynomials of arbitrary orders
publisher	IEEE
publishDate	2021
url	https://doaj.org/article/05e4a3fc584e4cc1a738e960034db8c4
work_keys_str_mv	AT junboduan hopsafastalgorithmforsegmentingpiecewisepolynomialsofarbitraryorders AT qingwang hopsafastalgorithmforsegmentingpiecewisepolynomialsofarbitraryorders AT yupingwang hopsafastalgorithmforsegmentingpiecewisepolynomialsofarbitraryorders
_version_	1718406122410344448

HOPS: A Fast Algorithm for Segmenting Piecewise Polynomials of Arbitrary Orders

Documents similaires