Solution of overdetermined linear system in the Max norm

Question

Suppose we have an over-determined system $A x = b$, where $A \in \mathbb K_{m \times n}$ matrix, $x = (n \times 1)$ vector, and $b = (m \times 1)$ vector, $m > n$. How do we find $x$ that minimizes $\| b- A x \|_{\infty}$ ($L_{\text{inf}}$ norm)?

I was told this is equivalent to a linear programming problem, but could someone show me how this is so?

Thanks.

Answer 1

You can utilize CVX or CVX OPT which is for Python. There is an example of this on the site. The following is Matlab Optimization Toolbox

f    = [ zeros(n,1); 1          ];
Ane  = [ +A,         -ones(m,1)  ; ...
         -A,         -ones(m,1) ];
bne  = [ +b;         -b         ];
xt   = linprog(f,Ane,bne);
x_cheb = xt(1:n,:);

simply becomes the following in CVX

cvx_begin
    variable x(n)
    minimize( norm(A*x-b,Inf) )
cvx_end

Answer 2

Let the $i$th row of $A$ be $a_i^T$. Your problem is equivalent to: \begin{align} \text{minimize} &\quad t \\ \text{subject to} &\quad -t \leq a_i^T x - b_i \leq t \text{ for all } i. \end{align}

That is a linear program.

Answer 3

Hint: Note that $$\|\mathbf{v}\|_{\infty} = \max_{1 \le i \le m}{|v_i|}.$$ Consequently, minimizing $\|\mathbf{v}\|_{\infty}$ is equal to the following optimization problem: \begin{align} \text{minimize } & c\\ \text{subject to: } & -c \le v_i \le c, \text{ where } 1\le i \le m. \end{align}

Can you figure out how to transform your problem to a linear-programming problem?