How to solve for $x$ by minimizing infinity norm: $\arg \min_{x} \left\{\|y - Ax\|_{\infty}\right\}$?

Question

$y$ and $x$ are vectors and $A$ is a $m$ x $n$ matrix such that $n$ > $m$

Answer 1

You can transfer this into a linear optimization problem: $$ \min t $$ subject to $$ -t \le y_i - (Ax)_i \le t. $$ Then solve this problem using a standard method (e.g., simplex method).