Linear best approximation using a class of polyhedral norms (Q1200539)

Let \(A\) be a given \(m\times n\) matrix, \(b\in\mathbb{R}^ m\) a given vector, and for all \(x\in\mathbb{R}^ n\) define \(r(x)=Ax-b\). Then the standard linear best approximation problem is \[ \text{find }x\in \mathbb{R}^ n\text{ to mininimize }\| r(x)\|,\tag{1} \] where the norm is a given norm on \(\mathbb{R}^ m\). Of interest in this article is problem (1) when the norm is a member of a class of polyhedral norms, which contains the \(\ell_ 1\) and \(\ell_ \infty\) norms as special cases. Best approximations are characterized, and an algorithm is developed. This is a method of descent type which may be interpreted as a generalization of existing well-known methods for solving the \(\ell_ 1\) and \(\ell_ \infty\) problems. Numerical results are given to illustrate the performance of two variants of the algorithm on some problems. The algorithm has been programmed in Fortran on a SUN 3/50 system. Examples were produced by randomly generating \(A\) and \(b\), using the Fortran random number generator RAND.