Linear best approximation using a class of polyhedral norms
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.
- scientific article; zbMATH DE number 89032
- Best approximation in certain classes of normed linear spaces
- scientific article; zbMATH DE number 3971405
- Linear best approximation using a class of \(k\)-major \(l_ p\) norms
- scientific article; zbMATH DE number 952613
- scientific article; zbMATH DE number 3851671
- scientific article; zbMATH DE number 65793
- Best Polynomial Approximation with Linear Constraints
- LINEAR ESTIMATES OF THE BEST LP -APPROXIMATION BY POLYNOMIALS
- scientific article; zbMATH DE number 898127
- Convex Analysis
- Discrete, linear approximation problems in polyhedral norms
- scientific article; zbMATH DE number 3915531 (Why is no real title available?)
- scientific article; zbMATH DE number 3690528 (Why is no real title available?)
- Minimization Techniques for Piecewise Differentiable Functions: The l₁ Solution to an Overdetermined Linear System
- On Cline’s Direct Method for Solving Overdetermined Linear Systems in the $L_\infty $ Sense
- On a class of algorithms for total approximation
- On orthogonal linear \(\ell_1\) approximation
- On matrix approximation problems with Ky Fan \(k\) norms
- Linear best approximation using a class of \(k\)-major \(l_ p\) norms
- DC formulations and algorithms for sparse optimization problems
- The \(L_1\)-norm best-fit hyperplane problem
- Solving nonnegative sparsity-constrained optimization via DC quadratic-piecewise-linear approximations
- Feature selection in SVM via polyhedral \(k\)-norm
- Variational analysis of the Ky Fan k-norm
- Polytopal balls arising in optimization
- An algorithm for the best approximation by elements of a polyhedral set in banach spaces
- scientific article; zbMATH DE number 19423 (Why is no real title available?)
- scientific article; zbMATH DE number 89032 (Why is no real title available?)
- scientific article; zbMATH DE number 123308 (Why is no real title available?)
- scientific article; zbMATH DE number 125063 (Why is no real title available?)
- Deforming \(\|.\|_1\) into \(\|.\|_{\infty}\) via polyhedral norms: a pedestrian approach
- Sparse optimization via vector \(k\)-norm and DC programming with an application to feature selection for support vector machines
- Weakly invariant norms: geometry of spheres in the space of skew-Hermitian matrices
- Dual formulation of the sparsity constrained optimization problem: application to classification
- An inexact proximal DC algorithm for the large-scale cardinality constrained mean-variance model in sparse portfolio selection
- An adaptive proximal safeguarded augmented Lagrangian method for nonsmooth DC problems with convex constraints
- The largest- K -norm for general measure spaces and a DC reformulation for L 0 -constrained problems in function spaces
This page was built for publication: Linear best approximation using a class of polyhedral norms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1200539)
