Abstract
The
basic solutions of the linear equations
Ax = b are the solutions of subsystems corresponding to maximal nonsingular submatrices of A. The convex hull of the basic solutions is denoted by
C =
C(
A, b). Given 1 ≤
p ≤ ∞, the
l
p
-
approximate solutions of
Ax = b, denoted
x
{
p}
, are minimizers of ∥
Ax − b∥
p
. Given
M ∈
D
m
, the set of positive diagonal
m ×
m matrices, the solutions of min
x ∥
M(
Ax − b)∥
p
are called
scaled
l
p
-
approximate solutions. For 1 ≤
p
1,
p
2 ≤ ∞, the
minimum-
l
p2
-norm
l
p1
-
approximate solutions are denoted
x
{p
1}
{p
2}
. Main results:
1.
(1) If
A ∈ R
m ×
n
m
, then C contains all [some] minimum
l
p
-norm solutions, for 1 ≤
p < ∞ [
p = ∞].
2.
(2) For general A and any 1 ≤
p
1,
p
2 < ∞ the set C contains all
x
{p1}
{p2}.
3.
(3) The set of scaled
l
p
-approximate solutions, with M ranging over
D
m
, is the same for all 1 <
p < ∞.
4.
(4) The set of scaled least-squares solutions has the same closure as the set of solutions of min
x
f (|
Ax − b|), where
f:R
m
+ → R ranges over all strictly isotone functions.