Introduction
Slope change detection seeks the location in a time-ordered sequence, called a breakpoint , at which the rate of change of an underlying signal changes. Unlike mean-shift detection, which seeks abrupt changes in the signal level, slope change detection considers changes in trend while preserving continuity. Slope-change models have been used in a variety of applications, including surface-temperature trends in climatology [2 , 48 , 7 , 57 ] , rainfall trends [20 ] , changes in health outcomes measured repeatedly over time [17 ] , and sensor-based monitoring [19 ] . In many applications, multiple signals are observed at each observation time, and a common event, such as a regime shift or a system fault, may change their trends simultaneously. This motivates fitting a slope change that is shared across the dimensions of a multidimensional time series.
Problem formulation
Let T ≥ 4 T \ge4 T ≥ 4 be an integer, let x 1 < x 2 < ⋯ < x T x_1 < x_2 < \cdots< x_T x 1 < x 2 < ⋯ < x T be rational time coordinates, and let y i = ( y i 1 , … , y i J ) ∈ Q J y_i = (y_i^1,\ldots,y_i^J) \in\mathbb{Q}^J y i = ( y i 1 , … , y i J ) ∈ Q J be the observation at time x i x_i x i , so that y i j y_i^j y i j is the observation of dimension j ∈ [ J ] j \in[J] j ∈ [ J ] at time x i x_i x i . For a breakpoint z ∈ R z \in\mathbb{R} z ∈ R , every continuous function that is affine on ( − ∞ , z ] (-\infty,z] ( − ∞ , z ] and on [ z , ∞ ) [z,\infty) [ z , ∞ ) can be written uniquely as
x ↦ α + β x + δ ( x − z ) + , x \mapsto\alpha+ \beta x + \delta(x-z)_+, x ↦ α + β x + δ ( x − z ) + ,
where ( t ) + : = max { t , 0 } (t)_+ := \max\{t,0\} ( t ) + := max { t , 0 } . We call z z z the breakpoint of this function. This function has slope β \beta β and intercept α \alpha α before the breakpoint, and slope β + δ \beta+\delta β + δ and intercept α − δ z \alpha-\delta z α − δ z after it. Thus δ \delta δ is the change in slope, and continuity at z z z is built into the representation. We fit one such function to each dimension, with a breakpoint common to all dimensions. Given z ∈ R z \in\mathbb{R} z ∈ R and α , β , δ ∈ R J \alpha,\beta,\delta\in\mathbb{R}^J α , β , δ ∈ R J , the residual of dimension j j j at time x i x_i x i is
r i j = y i j − α j − β j x i − δ j ( x i − z ) + , i ∈ [ T ] , j ∈ [ J ] , (1) r_i^j = y_i^j - \alpha_j - \beta_j x_i - \delta_j(x_i-z)_+,\qquad i \in[T],\ j \in[J], \tag*{(1)} r i j = y i j − α j − β j x i − δ j ( x i − z ) + , i ∈ [ T ] , j ∈ [ J ] , (1)
and r ∈ R T J r \in\mathbb{R}^{TJ} r ∈ R T J denotes the vector of these T J TJ T J residuals. For p ∈ { 1 , 2 , ∞ } p \in\{1,2,\infty\} p ∈ { 1 , 2 , ∞ } , define the loss
L p ( r ) : = { ∑ i , j ∣ r i j ∣ , p = 1 , ∑ i , j ( r i j ) 2 , p = 2 , max i , j ∣ r i j ∣ , p = ∞ . L_p(r) := \begin{cases}
\sum_{i,j} |r_i^j|, & p=1,\\
\sum_{i,j} (r_i^j)^2, & p=2,\\
\max_{i,j} |r_i^j|, & p=\infty.
\end{cases} L p ( r ) := ⎩ ⎨ ⎧ ∑ i , j ∣ r i j ∣ , ∑ i , j ( r i j ) 2 , max i , j ∣ r i j ∣ , p = 1 , p = 2 , p = ∞.
Given data ( x i , y i ) i ∈ [ T ] (x_i,y_i)_{i\in[T]} ( x i , y i ) i ∈ [ T ] with x i ∈ Q x_i \in\mathbb{Q} x i ∈ Q and y i ∈ Q J y_i \in\mathbb{Q}^J y i ∈ Q J , and k ∈ { 0 , 1 , … , J } k \in\{0,1,\ldots,J\} k ∈ { 0 , 1 , … , J } , the slope change problem is
OPT p , k : = min z , α , β , δ , r { L p ( r ) : r satisfies ( 1 ) , ∥ δ ∥ 0 ≤ k , z ∈ [ x 2 , x T − 1 ] } . (2) \operatorname{OPT}_{p,k} := \min_{z,\alpha,\beta,\delta,r} \left\{L_p(r): r\text{ satisfies }{(1)},\ \|\delta\|_0 \le k,\ z \in[x_2,x_{T-1}]\right\}. \tag*{(2)} OPT p , k := z , α , β , δ , r min { L p ( r ) : r satisfies ( 1 ) , ∥ δ ∥ 0 ≤ k , z ∈ [ x 2 , x T − 1 ] } . (2)
The constraint ∥ δ ∥ 0 ≤ k \|\delta\|_0 \le k ∥ δ ∥ 0 ≤ k allows at most k k k dimensions to change slope, and each remaining dimension is fitted by a single line. We refer to the case k = J k=J k = J as the dense problem and to the case k < J k<J k < J as the sparse problem . The constraint z ∈ [ x 2 , x T − 1 ] z \in[x_2,x_{T-1}] z ∈ [ x 2 , x T − 1 ] ensures that at least two observations lie on each side of the breakpoint, since a change in slope cannot be inferred from a segment containing a single observation.
Three features make this problem nontrivial. First, the breakpoint z z z is a continuous decision variable, and the terms δ j ( x i − z ) + \delta_j(x_i-z)_+ δ j ( x i − z ) + introduce nonconvexity. Second, the breakpoint is shared across all dimensions, coupling their fitting problems. Third, the sparse problem introduces the additional combinatorial problem of selecting which dimensions may change slope. Although the problem can be formulated as a mixed-integer nonlinear program [47 ] , we show that its special structure permits polynomial-time algorithms.
Related literature
Single-dimension time series. Most methods for a single time series allow several breakpoints but restrict the breakpoints to the observation times or a prespecified candidate set. Without continuity, dynamic programming finds exact solutions [38 , 5 , 39 ] . With continuity, [25 ] use functional dynamic programming with an ℓ 0 \ell_0 ℓ 0 penalty on the number of slope changes, and [24 ] allow unevenly spaced observations and more flexible candidate sets. The convex alternative, ℓ 1 \ell_1 ℓ 1 trend filtering [42 , 55 ] , penalizes the second differences of the fitted values, so its breakpoints arise implicitly at observation times. Fewer methods treat breakpoint locations as continuous. For one breakpoint under least squares, the setting closest to ours, [37 ] obtains the exact fit by examining each interval between consecutive observations, with statistical properties studied in [36 , 26 ] and a grid-search alternative proposed by [44 ] . For several breakpoints, iterative linearization [46 ] guarantees only local optimality, while mixed-integer programming provides exact formulations [56 , 49 , 30 , 47 ] .
Multiple-dimension time series with shared breakpoints. Here, the breakpoints are common to all dimensions. [40 ] estimates a break in the intercept, slope, or both of a linear trend, common to all series in a large panel, by minimizing the total sum of squared residuals over all break dates, and [41 ] estimates the break date jointly with latent common factors in the errors. For shared changes in the mean, the group fused lasso [11 ] gives a convex formulation. [19 ] detects, online, a common change point after which a subset of the dimensions moves from a constant mean to a linear drift, with sparsity modeled through the probability that each dimension is affected. Sparse changes in the mean of high-dimensional time series are studied by [58 ] and [23 ] . These works differ from our setting in their restrictions on breakpoint locations, assumptions on the form of the slope change, or statistical detection objectives, and none establishes polynomial-time global optimization for the formulation (2) . [47 ] extends their mixed-integer formulations to shared breakpoints. These formulations are exact, but they are not known to be solvable in polynomial time.
Parametric linear programming. [15 ] optimizes the value of min { c T x : ( A 0 + λ A 1 ) x ≤ b , x ≥ 0 } \min\{c^{\mathsf{T}}x : (A_0+\lambda A_1)x \le b,\ x \ge0\} min { c T x : ( A 0 + λ A 1 ) x ≤ b , x ≥ 0 } over a scalar λ \lambda λ in an interval, extending sensitivity analysis [28 ] . They prove that both minimizing and maximizing this value are NP-hard, and identify easier cases where A 1 A_1 A 1 has entries of one sign or a single nonzero row or column. For p ∈ { 1 , ∞ } p \in\{1,\infty\} p ∈ { 1 , ∞ } and fixed i ∗ i^* i ∗ , our dense problem is the minimization version with λ = z \lambda= z λ = z . However, because of the absolute values, A 1 A_1 A 1 always has entries of both signs, and for J ≥ 2 J \ge2 J ≥ 2 it has J J J nonzero columns, so none of these cases applies. We nevertheless solve the dense and sparse problems exactly in polynomial time, even though the optimal z z z may be irrational and the sparse problem is not an LP for fixed i ∗ i^* i ∗ .
Complexity and connection to ReLU networks. Closely related function recovery problems are NP-hard [60 ] , and [25 ] notes that it is unclear whether detecting multiple slope changes is NP-hard. We study the setting with a single breakpoint that is shared across dimensions and located continuously. This setting is also the global training of a ReLU network whose input is time, with a single hidden unit ( x − z ) + (x-z)_+ ( x − z ) + shared by J J J outputs with affine skip connections, where the breakpoint z z z is restricted to [ x 2 , x T − 1 ] [x_2,x_{T-1}] [ x 2 , x T − 1 ] . Training ReLU networks is NP-hard for other architectures [22 , 14 , 29 ] , and optimal weights can be irrational [1 , 9 ] . These results do not imply hardness for ours. Exact polynomial-time training is known for one hidden layer with a single output and fixed input dimension [4 ] , but this does not cover multiple outputs.
Main complexity results
Throughout, ⟨ D ⟩ \langle\mathcal{D}\rangle ⟨ D ⟩ denotes the binary encoding length of the data D : = ( x i , y i ) i ∈ [ T ] \mathcal{D}:=(x_i,y_i)_{i\in[T]} D := ( x i , y i ) i ∈ [ T ] . The existence and representation of rational solutions are important issues in mixed-integer nonlinear programming. For example, mixed-integer quadratic programming admits polynomial-size certificates of feasibility [21 ] , whereas systems of cubic polynomial inequalities with rational data may have only irrational feasible solutions, and deciding the existence of rational solutions is NP-hard [10 ] . Problem (2) exhibits both phenomena, that is, optimal breakpoints can be irrational, yet we show that optimal solutions admit polynomial-size algebraic representations and can be computed exactly in polynomial time. To see that optimal breakpoints can be irrational, let T = 6 T=6 T = 6 , J = 2 J=2 J = 2 , x i = i − 1 x_i=i-1 x i = i − 1 for i ∈ [ 6 ] i\in[6] i ∈ [ 6 ] , y 1 = ( − 2 , 2 , − 2 , − 2 , 5 , 0 ) y^1=(-2,2,-2,-2,5,0) y 1 = ( − 2 , 2 , − 2 , − 2 , 5 , 0 ) , and y 2 = ( − 9 , 4 , 8 , − 6 , − 4 , 0 ) y^2=(-9,4,8,-6,-4,0) y 2 = ( − 9 , 4 , 8 , − 6 , − 4 , 0 ) . Then
OPT 2 , 2 = 74531 − 477755737 420 ≈ 125.4128 , \operatorname{OPT}_{2,2}=\frac{74531-\sqrt{477755737}}{420}\approx125.4128, OPT 2 , 2 = 420 74531 − 477755737 ≈ 125.4128 ,
attained at z ⋆ = ( − 58563 + 5 477755737 ) / 49162 ≈ 1.0318 z^\star=(-58563+5\sqrt{477755737})/49162\approx1.0318 z ⋆ = ( − 58563 + 5 477755737 ) /49162 ≈ 1.0318 . Since 477755737 477755737 477755737 is not a perfect square, both z ⋆ z^\star z ⋆ and OPT 2 , 2 \operatorname{OPT}_{2,2} OPT 2 , 2 are irrational. This irrationality is caused by sharing the breakpoint across dimensions. For J = 1 J=1 J = 1 and p = 2 p=2 p = 2 a rational optimal breakpoint always exists (see § 3 ). We therefore specify what an algorithm returns.
Definition 1. An algorithm solves (2) if it returns an optimal breakpoint z ⋆ z^\star z ⋆ , represented as a real algebraic number by a univariate polynomial with rational coefficients together with an interval with rational endpoints that contains z ⋆ z^\star z ⋆ and no other root of the polynomial, and returns α ⋆ , β ⋆ , δ ⋆ \alpha^\star,\beta^\star,\delta^\star α ⋆ , β ⋆ , δ ⋆ as explicit rational functions of z ⋆ z^\star z ⋆ with rational coefficients.
As we shall see, for p ∈ { 2 , ∞ } p\in\{2,\infty\} p ∈ { 2 , ∞ } , our algorithms return an optimal breakpoint z ⋆ z^\star z ⋆ that is algebraic of degree at most two over Q \mathbb{Q} Q . For p = 1 p=1 p = 1 , its degree is at most max { 2 , 2 J − 2 } \max\{2,2J-2\} max { 2 , 2 J − 2 } in the dense problem and at most max { 2 , 2 k − 2 } \max\{2,2k-2\} max { 2 , 2 k − 2 } in the sparse problem. In all cases, the optimal fitting coefficients can be chosen in Q ( z ⋆ ) \mathbb{Q}(z^\star) Q ( z ⋆ ) , the smallest subfield of R \mathbb{R} R containing Q \mathbb{Q} Q and z ⋆ z^\star z ⋆ , which consists of the values at z ⋆ z^\star z ⋆ of rational functions with rational coefficients.
The encoding length of an algebraic number represented as in Definition 1 is the total binary encoding length of the coefficients of the polynomial and the endpoints of the interval. All rational and algebraic numbers arising in our algorithms admit representations of encoding length polynomial in T T T , J J J , and ⟨ D ⟩ \langle D\rangle ⟨ D ⟩ . Standard algorithms for real algebraic numbers perform exact arithmetic, root isolation, sign evaluation, and comparison on these representations in polynomial time [6 , 51 ] . Consequently, the optimal breakpoint, objective value, and fitting coefficients can also be approximated to within 2 − t 2^{-t} 2 − t in time polynomial in T T T , J J J , ⟨ D ⟩ \langle D\rangle ⟨ D ⟩ , and t t t [16 , 51 ] .
Poly-time complexity
Theorem 1. For every p ∈ { 1 , 2 , ∞ } p\in\{1,2,\infty\} p ∈ { 1 , 2 , ∞ } and k ∈ { 0 , 1 , … , J } k\in\{0,1,\ldots,J\} k ∈ { 0 , 1 , … , J } , problem (2) can be solved, in the sense of Definition 1, in time polynomial in T T T , J J J , and ⟨ D ⟩ \langle D\rangle ⟨ D ⟩ . More precisely, the algorithms perform the arithmetic operations counted in Table 1 . All numbers involved are rational or algebraic, with encoding length polynomial in T T T , J J J , and ⟨ D ⟩ \langle D\rangle ⟨ D ⟩ . For p ∈ { 2 , ∞ } p\in\{2,\infty\} p ∈ { 2 , ∞ } , these operations include, and the table counts among them, computations of roots of quadratic polynomials and exact comparisons of quadratic algebraic numbers. For p = 1 p=1 p = 1 , the algorithm additionally performs root isolations and algebraic-number comparisons, counted in Table 1 . All these algebraic operations have polynomial bit complexity.
Table 1. Number of operations of the algorithms. Quadratic root computations and comparisons of quadratic algebraic numbers count as single operations. For p = 1 p=1 p = 1 , the table also lists the root isolations of the polynomials of degree at most 2 J − 2 2J-2 2 J − 2 or 2 k − 2 2k-2 2 k − 2 , which are needed only if J ≥ 2 J\ge2 J ≥ 2 or k ≥ 2 k\ge2 k ≥ 2 , and the comparisons of the resulting algebraic numbers. All these operations have polynomial bit complexity Theorem 1.
When k = 0 k=0 k = 0 , each dimension is fitted by a single line, and the problem is solved directly. For p = 2 p=2 p = 2 , the dense algorithm is linear in the number J T JT J T of observations, which is optimal up to a constant factor since every observation must be read, and the sparse algorithm is linear in T T T and nearly quadratic in J J J . In our experiments, a dense instance with J = 10 5 J=10^5 J = 1 0 5 and T = 100 T=100 T = 100 , that is, 10 7 10^7 1 0 7 observations, is solved in less than 0.1 seconds on a laptop, and sparse instances with about 10 3 10^3 1 0 3 dimensions are solved in under a second. § 5 describes the experiments, software, and hardware. We have not tried to optimize the running-time for p ∈ { 1 , ∞ } p\in\{1,\infty\} p ∈ { 1 , ∞ } , whose purpose is to establish polynomial-time solvability.
Outline of the proof of Theorem 1
The three losses, each in the dense and the sparse setting, give six variants of the problem. All six variants are solved by the same six-step strategy described below. The details of each step depend on the variant. The main idea is that, for a fixed breakpoint z z z , the problem splits into J J J small fitting problems, one for each dimension. We study how the optimal error of each of these problems varies with z z z , combine these errors over the dimensions, and reduce the search for z z z to finitely many candidates.
Step 1: reduction to intervals. The nonlinear terms ( x i − z ) + (x_i-z)_+ ( x i − z ) + depend on which observations lie to the right of z z z . Once we restrict z z z to an interval between consecutive observations, this set is fixed and each residual term, r i j r_i^j r i j , becomes affine in z z z . For i ∗ ∈ { 2 , … , T − 2 } i^* \in\{2,\ldots,T-2\} i ∗ ∈ { 2 , … , T − 2 } , let OPT p , k i ∗ \operatorname{OPT}_{p,k}^{i^*} OPT p , k i ∗ denote the optimal value of (2) with z ∈ [ x i ∗ , x i ∗ + 1 ] z\in[x_{i^*},x_{i^*+1}] z ∈ [ x i ∗ , x i ∗ + 1 ] . Since these intervals cover [ x 2 , x T − 1 ] [x_2,x_{T-1}] [ x 2 , x T − 1 ] , we have that OPT p , k = min i ∗ ∈ { 2 , … , T − 2 } OPT p , k i ∗ \operatorname{OPT}_{p,k}=\min_{i^*\in\{2,\ldots,T-2\}}\operatorname{OPT}_{p,k}^{i^*} OPT p , k = min i ∗ ∈ { 2 , … , T − 2 } OPT p , k i ∗ . For z ∈ [ x i ∗ , x i ∗ + 1 ] z\in[x_{i^*},x_{i^*+1}] z ∈ [ x i ∗ , x i ∗ + 1 ] , including the endpoints, the residuals (1) become
r i j = y i j − α j − β j x i − δ j h i ( z ) , h i ( z ) : = { 0 , i ≤ i ∗ , x i − z , i > i ∗ . r_i^j=y_i^j-\alpha_j-\beta_jx_i-\delta_jh_i(z),\qquad h_i(z):=\begin{cases}0,&i\le i^*,\\x_i-z,&i>i^*.\end{cases} r i j = y i j − α j − β j x i − δ j h i ( z ) , h i ( z ) := { 0 , x i − z , i ≤ i ∗ , i > i ∗ .
Since 2 ≤ i ∗ ≤ T − 2 2\le i^*\le T-2 2 ≤ i ∗ ≤ T − 2 , each side of the breakpoint contains at least two observations with distinct time coordinates. We show this implies the three columns ( 1 ) i ∈ [ T ] (1)_{i\in[T]} ( 1 ) i ∈ [ T ] , ( x i ) i ∈ [ T ] (x_i)_{i\in[T]} ( x i ) i ∈ [ T ] , and ( h i ( z ) ) i ∈ [ T ] (h_i(z))_{i\in[T]} ( h i ( z ) ) i ∈ [ T ] of the fitting problem, corresponding to α j \alpha_j α j , β j \beta_j β j , and δ j \delta_j δ j , are linearly independent for every z z z , so none of them becomes redundant. We fix i ∗ i^* i ∗ for the rest of the outline.
Step 2: decoupling for fixed z z z . For fixed z z z , the dimensions interact only through the choice of which of them may change slope. Each dimension is otherwise fitted separately using the three variables ( α j , β j , δ j ) (\alpha_j,\beta_j,\delta_j) ( α j , β j , δ j ) . For j ∈ [ J ] j\in[J] j ∈ [ J ] and z ∈ [ x i ∗ , x i ∗ + 1 ] z\in[x_{i^*},x_{i^*+1}] z ∈ [ x i ∗ , x i ∗ + 1 ] , let f j ( z ) f_j(z) f j ( z ) be the minimum error when dimension j j j may change slope at z z z . This error is ∑ i ∣ r i j ∣ \sum_i|r_i^j| ∑ i ∣ r i j ∣ , ∑ i ( r i j ) 2 \sum_i(r_i^j)^2 ∑ i ( r i j ) 2 , or max i ∣ r i j ∣ \max_i|r_i^j| max i ∣ r i j ∣ for p = 1 , 2 , ∞ p=1,2,\infty p = 1 , 2 , ∞ , respectively. Let U j U_j U j be the corresponding minimum with δ j = 0 \delta_j=0 δ j = 0 . Thus U j U_j U j is the error of the best single line, independent of z z z , and f j ( z ) ≤ U j f_j(z)\le U_j f j ( z ) ≤ U j . Then
OPT p , k i ∗ = min z ∈ [ x i ∗ , x i ∗ + 1 ] min S ⊆ [ J ] , ∣ S ∣ ≤ k ( ⨁ j ∈ S f j ( z ) ) ⊕ ( ⨁ j ∉ S U j ) . \operatorname{OPT}_{p,k}^{i^*}=\min_{z\in[x_{i^*},x_{i^*+1}]}\min_{S\subseteq[J],\,|S|\le k}\left(\bigoplus_{j\in S}f_j(z)\right)\oplus\left(\bigoplus_{j\notin S}U_j\right). OPT p , k i ∗ = z ∈ [ x i ∗ , x i ∗ + 1 ] min S ⊆ [ J ] , ∣ S ∣ ≤ k min j ∈ S ⨁ f j ( z ) ⊕ j ∈ / S ⨁ U j .
where ⊕ \oplus ⊕ denotes addition for p ∈ { 1 , 2 } p\in\{1,2\} p ∈ { 1 , 2 } and maximum for p = ∞ p=\infty p = ∞ , and an empty aggregation equals zero. Thus the problem reduces to understanding and combining the functions f j ( ⋅ ) f_j(\cdot) f j ( ⋅ ) .
Step 3: structure of each f j ( ⋅ ) f_j(\cdot) f j ( ⋅ ) . We establish that f j ( ⋅ ) f_j(\cdot) f j ( ⋅ ) is continuous. As we cannot evaluate f j ( z ) f_j(z) f j ( z ) for every z z z , we show that each f j ( ⋅ ) f_j(\cdot) f j ( ⋅ ) is piecewise rational on [ x i ∗ , x i ∗ + 1 ] [x_i^*,x_{i^*+1}] [ x i ∗ , x i ∗ + 1 ] , with polynomially many pieces. Each piece has numerator and denominator of degree at most two, and its endpoints are roots of polynomials of degree at most two with rational coefficients.
For p = 2 p=2 p = 2 , the least-squares projection gives a single piece, f j ( z ) = U j − ν j ( z ) 2 / D ( z ) f_j(z)=U_j-\nu_j(z)^2/D(z) f j ( z ) = U j − ν j ( z ) 2 / D ( z ) , where ν j ( z ) \nu_j(z) ν j ( z ) is affine in z z z and D ( z ) D(z) D ( z ) is a positive quadratic in z z z . Crucially, D ( ⋅ ) D(\cdot) D ( ⋅ ) is common to all dimensions.
For p ∈ { 1 , ∞ } p\in\{1,\infty\} p ∈ { 1 , ∞ } , f j ( z ) f_j(z) f j ( z ) is the optimal value of a linear program. We show that its feasible region is pointed. Since its objective is bounded below by zero, the linear program has an optimal vertex. Since z z z appears only, and affinely, in the column of δ j \delta_j δ j , the Cramer rule shows that every basic solution has entries ( a + b z ) / ( c + d z ) (a+bz)/(c+dz) ( a + b z ) / ( c + d z ) with a , b , c , d ∈ Q a,b,c,d\in\mathbb{Q} a , b , c , d ∈ Q . We call such functions linear-fractional. Such a function can be shown to be monotone on every interval that avoids its pole, and two distinct ones cross at most twice. We bound the number of vertices and determine where each is feasible.
For p = ∞ p=\infty p = ∞ , the linear program minimizes η \eta η over the four variables ( α j , β j , δ j , η ) (\alpha_j,\beta_j,\delta_j,\eta) ( α j , β j , δ j , η ) , subject to the 2 T 2T 2 T constraints − η ≤ r i j ≤ η -\eta\le r_i^j\le\eta − η ≤ r i j ≤ η for i ∈ [ T ] i\in[T] i ∈ [ T ] . A vertex is determined by four active constraints, so there are O ( T 4 ) O(T^4) O ( T 4 ) candidate vertices. For each candidate, η \eta η is linear-fractional in z z z , and the candidate is feasible on a union of O ( T ) O(T) O ( T ) intervals. Hence f j ( ⋅ ) f_j(\cdot) f j ( ⋅ ) is the minimum of O ( T 5 ) O(T^5) O ( T 5 ) linear-fractional functions, each restricted to one interval.
For p = 1 p=1 p = 1 , we prove that an optimal fit can be chosen to pass through three observations, not all on the same side of the breakpoint. Thus, there are O ( T 3 ) O(T^3) O ( T 3 ) choices. Each determines ( α j , β j , δ j ) (\alpha_j,\beta_j,\delta_j) ( α j , β j , δ j ) uniquely as linear-fractional functions of z z z . Every such fit is feasible, so, unlike for p = ∞ p=\infty p = ∞ , no restriction on z z z is needed. Its loss ∑ i ∣ r i j ∣ \sum_i|r_i^j| ∑ i ∣ r i j ∣ is piecewise linear-fractional, with O ( T ) O(T) O ( T ) pieces separated by residual sign changes. Thus f j ( ⋅ ) f_j(\cdot) f j ( ⋅ ) is the minimum of O ( T 4 ) O(T^4) O ( T 4 ) linear-fractional functions, each restricted to one interval.
Step 4: aggregation in the dense problem. Here we minimize ⨁ j ∈ [ J ] f j ( z ) \bigoplus_{j\in[J]}f_j(z) ⨁ j ∈ [ J ] f j ( z ) . Each f j f_j f j is piecewise rational on [ x i ∗ , x i ∗ + 1 ] [x_i^*,x_{i^*+1}] [ x i ∗ , x i ∗ + 1 ] , and together their breakpoints partition this interval into cells. On each cell, every f j f_j f j is given by a single rational expression whose denominator does not vanish on the cell. We minimize the resulting univariate function on each cell and take the best value over all cells.
If ⊕ \oplus ⊕ is the maximum, the objective on each cell is the upper envelope of J J J linear-fractional functions. We show each is monotone on the cell, so a minimum occurs at a cell endpoint or a crossing of two functions.
Step 5: support selection in the sparse problem. Allowing dimension j j j to change slope gives the gain u j ( z ) : = U j − f j ( z ) ≥ 0 u_j(z):=U_j-f_j(z)\ge0 u j ( z ) := U j − f j ( z ) ≥ 0 . Our task is to choose at most k k k dimensions. The optimal choice depends on the aggregation.
First, suppose ⊕ \oplus ⊕ is addition. For a set S S S , the total error is ∑ j ∈ [ J ] U j − ∑ j ∈ S u j ( z ) \sum_{j\in[J]}U_j-\sum_{j\in S}u_j(z) ∑ j ∈ [ J ] U j − ∑ j ∈ S u j ( z ) . For fixed z z z , an optimal S S S consists of the k k k dimensions with the largest gains. The ranking of the gains, however, varies with z z z , and the set of the k k k largest gains can change only at crossings of two gains, where their relative order may change. Therefore, between consecutive crossings, S S S is fixed and we solve the dense problem restricted to S S S . For p = 1 p=1 p = 1 , the gains are linear-fractional on each cell of Step 4, so two distinct gains cross at most twice, giving O ( J 2 ) O(J^2) O ( J 2 ) crossings per cell. For p = 2 p=2 p = 2 , the common denominator in u j ( z ) = ν j ( z ) 2 / D ( z ) u_j(z)=\nu_j(z)^2/D(z) u j ( z ) = ν j ( z ) 2 / D ( z ) means that the ranking is determined by ∣ ν j ( z ) ∣ |\nu_j(z)| ∣ ν j ( z ) ∣ , which gives the subcells on which the ranking is constant.
Next, suppose ⊕ \oplus ⊕ is maximum. For S ⊆ [ J ] S\subseteq[J] S ⊆ [ J ] with ∣ S ∣ = k |S|=k ∣ S ∣ = k , the objective is
Φ S ( z ) : = max { max j ∈ S f j ( z ) , max j ∉ S U j } . \Phi_S(z):=\max\left\{\max_{j\in S} f_j(z),\max_{j\notin S} U_j\right\}. Φ S ( z ) := max { j ∈ S max f j ( z ) , j ∈ / S max U j } .
A dimension outside S S S keeps its single-line error U j U_j U j , so the dimensions with the largest U j U_j U j should be the ones allowed to change slope. We verify this as follows. Let S ⋆ S^\star S ⋆ be the set of the k k k dimensions with the largest single-line errors U j U_j U j , with arbitrary tie-breaking. This set is independent of z z z . We claim that Φ S ⋆ ( z ) ≤ Φ S ( z ) \Phi_{S^\star}(z)\leq\Phi_S(z) Φ S ⋆ ( z ) ≤ Φ S ( z ) for every z z z and every S S S of size k k k . If S ≠ S ⋆ S\ne S^\star S = S ⋆ , choose j ∈ S ⋆ ∖ S j\in S^\star\setminus S j ∈ S ⋆ ∖ S and j ′ ∈ S ∖ S ⋆ j'\in S\setminus S^\star j ′ ∈ S ∖ S ⋆ . Then U j ≥ U j ′ U_j\geq U_{j'} U j ≥ U j ′ . Swapping j j j and j ′ j' j ′ removes U j U_j U j and f j ′ ( z ) f_{j'}(z) f j ′ ( z ) from the maximum and adds f j ( z ) ≤ U j f_j(z)\leq U_j f j ( z ) ≤ U j and U j ′ ≤ U j U_{j'}\leq U_j U j ′ ≤ U j . Thus the maximum cannot increase. Repeated swaps yield S ⋆ S^\star S ⋆ , proving the claim. Setting M : = max j ∉ S ⋆ U j M:=\max_{j\notin S^\star}U_j M := max j ∈ / S ⋆ U j , the problem becomes min z ∈ [ x i ⋆ , x i ⋆ + 1 ] max { max j ∈ S ⋆ f j ( z ) , M } \min_{z\in[x_{i^\star},x_{i^\star+1}]}\max\left\{\max_{j\in S^\star}f_j(z),M\right\} min z ∈ [ x i ⋆ , x i ⋆ + 1 ] max { max j ∈ S ⋆ f j ( z ) , M } , which is the dense problem on S ⋆ S^\star S ⋆ , followed by a maximum with the constant M M M .
Step 6: candidates and exact comparison. Steps 4 and 5 reduce the search to finitely many candidates, namely cell endpoints, stationary points, and crossings. These are algebraic numbers of low degree (see Definition 1), so we evaluate the objective at each and compare the values exactly. Given an optimal breakpoint z ⋆ z^\star z ⋆ , solving the fitting problems of Step 2 at z ⋆ z^\star z ⋆ recovers ( α ⋆ , β ⋆ , δ ⋆ ) (\alpha^\star,\beta^\star,\delta^\star) ( α ⋆ , β ⋆ , δ ⋆ ) .
Complexity. Each f j ( ⋅ ) f_j(\cdot) f j ( ⋅ ) has one piece for p = 2 p=2 p = 2 and O ( T 8 ) O(T^8) O ( T 8 ) pieces for p ∈ { 1 , ∞ } p\in\{1,\infty\} p ∈ { 1 , ∞ } . Merging the endpoints of all pieces, and refining by pairwise crossings where needed, gives polynomially many cells. The bounds in Table 1 multiply the number of cells by the cost per cell and by the T − 3 T-3 T − 3 intervals of Step 1.
Detailed proofs are presented in § 3 for the dense case and § 4 for the sparse case.
Polynomial-Time Solvability: Dense Setting
This section and the next carry out Steps 3 to 6 of § 2.2 , with the notation introduced there. Throughout, we fix i ⋆ ∈ { 2 , … , T − 2 } i^\star\in\{2,\ldots,T-2\} i ⋆ ∈ { 2 , … , T − 2 } and write I : = [ x i ⋆ , x i ⋆ + 1 ] \mathcal{I}:=[x_{i^\star},x_{i^\star+1}] I := [ x i ⋆ , x i ⋆ + 1 ] . By Step 1, the algorithm is run once for each of the T − 3 T-3 T − 3 values of i ⋆ i^\star i ⋆ , and the best of the resulting solutions is returned. Hence, all operation counts below are per interval, and they are multiplied by T T T in Table 1 . For i ∈ [ T ] i\in[T] i ∈ [ T ] and z ∈ R z\in\mathbb{R} z ∈ R , let a i ( z ) : = ( 1 , x i , h i ( z ) ) ⊤ a_i(z):=(1,x_i,h_i(z))^\top a i ( z ) := ( 1 , x i , h i ( z ) ) ⊤ , and for θ j = ( α j , β j , δ j ) ⊤ \theta_j=(\alpha_j,\beta_j,\delta_j)^\top θ j = ( α j , β j , δ j ) ⊤ let r i ( θ j , z ) : = y i i − a i ( z ) ⊤ θ j r^i(\theta_j,z):=y_i^i-a_i(z)^\top\theta_j r i ( θ j , z ) := y i i − a i ( z ) ⊤ θ j be the residual of Step 1. For a linear-fractional of the form ( a + b z ) / ( c + d z ) (a+bz)/(c+dz) ( a + b z ) / ( c + d z ) with ( c , d ) ≠ ( 0 , 0 ) (c,d)\ne(0,0) ( c , d ) = ( 0 , 0 ) , its derivative is ( b c − a d ) / ( c + d z ) 2 (bc-ad)/(c+dz)^2 ( b c − a d ) / ( c + d z ) 2 , whose sign is that of the constant b c − a d bc-ad b c − a d wherever c + d z ≠ 0 c+dz\ne0 c + d z = 0 . Hence it is strictly increasing, strictly decreasing, or constant on every interval on which c + d z ≠ 0 c+dz\ne0 c + d z = 0 .
Preliminaries
Lemma 1. Fix j ∈ [ J ] j\in[J] j ∈ [ J ] and p ∈ { 1 , 2 , ∞ } p\in\{1,2,\infty\} p ∈ { 1 , 2 , ∞ } .
(a) For every z ∈ R z\in\mathbb{R} z ∈ R , the vectors 1 \mathbf{1} 1 , x x x , and h ( z ) : = ( h i ( z ) ) i ∈ [ T ] h(z):=(h_i(z))_{i\in[T]} h ( z ) := ( h i ( z ) ) i ∈ [ T ] are linearly independent. Equivalently, the vectors a i ( z ) a_i(z) a i ( z ) , i ∈ [ T ] i\in[T] i ∈ [ T ] , span R 3 \mathbb{R}^3 R 3 .
(b) For every z ∈ I z\in\mathcal{I} z ∈ I , the minimum defining f j ( z ) f_j(z) f j ( z ) is attained, and f j f_j f j is continuous on I \mathcal{I} I .
Proof. (a) Let λ 1 1 + λ 2 x + λ 3 h ( z ) = 0 \lambda_1\mathbf{1}+\lambda_2x+\lambda_3h(z)=0 λ 1 1 + λ 2 x + λ 3 h ( z ) = 0 . Since i ⋆ ≥ 2 i^\star\geq2 i ⋆ ≥ 2 and h 1 ( z ) = h 2 ( z ) = 0 h_1(z)=h_2(z)=0 h 1 ( z ) = h 2 ( z ) = 0 , we have λ 1 + λ 2 x i = 0 \lambda_1+\lambda_2x_i=0 λ 1 + λ 2 x i = 0 for i ∈ { 1 , 2 } i\in\{1,2\} i ∈ { 1 , 2 } , and x 1 ≠ x 2 x_1\ne x_2 x 1 = x 2 gives λ 1 = λ 2 = 0 \lambda_1=\lambda_2=0 λ 1 = λ 2 = 0 . Since i ⋆ ≤ T − 2 i^\star\leq T-2 i ⋆ ≤ T − 2 , we have h i ( z ) = x i − z h_i(z)=x_i-z h i ( z ) = x i − z for i ∈ { T − 1 , T } i\in\{T-1,T\} i ∈ { T − 1 , T } , and these cannot vanish, so h ( z ) ≠ 0 h(z)\ne0 h ( z ) = 0 and λ 3 = 0 \lambda_3=0 λ 3 = 0 . (b) Let ℓ j ( θ , z ) \ell_j(\theta,z) ℓ j ( θ , z ) denote the loss of dimension j j j , that is, ∑ i ∣ r i j ∣ \sum_i |r_i^j| ∑ i ∣ r i j ∣ , ∑ i ( r i j ) 2 \sum_i (r_i^j)^2 ∑ i ( r i j ) 2 , or max i ∣ r i j ∣ \max_i |r_i^j| max i ∣ r i j ∣ . We remind the reader that U j = min α j , β j L p ( ( y i j − α j − β j x i ) i ∈ [ T ] ) U_j=\min_{\alpha_j,\beta_j} L_p((y_i^j-\alpha_j-\beta_jx_i)_{i\in[T]}) U j = min α j , β j L p (( y i j − α j − β j x i ) i ∈ [ T ] ) is the error of the best single line, so f j ( z ) ≤ U j f_j(z)\le U_j f j ( z ) ≤ U j for every z z z . Let ρ : = U j + 1 \rho:=U_j+1 ρ := U j + 1 for p ∈ { 1 , ∞ } p\in\{1,\infty\} p ∈ { 1 , ∞ } and ρ : = U j + 1 \rho:=\sqrt{U_j}+1 ρ := U j + 1 for p = 2 p=2 p = 2 . Let
Θ : = { θ ∈ R 3 : ℓ j ( θ , z ) ≤ U j + 1 for some z ∈ I } . \Theta:=\{\theta\in\mathbb{R}^3:\ell_j(\theta,z)\le U_j+1\text{ for some }z\in\mathcal{I}\}. Θ := { θ ∈ R 3 : ℓ j ( θ , z ) ≤ U j + 1 for some z ∈ I } .
which does not depend on z z z . Let θ ∈ Θ \theta\in\Theta θ ∈ Θ , and let z ∈ I z\in\mathcal{I} z ∈ I satisfy ℓ j ( θ , z ) ≤ U j + 1 \ell_j(\theta,z)\le U_j+1 ℓ j ( θ , z ) ≤ U j + 1 . Then ∣ r i j ( θ , z ) ∣ ≤ ρ |r_i^j(\theta,z)|\le\rho ∣ r i j ( θ , z ) ∣ ≤ ρ for every i i i . Using h 1 ( z ) = h 2 ( z ) = 0 h_1(z)=h_2(z)=0 h 1 ( z ) = h 2 ( z ) = 0 , h i ( z ) = x i − z h_i(z)=x_i-z h i ( z ) = x i − z for i ∈ { T − 1 , T } i\in\{T-1,T\} i ∈ { T − 1 , T } , and
r 1 j − r 2 j = y 1 j − y 2 j − β ( x 1 − x 2 ) , r T j − r T − 1 j = y T j − y T − 1 j − ( β + δ ) ( x T − x T − 1 ) , r_1^j-r_2^j=y_1^j-y_2^j-\beta(x_1-x_2),\qquad r_T^j-r_{T-1}^j=y_T^j-y_{T-1}^j-(\beta+\delta)(x_T-x_{T-1}), r 1 j − r 2 j = y 1 j − y 2 j − β ( x 1 − x 2 ) , r T j − r T − 1 j = y T j − y T − 1 j − ( β + δ ) ( x T − x T − 1 ) ,
we obtain ∣ β ∣ ≤ ( ∣ y 1 j − y 2 j ∣ + 2 ρ ) / ( x 2 − x 1 ) |\beta|\le(|y_1^j-y_2^j|+2\rho)/(x_2-x_1) ∣ β ∣ ≤ ( ∣ y 1 j − y 2 j ∣ + 2 ρ ) / ( x 2 − x 1 ) and ∣ β + δ ∣ ≤ ( ∣ y T j − y T − 1 j ∣ + 2 ρ ) / ( x T − x T − 1 ) |\beta+\delta|\le(|y_T^j-y_{T-1}^j|+2\rho)/(x_T-x_{T-1}) ∣ β + δ ∣ ≤ ( ∣ y T j − y T − 1 j ∣ + 2 ρ ) / ( x T − x T − 1 ) . Since α = y 1 j − β x 1 − r 1 j \alpha=y_1^j-\beta x_1-r_1^j α = y 1 j − β x 1 − r 1 j , we have ∣ α ∣ ≤ ∣ y 1 j ∣ + ∣ β ∣ ∣ x 1 ∣ + ρ |\alpha|\le|y_1^j|+|\beta||x_1|+\rho ∣ α ∣ ≤ ∣ y 1 j ∣ + ∣ β ∣∣ x 1 ∣ + ρ . Hence Θ \Theta Θ is bounded, and its closure Θ ‾ \overline{\Theta} Θ is compact.
Fix z ∈ I z\in\mathcal{I} z ∈ I . We show that the minimum defining f j ( z ) f_j(z) f j ( z ) is attained. By definition, f j ( z ) = inf θ ∈ R 3 ℓ j ( θ , z ) f_j(z)=\inf_{\theta\in\mathbb{R}^3}\ell_j(\theta,z) f j ( z ) = inf θ ∈ R 3 ℓ j ( θ , z ) , and f j ( z ) ≤ U j < U j + 1 f_j(z)\le U_j<U_j+1 f j ( z ) ≤ U j < U j + 1 . If θ ∉ Θ \theta\notin\Theta θ ∈ / Θ , then, by the definition of Θ \Theta Θ , ℓ j ( θ , z ′ ) > U j + 1 \ell_j(\theta,z')>U_j+1 ℓ j ( θ , z ′ ) > U j + 1 for every z ′ ∈ I z'\in\mathcal{I} z ′ ∈ I , and in particular ℓ j ( θ , z ) > U j + 1 > f j ( z ) \ell_j(\theta,z)>U_j+1>f_j(z) ℓ j ( θ , z ) > U j + 1 > f j ( z ) . Hence the points outside Θ \Theta Θ do not affect the infimum, and f j ( z ) = inf θ ∈ Θ ℓ j ( θ , z ) f_j(z)=\inf_{\theta\in\Theta}\ell_j(\theta,z) f j ( z ) = inf θ ∈ Θ ℓ j ( θ , z ) . Moreover, Θ ⊆ Θ ‾ ⊆ R 3 \Theta\subseteq\overline{\Theta}\subseteq\mathbb{R}^3 Θ ⊆ Θ ⊆ R 3 gives
f j ( z ) = inf θ ∈ R 3 ℓ j ( θ , z ) ≤ inf θ ∈ Θ ‾ ℓ j ( θ , z ) ≤ inf θ ∈ Θ ℓ j ( θ , z ) = f j ( z ) , f_j(z)=\inf_{\theta\in\mathbb{R}^3}\ell_j(\theta,z)\le\inf_{\theta\in\overline{\Theta}}\ell_j(\theta,z)\le\inf_{\theta\in\Theta}\ell_j(\theta,z)=f_j(z), f j ( z ) = θ ∈ R 3 inf ℓ j ( θ , z ) ≤ θ ∈ Θ inf ℓ j ( θ , z ) ≤ θ ∈ Θ inf ℓ j ( θ , z ) = f j ( z ) ,
so f j ( z ) = inf θ ∈ Θ ‾ ℓ j ( θ , z ) f_j(z)=\inf_{\theta\in\overline{\Theta}}\ell_j(\theta,z) f j ( z ) = inf θ ∈ Θ ℓ j ( θ , z ) . Each residual r i j ( θ , z ) = y i j − α − β x i − δ h i ( z ) r_i^j(\theta,z)=y_i^j-\alpha-\beta x_i-\delta h_i(z) r i j ( θ , z ) = y i j − α − β x i − δ h i ( z ) is continuous in ( θ , z ) (\theta,z) ( θ , z ) . Since ℓ j \ell_j ℓ j is a sum of absolute values (p = 1 p=1 p = 1 ), a sum of squares (p = 2 p=2 p = 2 ), or a maximum of absolute values (p = ∞ p=\infty p = ∞ ) of these residuals, ℓ j \ell_j ℓ j is continuous on R 3 × I \mathbb{R}^3\times\mathcal{I} R 3 × I . In particular, ℓ j ( ⋅ , z ) \ell_j(\cdot,z) ℓ j ( ⋅ , z ) is continuous, and since Θ ‾ \overline{\Theta} Θ is compact and nonempty, the infimum is attained, that is, f j ( z ) = min θ ∈ Θ ‾ ℓ j ( θ , z ) f_j(z)=\min_{\theta\in\overline{\Theta}}\ell_j(\theta,z) f j ( z ) = min θ ∈ Θ ℓ j ( θ , z ) . As ℓ j \ell_j ℓ j is continuous on the compact set Θ ‾ × I \overline{\Theta}\times\mathcal{I} Θ × I , f j ( ⋅ ) f_j(\cdot) f j ( ⋅ ) is continuous on I \mathcal{I} I , by Berge’s maximum theorem [8 ] (Chapter VI, Section 3).
For p ∈ { 1 , ∞ } p\in\{1,\infty\} p ∈ { 1 , ∞ } , f j f_j f j is the pointwise minimum of finitely many linear-fractional functions, each available on a part of I \mathcal{I} I . The next lemma turns such a minimum into a piecewise linear-fractional function. It is also used to aggregate the dimensions for p = ∞ p=\infty p = ∞ .
Lemma 2. Let C = [ l , u ] C=[l,u] C = [ l , u ] with l < u l<u l < u , where l l l and u u u are rational or roots of quadratic polynomials with rational coefficients. For k ∈ [ m ] k\in[m] k ∈ [ m ] , let φ k = ( a k + b k z ) / ( c k + d k z ) \varphi_k=(a_k+b_kz)/(c_k+d_kz) φ k = ( a k + b k z ) / ( c k + d k z ) have rational coefficients. Let V k ⊆ C V_k\subseteq C V k ⊆ C be the set of points at which φ k \varphi_k φ k takes part in the minimum below. Assume the following.
Each V k V_k V k is a union of at most r r r intervals. Each interval may be open, closed, half-open, or a single point.
Each endpoint of these intervals is rational, equal to l l l or u u u , or a root of a quadratic polynomial with rational coefficients.
For every k k k , c k + d k z ≠ 0 c_k+d_kz\ne0 c k + d k z = 0 for all z ∈ V k z\in V_k z ∈ V k .
V 1 ∪ ⋯ ∪ V m = C V_1\cup\cdots\cup V_m=C V 1 ∪ ⋯ ∪ V m = C , and φ ( z ) : = min k ∈ [ m ] : z ∈ V k φ k ( z ) \varphi(z):=\min_{k\in[m]:\,z\in V_k}\varphi_k(z) φ ( z ) := min k ∈ [ m ] : z ∈ V k φ k ( z ) is continuous on C C C .
Then there exist points l = ζ 0 < ζ 1 < ⋯ < ζ P = u l=\zeta_0<\zeta_1<\cdots<\zeta_P=u l = ζ 0 < ζ 1 < ⋯ < ζ P = u with P ≤ 2 m r + m 2 P\le2mr+m^2 P ≤ 2 m r + m 2 , and linear-fractional functions ψ 1 , … , ψ P \psi_1,\ldots,\psi_P ψ 1 , … , ψ P with rational coefficients, with the following properties. For every ℓ ∈ [ P ] \ell\in[P] ℓ ∈ [ P ] , the denominator of ψ ℓ \psi_\ell ψ ℓ has no zero in [ ζ ℓ − 1 , ζ ℓ ] [\zeta_{\ell-1},\zeta_\ell] [ ζ ℓ − 1 , ζ ℓ ] , and φ = ψ ℓ \varphi=\psi_\ell φ = ψ ℓ on [ ζ ℓ − 1 , ζ ℓ ] [\zeta_{\ell-1},\zeta_\ell] [ ζ ℓ − 1 , ζ ℓ ] . Each ζ ℓ \zeta_\ell ζ ℓ is l l l , u u u , an endpoint of an interval of some V k V_k V k , or a root of a nonzero polynomial of degree at most two with
rational coefficients. Given the φ k \varphi_k φ k and the endpoints of the intervals of the V k V_k V k , the points ζ ℓ \zeta_\ell ζ ℓ and the functions ψ ℓ \psi_\ell ψ ℓ are computed with O ( ( m 2 + m r ) log ( m + r ) ) O((m^2+mr)\log(m+r)) O (( m 2 + m r ) log ( m + r )) operations. The same holds with the minimum replaced by the maximum.
Proof. For k ≠ k ′ k \ne k' k = k ′ , let π k k ′ : = ( a k + b k z ) ( c k ′ + d k ′ z ) − ( a k ′ + b k ′ z ) ( c k + d k z ) \pi_{kk'} := (a_k+b_kz)(c_{k'}+d_{k'}z)-(a_{k'}+b_{k'}z)(c_k+d_kz) π k k ′ := ( a k + b k z ) ( c k ′ + d k ′ z ) − ( a k ′ + b k ′ z ) ( c k + d k z ) , a polynomial of degree at most two. Wherever both functions are defined, we have
φ k ( z ) − φ k ′ ( z ) = π k k ′ ( z ) ( c k + d k z ) ( c k ′ + d k ′ z ) . \varphi_k(z)-\varphi_{k'}(z)=\frac{\pi_{kk'}(z)}{(c_k+d_kz)(c_{k'}+d_{k'}z)}. φ k ( z ) − φ k ′ ( z ) = ( c k + d k z ) ( c k ′ + d k ′ z ) π k k ′ ( z ) .
Let E E E be the set of points of ( l , u ) (l,u) ( l , u ) that are endpoints of the intervals forming the sets V k V_k V k , or roots of a polynomial π k k ′ ≢ 0 \pi_{kk'} \not\equiv0 π k k ′ ≡ 0 . Then ∣ E ∣ ≤ 2 m r + m ( m − 1 ) |E| \le2mr+m(m-1) ∣ E ∣ ≤ 2 m r + m ( m − 1 ) . Let ζ 0 < ⋯ < ζ P \zeta_0 < \cdots< \zeta_P ζ 0 < ⋯ < ζ P be the points of E ∪ { l , u } E \cup\{l,u\} E ∪ { l , u } , where points that coincide are listed once, which is detected by exact comparisons as in Remark 1 , so that P ≤ ∣ E ∣ + 1 ≤ 2 m r + m 2 P \le|E|+1 \le2mr+m^2 P ≤ ∣ E ∣ + 1 ≤ 2 m r + m 2 , and consider an open cell C ℓ : = ( ζ ℓ − 1 , ζ ℓ ) C_\ell:= (\zeta_{\ell-1},\zeta_\ell) C ℓ := ( ζ ℓ − 1 , ζ ℓ ) . No endpoint of an interval of V k V_k V k lies in C ℓ C_\ell C ℓ , so either C ℓ ⊆ V k C_\ell\subseteq V_k C ℓ ⊆ V k or C ℓ ∩ V k = ∅ C_\ell\cap V_k=\varnothing C ℓ ∩ V k = ∅ . Let A ℓ : = { k : C ℓ ⊆ V k } A_\ell:= \{k:C_\ell\subseteq V_k\} A ℓ := { k : C ℓ ⊆ V k } . Since V 1 ∪ ⋯ ∪ V m = C V_1 \cup\cdots\cup V_m=C V 1 ∪ ⋯ ∪ V m = C , the set A ℓ A_\ell A ℓ is nonempty.
Let k , k ′ ∈ A ℓ k,k' \in A_\ell k , k ′ ∈ A ℓ . Then C ℓ ⊆ V k ∩ V k ′ C_\ell\subseteq V_k \cap V_{k'} C ℓ ⊆ V k ∩ V k ′ , so both denominators have no zero in C ℓ C_\ell C ℓ by the assumption on V k V_k V k and V k ′ V_{k'} V k ′ . If π k k ′ ≡ 0 \pi_{kk'} \equiv0 π k k ′ ≡ 0 , then φ k = φ k ′ \varphi_k=\varphi_{k'} φ k = φ k ′ on C ℓ C_\ell C ℓ . Otherwise, π k k ′ \pi_{kk'} π k k ′ has no zero in C ℓ C_\ell C ℓ , since all its roots in ( l , u ) (l,u) ( l , u ) belong to E E E . Hence φ k − φ k ′ \varphi_k-\varphi_{k'} φ k − φ k ′ is continuous and nonzero on C ℓ C_\ell C ℓ , and by the intermediate value theorem it has a constant nonzero sign on C ℓ C_\ell C ℓ . Order A ℓ A_\ell A ℓ by k ≺ k ′ k \prec k' k ≺ k ′ if φ k < φ k ′ \varphi_k<\varphi_{k'} φ k < φ k ′ on C ℓ C_\ell C ℓ , or if φ k = φ k ′ \varphi_k=\varphi_{k'} φ k = φ k ′ on C ℓ C_\ell C ℓ and k < k ′ k<k' k < k ′ . This order does not depend on z ∈ C ℓ z\in C_\ell z ∈ C ℓ , so its first element k ℓ k_\ell k ℓ satisfies φ = φ k ℓ \varphi=\varphi_{k_\ell} φ = φ k ℓ on C ℓ C_\ell C ℓ .
We now extend the formula φ = φ k ℓ \varphi=\varphi_{k_\ell} φ = φ k ℓ from C ℓ C_\ell C ℓ to its closure [ ζ ℓ − 1 , ζ ℓ ] [\zeta_{\ell-1},\zeta_\ell] [ ζ ℓ − 1 , ζ ℓ ] . If b k ℓ c k ℓ = a k ℓ d k ℓ b_{k_\ell}c_{k_\ell}=a_{k_\ell}d_{k_\ell} b k ℓ c k ℓ = a k ℓ d k ℓ , then ( a k ℓ , b k ℓ ) (a_{k_\ell},b_{k_\ell}) ( a k ℓ , b k ℓ ) is a multiple of ( c k ℓ , d k ℓ ) (c_{k_\ell},d_{k_\ell}) ( c k ℓ , d k ℓ ) , so φ k ℓ \varphi_{k_\ell} φ k ℓ is a rational constant on its domain, and we let ψ ℓ \psi_\ell ψ ℓ be this constant. Otherwise, φ k ℓ \varphi_{k_\ell} φ k ℓ is nonconstant, and we let ψ ℓ : = φ k ℓ \psi_\ell:=\varphi_{k_\ell} ψ ℓ := φ k ℓ . The denominator c k ℓ + d k ℓ z c_{k_\ell}+d_{k_\ell}z c k ℓ + d k ℓ z of ψ ℓ \psi_\ell ψ ℓ has no zero in C ℓ C_\ell C ℓ , since C ℓ ⊆ V k ℓ C_\ell\subseteq V_{k_\ell} C ℓ ⊆ V k ℓ . We show that it has no zero at ζ ℓ − 1 \zeta_{\ell-1} ζ ℓ − 1 or ζ ℓ \zeta_\ell ζ ℓ either. Since φ \varphi φ is continuous on the compact interval [ l , u ] [l,u] [ l , u ] , it is bounded. As ψ ℓ = φ \psi_\ell=\varphi ψ ℓ = φ on C ℓ C_\ell C ℓ , the function ψ ℓ \psi_\ell ψ ℓ is bounded on C ℓ C_\ell C ℓ . A nonconstant linear-fractional function, however, is unbounded near a zero of its denominator. Hence the denominator of ψ ℓ \psi_\ell ψ ℓ does not vanish at ζ ℓ − 1 \zeta_{\ell-1} ζ ℓ − 1 or ζ ℓ \zeta_\ell ζ ℓ . Thus, in both cases, ψ ℓ \psi_\ell ψ ℓ and φ \varphi φ are continuous on [ ζ ℓ − 1 , ζ ℓ ] [\zeta_{\ell-1},\zeta_\ell] [ ζ ℓ − 1 , ζ ℓ ] and agree on C ℓ C_\ell C ℓ , so they agree on [ ζ ℓ − 1 , ζ ℓ ] [\zeta_{\ell-1},\zeta_\ell] [ ζ ℓ − 1 , ζ ℓ ] .
It remains to compute k ℓ k_\ell k ℓ for all ℓ \ell ℓ , and for this we compare neighboring cells. For ℓ ∈ [ P − 1 ] \ell\in[P-1] ℓ ∈ [ P − 1 ] , call an index k k k involved at ζ ℓ \zeta_\ell ζ ℓ if ζ ℓ \zeta_\ell ζ ℓ is an endpoint of an interval of V k V_k V k or a root of π k k ′ ≢ 0 \pi_{kk'}\not\equiv0 π k k ′ ≡ 0 for some k ′ k' k ′ , and let E ζ ℓ E_{\zeta_\ell} E ζ ℓ be the set of these indices. Indices that are not involved at ζ ℓ \zeta_\ell ζ ℓ are unaffected when passing from C ℓ C_\ell C ℓ to C ℓ + 1 C_{\ell+1} C ℓ + 1 . Indeed, let k ∉ E ζ ℓ k\notin E_{\zeta_\ell} k ∈ / E ζ ℓ . Since ζ ℓ \zeta_\ell ζ ℓ is not an endpoint of an interval of V k V_k V k , either ζ ℓ \zeta_\ell ζ ℓ is an interior point of an interval of V k V_k V k , and then k ∈ A ℓ ∩ A ℓ + 1 k\in A_\ell\cap A_{\ell+1} k ∈ A ℓ ∩ A ℓ + 1 and ζ ℓ ∈ V k \zeta_\ell\in V_k ζ ℓ ∈ V k , or k ∉ A ℓ ∪ A ℓ + 1 k\notin A_\ell\cup A_{\ell+1} k ∈ / A ℓ ∪ A ℓ + 1 . If, moreover, k ′ ∉ E ζ ℓ k'\notin E_{\zeta_\ell} k ′ ∈ / E ζ ℓ and k , k ′ ∈ A ℓ k,k'\in A_\ell k , k ′ ∈ A ℓ , then both denominators are nonzero at ζ ℓ ∈ V k ∩ V k ′ \zeta_\ell\in V_k\cap V_{k'} ζ ℓ ∈ V k ∩ V k ′ , and either π k k ′ ≡ 0 \pi_{kk'}\equiv0 π k k ′ ≡ 0 or π k k ′ ( ζ ℓ ) ≠ 0 \pi_{kk'}(\zeta_\ell)\ne0 π k k ′ ( ζ ℓ ) = 0 . Hence φ k − φ k ′ \varphi_k-\varphi_{k'} φ k − φ k ′ is identically zero or has the same sign on C ℓ C_\ell C ℓ and C ℓ + 1 C_{\ell+1} C ℓ + 1 , so the relative order of k k k and k ′ k' k ′ is the same on both cells.
This suggests the following sweep. Sort E E E , which takes O ( ∣ E ∣ log ∣ E ∣ ) O(|E|\log|E|) O ( ∣ E ∣ log ∣ E ∣ ) operations, and visit the cells from left to right, keeping the indices of the current set A ℓ A_\ell A ℓ in a balanced binary search tree ordered by ≺ \prec ≺ . When the sweep passes ζ ℓ \zeta_\ell ζ ℓ , delete from the tree the indices of E ζ ℓ E_{\zeta_\ell} E ζ ℓ that it contains, and insert those indices of E ζ ℓ E_{\zeta_\ell} E ζ ℓ that belong to A ℓ + 1 A_{\ell+1} A ℓ + 1 , each at its position on C ℓ + 1 C_{\ell+1} C ℓ + 1 . By the observation above, the tree then contains A ℓ + 1 A_{\ell+1} A ℓ + 1 ordered by ≺ \prec ≺ on C ℓ + 1 C_{\ell+1} C ℓ + 1 , and its first element is k ℓ + 1 k_{\ell+1} k ℓ + 1 . Each comparison of two indices k , k ′ k,k' k , k ′ during an insertion is decided by the index if π k k ′ ≡ 0 \pi_{kk'}\equiv0 π k k ′ ≡ 0 , and otherwise by the signs on C ℓ + 1 C_{\ell+1} C ℓ + 1 of π k k ′ \pi_{kk'} π k k ′ and of the two denominators. Each of these is a nonzero polynomial g g g of degree at most two with no zero in C ℓ + 1 C_{\ell+1} C ℓ + 1 . By the exact Taylor expansion g ( ζ ℓ + t ) = g ( ζ ℓ ) + g ′ ( ζ ℓ ) t + 1 2 g ′ ′ ( ζ ℓ ) t 2 g(\zeta_\ell+t)=g(\zeta_\ell)+g'(\zeta_\ell)t+\frac{1}{2}g''(\zeta_\ell)t^2 g ( ζ ℓ + t ) = g ( ζ ℓ ) + g ′ ( ζ ℓ ) t + 2 1 g ′′ ( ζ ℓ ) t 2 , its sign on C ℓ + 1 C_{\ell+1} C ℓ + 1 is the sign of the first nonzero number among g ( ζ ℓ ) g(\zeta_\ell) g ( ζ ℓ ) , g ′ ( ζ ℓ ) g'(\zeta_\ell) g ′ ( ζ ℓ ) , and g ′ ′ ( ζ ℓ ) g''(\zeta_\ell) g ′′ ( ζ ℓ ) . Each index k k k is involved at no more than the 2 r 2r 2 r endpoints of the intervals of V k V_k V k and the 2 ( m − 1 ) 2(m-1) 2 ( m − 1 ) roots of the polynomials π k k ′ \pi_{kk'} π k k ′ . Hence ∑ ℓ ∣ E ζ ℓ ∣ ≤ 2 m r + 2 m ( m − 1 ) \sum_\ell|E_{\zeta_\ell}|\le2mr+2m(m-1) ∑ ℓ ∣ E ζ ℓ ∣ ≤ 2 m r + 2 m ( m − 1 ) , and the sweep, including the construction of the initial tree for C 1 C_1 C 1 , takes O ( ( m 2 + m r ) log ( m + r ) ) O((m^2+mr)\log(m+r)) O (( m 2 + m r ) log ( m + r )) operations (see [31 ] for the runtime guarantees of balanced binary search tree operations). For the maximum, the same argument applies with the order of the values reversed.
The ℓ 2 \ell_2 ℓ 2 loss
Let A : = [ 1 x ] ∈ Q T × 2 A := [1\ x] \in\mathbb{Q}^{T\times2} A := [ 1 x ] ∈ Q T × 2 and G : = A T A G := A^\mathsf{T}A G := A T A , which is invertible since the x i x_i x i are distinct. Let M : = I T − A G − 1 A T M := I_T-AG^{-1}A^\mathsf{T} M := I T − A G − 1 A T be the orthogonal projector onto the orthogonal complement of the column space of A A A . Write h ( z ) = v − z w h(z)=v-zw h ( z ) = v − z w , where v , w ∈ Q T v,w\in\mathbb{Q}^T v , w ∈ Q T are given by
v i : = { 0 , i ≤ i ∗ , x i , i > i ∗ , w i : = { 0 , i ≤ i ∗ , 1 , i > i ∗ . v_i :=
\begin{cases}
0, & i\leq i^*,\\
x_i, & i>i^*,
\end{cases}
\qquad
w_i :=
\begin{cases}
0, & i\leq i^*,\\
1, & i>i^*.
\end{cases} v i := { 0 , x i , i ≤ i ∗ , i > i ∗ , w i := { 0 , 1 , i ≤ i ∗ , i > i ∗ .
Lemma 3 establishes the structure of f j f_j f j , which completes Step 3 for p = 2 p=2 p = 2 .
Lemma 3. For every j ∈ [ J ] j\in[J] j ∈ [ J ] and z ∈ R z\in\mathbb{R} z ∈ R ,
f j ( z ) = U j − ν j ( z ) 2 D ( z ) , U j = ( y j ) T M y j , f_j(z)=U_j-\frac{\nu_j(z)^2}{D(z)},\qquad U_j=(y^j)^\mathsf{T}My^j, f j ( z ) = U j − D ( z ) ν j ( z ) 2 , U j = ( y j ) T M y j , where
ν j ( z ) : = ( y j ) T M h ( z ) = s j , 0 + s j , 1 z , D ( z ) : = h ( z ) T M h ( z ) = d 0 + d 1 z + d 2 z 2 , \nu_j(z):=(y^j)^\mathsf{T}Mh(z)=s_{j,0}+s_{j,1}z,\qquad D(z):=h(z)^\mathsf{T}Mh(z)=d_0+d_1z+d_2z^2, ν j ( z ) := ( y j ) T M h ( z ) = s j , 0 + s j , 1 z , D ( z ) := h ( z ) T M h ( z ) = d 0 + d 1 z + d 2 z 2 , with s j , 0 : = ( y j ) T M v s_{j,0}:=(y^j)^\mathsf{T}Mv s j , 0 := ( y j ) T M v , s j , 1 : = − ( y j ) T M w s_{j,1}:=-(y^j)^\mathsf{T}Mw s j , 1 := − ( y j ) T M w , d 0 : = v T M v d_0:=v^\mathsf{T}Mv d 0 := v T M v , d 1 : = − 2 v T M w d_1:=-2v^\mathsf{T}Mw d 1 := − 2 v T M w , and d 2 : = w T M w d_2:=w^\mathsf{T}Mw d 2 := w T M w . Moreover, D ( z ) > 0 D(z)>0 D ( z ) > 0 for every z ∈ R z\in\mathbb{R} z ∈ R , and the minimum defining f j ( z ) f_j(z) f j ( z ) is attained at
δ j = ν j ( z ) D ( z ) , ( α j , β j ) T = G − 1 A T ( y j − δ j h ( z ) ) . \delta_j=\frac{\nu_j(z)}{D(z)},\qquad
(\alpha_j,\beta_j)^\mathsf{T}=G^{-1}A^\mathsf{T}(y^j-\delta_jh(z)). δ j = D ( z ) ν j ( z ) , ( α j , β j ) T = G − 1 A T ( y j − δ j h ( z )) .
Proof. For fixed δ j \delta_j δ j , the minimum of ∥ y j − δ j h ( z ) − A ( α j , β j ) T ∥ 2 2 \lVert y^j-\delta_jh(z)-A(\alpha_j,\beta_j)^\mathsf{T}\rVert_2^2 ∥ y j − δ j h ( z ) − A ( α j , β j ) T ∥ 2 2 over ( α j , β j ) (\alpha_j,\beta_j) ( α j , β j ) is attained at G − 1 A T ( y j − δ j h ( z ) ) G^{-1}A^\mathsf{T}(y^j-\delta_jh(z)) G − 1 A T ( y j − δ j h ( z )) , with value ∥ M ( y j − δ j h ( z ) ) ∥ 2 2 \lVert M(y^j-\delta_jh(z))\rVert_2^2 ∥ M ( y j − δ j h ( z )) ∥ 2 2 . Since M M M is symmetric and M 2 = M M^2=M M 2 = M , this value equals U j − 2 δ j ν j ( z ) + δ j 2 D ( z ) U_j-2\delta_j\nu_j(z)+\delta_j^2D(z) U j − 2 δ j ν j ( z ) + δ j 2 D ( z ) , where U j = ( y j ) T M y j U_j=(y^j)^\mathsf{T}My^j U j = ( y j ) T M y j is the value for δ j = 0 \delta_j=0 δ j = 0 (that is, the error of the best single line). By Lemma 1(a), h ( z ) h(z) h ( z ) is not in the column space of A A A , so M h ( z ) ≠ 0 Mh(z)\neq0 M h ( z ) = 0 and D ( z ) = ∥ M h ( z ) ∥ 2 2 > 0 D(z)=\lVert Mh(z)\rVert_2^2>0 D ( z ) = ∥ M h ( z ) ∥ 2 2 > 0 . Minimizing the quadratic U j − 2 δ j ν j ( z ) + δ j 2 D ( z ) U_j-2\delta_j\nu_j(z)+\delta_j^2D(z) U j − 2 δ j ν j ( z ) + δ j 2 D ( z ) in δ j \delta_j δ j gives the claim.
Lemma 4. Let D D D be as in Lemma 3 , a polynomial of degree at most two with D > 0 D>0 D > 0 on R \mathbb{R} R . Let N N N be a polynomial of degree at most two, let c ∈ R c\in\mathbb{R} c ∈ R , and let F : = c − N / D F:=c-N/D F := c − N / D . Then R : = N ′ D − N D ′ R:=N'D-ND' R := N ′ D − N D ′ has degree at most two, and F ′ = − R / D 2 F'=-R/D^2 F ′ = − R / D 2 on R \mathbb{R} R . Consequently, for every interval [ l , u ] [l,u] [ l , u ] , the minimum of F F F over [ l , u ] [l,u] [ l , u ] is attained either at l l l , or at u u u , or, if R ≢ 0 R\not\equiv0 R ≡ 0 , at a root of R R R in ( l , u ) (l,u) ( l , u ) .
Proof. If N = n 0 + n 1 z + n 2 z 2 N=n_0+n_1z+n_2z^2 N = n 0 + n 1 z + n 2 z 2 , the coefficient of z 3 z^3 z 3 is 2 n 2 d 2 2n_2d_2 2 n 2 d 2 in both N ′ D N'D N ′ D and N D ′ ND' N D ′ , so deg R ≤ 2 \deg R\leq2 deg R ≤ 2 . Since D > 0 D>0 D > 0 , F F F is differentiable on R \mathbb{R} R with F ′ = − R / D 2 F'=-R/D^2 F ′ = − R / D 2 . The continuous function F F F attains its minimum over [ l , u ] [l,u] [ l , u ] . At an interior minimizer, F ′ = 0 F'=0 F ′ = 0 , so R = 0 R=0 R = 0 . If R ≡ 0 R\equiv0 R ≡ 0 , then F F F is constant, and l l l is a minimizer.
Aggregation and candidates (Step 4). By Step 2, OPT 2 , J i ∗ = min z ∈ I F ( z ) \operatorname{OPT}_{2,J}^{i^*}=\min_{z\in I}F(z) OPT 2 , J i ∗ = min z ∈ I F ( z ) , where, by Lemma 3,
F ( z ) : = ∑ j ∈ [ J ] f j ( z ) = C − N ( z ) D ( z ) , C : = ∑ j ∈ [ J ] U j , N ( z ) : = ∑ j ∈ [ J ] ν j ( z ) 2 . F(z):=\sum_{j\in[J]}f_j(z)=C-\frac{N(z)}{D(z)},\qquad C:=\sum_{j\in[J]}U_j,\qquad N(z):=\sum_{j\in[J]}\nu_j(z)^2. F ( z ) := j ∈ [ J ] ∑ f j ( z ) = C − D ( z ) N ( z ) , C := j ∈ [ J ] ∑ U j , N ( z ) := j ∈ [ J ] ∑ ν j ( z ) 2 .
The polynomial N = n 0 + n 1 z + n 2 z 2 N=n_0+n_1z+n_2z^2 N = n 0 + n 1 z + n 2 z 2 , with n 0 = ∑ j s j , 0 2 n_0=\sum_j s_{j,0}^2 n 0 = ∑ j s j , 0 2 , n 1 = 2 ∑ j s j , 0 s j , 1 n_1=2\sum_j s_{j,0}s_{j,1} n 1 = 2 ∑ j s j , 0 s j , 1 , and n 2 = ∑ j s j , 1 2 n_2=\sum_j s_{j,1}^2 n 2 = ∑ j s j , 1 2 , has degree at most two irrespective of J J J . By Lemma 4, an optimal breakpoint on I I I lies in the set consisting of x i ∗ x_{i^*} x i ∗ , x i ∗ + 1 x_{i^*+1} x i ∗ + 1 , and at most two roots in ( x i ∗ , x i ∗ + 1 ) (x_{i^*},x_{i^*+1}) ( x i ∗ , x i ∗ + 1 ) of the quadratic R = r 0 + r 1 z + r 2 z 2 R=r_0+r_1z+r_2z^2 R = r 0 + r 1 z + r 2 z 2 with rational coefficients. Hence every candidate lies in Q ( Δ ) \mathbb{Q}(\sqrt{\Delta}) Q ( Δ ) with Δ : = r 1 2 − 4 r 0 r 2 ∈ Q \Delta:=r_1^2-4r_0r_2\in\mathbb{Q} Δ := r 1 2 − 4 r 0 r 2 ∈ Q , and so does its value C − N ( z ) / D ( z ) C-N(z)/D(z) C − N ( z ) / D ( z ) . By Remark 1, the values at the at most four candidates are compared exactly in polynomial time, which yields an optimal breakpoint on I I I .
Remark 2. For J = 1 J=1 J = 1 , this procedure is closely related to the classical approach of [37 ] , which also examines each interval between consecutive observations. For J ≥ 2 J\ge2 J ≥ 2 , the key point is that D D D depends only on the time coordinates, so N N N has degree at most two for every J J J , which is what makes the bound O ( J T ) O(JT) O ( J T ) possible. Sharing the breakpoint does change the arithmetic, however. For J = 1 J=1 J = 1 , we have R = ν 1 ⋅ ( 2 ν 1 ′ D − ν 1 D ′ ) R=\nu_1\cdot(2\nu'_1D-\nu_1D') R = ν 1 ⋅ ( 2 ν 1 ′ D − ν 1 D ′ ) , and 2 ν 1 ′ D − ν 1 D ′ = ( 2 s 1 , 1 d 0 − s 1 , 0 d 1 ) + ( s 1 , 1 d 1 − 2 s 1 , 0 d 2 ) z 2\nu'_1D-\nu_1D'=(2s_{1,1}d_0-s_{1,0}d_1)+(s_{1,1}d_1-2s_{1,0}d_2)z 2 ν 1 ′ D − ν 1 D ′ = ( 2 s 1 , 1 d 0 − s 1 , 0 d 1 ) + ( s 1 , 1 d 1 − 2 s 1 , 0 d 2 ) z is affine. Hence every candidate is rational, and a rational optimal breakpoint exists, whereas for J = 2 J=2 J = 2 the optimal breakpoint can be irrational (§ 2 ).
Recovering the solution. Given an optimal breakpoint z ∗ z^* z ∗ , Lemma 3 gives δ j ∗ = ν j ( z ∗ ) / D ( z ∗ ) \delta_j^*=\nu_j(z^*)/D(z^*) δ j ∗ = ν j ( z ∗ ) / D ( z ∗ ) and ( α j ∗ , β j ∗ ) ⊤ = G − 1 A ⊤ ( y j ∗ − δ j ∗ h ( z ∗ ) ) (\alpha_j^*,\beta_j^*)^\top=G^{-1}A^\top(y_j^*-\delta_j^*h(z^*)) ( α j ∗ , β j ∗ ) ⊤ = G − 1 A ⊤ ( y j ∗ − δ j ∗ h ( z ∗ )) , which lie in Q ( z ∗ ) \mathbb{Q}(z^*) Q ( z ∗ ) . This takes O ( J T ) O(JT) O ( J T ) operations.
Operation count. Hence the coefficients d 0 , d 1 , d 2 d_0,d_1,d_2 d 0 , d 1 , d 2 of D D D , the coefficients s j , 0 , s j , 1 s_{j,0},s_{j,1} s j , 0 , s j , 1 of ν j \nu_j ν j , and U j U_j U j are determined by G G G , the vectors A ⊤ y j = ( ∑ i > i ∗ y i j , ∑ i > i ∗ x i y i j ) A^\top y^j=(\sum_{i>i^*}y_i^j,\sum_{i>i^*}x_i y_i^j) A ⊤ y j = ( ∑ i > i ∗ y i j , ∑ i > i ∗ x i y i j ) , the numbers ∑ i ( y i j ) 2 \sum_i(y_i^j)^2 ∑ i ( y i j ) 2 , and the suffix sums
∑ i > i ∗ x i , ∑ i > i ∗ x i 2 , ∑ i > i ∗ y i j , ∑ i > i ∗ x i y i j , \sum_{i>i^*}x_i,\qquad\sum_{i>i^*}x_i^2,\qquad\sum_{i>i^*}y_i^j,\qquad\sum_{i>i^*}x_i y_i^j, i > i ∗ ∑ x i , i > i ∗ ∑ x i 2 , i > i ∗ ∑ y i j , i > i ∗ ∑ x i y i j ,
together with T − i ∗ T-i^* T − i ∗ , since A ⊤ v = ( ∑ i > i ∗ x i , ∑ i > i ∗ x i 2 ) A^\top v=(\sum_{i>i^*}x_i,\sum_{i>i^*}x_i^2) A ⊤ v = ( ∑ i > i ∗ x i , ∑ i > i ∗ x i 2 ) , A ⊤ w = ( T − i ∗ , ∑ i > i ∗ x i ) A^\top w=(T-i^*,\sum_{i>i^*}x_i) A ⊤ w = ( T − i ∗ , ∑ i > i ∗ x i ) , v ⊤ v = ∑ i > i ∗ x i 2 v^\top v=\sum_{i>i^*}x_i^2 v ⊤ v = ∑ i > i ∗ x i 2 , v ⊤ w = ∑ i > i ∗ x i v^\top w=\sum_{i>i^*}x_i v ⊤ w = ∑ i > i ∗ x i , w ⊤ w = T − i ∗ w^\top w=T-i^* w ⊤ w = T − i ∗ , ( y j ) ⊤ v = ∑ i > i ∗ x i y i j (y^j)^\top v=\sum_{i>i^*}x_i y_i^j ( y j ) ⊤ v = ∑ i > i ∗ x i y i j , and ( y j ) ⊤ w = ∑ i > i ∗ y i j (y^j)^\top w=\sum_{i>i^*}y_i^j ( y j ) ⊤ w = ∑ i > i ∗ y i j . The quantities that do not depend on i ∗ i^* i ∗ are computed once with O ( J T ) O(JT) O ( J T ) operations. The suffix sums are updated from one value of i ∗ i^* i ∗ to the next with O ( J ) O(J) O ( J ) operations, after which D D D , the s j , 0 , s j , 1 s_{j,0},s_{j,1} s j , 0 , s j , 1 , N N N , and R R R are formed with O ( J ) O(J) O ( J ) operations. Each interval then requires one quadratic root computation and a constant number of comparisons. Over all intervals, and with the recovery step, this gives O ( J T ) O(JT) O ( J T ) operations.
The loss
Fix j j j and we drop the superscript j j j for simplicity. For z ∈ I z\in I z ∈ I , f ( z ) f(z) f ( z ) is the optimal value of the linear program
min θ ∈ R 3 , η ∈ R { η : σ ( y i − a i ( z ) ⊤ θ ) ≤ η for all ( i , σ ) ∈ [ T ] × { − 1 , 1 } } (3) \min_{\theta\in\mathbb{R}^3,\ \eta\in\mathbb{R}}\left\{\eta:\sigma(y_i-a_i(z)^\top\theta)\le\eta\ \text{ for all }(i,\sigma)\in[T]\times\{-1,1\}\right\} \tag*{(3)} θ ∈ R 3 , η ∈ R min { η : σ ( y i − a i ( z ) ⊤ θ ) ≤ η for all ( i , σ ) ∈ [ T ] × { − 1 , 1 } } (3)
Call a set B ⊆ [ T ] × { − 1 , 1 } B\subseteq[T]\times\{-1,1\} B ⊆ [ T ] × { − 1 , 1 } with ∣ B ∣ = 4 |B|=4 ∣ B ∣ = 4 a basis, and let K B ( z ) ∈ R 4 × 4 K_B(z)\in\mathbb{R}^{4\times4} K B ( z ) ∈ R 4 × 4 be the matrix with rows ( a i ( z ) ⊤ , σ ) (a_i(z)^\top,\sigma) ( a i ( z ) ⊤ , σ ) for ( i , σ ) ∈ B (i,\sigma)\in B ( i , σ ) ∈ B . The constraint ( i , σ ) (i,\sigma) ( i , σ ) holds with equality if and only if a i ( z ) ⊤ θ + σ η = y i a_i(z)^\top\theta+\sigma\eta=y_i a i ( z ) ⊤ θ + σ η = y i .
Lemma 5. (a) For every basis B B B , det K B ( z ) \det K_B(z) det K B ( z ) is an affine function of z z z . If det K B ≠ 0 \det K_B\ne0 det K B = 0 , let ( θ B ( z ) , η B ( z ) ) (\theta_B(z),\eta_B(z)) ( θ B ( z ) , η B ( z )) be the solution of a i ( z ) ⊤ θ + σ η = y i a_i(z)^\top\theta+\sigma\eta=y_i a i ( z ) ⊤ θ + σ η = y i , ( i , σ ) ∈ B (i,\sigma)\in B ( i , σ ) ∈ B . Then η B \eta_B η B is linear-fractional with rational coefficients and denominator det K B \det K_B det K B , and, for every ( i , σ ) (i,\sigma) ( i , σ ) , the slack η B ( z ) − σ r i ( θ B ( z ) , z ) \eta_B(z)-\sigma r_i(\theta_B(z),z) η B ( z ) − σ r i ( θ B ( z ) , z ) is an affine function with rational coefficients divided by det K B ( z ) \det K_B(z) det K B ( z ) .
(b) For each basis B B B with det K B ≢ 0 \det K_B \not\equiv0 det K B ≡ 0 , let
V B : = { t ∈ I : det K B ( t ) ≠ 0 and all 2 T slacks of ( θ B ( t ) , η B ( t ) ) are nonnegative } , V_B := \{t \in\mathcal{I}: \det K_B(t) \ne0 \text{ and all } 2T \text{ slacks of }(\theta_B(t),\eta_B(t))\text{ are nonnegative}\}, V B := { t ∈ I : det K B ( t ) = 0 and all 2 T slacks of ( θ B ( t ) , η B ( t )) are nonnegative } ,
the set of breakpoints at which B B B defines a feasible vertex of (3) . Each V B V_B V B is a union of at most 4 T + 5 4T+5 4 T + 5 intervals with rational endpoints. Moreover, for every fixed z ∈ I z \in\mathcal{I} z ∈ I ,
f ( z ) = min { η B ( z ) : B a basis with z ∈ V B } . f(z)=\min\{\eta_B(z): B\text{ a basis with }z\in V_B\}. f ( z ) = min { η B ( z ) : B a basis with z ∈ V B } .
Proof. (a) Only the third column of K B ( z ) K_B(z) K B ( z ) depends on z z z , and its entries h i ( z ) h_i(z) h i ( z ) are affine in z z z . Expanding along this column shows that det K B ( z ) \det K_B(z) det K B ( z ) is affine in z z z . By Cramer’s rule, each entry of ( θ B ( z ) , η B ( z ) ) (\theta_B(z),\eta_B(z)) ( θ B ( z ) , η B ( z )) is a determinant divided by det K B ( z ) \det K_B(z) det K B ( z ) . For δ B \delta_B δ B , the third column is replaced by the right-hand side, so the numerator is a rational constant κ \kappa κ . For α B \alpha_B α B , β B \beta_B β B , and η B \eta_B η B , the numerator still contains the third column, so it is affine. Hence η B \eta_B η B is linear-fractional. Moreover, δ B ( z ) h i ( z ) = κ h i ( z ) / det K B ( z ) \delta_B(z)h_i(z)=\kappa h_i(z)/\det K_B(z) δ B ( z ) h i ( z ) = κ h i ( z ) / det K B ( z ) , so every residual r i ( θ B ( z ) , z ) = y i − α B ( z ) − β B ( z ) x i − δ B ( z ) h i ( z ) r_i(\theta_B(z),z)=y_i-\alpha_B(z)-\beta_B(z)x_i-\delta_B(z)h_i(z) r i ( θ B ( z ) , z ) = y i − α B ( z ) − β B ( z ) x i − δ B ( z ) h i ( z ) , and therefore every slack, is an affine function divided by det K B ( z ) \det K_B(z) det K B ( z ) .
(b) By Lemma 1(a), the vectors a i ( z ) a_i(z) a i ( z ) span R 3 \mathbb{R}^3 R 3 . Since the rows ( a i ( z ) ⊤ , 1 ) (a_i(z)^\top,1) ( a i ( z ) ⊤ , 1 ) and ( − a i ( z ) ⊤ , 1 ) (-a_i(z)^\top,1) ( − a i ( z ) ⊤ , 1 ) of the constraints of (3) add up to ( 0 , 0 , 0 , 2 ) (0,0,0,2) ( 0 , 0 , 0 , 2 ) , the constraint matrix has rank four. Hence the feasible region contains no line, that is it is pointed. As (3) is feasible and objective bounded below by 0, it has an optimal vertex [53 ] . A vertex is the unique solution of four linearly independent active constraints. Thus it equals ( θ B ( z ) , η B ( z ) ) (\theta_B(z),\eta_B(z)) ( θ B ( z ) , η B ( z )) for a basis B B B with det K B ( z ) ≠ 0 \det K_B(z)\ne0 det K B ( z ) = 0 , and then z ∈ V B z\in V_B z ∈ V B . Conversely, for z ∈ V B z\in V_B z ∈ V B , the point ( θ B ( z ) , η B ( z ) ) (\theta_B(z),\eta_B(z)) ( θ B ( z ) , η B ( z )) is feasible, so η B ( z ) ≥ f ( z ) \eta_B(z)\ge f(z) η B ( z ) ≥ f ( z ) .
By (a), det K B \det K_B det K B is an affine function with rational coefficients, and it is not identically zero, so it has at most one zero, which is rational. Also by (a), each of the 2 T 2T 2 T slacks has the form n ( t ) / det K B ( t ) n(t)/\det K_B(t) n ( t ) / det K B ( t ) , where n n n is an affine function with rational coefficients. If n ≢ 0 n\not\equiv0 n ≡ 0 , then n n n has at most one zero, which is rational. If n ≡ 0 n\equiv0 n ≡ 0 , the slack is zero wherever it is defined and never changes sign. Hence the points at which det K B \det K_B det K B or some slack numerator vanishes are at most 2 T + 1 2T+1 2 T + 1 rational points. They split I \mathcal{I} I into at most 2 T + 2 2T+2 2 T + 2 open intervals, on each of which all signs are constant, and at most 2 T + 3 2T+3 2 T + 3 remaining points, namely these zeros and the two endpoints of I \mathcal{I} I . Hence V B V_B V B is a union of at most ( 2 T + 2 ) + ( 2 T + 3 ) = 4 T + 5 (2T+2)+(2T+3)=4T+5 ( 2 T + 2 ) + ( 2 T + 3 ) = 4 T + 5 intervals, some of which may be single points.
Structure of f j f_j f j (Step 3). We discard the bases with det K B ≡ 0 \det K_B\equiv0 det K B ≡ 0 . We apply Lemma 2 on [ l , u ] = I [l,u]=\mathcal{I} [ l , u ] = I , whose endpoints are rational, to the functions η B \eta_B η B on the sets V B V_B V B , with m ≤ ( 2 T 4 ) = O ( T 4 ) m\leq\binom{2T}{4}=O(T^4) m ≤ ( 4 2 T ) = O ( T 4 ) and r ≤ 4 T + 5 r\leq4T+5 r ≤ 4 T + 5 . Its hypotheses hold for the following reasons. By Lemma 5(a), each η B \eta_B η B is linear-fractional with rational coefficients and denominator det K B \det K_B det K B , which is nonzero on V B V_B V B by the definition of V B V_B V B . By Lemma 5(b), each V B V_B V B is a union of at most 4 T + 5 4T+5 4 T + 5 intervals with rational endpoints, the sets V B V_B V B cover I \mathcal{I} I , and f j ( z ) = min B : z ∈ V B η B ( z ) f_j(z)=\min_{B:z\in V_B}\eta_B(z) f j ( z ) = min B : z ∈ V B η B ( z ) . By Lemma 1(b), f j f_j f j is continuous on I \mathcal{I} I . Hence f j f_j f j is piecewise linear-fractional with O ( T 8 ) O(T^8) O ( T 8 ) pieces. On each piece, f j f_j f j is a linear-fractional function with rational coefficients whose denominator has no zero on the closed piece. The endpoints of the pieces are rational or roots of quadratic polynomials with rational coefficients. Forming the bases and the sets V B V_B V B takes O ( T 6 log T ) O(T^6\log T) O ( T 6 log T ) operations, and Lemma 2 takes O ( T 8 log T ) O(T^8\log T) O ( T 8 log T ) operations.
Aggregation and candidates (Step 4). By Step 2, OPT ∞ , J ∗ = min z ∈ I F ( z ) \operatorname{OPT}^{*}_{\infty,J}=\min_{z\in\mathcal{I}}F(z) OPT ∞ , J ∗ = min z ∈ I F ( z ) with F : = max j ∈ [ J ] f j F:=\max_{j\in[J]}f_j F := max j ∈ [ J ] f j . We merge the endpoints of the pieces of all f j f_j f j , which partitions I \mathcal{I} I into O ( J T 8 ) O(JT^8) O ( J T 8 ) closed cells. On a cell C C C , each f j f_j f j is a linear-fractional function with rational coefficients whose denominator has no zero on C C C , and F F F is continuous. Lemma 2, applied to the maximum with m = J m=J m = J , r = 1 r=1 r = 1 , and V j = C V_j = C V j = C , splits C C C into O ( J 2 ) O(J^2) O ( J 2 ) closed subcells, on each of which F F F equals one linear-fractional function whose denominator has no zero on the subcell.
On a subcell [ α , β ] [\alpha,\beta] [ α , β ] , we have F ( z ) = a z + b c z + d F(z) = \frac{az+b}{cz+d} F ( z ) = cz + d a z + b with c z + d ≠ 0 cz+d \ne0 cz + d = 0 for all z ∈ [ α , β ] z \in[\alpha,\beta] z ∈ [ α , β ] . Since c z + d cz+d cz + d is continuous and has no zero on [ α , β ] [\alpha,\beta] [ α , β ] , it has constant sign on [ α , β ] [\alpha,\beta] [ α , β ] . Hence, for all z , w ∈ [ α , β ] z,w \in[\alpha,\beta] z , w ∈ [ α , β ] ,
F ( z ) − F ( w ) = ( a z + b ) ( c w + d ) − ( a w + b ) ( c z + d ) ( c z + d ) ( c w + d ) = ( a d − b c ) ( z − w ) ( c z + d ) ( c w + d ) , F(z)-F(w)=\frac{(az+b)(cw+d)-(aw+b)(cz+d)}{(cz+d)(cw+d)}=\frac{(ad-bc)(z-w)}{(cz+d)(cw+d)}, F ( z ) − F ( w ) = ( cz + d ) ( c w + d ) ( a z + b ) ( c w + d ) − ( a w + b ) ( cz + d ) = ( cz + d ) ( c w + d ) ( a d − b c ) ( z − w ) ,
( c z + d ) ( c w + d ) > 0. (cz+d)(cw+d)>0. ( cz + d ) ( c w + d ) > 0.
Thus F F F is nondecreasing on [ α , β ] [\alpha,\beta] [ α , β ] if a d − b c ≥ 0 ad-bc \ge0 a d − b c ≥ 0 and nonincreasing on [ α , β ] [\alpha,\beta] [ α , β ] if a d − b c ≤ 0 ad-bc \le0 a d − b c ≤ 0 . In either case,
min z ∈ [ α , β ] F ( z ) = min { F ( α ) , F ( β ) } . \min_{z\in[\alpha,\beta]} F(z)=\min\{F(\alpha),F(\beta)\}. z ∈ [ α , β ] min F ( z ) = min { F ( α ) , F ( β )} .
Hence an optimal breakpoint is among the endpoints of the subcells, and it remains to select an endpoint with the smallest value of F F F . Each endpoint lies in Q ( Δ ) \mathbb{Q}(\sqrt{\Delta}) Q ( Δ ) for some Δ ∈ Q \Delta\in\mathbb{Q} Δ ∈ Q , and so does the value of F F F at it, since F F F is linear-fractional with rational coefficients on the subcell. By Remark 1, these values are compared exactly, so an optimal breakpoint is found exactly in polynomial time.
Recovering the solution. Given an optimal breakpoint z ⋆ z^\star z ⋆ and j ∈ [ J ] j \in[J] j ∈ [ J ] , Lemma 5(b) gives an optimal vertex ( θ B ( z ⋆ ) , η B ( z ⋆ ) ) (\theta_B(z^\star),\eta_B(z^\star)) ( θ B ( z ⋆ ) , η B ( z ⋆ )) , where B B B minimizes η B ( z ⋆ ) \eta_B(z^\star) η B ( z ⋆ ) over the O ( T 4 ) O(T^4) O ( T 4 ) bases with z ⋆ ∈ V B z^\star\in V_B z ⋆ ∈ V B . By Cramer’s rule, its entries lie in Q ( z ⋆ ) \mathbb{Q}(z^\star) Q ( z ⋆ ) . This takes O ( J T 5 ) O(JT^5) O ( J T 5 ) operations.
Operation count. For each interval, computing the pieces of all f j f_j f j takes O ( J T 8 log T ) O(JT^8\log T) O ( J T 8 log T ) operations, and sorting their endpoints takes O ( J T 8 log ( J T ) ) O(JT^8\log(JT)) O ( J T 8 log ( J T )) operations. Each of the O ( J T 8 ) O(JT^8) O ( J T 8 ) cells takes O ( J 2 log J ) O(J^2\log J) O ( J 2 log J ) operations, and each of the resulting O ( J 3 T 8 ) O(J^3T^8) O ( J 3 T 8 ) candidates is evaluated with O ( 1 ) O(1) O ( 1 ) operations. This gives O ( J 3 T 8 log ( J T ) ) O(J^3T^8\log(JT)) O ( J 3 T 8 log ( J T )) operations per interval, and O ( J 3 T 9 log ( J T ) ) O(J^3T^9\log(JT)) O ( J 3 T 9 log ( J T )) operations in total.
The ℓ 1 \ell_1 ℓ 1 loss
Fix j ∈ [ J ] j \in[J] j ∈ [ J ] . For convenience, we drop the superscript j j j . For z ∈ I z \in\mathcal{I} z ∈ I , f ( z ) f(z) f ( z ) is the optimal value of the linear program
min θ ∈ R 3 , e ∈ R T { ∑ i ∈ [ T ] e i : σ ( y i − a i ( z ) ⊤ θ ) ≤ e i for all ( i , σ ) ∈ [ T ] × { − 1 , 1 } } (4) \min_{\theta\in\mathbb{R}^3,\ e\in\mathbb{R}^T}\left\{\sum_{i\in[T]} e_i:\ \sigma(y_i-a_i(z)^\top\theta)\le e_i\ \text{for all }(i,\sigma)\in[T]\times\{-1,1\}\right\} \tag*{(4)} θ ∈ R 3 , e ∈ R T min ⎩ ⎨ ⎧ i ∈ [ T ] ∑ e i : σ ( y i − a i ( z ) ⊤ θ ) ≤ e i for all ( i , σ ) ∈ [ T ] × { − 1 , 1 } ⎭ ⎬ ⎫ (4)
For Q ⊆ [ T ] Q\subseteq[T] Q ⊆ [ T ] with ∣ Q ∣ = 3 |Q|=3 ∣ Q ∣ = 3 , let A Q ( z ) ∈ R 3 × 3 A_Q(z)\in\mathbb{R}^{3\times3} A Q ( z ) ∈ R 3 × 3 have rows a i ( z ) ⊤ a_i(z)^\top a i ( z ) ⊤ , i ∈ Q i\in Q i ∈ Q . If det A Q ( z ) ≠ 0 \det A_Q(z)\ne0 det A Q ( z ) = 0 , let θ Q ( z ) : = A Q ( z ) − 1 ( y i ) i ∈ Q \theta_Q(z):=A_Q(z)^{-1}(y_i)_{i\in Q} θ Q ( z ) := A Q ( z ) − 1 ( y i ) i ∈ Q be the unique fit with zero residual at the observations in Q Q Q , and let L Q ( z ) : = ∑ i ∈ [ T ] ∣ r i ( θ Q ( z ) , z ) ∣ L_Q(z):=\sum_{i\in[T]}|r_i(\theta_Q(z),z)| L Q ( z ) := ∑ i ∈ [ T ] ∣ r i ( θ Q ( z ) , z ) ∣ be its loss.
Lemma 6. (a) If det A Q ( z ) ≠ 0 \det A_Q(z)\ne0 det A Q ( z ) = 0 , then Q Q Q contains an index i ≤ i ∗ i\le i^\ast i ≤ i ∗ and an index i > i ∗ i>i^\ast i > i ∗ .
(b) For z ∈ I z\in\mathcal{I} z ∈ I , f ( z ) = min { L Q ( z ) : ∣ Q ∣ = 3 , det A Q ( z ) ≠ 0 } f(z)=\min\{L_Q(z): |Q|=3,\ \det A_Q(z)\ne0\} f ( z ) = min { L Q ( z ) : ∣ Q ∣ = 3 , det A Q ( z ) = 0 } .
(c) If det A Q ( z ) ≢ 0 \det A_Q(z)\not\equiv0 det A Q ( z ) ≡ 0 , then det A Q ( z ) \det A_Q(z) det A Q ( z ) is affine in z z z , and r i ( θ Q ( z ) , z ) = n Q , i ( z ) / det A Q ( z ) r_i(\theta_Q(z),z)=n_{Q,i}(z)/\det A_Q(z) r i ( θ Q ( z ) , z ) = n Q , i ( z ) / det A Q ( z ) for affine functions n Q , i n_{Q,i} n Q , i with rational coefficients. Consequently, det A Q \det A_Q det A Q has at most one zero, and each of the at most T − 3 T-3 T − 3 functions n Q , i ≢ 0 n_{Q,i}\not\equiv0 n Q , i ≡ 0 , i ∉ Q i\notin Q i ∈ / Q , has at most one zero. These at most T − 2 T-2 T − 2 points split I \mathcal{I} I into at most T − 1 T-1 T − 1 closed intervals. On each of them, with the zero of det A Q \det A_Q det A Q removed, L Q = ( ∑ i σ i n Q , i ) / ( σ 0 det A Q ) L_Q=(\sum_i\sigma_i n_{Q,i})/(\sigma_0\det A_Q) L Q = ( ∑ i σ i n Q , i ) / ( σ 0 det A Q ) for fixed signs σ 0 , σ i ∈ { − 1 , 1 } \sigma_0,\sigma_i\in\{-1,1\} σ 0 , σ i ∈ { − 1 , 1 } , which is linear-fractional.
Proof. (a) If Q ⊆ [ i ∗ ] Q \subseteq[i^*] Q ⊆ [ i ∗ ] , the third column of A Q ( z ) A_Q(z) A Q ( z ) is zero. If Q ∩ [ i ∗ ] = ∅ Q \cap[i^*] = \varnothing Q ∩ [ i ∗ ] = ∅ , the third column equals the second column minus z z z times the first. In both cases, A Q ( z ) A_Q(z) A Q ( z ) is singular.
(b) We show that f ( z ) = min { L Q ( z ) : Q ⊆ [ T ] , ∣ Q ∣ = 3 , det A Q ( z ) ≠ 0 } f(z) = \min\{L_Q(z) : Q \subseteq[T],\ |Q| = 3,\ \det A_Q(z) \ne0\} f ( z ) = min { L Q ( z ) : Q ⊆ [ T ] , ∣ Q ∣ = 3 , det A Q ( z ) = 0 } .
Step 1: f ( z ) ≤ L Q ( z ) f(z) \le L_Q(z) f ( z ) ≤ L Q ( z ) for every such Q Q Q . The point ( θ Q ( z ) , ( ∣ r i ( θ Q ( z ) , z ) ∣ ) i ) (\theta_Q(z), (|r_i(\theta_Q(z),z)|)_i) ( θ Q ( z ) , ( ∣ r i ( θ Q ( z ) , z ) ∣ ) i ) is feasible for (4) , and its objective value is L Q ( z ) L_Q(z) L Q ( z ) . Hence f ( z ) ≤ L Q ( z ) f(z) \le L_Q(z) f ( z ) ≤ L Q ( z ) .
Step 2: f ( z ) = L Q ( z ) f(z) = L_Q(z) f ( z ) = L Q ( z ) for some such Q Q Q . We first show that (4) has an optimal vertex. Every feasible point satisfies e i ≥ ∣ r i ( θ , z ) ∣ ≥ 0 e_i \ge|r_i(\theta,z)| \ge0 e i ≥ ∣ r i ( θ , z ) ∣ ≥ 0 for all i i i . Let ( θ , e ) + t ( θ ′ , e ′ ) (\theta,e) + t(\theta',e') ( θ , e ) + t ( θ ′ , e ′ ) , t ∈ R t \in\mathbb{R} t ∈ R , be a line in the feasible region. Since e + t e ′ ≥ 0 e + te' \ge0 e + t e ′ ≥ 0 for all t ∈ R t \in\mathbb{R} t ∈ R , we have e ′ = 0 e' = 0 e ′ = 0 . Then ∣ y i − a i ( z ) ⊤ θ − t a i ( z ) ⊤ θ ′ ∣ ≤ e i |y_i - a_i(z)^\top\theta- t a_i(z)^\top\theta'| \le e_i ∣ y i − a i ( z ) ⊤ θ − t a i ( z ) ⊤ θ ′ ∣ ≤ e i for all t ∈ R t \in\mathbb{R} t ∈ R and all i i i , so a i ( z ) ⊤ θ ′ = 0 a_i(z)^\top\theta' = 0 a i ( z ) ⊤ θ ′ = 0 for all i i i . By Lemma 1(a), the vectors a i ( z ) a_i(z) a i ( z ) , i ∈ [ T ] i \in[T] i ∈ [ T ] , span R 3 \mathbb{R}^3 R 3 , so θ ′ = 0 \theta' = 0 θ ′ = 0 . Hence the feasible region contains no line. As (4) is feasible and its objective is bounded below by 0 0 0 , it has an optimal vertex ( θ ˉ , e ˉ ) (\bar{\theta}, \bar{e}) ( θ ˉ , e ˉ ) [53 ] .
We next count the active constraints at ( θ ˉ , e ˉ ) (\bar{\theta}, \bar{e}) ( θ ˉ , e ˉ ) . By optimality, e ˉ i = ∣ r i ( θ ˉ , z ) ∣ \bar{e}_i = |r_i(\bar{\theta},z)| e ˉ i = ∣ r i ( θ ˉ , z ) ∣ for every i i i , since otherwise e ˉ i \bar{e}_i e ˉ i could be decreased. Let Q ˉ : = { i : r i ( θ ˉ , z ) = 0 } \bar{Q} := \{i : r_i(\bar{\theta},z) = 0\} Q ˉ := { i : r i ( θ ˉ , z ) = 0 } . For i ∉ Q ˉ i \notin\bar{Q} i ∈ / Q ˉ , exactly one of the two constraints of i i i is active. For i ∈ Q ˉ i \in\bar{Q} i ∈ Q ˉ , both are active, and their rows ( a i ( z ) ⊤ , 1 i ⊤ ) (a_i(z)^\top,1_i^\top) ( a i ( z ) ⊤ , 1 i ⊤ ) and ( − a i ( z ) ⊤ , 1 i ⊤ ) (-a_i(z)^\top,1_i^\top) ( − a i ( z ) ⊤ , 1 i ⊤ ) span the same space as ( a i ( z ) ⊤ , 0 ) (a_i(z)^\top,0) ( a i ( z ) ⊤ , 0 ) and ( 0 , 1 i ⊤ ) (0,1_i^\top) ( 0 , 1 i ⊤ ) , where 1 i 1_i 1 i is the i i i th unit vector in R T \mathbb{R}^T R T . Hence the rank of the active constraints is at most
rank { a i ( z ) : i ∈ Q ˉ } + ∣ Q ˉ ∣ + ( T − ∣ Q ˉ ∣ ) = rank { a i ( z ) : i ∈ Q ˉ } + T . \operatorname{rank}\{a_i(z) : i \in\bar{Q}\} + |\bar{Q}| + (T-|\bar{Q}|) = \operatorname{rank}\{a_i(z) : i \in\bar{Q}\} + T. rank { a i ( z ) : i ∈ Q ˉ } + ∣ Q ˉ ∣ + ( T − ∣ Q ˉ ∣ ) = rank { a i ( z ) : i ∈ Q ˉ } + T .
At a vertex of a polyhedron in R T + 3 \mathbb{R}^{T+3} R T + 3 , this rank equals T + 3 T+3 T + 3 . Therefore the vectors a i ( z ) a_i(z) a i ( z ) , i ∈ Q ˉ i \in\bar{Q} i ∈ Q ˉ , span R 3 \mathbb{R}^3 R 3 , and some Q ⊆ Q ˉ Q \subseteq\bar{Q} Q ⊆ Q ˉ with ∣ Q ∣ = 3 |Q| = 3 ∣ Q ∣ = 3 has det A Q ( z ) ≠ 0 \det A_Q(z) \ne0 det A Q ( z ) = 0 . Since a i ( z ) ⊤ θ ˉ = y i a_i(z)^\top\bar{\theta} = y_i a i ( z ) ⊤ θ ˉ = y i for i ∈ Q i \in Q i ∈ Q , we get θ ˉ = θ Q ( z ) \bar{\theta} = \theta_Q(z) θ ˉ = θ Q ( z ) , and therefore L Q ( z ) = ∑ i ∣ r i ( θ ˉ , z ) ∣ = ∑ i e ˉ i = f ( z ) L_Q(z) = \sum_i |r_i(\bar{\theta},z)| = \sum_i \bar{e}_i = f(z) L Q ( z ) = ∑ i ∣ r i ( θ ˉ , z ) ∣ = ∑ i e ˉ i = f ( z ) .
Steps 1 and 2 together prove the claim.
(c) As in the proof of Lemma 5(a), det A Q ( z ) \det A_Q(z) det A Q ( z ) is affine, and by Cramer’s rule, δ Q \delta_Q δ Q is a rational constant divided by det A Q ( z ) \det A_Q(z) det A Q ( z ) , while α Q \alpha_Q α Q and β Q \beta_Q β Q are affine functions divided by det A Q ( z ) \det A_Q(z) det A Q ( z ) . Hence each residual is an affine function n Q , i n_{Q,i} n Q , i divided by det A Q ( z ) \det A_Q(z) det A Q ( z ) , with n Q , i ≡ 0 n_{Q,i} \equiv0 n Q , i ≡ 0 for i ∈ Q i \in Q i ∈ Q . Neither det A Q \det A_Q det A Q nor any n Q , i ≢ 0 n_{Q,i} \not\equiv0 n Q , i ≡ 0 vanishes in the interior of one of the closed intervals. At an endpoint, the n Q , i n_{Q,i} n Q , i that vanish contribute zero with either sign. This gives the formula. □ \square □
Structure of f j f_j f j (Step 3). By Lemma 6 (b) and (c), f j f_j f j is the minimum of the m ≤ ( T 3 ) ( T − 1 ) = O ( T 4 ) m \le\binom{T}{3}(T-1) = O(T^4) m ≤ ( 3 T ) ( T − 1 ) = O ( T 4 ) linear-fractional functions of Lemma 6 (c), each available on a single interval. By Lemmas 1(b) and 2 with r = 1 r = 1 r = 1 , f j f_j f j is piecewise linear-fractional with O ( T 8 ) O(T^8) O ( T 8 ) pieces. On each piece, f j f_j f j is a linear-fractional function with rational coefficients whose denominator has no zero on the closed piece. The endpoints of the pieces are rational or roots of quadratic polynomials with rational coefficients. Forming the functions takes O ( T 4 log T ) O(T^4 \log T) O ( T 4 log T ) operations, and Lemma 2 takes O ( T 8 log T ) O(T^8 \log T) O ( T 8 log T ) operations.
Aggregation and candidates (Step 4). By Step 2, OPT i ∗ , J = min z ∈ I F ( z ) \operatorname{OPT}_{i^*,J} = \min_{z \in\mathcal{I}} F(z) OPT i ∗ , J = min z ∈ I F ( z ) with F : = ∑ j ∈ [ J ] f j F := \sum_{j \in[J]} f_j F := ∑ j ∈ [ J ] f j . Merging the endpoints of the pieces of all f j f_j f j partitions I \mathcal{I} I into O ( J T 8 ) O(JT^8) O ( J T 8 ) closed cells. On a cell C \mathcal{C} C , f j = ( a j + b j z ) / ( c j + d j z ) f_j = (a_j + b_jz)/(c_j + d_jz) f j = ( a j + b j z ) / ( c j + d j z ) with rational coefficients and c j + d j z ≠ 0 c_j + d_jz \ne0 c j + d j z = 0 on C \mathcal{C} C . Hence F = P / Q F = P/Q F = P / Q on C \mathcal{C} C , where
Q ( z ) : = ∏ j ∈ [ J ] ( c j + d j z ) , P ( z ) : = ∑ j ∈ [ J ] ( a j + b j z ) ∏ h ∈ [ J ] ∖ { j } ( c h + d h z ) , Q(z) := \prod_{j \in[J]} (c_j + d_jz), \qquad P(z) := \sum_{j \in[J]} (a_j + b_jz)\prod_{h \in[J]\setminus\{j\}} (c_h + d_hz), Q ( z ) := j ∈ [ J ] ∏ ( c j + d j z ) , P ( z ) := j ∈ [ J ] ∑ ( a j + b j z ) h ∈ [ J ] ∖ { j } ∏ ( c h + d h z ) ,
both of degree at most J J J , and Q ≠ 0 Q \ne0 Q = 0 on C \mathcal{C} C . Then F ′ = H / Q 2 F' = H/Q^2 F ′ = H / Q 2 with H : = P ′ Q − P Q ′ H := P'Q - PQ' H := P ′ Q − P Q ′ . If P = ∑ t ≤ J p t z t P = \sum_{t \le J} p_t z^t P = ∑ t ≤ J p t z t and Q = ∑ t ≤ J q t z t Q = \sum_{t \le J} q_t z^t Q = ∑ t ≤ J q t z t , the coefficient of z 2 J − 1 z^{2J-1} z 2 J − 1 in H H H is J p J q J − J p J q J = 0 Jp_Jq_J - Jp_Jq_J = 0 J p J q J − J p J q J = 0 , so deg H ≤ 2 J − 2 \deg H \le2J - 2 deg H ≤ 2 J − 2 . As in the proof of Lemma 4 , the minimum of F F F over C \mathcal{C} C is attained at an endpoint of C \mathcal{C} C or, if H ≠ 0 H \ne0 H = 0 , at a real root of H H H in the interior of C \mathcal{C} C . We isolate these roots and compare the values of F F F at all candidates exactly. Every candidate is rational, a root of a quadratic polynomial with rational coefficients, or a root of H H H , which has rational coefficients and degree at most 2 J − 2 2J-2 2 J − 2 . Hence every candidate and every value of F F F at a candidate is a real algebraic number of degree at most 2 J − 2 2J-2 2 J − 2 whose representation has encoding length polynomial in T T T , J J J , and ⟨ D ⟩ \langle D\rangle ⟨ D ⟩ , and such numbers are compared exactly in polynomial time, even when their degrees differ [6 , 51 ] .
Recovering the solution. Given an optimal breakpoint z ⋆ z^\star z ⋆ and j ∈ [ J ] j \in[J] j ∈ [ J ] , Lemma 6(b) gives an optimal fit θ Q ( z ⋆ ) \theta_Q(z^\star) θ Q ( z ⋆ ) , where Q Q Q minimizes L Q ( z ⋆ ) L_Q(z^\star) L Q ( z ⋆ ) over the triples with det A Q ( z ⋆ ) ≠ 0 \det A_Q(z^\star) \ne0 det A Q ( z ⋆ ) = 0 . By Cramer’s rule, its entries lie in Q ( z ⋆ ) \mathbb{Q}(z^\star) Q ( z ⋆ ) . We find such a Q Q Q by enumerating the O ( T 3 ) O(T^3) O ( T 3 ) triples and evaluating L Q ( z ⋆ ) L_Q(z^\star) L Q ( z ⋆ ) for each with O ( T ) O(T) O ( T ) operations, which takes O ( J T 4 ) O(JT^4) O ( J T 4 ) operations in Q ( z ⋆ ) \mathbb{Q}(z^\star) Q ( z ⋆ ) over all j j j .
Operation count. For each interval, computing the pieces of all f j f_j f j takes O ( J T 8 log T ) O(JT^8\log T) O ( J T 8 log T ) operations, and sorting their endpoints takes O ( J T 8 log ( J T ) ) O(JT^8\log(JT)) O ( J T 8 log ( J T )) operations. On each of the O ( J T 8 ) O(JT^8) O ( J T 8 ) cells, P P P , Q Q Q , and H H H are formed with O ( J 2 ) O(J^2) O ( J 2 ) operations, the real roots of one polynomial of degree at most 2 J − 2 2J-2 2 J − 2 are isolated, and at most 2 J 2J 2 J candidates are compared. This gives O ( J 3 T 9 + J T 9 log ( J T ) ) O(J^3T^9+JT^9\log(JT)) O ( J 3 T 9 + J T 9 log ( J T )) arithmetic operations, O ( J T 9 ) O(JT^9) O ( J T 9 ) root isolations, and O ( J T 9 ) O(JT^9) O ( J T 9 ) algebraic comparisons in total.
Polynomial-Time Solvability: Sparse Setting
We now carry out Step 5 of the proof outline, which handles the sparsity constraint. Let 1 ≤ k < J 1 \le k < J 1 ≤ k < J , since the case k = 0 k=0 k = 0 is solved directly. For p ∈ { 1 , 2 } p \in\{1,2\} p ∈ { 1 , 2 } , let u j : = U j − f j ≥ 0 u_j := U_j-f_j \ge0 u j := U j − f j ≥ 0 be the gains of Step 5. Since the gains are nonnegative, the constraint ∣ S ∣ ≤ k |S| \le k ∣ S ∣ ≤ k may be replaced by ∣ S ∣ = k |S|=k ∣ S ∣ = k . By Step 2,
OPT p , k ⋆ = min z ∈ I Φ ( z ) , Φ ( z ) : = ∑ j ∈ [ J ] U j − max S ⊆ [ J ] ∣ S ∣ = k ∑ j ∈ S u j ( z ) . \operatorname{OPT}_{p,k}^{\star}=\min_{z\in I}\Phi(z),\qquad\Phi(z):=\sum_{j\in[J]}U_j-\max_{\substack{S\subseteq[J]\\|S|=k}}\sum_{j\in S}u_j(z). OPT p , k ⋆ = z ∈ I min Φ ( z ) , Φ ( z ) := j ∈ [ J ] ∑ U j − S ⊆ [ J ] ∣ S ∣ = k max j ∈ S ∑ u j ( z ) .
Lemma 7. Let p ∈ { 1 , 2 } p \in\{1,2\} p ∈ { 1 , 2 } , let x i ⋆ = t 0 < t 1 < ⋯ < t n = x i ⋆ + 1 x_{i^\star}=t_0<t_1<\cdots<t_n=x_{i^\star+1} x i ⋆ = t 0 < t 1 < ⋯ < t n = x i ⋆ + 1 , and for each q ∈ [ n ] q \in[n] q ∈ [ n ] let S q ⊆ [ J ] S_q\subseteq[J] S q ⊆ [ J ] with ∣ S q ∣ = k |S_q|=k ∣ S q ∣ = k attain the maximum in the definition of Φ ( z ) \Phi(z) Φ ( z ) for every z ∈ ( t q − 1 , t q ) z\in(t_{q-1},t_q) z ∈ ( t q − 1 , t q ) . Then
OPT p , k ⋆ = min q ∈ [ n ] min z ∈ [ t q − 1 , t q ] ( ∑ j ∉ S q U j + ∑ j ∈ S q f j ( z ) ) . \operatorname{OPT}_{p,k}^{\star}=\min_{q\in[n]}\min_{z\in[t_{q-1},t_q]}\left(\sum_{j\notin S_q}U_j+\sum_{j\in S_q}f_j(z)\right). OPT p , k ⋆ = q ∈ [ n ] min z ∈ [ t q − 1 , t q ] min j ∈ / S q ∑ U j + j ∈ S q ∑ f j ( z ) .
Proof. Let Φ q ( z ) : = ∑ j ∉ S q U j + ∑ j ∈ S q f j ( z ) = ∑ j ∈ [ J ] U j − ∑ j ∈ S q u j ( z ) \Phi_q(z):=\sum_{j\notin S_q}U_j+\sum_{j\in S_q}f_j(z)=\sum_{j\in[J]}U_j-\sum_{j\in S_q}u_j(z) Φ q ( z ) := ∑ j ∈ / S q U j + ∑ j ∈ S q f j ( z ) = ∑ j ∈ [ J ] U j − ∑ j ∈ S q u j ( z ) . Then Φ q ≥ Φ \Phi_q\ge\Phi Φ q ≥ Φ on I I I , with equality on ( t q − 1 , t q ) (t_{q-1},t_q) ( t q − 1 , t q ) . Both functions are continuous by Lemma 1(b), so they are equal on [ t q − 1 , t q ] [t_{q-1},t_q] [ t q − 1 , t q ] .
loss with sparsity constraint
By Lemma 3, u j ( z ) = U j − f j ( z ) = ν j ( z ) 2 / D ( z ) u_j(z)=U_j-f_j(z)=\nu_j(z)^2/D(z) u j ( z ) = U j − f j ( z ) = ν j ( z ) 2 / D ( z ) , where ν j ( z ) = ( y j ) T M h ( z ) \nu_j(z)=(y^j)^\mathsf{T}Mh(z) ν j ( z ) = ( y j ) T M h ( z ) is affine in z z z and D ( z ) = h ( z ) T M h ( z ) D(z)=h(z)^\mathsf{T}Mh(z) D ( z ) = h ( z ) T M h ( z ) is a quadratic in z z z that is positive on R \mathbb{R} R and the same for all j j j . For each z z z , rank the dimensions by j ≺ j ′ j\prec j' j ≺ j ′ if ν j ( z ) 2 > ν j ′ ( z ) 2 \nu_j(z)^2>\nu_{j'}(z)^2 ν j ( z ) 2 > ν j ′ ( z ) 2 , or if ν j ( z ) 2 = ν j ′ ( z ) 2 \nu_j(z)^2=\nu_{j'}(z)^2 ν j ( z ) 2 = ν j ′ ( z ) 2 and j < j ′ j<j' j < j ′ . For every z z z , the first k k k dimensions in this ranking attain the maximum in the definition of Φ ( z ) \Phi(z) Φ ( z ) . The ranking can change only at points where ν j ( z ) 2 = ν j ′ ( z ) 2 \nu_j(z)^2=\nu_{j'}(z)^2 ν j ( z ) 2 = ν j ′ ( z ) 2 for some j ≠ j ′ j\ne j' j = j ′ , so we partition I I I by these points. Let E E E be the set of roots in ( x i ⋆ , x i ⋆ + 1 ) (x_{i^\star},x_{i^\star+1}) ( x i ⋆ , x i ⋆ + 1 ) of the affine functions ν j ( z ) − ν j ′ ( z ) \nu_j(z)-\nu_{j'}(z) ν j ( z ) − ν j ′ ( z ) and ν j ( z ) + ν j ′ ( z ) \nu_j(z)+\nu_{j'}(z) ν j ( z ) + ν j ′ ( z ) , for the pairs j ≠ j ′ j\ne j' j = j ′ with ν j ( z ) 2 − ν j ′ ( z ) 2 ≢ 0 \nu_j(z)^2-\nu_{j'}(z)^2\not\equiv0 ν j ( z ) 2 − ν j ′ ( z ) 2 ≡ 0 . These roots are rational, and ∣ E ∣ ≤ J ( J − 1 ) |E|\le J(J-1) ∣ E ∣ ≤ J ( J − 1 ) . On each open cell between consecutive points of E ∪ { x i ⋆ , x i ⋆ + 1 } E\cup\{x_{i^\star},x_{i^\star+1}\} E ∪ { x i ⋆ , x i ⋆ + 1 } , the function ν j ( z ) 2 − ν j ′ ( z ) 2 = ( ν j ( z ) − ν j ′ ( z ) ) ( ν j ( z ) + ν j ′ ( z ) ) \nu_j(z)^2-\nu_{j'}(z)^2=(\nu_j(z)-\nu_{j'}(z))(\nu_j(z)+\nu_{j'}(z)) ν j ( z ) 2 − ν j ′ ( z ) 2 = ( ν j ( z ) − ν j ′ ( z )) ( ν j ( z ) + ν j ′ ( z )) is either identically zero or has a constant nonzero sign. Hence the ranking, and therefore the set S S S of its first k k k dimensions, is constant on the cell. By Lemma 7 , on the closed cell we minimize
∑ j ∈ [ J ] U j − N S ( z ) D ( z ) , N S ( z ) : = ∑ j ∈ S ν j ( z ) 2 , \sum_{j\in[J]} U_j-\frac{N_S(z)}{D(z)},\qquad N_S(z):=\sum_{j\in S}\nu_j(z)^2, j ∈ [ J ] ∑ U j − D ( z ) N S ( z ) , N S ( z ) := j ∈ S ∑ ν j ( z ) 2 ,
where N S ( z ) N_S(z) N S ( z ) has degree at most two irrespective of k k k and J J J . Lemma 4 gives at most four candidates per cell. Each lies in Q \mathbb{Q} Q or in a real quadratic field over Q \mathbb{Q} Q and, by Remark 1 , the candidates are compared exactly in polynomial time. Given an optimal breakpoint z ⋆ z^\star z ⋆ and the set S S S of its cell, we set δ j ⋆ = 0 \delta_j^\star=0 δ j ⋆ = 0 and ( α j ⋆ , β j ⋆ ) ⊤ = G − 1 A ⊤ y j (\alpha_j^\star,\beta_j^\star)^\top=G^{-1}A^\top y^j ( α j ⋆ , β j ⋆ ) ⊤ = G − 1 A ⊤ y j for j ∉ S j\notin S j ∈ / S , and we recover ( α j ⋆ , β j ⋆ , δ j ⋆ ) (\alpha_j^\star,\beta_j^\star,\delta_j^\star) ( α j ⋆ , β j ⋆ , δ j ⋆ ) for j ∈ S j\in S j ∈ S as in Section 3.2.
Sweep. The cells are visited from left to right. On the first cell, the ranking is obtained by sorting, with comparisons at a rational point of the cell. For t ∈ E t\in E t ∈ E , let E t E_t E t be the set of dimensions j j j such that t t t is a root of ν j − ν j ′ \nu_j-\nu_{j'} ν j − ν j ′ or of ν j + ν j ′ \nu_j+\nu_{j'} ν j + ν j ′ for some j ′ j' j ′ with ν j 2 − ν j ′ 2 ≢ 0 \nu_j^2-\nu_{j'}^2\not\equiv0 ν j 2 − ν j ′ 2 ≡ 0 . If j ∉ E t j\notin E_t j ∈ / E t , then, for every j ′ j' j ′ , the sign of ν j 2 − ν j ′ 2 \nu_j^2-\nu_{j'}^2 ν j 2 − ν j ′ 2 is the same on the two cells adjacent to t t t , so j j j has the same rank on both cells. Hence the ranks held by the dimensions in E t E_t E t are also the same on both cells. The set S S S of the cell to the right of t t t is therefore obtained from the set S S S of the cell to the left of t t t by replacing S ∩ E t S\cap E_t S ∩ E t with the first ∣ S ∩ E t ∣ |S\cap E_t| ∣ S ∩ E t ∣ dimensions of E t E_t E t in the ranking on the right cell. This takes O ( ∣ E t ∣ log ∣ E t ∣ ) O(|E_t|\log|E_t|) O ( ∣ E t ∣ log ∣ E t ∣ ) operations. The coefficients of N S N_S N S are updated with O ( ∣ E t ∣ ) O(|E_t|) O ( ∣ E t ∣ ) operations. Since ∑ t ∈ E ∣ E t ∣ ≤ 2 J ( J − 1 ) \sum_{t\in E}|E_t|\le2J(J-1) ∑ t ∈ E ∣ E t ∣ ≤ 2 J ( J − 1 ) , the sweep takes O ( J 2 log J ) O(J^2\log J) O ( J 2 log J ) operations.
Operation count. For each interval, the coefficients s j , 0 s_{j,0} s j , 0 , s j , 1 s_{j,1} s j , 1 and d 0 d_0 d 0 , d 1 d_1 d 1 , d 2 d_2 d 2 are obtained with O ( J ) O(J) O ( J ) operations from the suffix sums of Section 3.2. Forming and sorting E E E takes O ( J 2 log J ) O(J^2\log J) O ( J 2 log J ) operations, the sweep takes O ( J 2 log J ) O(J^2\log J) O ( J 2 log J ) operations, and each of the O ( J 2 ) O(J^2) O ( J 2 ) cells requires a constant number of operations, quadratic root computations, and comparisons. Over all intervals, and with the recovery step, this gives O ( J 2 T log J ) O(J^2T\log J) O ( J 2 T log J ) operations.
ℓ ∞ \ell_\infty ℓ ∞ loss with sparsity constraint
By Step 5, where S ⋆ S^\star S ⋆ consists of the k k k dimensions with the largest U j U_j U j , any minimizer of g : = max j ∈ S ⋆ f j g:=\max_{j\in S^\star}f_j g := max j ∈ S ⋆ f j over I \mathcal{I} I also minimizes max { g , M } \max\{g,M\} max { g , M } , since t ↦ max { t , M } t\mapsto\max\{t,M\} t ↦ max { t , M } is nondecreasing. Hence we run the algorithm of Section 3.3 on the dimensions in S ⋆ S^\star S ⋆ , which takes O ( k T 9 log ( k T ) ) O(kT^9\log(kT)) O ( k T 9 log ( k T )) operations. For j ∉ S ⋆ j\notin S^\star j ∈ / S ⋆ , we use an optimal single line with δ j ⋆ = 0 \delta_j^\star=0 δ j ⋆ = 0 , obtained as a rational optimal vertex of a linear program with three variables and 2 T 2T 2 T constraints in O ( T ) O(T) O ( T ) operations [45 ] . This also gives U j U_j U j , so computing all U j U_j U j and sorting them takes O ( J T + J log J ) O(JT+J\log J) O ( J T + J log J ) operations.
ℓ 1 \ell_1 ℓ 1 loss with sparsity constraint
Each U j U_j U j is the optimal value of a linear program, so it can be computed in polynomial time by any polynomial-time linear programming algorithm. To obtain an operation count that does not depend on the encoding length of the data, we instead compute it as follows. The proof of Lemma 6 (b), with a i ( z ) a_i(z) a i ( z ) replaced by ( 1 , x i ) ⊤ (1,x_i)^\top ( 1 , x i ) ⊤ , shows that some optimal single line passes through two observations. Hence U j U_j U j is the smallest loss among the ( T 2 ) \binom{T}{2} ( 2 T ) lines through two observations. Computing all U j U_j U j , together with optimal lines, takes O ( J T 3 ) O(JT^3) O ( J T 3 ) operations.
By § 3.4 , each f j f_j f j , and hence each gain u j = U j − f j u_j=U_j-f_j u j = U j − f j , is piecewise linear-fractional with O ( T 8 ) O(T^8) O ( T 8 ) pieces. Merging the endpoints of the pieces of all f j f_j f j partitions I \mathcal{I} I into O ( J T 8 ) O(JT^8) O ( J T 8 ) closed cells. On a cell C \mathcal{C} C , each u j = ( a j + b j z ) / ( c j + d j z ) u_j=(a_j+b_jz)/(c_j+d_jz) u j = ( a j + b j z ) / ( c j + d j z ) has rational coefficients, and c j + d j z ≠ 0 c_j+d_jz\ne0 c j + d j z = 0 on C \mathcal{C} C . For each pair j ≠ j ′ j \ne j' j = j ′ , let π j j ′ \pi_{jj'} π j j ′ be the polynomial of degree at most two defined in the proof of Lemma 2. We refine C C C by the at most J ( J − 1 ) J(J-1) J ( J − 1 ) roots in its interior of the polynomials π j j ′ ≢ 0 \pi_{jj'} \not\equiv0 π j j ′ ≡ 0 . As in the proof of Lemma 2, on each open subcell the order of the values u j u_j u j , with ties broken by index, is constant. Hence the set S S S of the k k k largest gains is constant on the subcell. We find S S S with O ( J ) O(J) O ( J ) comparisons by linear-time selection [12 ] . To compare u j u_j u j and u j ′ u_{j'} u j ′ on the subcell, let ζ \zeta ζ be its left endpoint, and note that
u j ( z ) − u j ′ ( z ) = π j j ′ ( z ) ( c j + d j z ) ( c j ′ + d j ′ z ) . u_j(z)-u_{j'}(z)=\frac{\pi_{jj'}(z)}{(c_j+d_jz)(c_{j'}+d_{j'}z)}. u j ( z ) − u j ′ ( z ) = ( c j + d j z ) ( c j ′ + d j ′ z ) π j j ′ ( z ) .
If π j j ′ ≡ 0 \pi_{jj'} \equiv0 π j j ′ ≡ 0 , the tie is broken by index. Otherwise, π j j ′ \pi_{jj'} π j j ′ has no zero on the open subcell, and the denominator has no zero on the closed cell C C C . Hence the sign of u j − u j ′ u_j-u_{j'} u j − u j ′ is constant on the open subcell, and it equals the sign of ( c j + d j ζ ) ( c j ′ + d j ′ ζ ) (c_j+d_j\zeta)(c_{j'}+d_{j'}\zeta) ( c j + d j ζ ) ( c j ′ + d j ′ ζ ) times the sign of π j j ′ ( z ) \pi_{jj'}(z) π j j ′ ( z ) for z > ζ z>\zeta z > ζ close to ζ \zeta ζ . Since π j j ′ ( ζ + ε ) = π j j ′ ( ζ ) + π j j ′ ′ ( ζ ) ε + 1 2 π j j ′ ′ ′ ( ζ ) ε 2 \pi_{jj'}(\zeta+\varepsilon)=\pi_{jj'}(\zeta)+\pi_{jj'}'(\zeta)\varepsilon+\frac{1}{2}\pi_{jj'}''(\zeta)\varepsilon^2 π j j ′ ( ζ + ε ) = π j j ′ ( ζ ) + π j j ′ ′ ( ζ ) ε + 2 1 π j j ′ ′′ ( ζ ) ε 2 , the latter is the sign of the first nonzero number among π j j ′ ( ζ ) \pi_{jj'}(\zeta) π j j ′ ( ζ ) , π j j ′ ′ ( ζ ) \pi_{jj'}'(\zeta) π j j ′ ′ ( ζ ) , and π j j ′ ′ ′ ( ζ ) \pi_{jj'}''(\zeta) π j j ′ ′′ ( ζ ) . As ζ \zeta ζ lies in Q \mathbb{Q} Q or in a real quadratic field over Q \mathbb{Q} Q , these signs are determined exactly with O ( 1 ) O(1) O ( 1 ) operations by Remark 1.
If π j j ′ ≡ 0 \pi_{jj'} \equiv0 π j j ′ ≡ 0 , the tie is broken by index. By Lemma 7 , on the closed subcell we minimize ∑ j ∉ S U j + ∑ j ∈ S f j ( z ) \sum_{j\notin S}U_j+\sum_{j\in S}f_j(z) ∑ j ∈ / S U j + ∑ j ∈ S f j ( z ) . This is the problem of § 3.4 with J J J replaced by k k k . Its minimum is attained at an endpoint of the subcell or at a root of a polynomial H S H_S H S of degree at most 2 k − 2 2k-2 2 k − 2 , formed with O ( k 2 ) O(k^2) O ( k 2 ) operations. For k = 1 k=1 k = 1 , H S H_S H S is constant, and only the endpoints are candidates. Given an optimal breakpoint z ⋆ z^\star z ⋆ and the set S S S of its subcell, the fits of the dimensions in S S S are recovered as in § 3.4 , and an optimal line is used for every j ∉ S j\notin S j ∈ / S .
Operation count. For each interval, computing the pieces of all f j f_j f j and sorting their endpoints takes O ( J T 8 log ( J T ) ) O(JT^8\log(JT)) O ( J T 8 log ( J T )) operations. Each of the O ( J T 8 ) O(JT^8) O ( J T 8 ) cells requires O ( J 2 log J ) O(J^2\log J) O ( J 2 log J ) operations to form and sort the crossings, and each of its O ( J 2 ) O(J^2) O ( J 2 ) subcells requires O ( J + k 2 ) O(J+k^2) O ( J + k 2 ) operations, one root isolation of a polynomial of degree at most 2 k − 2 2k-2 2 k − 2 , and O ( k ) O(k) O ( k ) algebraic comparisons. Together with the computation of the U j U_j U j , this gives O ( ( J + k 2 ) J 3 T 9 + J T 9 log ( J T ) ) O((J+k^2)J^3T^9+JT^9\log(JT)) O (( J + k 2 ) J 3 T 9 + J T 9 log ( J T )) arithmetic operations, O ( J 3 T 9 ) O(J^3T^9) O ( J 3 T 9 ) root isolations, and O ( k J 3 T 9 ) O(kJ^3T^9) O ( k J 3 T 9 ) algebraic comparisons in total.
Computational Results
In this section, we evaluate the practical performance of our algorithms for the least-squares loss (p = 2 p=2 p = 2 ). We solve the dense and sparse problems on simulated time series and on three public datasets, and we compare our algorithms against Gurobi applied to a mixed-integer nonlinear programming (MINLP) formulation.
Scope of the experiments
Why only the ℓ 2 \ell_2 ℓ 2 loss. We restrict the experiments to p = 2 p=2 p = 2 . Least squares is the standard loss for fitting a continuous piecewise-linear trend, and it corresponds to maximum likelihood estimation under Gaussian noise [37 , 40 , 25 ] . It is also the case in which our algorithms are practical. By Table 1 , the dense algorithm is linear in the size of the input, and the sparse algorithm performs O ( J T 2 log J ) O(JT^2\log J) O ( J T 2 log J ) operations. Although the algorithms for p ∈ { 1 , ∞ } p\in\{1,\infty\} p ∈ { 1 , ∞ } run in polynomial time, their high-degree dependence on T T T makes them impractical for moderate-sized instances. This is not merely an artifact of the worst-case analysis: for p = ∞ p=\infty p = ∞ , the algorithm explicitly enumerates all ( 2 T 4 ) \binom{2T}{4} ( 4 2 T ) bases of [3 ] for each dimension and interval, resulting in more than 6.4 × 10 7 6.4\times10^7 6.4 × 1 0 7 bases per dimension when T = 100 T=100 T = 100 .
Why floating-point arithmetic. Theorem 1 guarantees exact computation, but our implementation uses double-precision arithmetic, so its solutions are approximately optimal and not certified in the sense of Definition 1. Exact arithmetic is possible, but for large J J J its cost would be dominated by large-integer operations, since the coefficients of N N N aggregate all J J J dimensions.
Datasets
Table 2 summarizes the instances. Each dataset gives one dense instance and two sparse instances with k = ⌊ 0.20 J ⌋ k = \lfloor0.20J\rfloor k = ⌊ 0.20 J ⌋ and k = ⌊ 0.10 J ⌋ k = \lfloor0.10J\rfloor k = ⌊ 0.10 J ⌋ . We consider sparsity levels of 20% and 10% to evaluate the algorithms under different degrees of sparsity, where changes are restricted to a subset of dimensions, motivated by similar sparsity levels considered in the computational experiments of [33 , 3 ] . The subsets of the three public datasets used in our experiments, together with visualizations, are available in the repositories listed below.
Table 2. Instances considered in the computational experiments, including the dense setting and the sparse setting with sparsity levels of 20% and 10%.
Simulated data. We generate correlated stock-price trajectories with market, sector, and stock-specific fluctuations, as described in Appendix § 9 . Each dimension independently undergoes a change in its expected daily log-return with a fixed probability, at a randomly selected time near the middle of the observation horizon. We use T = 100 T = 100 T = 100 and x i = i − 1 x_i = i - 1 x i = i − 1 .
ERA5 temperature data. ERA5 is a global atmospheric reanalysis produced by the European Centre for Medium-Range Weather Forecasts, which combines historical observations with numerical weather models [35 ] . Motivated by studies of changing warming rates [18 , 48 , 27 ] , we use the 2 m air temperature on a 201 × \times × 201 latitude-longitude grid with 0.25° spacing, covering 10°N to 60°N and 125°W to 75°W, including land and ocean. Each grid point is one dimension, so J = 40,401 J = 40{,}401 J = 40 , 401 . We use annual values for 2000 to 2025, so T = 26 T = 26 T = 26 and x i = 1999 + i x_i = 1999 + i x i = 1999 + i , where each value is the average over the year of the daily temperatures at 17:00 UTC. The data are available at https://github.com/ApoorvaGOR/ERA5-Regional-Temperature .
HoloAssist hand-tracking data. The HoloAssist dataset [59 ] contains hand movements tracked by the Microsoft HoloLens mixed-reality headset. We use an 8.013-second sequence sampled at about 30 frames per second, so T = 240 T = 240 T = 240 , and the time coordinates are the timestamps in seconds. Each hand has 26 tracked joints with 21 measurements per joint, namely 16 entries of a pose transformation matrix, 3 spatial coordinates, and 2 tracking-status indicators. This gives 546 dimensions per hand and J = 1,092 J = 1{,}092 J = 1 , 092 for both hands. The data are available at https://github.com/ApoorvaGOR/HoloAssist-Hand-Sample .
NASA C-MAPSS turbofan data. The Commercial Modular Aero-Propulsion System Simulation (C-MAPSS) dataset [52 ] contains multivariate sensor measurements from simulated aircraft engines undergoing progressive degradation, a setting that motivates multidimensional slope change detection [19 ] . We use training engine 1 of the FD001 subset, with all 21 sensor channels over its complete trajectory of 192 cycles, so J = 21 J = 21 J = 21 and T = 192 T = 192 T = 192 . Operational settings and remaining useful life (RUL) labels are not fitted. With R 0 = 191 R_0 = 191 R 0 = 191 the initial RUL and R i R_i R i the RUL at observation i i i , we set x i = R 0 + 1 − R i x_i = R_0 + 1 - R_i x i = R 0 + 1 − R i , which gives the operating cycles 1, ..., 192. The data are available at https://github.com/ApoorvaGOR/C-MAPSS-Turbofan-Data .
Implementation and benchmark
Implementation and computing environment. The algorithms are implemented in Python, and their computationally intensive routines are compiled with the just-in-time (JIT) compiler Numba [43 ] . The experiments were run on a MacBook Pro (November 2023) with an Apple M3 chip and 16 GB of unified memory, running macOS Golden Gate 27.0.1, and the MINLP was solved with Gurobi Optimizer 13.0.2 [32 ] . Both our algorithms and the Gurobi MINLP benchmark were run using a single CPU thread. For our algorithms, we restricted Numba and the underlying numerical libraries to one thread, while Gurobi was configured to use one thread. The source code and computational results are publicly available at the following repository: https://github.com/ApoorvaGOR/High-Dimensional-Piecewise-Linear-Fitting .
Runtime measurement. Numba compiles each numerical routine the first time it is called. Before the experiments, we therefore run each algorithm once on a small instance, with J = 2 J=2 J = 2 and T = 8 T=8 T = 8 for the dense algorithm and with J = 4 J=4 J = 4 , T = 8 T=8 T = 8 , and k = 2 k=2 k = 2 for the sparse algorithm. The experiments for the two sparsity levels (20% and 10%) are conducted in separate executions, each with its own warmup. The warmup is performed once per execution, and the compiled code is then reused for all instances within that execution. The warmup takes 3.613 s for the dense algorithm and 5.090 s and 5.120 s for the sparse algorithm in the 20% and 10% sparsity experiments, respectively. The reported runtimes of our algorithms exclude the warmup, data acquisition or generation, time-coordinate conversion, and output storage. All runtimes are from single runs. Runtimes are measured using Python’s time.perf_counter(), a high-resolution monotonic wall-clock timer, which uses macOS’s mach_absolute_time() with a reported resolution of approximately 41.67 ns on our machine.
MINLP benchmark. As a benchmark, we use the MINLP formulation of [47 ] for a single shared breakpoint, stated with its big-M M M constants in Appendix § 10 . It has T T T binary variables that assign the observations to the two segments, J J J further binary variables in the sparse problem, and J J J bilinear continuity constraints. Each instance is solved by Gurobi with a time limit of 10,000 s. The reported MINLP runtime is the solver time, and it excludes the construction of the parameter bounds and of the model. Gurobi may exceed the time limit slightly while terminating. We report the best lower bound (LB), the objective value of the best solution found (UB), and the relative optimality gap. Our algorithms are run without a time limit.
Results
Table 3 reports the results for the dense and the sparse problem. The column O P T 2 OPT_2 O P T 2 gives the optimal value, that is, the sum of squared errors, computed by our algorithms.
Table 3: Computational comparison of our algorithms and the MINLP benchmark for (a) the dense problem of Section 3.2, (b) the sparse problem of § 4 with k = ⌊ 0.20 J ⌋ k=\lfloor0.20J\rfloor k = ⌊ 0.20 J ⌋ , and (c) the sparse problem with k = ⌊ 0.10 J ⌋ k=\lfloor0.10J\rfloor k = ⌊ 0.10 J ⌋ .
Table 3.
Notes: The one-time JIT compilation times of approximately 3.613 s for the dense algorithm, 5.090 s for the sparse algorithm with 20% sparsity, and 5.120 s for the sparse algorithm with 10% sparsity are excluded from the reported runtimes. LB, UB, and the gap refer to the bounded MINLP, with the gap representing Gurobi’s relative gap. In each row, bold runtimes indicate the shorter runtime, and bold objective values indicate the lowest displayed objective value. *The MINLP reached the prescribed time limit of 10,000 s. †Our algorithm did not terminate within the prescribed time limit of 10,000 s; consequently, its runtime and objective value are not reported.
Dense problem. The dense algorithm solves every instance in less than 0.1 s, including the simulated instance with J = 10 5 J=10^{5} J = 1 0 5 and 10 7 10^{7} 1 0 7 observations, which takes less than 0.080 s. This speed matters in online detection [19 ] , where the problem is solved again after each new observation, for example to evaluate the generalized likelihood ratio statistic [54 ] , which under Gaussian noise is proportional to ∑ j ∈ [ J ] U j − O P T 2 , J \sum_{j\in[J]} U_j-\mathit{OPT}_{2,J} ∑ j ∈ [ J ] U j − OPT 2 , J . On HoloAssist, one solve takes 3.27 ms, well below the interval of about 33 ms between consecutive frames at 30 frames per second.
Sparse problem. For both sparsity levels (20% and 10%), the sparse algorithm solves all instances with J ≤ 1092 J\leq1092 J ≤ 1092 in less than 1 s. For the simulated instance with J = 10 4 J=10^{4} J = 1 0 4 , the runtimes are 67.68 s and 65.90 s for 20% and 10% sparsity, respectively. The ERA5 instance, with J = 40,401 J=40{,}401 J = 40 , 401 , takes approximately 2.5 hours and 2.1 hours, respectively. For the simulated instance with J = 10 5 J=10^{5} J = 1 0 5 , the algorithm does not finish within 10,000 s at either sparsity level. These results reflect the quadratic dependence on J J J in the bound O ( J 2 T log J ) O(J^{2}T\log J) O ( J 2 T log J ) , since each interval can contain up to J ( J − 1 ) J(J-1) J ( J − 1 ) crossings of two gains, approximately 1.6 × 10 9 1.6\times10^{9} 1.6 × 1 0 9 for ERA5. Hence, the sparse algorithm remains practical for instances with up to about 10 4 10^{4} 1 0 4 dimensions at both sparsity levels.
Comparison with the MINLP. Gurobi solves the MINLP to its default relative gap of 0.01% only on the NASA C-MAPSS instances and on the simulated instances with J ≤ 100 J \le100 J ≤ 100 in the dense problem and J ≤ 20 J \le20 J ≤ 20 in the sparse problem, at both 20% and 10% sparsity levels. On these instances, our algorithms obtain objective values no worse than Gurobi’s, and are faster by factors ranging from approximately 8.9 × 10 3 8.9 \times10^{3} 8.9 × 1 0 3 to 3.4 × 10 6 3.4 \times10^{6} 3.4 × 1 0 6 . On all other instances, Gurobi reaches the time limit of 10,000 s with gaps between 0.22% and 100%. Its best solution matches ours only on the dense simulated instance with J = 1000 J = 1000 J = 1000 and is otherwise worse, for example by 5.4% on the dense ERA5 instance and by 69% on the dense simulated instance with J = 10 5 J = 10^{5} J = 1 0 5 . For the sparse simulated instance with J = 10 5 J = 10^{5} J = 1 0 5 , neither method finishes within 10,000 s at either sparsity level.
Conclusion
We studied the problem of fitting continuous piecewise-linear functions with a single breakpoint shared by all dimensions of a multidimensional time series, where the breakpoint varies continuously. We showed that this problem is solvable in polynomial time under the ℓ 1 \ell_{1} ℓ 1 , ℓ 2 \ell_{2} ℓ 2 , and ℓ ∞ \ell_{\infty} ℓ ∞ losses, both in the dense setting and in the sparse setting, in which at most k k k dimensions may change slope. Since optimal breakpoints can be irrational, we specified what it means to solve the problem exactly. Our algorithms return an optimal breakpoint as a real algebraic number, of degree at most two for p ∈ { 2 , ∞ } p \in\{2,\infty\} p ∈ { 2 , ∞ } and of degree bounded in terms of J J J or k k k for p = 1 p = 1 p = 1 , and they return the fitting coefficients as rational functions of it. All six variants are handled by the same strategy, which involves reduction to intervals between consecutive observations, decoupling of the dimensions for a fixed breakpoint, a description of each dimension-wise optimal error as a function of the breakpoint, and aggregation of these functions over the dimensions.
For the least-squares loss, the algorithms are also practical. On simulated data and on climate, hand-tracking, and turbofan data, the dense algorithm solved every instance, with up to 10 7 10^{7} 1 0 7 observations, in less than 0.1 s, and the sparse algorithm solved instances with about a thousand dimensions in less than a second. In particular, the dense algorithm is fast enough to solve the problem again each time a new observation arrives, which makes exact least-squares fitting usable for online slope change detection. A state-of-the-art MINLP solver, applied to an exact mixed-integer formulation, solved only the smallest instances within 10,000 s and otherwise ended with large optimality gaps.
Several questions remain open. The sparse algorithm took approximately 2.5 hours and 2.1 hours on the ERA5 instance with 40,401 dimensions at 20% and 10% sparsity, respectively, primarily due to the large number of pairwise crossings of the gains that must be processed. An algorithm that tracks only the crossings that change the set of the k k k largest gains could improve this substantially. For p ∈ { 1 , ∞ } p \in\{1,\infty\} p ∈ { 1 , ∞ } , our operation counts are polynomial but of high degree in T T T , and it would be valuable to find algorithms whose dependence on T T T is close to that of the least-squares case. Finally, the complexity of fitting several shared breakpoints remains open. This problem is equivalent to globally training a ReLU network with time as its input, several hidden units, and J J J outputs that share those units. It is natural to ask whether the problem stays polynomial-time solvable when the number of breakpoints is fixed, and whether it becomes NP-hard when that number is part of the input.
Acknowledgements
The authors acknowledge the use of large language models to assist in writing the code for the computational experiments in § 5 . All code was reviewed and tested by the authors, who take full responsibility for its correctness and for the reported results.
Appendix
Synthetic Data Generation
Our synthetic data generation procedure is motivated by multifactor models of asset returns [50 ] , models of time-varying volatility [13 ] , and models allowing changes in the underlying return-generating process [34 ] . We generate J J J correlated stock-price trajectories, each observed over T = 100 T = 100 T = 100 consecutive business days, with observation times x i = i − 1 x_i = i - 1 x i = i − 1 for i ∈ [ T ] i \in[T] i ∈ [ T ] .
Generating stock returns. Each stock is assigned independently to one of 20 sectors and an initial price drawn uniformly from [ 20 , 250 ] [20, 250] [ 20 , 250 ] . Its daily log-return is generated as
R ~ j , t = μ j , t + γ j M R t M + γ j G R g j , t G + σ j v j , t ϵ j , t , (5) \widetilde{R}_{j,t} = \mu_{j,t} + \gamma_j^M R_t^M + \gamma_j^G R_{g_j,t}^G + \sigma_j v_{j,t} \epsilon_{j,t}, \tag*{(5)} R j , t = μ j , t + γ j M R t M + γ j G R g j , t G + σ j v j , t ϵ j , t , (5)
where R t M R_t^M R t M represents market-wide fluctuations, R g j , t G R_{g_j,t}^G R g j , t G represents fluctuations shared by stocks in sector g j g_j g j , and ϵ j , t \epsilon_{j,t} ϵ j , t represents independent stock-specific Gaussian noise. The coefficients γ j M \gamma_j^M γ j M , γ j G \gamma_j^G γ j G and σ j \sigma_j σ j control the contribution of these components. The market and stock-specific volatility factors vary over time based on preceding shocks, allowing periods of higher and lower variability. Thus, stocks are correlated through shared market and sector fluctuations while retaining stock-specific variability.
Introducing changes. Each stock independently undergoes a change in its baseline drift (the average daily log-return) with probability 0.70. For each stock, a potential change time is sampled from a normal distribution centered at 52% of the observation period, with a standard deviation of 10% of its length. The sampled time is rounded to an integer and restricted to lie away from the endpoints. The daily drift is then given by
μ j , t = μ j + κ j I { t > τ j } , (6) \mu_{j,t} = \mu_j + \kappa_j \mathbb{I}\{t > \tau_j\}, \tag*{(6)} μ j , t = μ j + κ j I { t > τ j } , (6)
where τ j \tau_j τ j is the change time and κ j ∼ N ( 0 , 0.0015 2 ) \kappa_j \sim\mathcal{N}(0, 0.0015^2) κ j ∼ N ( 0 , 0.001 5 2 ) for stocks undergoing a change, and κ j = 0 \kappa_j = 0 κ j = 0 otherwise. Thus, different stocks may experience changes at different times and of different magnitudes.
Constructing prices. The generated daily log-returns are capped to [ − 0.18 , 0.18 ] [-0.18, 0.18] [ − 0.18 , 0.18 ] to limit extreme daily fluctuations. Prices are then computed recursively as
P j , t + 1 = P j , t exp ( R j , t ) , R j , t = clip ( R ~ j , t , − 0.18 , 0.18 ) , (7) P_{j,t+1} = P_{j,t} \exp(R_{j,t}), \qquad R_{j,t} = \operatorname{clip}(\widetilde{R}_{j,t}, -0.18, 0.18), \tag*{(7)} P j , t + 1 = P j , t exp ( R j , t ) , R j , t = clip ( R j , t , − 0.18 , 0.18 ) , (7)
where clip ( a , l , u ) : = min { max { a , l } , u } \operatorname{clip}(a,l,u) := \min\{\max\{a,l\},u\} clip ( a , l , u ) := min { max { a , l } , u } . The resulting observations are y i j = P j , i y_i^j = P_{j,i} y i j = P j , i . The dense and sparse experiments use the same generation procedure, with J J J and k k k specified in Table 2 . The complete implementation, including the parameter distributions and volatility updates, is available at: https://github.com/ApoorvaGOR/High-Dimensional-Piecewise-Linear-Fitting/blob/main/data_simulator.py.
Relation to the optimization model. These data are not generated from the continuous piecewise-linear model (2) . Changes occur in the drift of log-returns rather than directly in price slopes, and their locations may differ across stocks. This allows us to evaluate our algorithms on noisy, correlated time series that do not necessarily satisfy the assumed shared-breakpoint model.
A Mixed-Integer Nonlinear Formulation and Its Big-M M M Constants
We state a mixed-integer nonlinear programming (MINLP) formulation of (2) for p = 2 p=2 p = 2 and describe its parameter bounds and big-M M M constants. The construction follows [47 ] .
Formulation
For each dimension j ∈ [ J ] j \in[J] j ∈ [ J ] and segment ℓ ∈ { 1 , 2 } \ell\in\{1,2\} ℓ ∈ { 1 , 2 } , let m ℓ j m_{\ell}^{j} m ℓ j and c ℓ j c_{\ell}^{j} c ℓ j be the slope and the intercept of the affine function on segment ℓ \ell ℓ , where segment 1 lies before the breakpoint and segment 2 after it. In the notation of (1) , m 1 j = β j m_{1}^{j}=\beta_{j} m 1 j = β j , c 1 j = α j c_{1}^{j}=\alpha_{j} c 1 j = α j , m 2 j = β j + δ j m_{2}^{j}=\beta_{j}+\delta_{j} m 2 j = β j + δ j , and c 2 j = α j − δ j z c_{2}^{j}=\alpha_{j}-\delta_{j}z c 2 j = α j − δ j z . Let y ^ i j \hat{y}_{i}^{j} y ^ i j be the fitted value of dimension j j j at time x i x_{i} x i , and let the binary variable X i X_{i} X i equal 1 if observation i i i is assigned to segment 1 and 0 if it is assigned to segment 2. The dense formulation is
min ∑ i ∈ [ T ] ∑ j ∈ [ J ] ( y i j − y ^ i j ) 2 (8) \min\sum_{i\in[T]}\sum_{j\in[J]}(y_{i}^{j}-\hat{y}_{i}^{j})^{2} \tag*{(8)} min i ∈ [ T ] ∑ j ∈ [ J ] ∑ ( y i j − y ^ i j ) 2 (8)
s.t. − M 1 , i j ( 1 − X i ) ≤ y ^ i j − m 1 j x i − c 1 j ≤ M 1 , i j ( 1 − X i ) , i ∈ [ T ] , j ∈ [ J ] , − M 1 , i j X i ≤ y ^ i j − m 2 j x i − c 2 j ≤ M 1 , i j X i , i ∈ [ T ] , j ∈ [ J ] , m 1 j z + c 1 j = m 2 j z + c 2 j , j ∈ [ J ] , x i ≤ z + M 2 , i ( 1 − X i ) , i ∈ [ T ] , x i ≥ z − M 3 , i X i , i ∈ [ T ] , X i ≥ X i + 1 , i ∈ [ T − 1 ] , ( m , c , z ) ∈ Θ , X ∈ { 0 , 1 } T . (9) \begin{aligned}
\text{s.t.}\quad&-M_{1,ij}(1-X_{i})\leq\hat{y}_{i}^{j}-m_{1}^{j}x_{i}-c_{1}^{j}\leq M_{1,ij}(1-X_{i}), && i\in[T],\ j\in[J],\\
&-M_{1,ij}X_{i}\leq\hat{y}_{i}^{j}-m_{2}^{j}x_{i}-c_{2}^{j}\leq M_{1,ij}X_{i}, && i\in[T],\ j\in[J],\\
&m_{1}^{j}z+c_{1}^{j}=m_{2}^{j}z+c_{2}^{j}, && j\in[J],\\
&x_{i}\leq z+M_{2,i}(1-X_{i}), && i\in[T],\\
&x_{i}\geq z-M_{3,i}X_{i}, && i\in[T],\\
&X_{i}\geq X_{i+1}, && i\in[T-1],\\
&(m,c,z)\in\Theta,\quad X\in\{0,1\}^{T}. \tag*{(9)}
\end{aligned} s.t. − M 1 , ij ( 1 − X i ) ≤ y ^ i j − m 1 j x i − c 1 j ≤ M 1 , ij ( 1 − X i ) , − M 1 , ij X i ≤ y ^ i j − m 2 j x i − c 2 j ≤ M 1 , ij X i , m 1 j z + c 1 j = m 2 j z + c 2 j , x i ≤ z + M 2 , i ( 1 − X i ) , x i ≥ z − M 3 , i X i , X i ≥ X i + 1 , ( m , c , z ) ∈ Θ , X ∈ { 0 , 1 } T . i ∈ [ T ] , j ∈ [ J ] , i ∈ [ T ] , j ∈ [ J ] , j ∈ [ J ] , i ∈ [ T ] , i ∈ [ T ] , i ∈ [ T − 1 ] , (9)
where the set Θ \Theta Θ and the constants M 1 , i j M_{1,ij} M 1 , ij , M 2 , i M_{2,i} M 2 , i , and M 3 , i M_{3,i} M 3 , i are defined below. The constraints (B.2) and (B.3) set y ^ i j \hat{y}_{i}^{j} y ^ i j to the value of the affine function of the segment to which observation i i i is assigned. The constraints (B.5)–(B.7) ensure that the observations of segment 1 are exactly those up to the breakpoint, with either assignment allowed for an observation at the breakpoint. The constraints (B.4) impose continuity at the breakpoint. They are bilinear, and they are the source of nonconvexity. For a fixed breakpoint z z z , every feasible point corresponds to a continuous piecewise-linear fit with breakpoint z z z in each dimension, and the objective (B.1) equals L 2 ( r ) L_{2}(r) L 2 ( r ) .
In the sparse problem, we add a binary variable ξ j \xi_{j} ξ j for each j ∈ [ J ] j\in[J] j ∈ [ J ] , where ξ j = 1 \xi_{j}=1 ξ j = 1 indicates that dimension j j j may change slope, and the constraints of Section B.5.
Parameter bounds
For each dimension j j j , the lower and upper slope bounds are the smallest and largest slopes between two observations,
L m j : = min i , i ′ ∈ [ T ] i ≠ i ′ y i j − y i ′ j x i − x i ′ . (10) L_{m}^{j}:=\min_{\substack{i,i'\in[T]\\i\ne i'}}\frac{y_{i}^{j}-y_{i'}^{j}}{x_{i}-x_{i'}}. \tag*{(10)} L m j := i , i ′ ∈ [ T ] i = i ′ min x i − x i ′ y i j − y i ′ j . (10)
U m j : = max i , i ′ ∈ [ T ] i ≠ i ′ y i j − y i ′ j x i − x i ′ . (11) U_{m}^{j}:=\max_{\substack{i,i'\in[T]\\i\ne i'}}\frac{y_{i}^{j}-y_{i'}^{j}}{x_{i}-x_{i'}}. \tag*{(11)} U m j := i , i ′ ∈ [ T ] i = i ′ max x i − x i ′ y i j − y i ′ j . (11)
Given these slope bounds, the intercept bounds are
L c j : = min i ∈ [ T ] min { y i j − L m j x i , y i j − U m j x i } . (12) L_c^j := \min_{i\in[T]} \min\left\{y_i^j-L_m^j x_i,\ y_i^j-U_m^j x_i\right\}. \tag*{(12)} L c j := i ∈ [ T ] min min { y i j − L m j x i , y i j − U m j x i } . (12)
U c j : = max i ∈ [ T ] max { y i j − L m j x i , y i j − U m j x i } . (13) U_c^j := \max_{i\in[T]} \max\left\{y_i^j-L_m^j x_i,\ y_i^j-U_m^j x_i\right\}. \tag*{(13)} U c j := i ∈ [ T ] max max { y i j − L m j x i , y i j − U m j x i } . (13)
For every j ∈ [ J ] j\in[J] j ∈ [ J ] and ℓ ∈ { 1 , 2 } \ell\in\{1,2\} ℓ ∈ { 1 , 2 } , we impose
L m j ≤ m ℓ j ≤ U m j , L c j ≤ c ℓ j ≤ U c j . (14) L_m^j\le m_\ell^j\le U_m^j,\qquad L_c^j\le c_\ell^j\le U_c^j. \tag*{(14)} L m j ≤ m ℓ j ≤ U m j , L c j ≤ c ℓ j ≤ U c j . (14)
The breakpoint is restricted to x 2 ≤ z ≤ x T − 1 x_2\le z\le x_{T-1} x 2 ≤ z ≤ x T − 1 , as in (2) , so that at least two observations lie on each side of the breakpoint. Hence
Θ : = { ( m , c , z ) : L m j ≤ m ℓ j ≤ U m j , L c j ≤ c ℓ j ≤ U c j for all j ∈ [ J ] , ℓ ∈ { 1 , 2 } , x 2 ≤ z ≤ x T − 1 } . (15) \Theta:=\left\{(m,c,z): L_m^j\le m_\ell^j\le U_m^j,\ L_c^j\le c_\ell^j\le U_c^j\ \text{for all }j\in[J],\ \ell\in\{1,2\},\ x_2\le z\le x_{T-1}\right\}. \tag*{(15)} Θ := { ( m , c , z ) : L m j ≤ m ℓ j ≤ U m j , L c j ≤ c ℓ j ≤ U c j for all j ∈ [ J ] , ℓ ∈ { 1 , 2 } , x 2 ≤ z ≤ x T − 1 } . (15)
The bounds defining Θ \Theta Θ are data-driven, and they are not guaranteed to contain an optimal solution of (2) , whose slopes and intercepts are unrestricted. Hence the formulation (B.1)–(B.8) is a restriction of (2) , and its optimal value is at least O P T 2 , k \mathrm{OPT}_{2,k} OPT 2 , k . The two values are equal if some optimal solution of (2) lies in Θ \Theta Θ . This can be checked using the solution returned by the algorithms of § 3 and § 4 .
Big-M M M constants for the fitted values
For i ∈ [ T ] i\in[T] i ∈ [ T ] and j ∈ [ J ] j\in[J] j ∈ [ J ] , let
f ‾ i j : = min { L m j x i , U m j x i } + L c j (16) \underline{f}_{ij}:=\min\left\{L_m^j x_i,U_m^j x_i\right\}+L_c^j \tag*{(16)} f ij := min { L m j x i , U m j x i } + L c j (16)
f ‾ i j : = max { L m j x i , U m j x i } + U c j . (17) \overline{f}_{ij}:=\max\left\{L_m^j x_i,U_m^j x_i\right\}+U_c^j. \tag*{(17)} f ij := max { L m j x i , U m j x i } + U c j . (17)
For every ( m , c , z ) ∈ Θ (m,c,z)\in\Theta ( m , c , z ) ∈ Θ and ℓ ∈ { 1 , 2 } \ell\in\{1,2\} ℓ ∈ { 1 , 2 } , we have m ℓ j x i ∈ [ min { L m j x i , U m j x i } , max { L m j x i , U m j x i } ] m_\ell^j x_i\in\left[\min\left\{L_m^j x_i,U_m^j x_i\right\},\max\left\{L_m^j x_i,U_m^j x_i\right\}\right] m ℓ j x i ∈ [ min { L m j x i , U m j x i } , max { L m j x i , U m j x i } ] , and therefore
f ‾ i j ≤ m ℓ j x i + c ℓ j ≤ f ‾ i j . (18) \underline{f}_{ij}\le m_\ell^j x_i+c_\ell^j\le\overline{f}_{ij}. \tag*{(18)} f ij ≤ m ℓ j x i + c ℓ j ≤ f ij . (18)
Let
M 1 , i j : = f ‾ i j − f ‾ i j . (19) M_{1,ij}:=\overline{f}_{ij}-\underline{f}_{ij}. \tag*{(19)} M 1 , ij := f ij − f ij . (19)
At every feasible point, y ^ i j \widehat{y}_i^j y i j equals m ℓ j x i + c ℓ j m_\ell^j x_i+c_\ell^j m ℓ j x i + c ℓ j for the segment ℓ \ell ℓ to which observation i i i is assigned, so f ‾ i j ≤ y ^ i j ≤ f ‾ i j \underline{f}_{ij}\le\widehat{y}_i^j\le\overline{f}_{ij} f ij ≤ y i j ≤ f ij by (B.17). Hence, for the other segment ℓ ′ \ell' ℓ ′ , (B.17) gives
∣ m ℓ ′ j x i + c ℓ ′ j − y ^ i j ∣ ≤ M 1 , i j . (20) \left|m_{\ell'}^j x_i+c_{\ell'}^j-\widehat{y}_i^j\right|\le M_{1,ij}. \tag*{(20)} m ℓ ′ j x i + c ℓ ′ j − y i j ≤ M 1 , ij . (20)
Thus the assignment constraint of the segment to which observation i i i is not assigned is satisfied automatically, and M 1 , i j M_{1,ij} M 1 , ij is a valid big-M M M constant in (B.2) and (B.3).
Big-M M M constants for the breakpoint
Since x 2 ≤ z ≤ x T − 1 x_2\le z\le x_{T-1} x 2 ≤ z ≤ x T − 1 , valid constants for (B.5) and (B.6) are
M 2 , i : = max { 0 , x i − x 2 } , i ∈ [ T ] , (21) M_{2,i}:=\max\{0,x_i-x_2\},\qquad i\in[T], \tag*{(21)} M 2 , i := max { 0 , x i − x 2 } , i ∈ [ T ] , (21)
M 3 , i : = max { 0 , x T − 1 − x i } , i ∈ [ T ] . (22) M_{3,i}:=\max\{0,x_{T-1}-x_i\},\qquad i\in[T]. \tag*{(22)} M 3 , i := max { 0 , x T − 1 − x i } , i ∈ [ T ] . (22)
If X i = 1 X_i=1 X i = 1 , then (B.5) enforces x i ≤ z x_i\le z x i ≤ z , and (B.6) reads x i ≥ z − M 3 , i x_i\ge z-M_{3,i} x i ≥ z − M 3 , i , which holds since z ≤ x T − 1 z\le x_{T-1} z ≤ x T − 1 . If X i = 0 X_i=0 X i = 0 , then (B.6) enforces x i ≥ z x_i\ge z x i ≥ z , and (B.5) reads x i ≤ z + M 2 , i x_i\le z+M_{2,i} x i ≤ z + M 2 , i , which holds since z ≥ x 2 z\ge x_2 z ≥ x 2 . The monotonicity constraints (B.7) ensure that the observations of each segment form a contiguous block.
Constraints and Big-M M M constants for the sparse problem
The bounds (B.13) imply
∣ m 2 j − m 1 j ∣ ≤ U m j − L m j , ∣ c 2 j − c 1 j ∣ ≤ U c j − L c j . (23) \lvert m_2^j-m_1^j\rvert\le U_m^j-L_m^j,\qquad\lvert c_2^j-c_1^j\rvert\le U_c^j-L_c^j. \tag*{(23)} ∣ m 2 j − m 1 j ∣ ≤ U m j − L m j , ∣ c 2 j − c 1 j ∣ ≤ U c j − L c j . (23)
Hence valid big-M M M constants are
M m j : = U m j − L m j , M c j : = U c j − L c j , (24) M_m^j := U_m^j-L_m^j,\qquad M_c^j := U_c^j-L_c^j, \tag*{(24)} M m j := U m j − L m j , M c j := U c j − L c j , (24)
and the sparse constraints are
− M m j ξ j ≤ m 2 j − m 1 j ≤ M m j ξ j , j ∈ [ J ] , (25) -M_m^j\xi_j \le m_2^j-m_1^j \le M_m^j\xi_j,\qquad j\in[J], \tag*{(25)} − M m j ξ j ≤ m 2 j − m 1 j ≤ M m j ξ j , j ∈ [ J ] , (25)
− M c j ξ j ≤ c 2 j − c 1 j ≤ M c j ξ j , j ∈ [ J ] , (26) -M_c^j\xi_j \le c_2^j-c_1^j \le M_c^j\xi_j,\qquad j\in[J], \tag*{(26)} − M c j ξ j ≤ c 2 j − c 1 j ≤ M c j ξ j , j ∈ [ J ] , (26)
∑ j ∈ [ J ] ξ j ≤ k , (27) \sum_{j\in[J]}\xi_j\le k, \tag*{(27)} j ∈ [ J ] ∑ ξ j ≤ k , (27)
ξ j ∈ { 0 , 1 } , j ∈ [ J ] . (28) \xi_j\in\{0,1\},\qquad j\in[J]. \tag*{(28)} ξ j ∈ { 0 , 1 } , j ∈ [ J ] . (28)
If ξ j = 0 \xi_j=0 ξ j = 0 , these constraints enforce m 1 j = m 2 j m_1^j=m_2^j m 1 j = m 2 j and c 1 j = c 2 j c_1^j=c_2^j c 1 j = c 2 j , so dimension j j j is fitted by a single line, that is, δ j = 0 \delta_j=0 δ j = 0 . If ξ j = 1 \xi_j=1 ξ j = 1 , they impose no restriction beyond (B.13).