Discrete Piecewise Affine Approximation
[Diskrete stückweise affine Approximation]
June 1997
Abstract. The paper investigates classical problems in approximation, the
metric projection P of the normed R^n onto a subset G of
R^n, corresponding selections, and their construction when G is a
linear subspace or a polyhedral subset of R^n.
We consider as well l_p(n)-norms, 1 <= p <= oo, as well as
polyhedral norms of R^n, and arrange more recent results
about the in general set-valued mapping P.
Moreover, the metric projection is piecewise polyhedral and globally
Lipschitz continuous with respect to the Hausdorff metric.
In l_p(n), 1 < p < oo, the metric projection is piecewise
affine and uniformly Lipschitz continuous with respect to p, i.e.,
for fixed G the Lipschitz constant does not depend on p.
If the projection is set-valued we ask for particular best approximants
and continuous selections.
The existence of continuous selections is obvious, however, their
constructions need detailed investigations.
Here we study continuous extremal point selections which turn
out to be piecewise affine and globally Lipschitz continuous in this
polyhedral setting, and also classical selections.
These are the strict best approximation which we consider in the more
general situation of polyhedral subsets G of l_oo(n),
and the least norm selection. They are all piecewise affine and globally
Lipschitz continuous, and, in addition, if G is a linear subspace, the
strict best approximation is quasi-linear with respect to G.
An elementary example in l_oo(3) demonstrates that in
general a selection does not exist which unifies the three properties
continuity, extremal point selection, and quasi linearity.
Nevertheless, the l_1(n) is an exception where a Chebyshev
perturbation always allows to construct a globally Lipschitz continuous
and piecewise affine selection which also satisfies the three properties
above.
The strict best approximation picks up this idea to construct
continuous selections by imitating the behavior of the metric
projection onto unicity subsets G. In l_oo(n) one cannot
apply perturbations, but we can carry out finitely
many iterations, each of them based on a description of the metric
projection in terms of Plücker-Graßmann
coordinates, a classification of these coordinates,
and elementary vectors. Elementary vectors of a subspace are vectors
therein which have minimal support.
If G is a linear subspace the tuples of the classification are
exactly the supports of the elementary vectors of the orthogonal
complement of G.
Hence there is a tool explicitly available which makes an excellent
match for the approximation problem in l_1(n) and
l_oo(n), and which also provides numerical approaches to selections.
Central are representations of the strict best approximation in
l_oo(n) and of continuous extremal point selections in
l_1(n) in terms of Plücker-Graßmann coordinates.
While the first case is iteratively described, the description of the
latter one is based on the interpolatory behavior of these selections.
Corresponding algorithms are formulated.
There is an elegant method to determine the Plücker-Graßmann coordinates
by a single
application of the Gauß process followed by a recursive and parallel
process. From that the elementary vectors are given by a generalized
vector product which almost does not require any further calculation.
If one is willing to determine the Plücker-Graßmann coordinates
of the subspace under consideration then the algorithms of the corresponding selections
take only few calculations what makes them effective under
repeated projections onto the same subspace.
References