L1-Optimal Splines for Outlier Rejection∗
Masaaki Nagahara1† and Clyde F. Martin2
1
Kyoto University, Kyoto JAPAN†
Corresponding author, e-mail: nagahara@ieee.org
2Texas Tech University, Texas, USAAbstract
In this article, we consider control theoretic splines with L1 optimization for rejecting outliers in data. Control theoretic splines areeither interpolating or smoothing splines, depending on a cost function with a constraint defined by linear differential equations. Control
theoretic splines are effective for Gaussian noise in data since the estimation is based on L2 optimization. However, in practice, there may
be outliers in data, which may occur with vanishingly small probability
under the Gaussian assumption of noise, to which L2 -optimized spline
regression may be very sensitive. To achieve robustness against outliers, we propose to use L1 optimality, which is also used in support
vector regression. A numerical example shows the effectiveness of theproposed method.

Keywords: control theoretic splines, smoothing, L1 optimization, outlier
rejection, support vector regression, convex optimization

1Introduction

Control theoretic spline is generalization of the smoothing spline proposedin Kimeldorf & Wahba (1971), Wahba (1990), using control theoretic ideas,
by which the spline curve is determined by the output of a linear control
system. Control theoretic splines give a richer class of smoothing curves
relative to polynomial curves. They have been proved to be useful for trajectory planning in Egerstedt & Martin (2001), mobile robots in Takahashi& Martin (2004), contour modeling of images in Kano et al. (2008), probability distribution estimation in Charles et al. (2010), to name a few. For∗This research is supported in part by the JSPS Grant-in-Aid for Scientific Research(C) No. 24560543

more applications and a rather complete theory of control theoretic splines,
see Egerstedt & Martin (2010).
Control theoretic splines are effective for reducing Gaussian noise in data
since the estimation is based on L2 optimization. This means that the noise
distribution is assumed to decay very rapidly as the amplitude increases
2(∝ e−|x| /2 ). However, in practice, there may exist outliers in data, which
may occur with vanishingly small probability under the assumption of theGaussian distribution of noise. To such noise, L2 -optimized spline regression
may be very sensitive.
Instead, we adopt L1 optimality for regression to achieve robustness
against outliers. That is, we assume Laplacian distribution for noise, which
is distributed much more slowly (∝ e−|x| ) than Gaussian tails. This is related
to support vector regression (SVR) (see e.g. Schölkopf & Smola (2002)),
which can be reduced to convex optimization that can be efficiently solved
by numerical optimization (see e.g. Boyd & Vandenberghe (2004)).

2L1 -Optimal Splines

Consider the following linear system P :(ẋ(t) = Ax(t) + bu(t),P :y(t) = c> x(t),t ∈ [0, ∞).

(1)

where A ∈ Rn×n , b, c ∈ Rn , x(0) = 0 ∈ Rn . We assume (A, b) is controllableand (c> , A) is observable. For this system, suppose that we are given data
D := {(t1 , y1 ), (t2 , y1 ), . . . (tN , yN )}, where t1 , . . . , tN are sampling instants
which satisfy 0 < t1 < t2 < · · · < tN =: T . The objective here is to findthe control input u(t), t ∈ [0, T ] for the system (1) such that y(ti ) ≈ yi for
i = 1, . . . , N . For this purpose, the following quadratic cost function has
been introduced in Sun et al. (2000), Egerstedt & Martin (2010):
Z T

2|u(t)| dt +Jq (u) := λ0NX

wi (y(ti ) − yi )2 ,(2)i=1where λ > 0 is the regularization parameter that specifies the tradeoff between the smoothness of u defined in the first term of (2) and the minimization of the empirical risk in the second term. Also, wi > 0 is a weightfor i-th empirical risk. The optimal control u = u∗q that minimizes Jq (u) isgiven by Sun et al. (2000), Egerstedt & Martin (2010) asu∗q (t) =NXθq∗ [i]gi (t),

(3)

i=1

where gi (t) is defined by(c> eA(ti −t) b,gi (t) :=0,if ti > t,if ti ≤ t,

(4)

and the optimal coefficients θq [1], . . . , θq [N ] are given by given by>θ ∗q := θq∗ [1], . . . , θq∗ [N ] = (λW −1 + G)−1 y,(5)where y := [y1 , . . . , yN ]> . The matrix G in (5) is the Grammian defined by
Gij = hgi , gj i, i, j = 1, . . . , N .
In (2), the empirical risk (the second term) is measured by L2 norm. Thisis based on the assumption that the noise added to the data is Gaussian.
However, there may exist outliers in data, which may be ignored under theGaussian assumption of noise. To such outliers, the regression may be very
sensitive.
To overcome this, we introduce the following distribution function instead of Gaussian, called -insensitive function (see Schölkopf & Smola(2002)):1p(ξ) =exp(−|ξ| ),(6)2(1 + )where  > 0 is a fixed parameter and |ξ| := max(|ξ| − , 0). The distribution
is an ”insensitive” version of the Laplace distribution, which is given bysetting  = 0.
The distribution (6) has heavier tails than the Gaussian distribution,and hence leads to more robust regression against outliers. Assuming thisdistribution, we introduce the following cost function:NX1
θ > ϕ i − yi  ,J := kθk22 + C2(7)i=1where C > 0 is the regularization parameter and ϕi := [Gi1 , Gi2 , . . . , GiN ]> .
The optimization above can be effectively solved by employing the methodof support vector regression (see Schölkopf & Smola (2002)). That is, they
5
4
3
2
10−1
00.5

1

1.5

2

2.5

3

3.5

4

4.5

5

Figure 1: Original curve y(t) = sin 2t (dashed line), sampled data D (circles),reconstructed curves via L1 optimization (solid line) and via L2 optimization(dash-dotted line).
optimization is reduced to the following convex optimization:
NX
1minimize kθk22 + C
ξi + ξˆi
2i=1>

subject to yi ≤ θ ϕi +  + ξi , yi ≥ θ > ϕi −  − ξˆi , ξi ≥ 0, ξˆi ≥ 0.

3Example

We here show an example. Let us consider a linear system (1) with
 

0 1
1
A=, b=, c> = 0 1 .
1 001
Note that this system has its transfer function as P (s) = (s+1)(s−1). Thesampling instants are taken by ti = 0.1 + (i − 1) × 0.25, i = 1, 2, . . . , 21, andthe data yi is generated by yi = sin 2ti + ei , where e1 , . . . , e21 are noise andincluding an outlier at t7 = 1.6 as shown in Fig. 1.
With these data, we compute two kinds of control; the proposed control u∗ with θ = θ ∗ minimizing J in (7), and the conventional L2 -optimal

error
2
1.8
1.6
1.4
1.2
1
0.8
0.6
0.4
0.2
0
0

0.5

1

1.5

2

2.5

3

3.5

4

4.5

5Figure 2: Regression error via L1 optimization (solid line) and via L2 optimization (dash-dotted line).
control u∗q minimizing Jq in (2). The regression result is shown in Fig. 1.
Fig. 2 also shows the regression error. We can see that the conventional
L2 -optimal regression shows high sensitivity to the outlier and around there
the regression error becomes very large. On the other hand, the result by
the proposed L1 optimization shows much more robust regression.

4Conclusion

In this article, we have proposed outlier rejection for control theoretic splines
based on L1 optimization. While conventional L2 -based splines are effectivefor Gaussian noise, they are very sensitive to outliers. To achieve robustness
against them, we have propose to adopt L1 optimality in the regression. A
numerical example has shown the effectiveness of our method. Future works
include to design constrained splines as discussed in Nagahara & Martin(2013), and to investigate the sparsity property of L1 -optimal splines as inNagahara & Quevedo (2011), Nagahara, Matsuda & Hayashi (2012), Nagahara, Quevedo & Østergaard (2012).

ReferencesBoyd, S. & Vandenberghe, L. (2004), Convex Optimization, Cambridge University Press.
Charles, J. K., Sun, S. & Martin, C. F. (2010), Cumulative distribution
estimation via control theoretic smoothing splines, in ‘Three Decades ofProgress in Control Sciences’, Springer, pp. 83–92.
Egerstedt, M. & Martin, C. (2010), Control Theoretic Splines, Princeton
University Press.
Egerstedt, M. & Martin, C. F. (2001), ‘Optimal trajectory planning andsmoothing splines’, Automatica 37(7), 1057–1064.
Kano, H., Egerstedt, M., Fujioka, H., Takahashi, S. & Martin, C. F. (2008),‘Periodic smoothing splines’, Automatica 44(1), 185–192.
Kimeldorf, G. & Wahba, G. (1971), ‘Some results on Tchebycheffian spline
functions’, Journal Math. Anal. Appl. 33(1), 82–95.
Nagahara, M. & Martin, C. F. (2013), ‘Monotone smoothing splines using
general linear systems’, Asian Journal of Control 5(2), 461–468.
Nagahara, M., Matsuda, T. & Hayashi, K. (2012), ‘Compressive sampling for
remote control systems’, EICE Trans. on Fundamentals E95-A(4), 713–722.
Nagahara, M. & Quevedo, D. E. (2011), Sparse representations for packetized predictive networked control, in ‘Proc. of IFAC 18th WorldCongress’, pp. 84–89.
Nagahara, M., Quevedo, D. E. & Østergaard, J. (2012), Packetized predictive control for rate-limited networks via sparse representation, in ‘Proc.
of 51th IEEE CDC’, pp. 1362–1367.
Schölkopf, B. & Smola, A. J. (2002), Learning with Kernels, MIT Press.
Sun, S., Egerstedt, M. B. & Martin, C. F. (2000), ‘Control theoretic smoothing splines’, IEEE Trans. on Automatic Control 45(12), 2271–2279.
Takahashi, S. & Martin, C. F. (2004), Optimal control theoretic splines
and its application to mobile robot, in ‘Proc. of the 2004 IEEE CCA’,
pp. 1729–1732.
Wahba, G. (1990), Spline Models for Observational Data, SIAM.