Calculating the $L_{\infty}$ regressionin Matlab

Question

I have the following problem: suppose, I have IID $(x_t,y_t)$ variable, where let's say $t=1,...,N$.

My task is to solve the following optimization problem:

$$\min_{\theta=[\theta_1,...,\theta_q]} \max_{t=1,...,N} |y_t-f(x_t)^T \theta|$$

I have looked up a bunch of articles about the $L_\infty$ regression and how to implement it in Matlab, and I am convinced that I need to use the CVX package.

I would be more then happy if I could solve this following example: let us have $x_1=1, x_2=2, x_3=3, y_1=0, y_2=1, y_3=2$.

What do I need to plot if I want to solve this polynomial problem?

$$\min_{\theta=[\theta_1,\theta_2]} \max_{t=1,2,3} |y_t-(\theta_1+\theta_2x_t)|$$

I have tried the following but I cant really progress:

X = [ 0 1 2 ];

Y = [ 1 2 3 ];

cvx_begin variable A minimize(norm(Y-A+A*X,inf)) cvx_end

Thanks in advance!

Answer 1

X = [0 1 2]';
Y = [1 2 3]';
cvx_begin
variable theta(2)
minimize(norm(Y - [ones(3,1) X]*theta,inf))
cvx_end

The optimal solution to your example is theta = [1 1]', which produces optimal objective value of zero, because there is a perfect fit. And in this example, this theta would be optimal for any norm, not just inf.

But for instance, if Y were instead [1 4 2]', there is no perfect fit with this functional form, and the optimal theta for the 1, 2, and inf norms would respectively be [1 0.5]', [1.833 0.5]', [2.25 0.5]'.