Bounded L1 Regression for Fitting One Time Series to Two Others
Summary
The document formulates a fit between a target time series and a linear combination of two other series. It minimizes the sum of absolute residuals, the L1 norm, while constraining both coefficients to lie between minus one and one. This differs from ordinary least squares, which minimizes squared residuals and can respond more strongly to large errors.
The answer identifies the problem as convex optimization because the objective is an L1 norm of an affine expression and the coefficient limits are affine constraints. It outlines two solution routes: use a general convex optimization package, or introduce nonnegative residual-bound variables and express the objective and constraints as a linear program. The response notes that multiple solver options exist and that a two-coefficient problem is small, but it does not compare solvers or provide an R implementation. The strict inequalities in the original question are represented as inclusive bounds in the proposed formulation.
Key ideas
- The objective is the sum of absolute residuals between the target series and a weighted combination of two predictors.
- Coefficient bounds can be expressed as linear constraints on the optimization variables.
- L1 minimization with affine constraints forms a convex optimization problem.
- Introducing variables that bound each residual’s absolute value converts the task into a linear program.
- The answer describes solver approaches but does not supply R-specific code.
Tags
Full text
# How to find coefficient that will minimize the distance between few times series
# How to find coefficient that will minimize the distance between few times series
I have 3 time series X1, X2, X3. I want to find the coefficient (c1, c2) that will minimize the distance between them as follow: $$MIN\sum\sqrt{(X1-(c1*X2+c2*X3))^2}$$
The constrains are: $$-1< c1,c2 < 1$$
How can I do it in R?
## Answer by Matthew Gunn (score 3, accepted)
https://quant.stackexchange.com/a/35153
Define $\|.\|_1$ as the $L_1$ norm. I'll use bold letters to denote vectors and I'm using $\mathbf{y} = \mathbf{x}_1$. Your problem is:
\begin{equation} \begin{array}{*2{>{\displaystyle}r}} \mbox{minimize (over $c_1, c_2$)} & \| \mathbf{y} - c_1 \mathbf{x}_2 - c_2 \mathbf{x}_3 \|_1 \\ \mbox{subject to} & -1 \leq c_1 \leq 1\\ & -1 \leq c_2 \leq 1 \end{array} \end{equation}
Or let matrix $X = \begin{bmatrix} \mathbf{x}_2 & \mathbf{x}_3 \end{bmatrix}$ . The problem can be written more succinctly as: \begin{equation} \begin{array}{*2{>{\displaystyle}r}} \mbox{minimize (over $\mathbf{c}$)} & \| X \mathbf{c} - \mathbf{y} \|_1 \\ \mbox{subject to} & \mathbf{c} \preceq \mathbf{1} \\ & -\mathbf{c} \preceq \mathbf{1} \end{array} \end{equation}
Minimizing the $L_1$ norm subject to affine constraints is a convex optimization problem. There are a multitude of approaches to solve this problem, and since it's only in two variables, it's quite trivial to solve. Any general purpose optimization library can probably solve this without issues.
Below is a short list of things you can do. It is not an exhaustive list.
## Option 1: Use CVX to solve this problem:
I'm just mentioning this because I know it well. There are ways to call CVX from R but it might be inconvenient. If you were in MATLAB or Python you could do something like:
```
%% initialize code (currently matlab code)
n = 200;
y = randn(n, 1);
X = randn(n, 2);
%% CVX CODE
cvx_begin
variables c(2);
minimize(norm(y - X * c, 1))
subject to:
-1 <= c
c <= 1
cvx_end
```
### Option 2: Rewrite the problem as a linear program.
By introducing a vector $\mathbf{s} \in \mathbb{R}^n$, the $L_1$ norm minimization problem can be written as a linear program:
\begin{equation} \begin{array}{*2{>{\displaystyle}r}} \mbox{minimize (over $\mathbf{c}, \mathbf{s}$)} & \mathbf{1}'\mathbf{s} \\ \mbox{subject to} & \mathbf{c} \preceq \mathbf{1} \\ & -\mathbf{c} \preceq \mathbf{1} \\ & X\mathbf{c} - \mathbf{y} \preceq \mathbf{s} \\ & -X\mathbf{c} + \mathbf{y} \preceq \mathbf{s} \end{array} \end{equation}
There are numerous solvers in R for linear programs.Shown in full with attribution under the source's licence. Licence: CC BY-SA 4.0 (Stack Exchange)
This summary was written by Stratmill's research agent from the original; it is not a copy of the source.