A Minimal Cardinality Solution to Fitting Sawtooth Piecewise-Linear Functions

Cody Allen () and Mauricio Oliveira ()
Additional contact information
Cody Allen: University of California, San Diego
Mauricio Oliveira: University of California, San Diego

Journal of Optimization Theory and Applications, 2022, vol. 192, issue 3, No 7, 930-959

Abstract: Abstract In this paper, we explore a method to parameterize a linear function with jump discontinuities, which we refer to as a “sawtooth” function, and then develop theory and algorithms for estimating the function parameters from noisy data in a least-squares framework. Because there will always exist a sawtooth function that exactly fits a given data set, one is led to bounding the maximum number of jumps the sawtooth function can have in order to obtain reasonable practical estimates. The main contribution of the paper is a proof that cardinality of the optimal solutions to a relaxation of the associated least-squares problem in which a constraint on the cardinality of the solutions is replaced by a 1-norm constraint on the vector of jumps is a monotonic function of the parameter of the relaxation. This property allows one to avoid dealing with the combinatorial cardinality constraint and quickly explore solutions using the proposed convex relaxation. A fitting algorithm based on the proposed results is developed and illustrated with a simple numerical example.

Keywords: Least squares; Cardinality constraint; Piecewise-linear functions; 90C27; 62J07; 46n10 (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10957-021-01998-6 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joptap:v:192:y:2022:i:3:d:10.1007_s10957-021-01998-6

Ordering information: This journal article can be ordered from
http://www.springer. ... cs/journal/10957/PS2

DOI: 10.1007/s10957-021-01998-6

Access Statistics for this article

Journal of Optimization Theory and Applications is currently edited by Franco Giannessi and David G. Hull

More articles in Journal of Optimization Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().