Linear best approximation using a class of polyhedral norms
type: Item
instance of: scholarly article
title: Linear best approximation using a class of polyhedral norms
zbMATH Open document ID: 0755.65011
DOI: 10.1007/BF02139472
published in: Numerical Algorithms
publication date: 1993-01-16T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 65D10
Mathematics Subject Classification ID: 65F30
Mathematics Subject Classification ID: 41A65
zbMATH DE Number: 95467
zbMATH Keywords: descent method
zbMATH Keywords: linear best approximation problem
zbMATH Keywords: polyhedral norms
zbMATH Keywords: algorithm
zbMATH Keywords: Numerical results
author: G. A. Watson
reviewed by: G. Dimitriu
MaRDI profile type: Publication
cites work: Discrete, linear approximation problems in polyhedral norms
cites work: On Cline’s Direct Method for Solving Overdetermined Linear Systems in the $L_\infty $ Sense
cites work: Minimization Techniques for Piecewise Differentiable Functions: The $l_1$ Solution to an Overdetermined Linear System
cites work: Q3690974
cites work: Convex Analysis
cites work: Q3885038
full work available at URL: https://doi.org/10.1007/bf02139472
OpenAlex ID: W2017740898
Recommended article: Q4016591
Recommended article: Best approximation in certain classes of normed linear spaces
Recommended article: Q3737972
Recommended article: Linear best approximation using a class of \(k\)-major \(l_ p\) norms
Recommended article: Q4717580
Recommended article: Q3320829
Recommended article: Q4010405
Recommended article: Best Polynomial Approximation with Linear Constraints
Recommended article: LINEAR ESTIMATES OF THE BEST LP -APPROXIMATION BY POLYNOMIALS
Recommended article: Q4884018
description: scientific article; zbMATH DE number 95467