An Efficient Algorithm for a Bounded Errors-in-Variables Model.
We pose and solve a parameter estimation problem in the presence of bounded data uncertainties. The problem involves a minimization step and admits a closed form solution in terms of the positive root of a secular equation.
Introduction
. Parameter estimation in the presence of data uncertainties
is a problem of considerable practical importance, and many estimators have been
proposed in the literature with the intent of handling modeling errors and measurement
noise. Among the most notable is the total least-squares method [1, 2, 3, 4],
also known as orthogonal regression or errors-in-variables method in statistics and
system identification [5]. In contrast to the standard least-squares problem, the TLS
formulation allows for errors in the data matrix. Its performance may degrade in
some situations where the effect of noise and uncertainties can be unnecessarily over-
emphasized. This may lead to overly conservative results.
Assume A 2 R m\Thetan is a given full rank matrix with m  n,
vector, and consider the problem of solving the inconsistent linear system A"x  b
in the least-squares sense. The TLS solution assumes data uncertainties in A and
proceeds to correct A and b by replacing them by their projections, "
A and " b, onto a
specific subspace, and by solving the consistent linear system of equations "
The spectral norm of the correction
in the TLS solution is bounded by the
smallest singular value of
\Theta
A b

. While this norm might be small for vectors b that
are close enough to the range space of A, it need not always be so. In other words,
addresses: shiv@ece.ucsb.edu, golub@sccm.stanford.edu, mgu@math.ucla.edu, and
sayed@ee.ucla.edu. The works of A. H. Sayed and S. Chandrasekaran were supported in part by the
National Science Foundation under Award numbers MIP-9796147, CCR-9732376, and CCR-9734290,
respectively.
the TLS solution may lead to situations in which the correction in A is unnecessarily
large. Consider, for example, a situation in which the uncertainties in A are very
small and, say, A is almost known exactly. Assume further that b is far from the
range space of A. In this case, it is not difficult to visualize that the TLS solution will
need to modify
may therefore end up with an overly corrected
approximant for A, despite the fact that A is almost exact.
These facts motivate us to introduce a new parameter estimation formulation
with a bound on the size of the allowable correction to A. The solution of the new
formulation turns out to involve the minimization of a cost function in an "indefinite"
metric, in a way that is similar to more recent works on robust (or H 1 ) estimation
and filtering (e.g., [6, 7, 8, 9]). However, the cost function considered in our work is
more complex and, contrary to robust estimation where no prior bounds are imposed
on the size of the disturbances, the problem of this paper shows how to solve the
resulting optimization problem in the presence of such constraints. A "closed" form
solution to the new optimization problem is obtained in terms of the positive root of
a secular equation.
The solution method proposed in this paper proceeds by first providing a geometric
interpretation of the new optimization problem, followed by an algebraic derivation
that establishes that the optimal solution can in fact be obtained by solving a related
"indefinite" regularized problem. The regression parameter of the regularization step
is further shown to be obtained from the positive root of a secular equation. The solution
involves an SVD step and its computational complexity amounts to O(mn 2 +n 3 ),
where n is the smaller matrix dimension. A summary of the problem and its solution
is provided in Sec. 4.7 at the end of this paper.
2. Problem Statement. Let A 2 R m\Thetan be a given matrix with m  n and let
be a given nonzero vector, which are assumed to be linearly related via an
unknown vector of parameters x 2 R n ,
The vector v explains the mismatch between Ax and the given vector (or
b.
We assume that the "true" coefficient matrix is A + ffiA, and that we only know
an upper bound on the perturbation ffiA:
with j being known, and where the notation k \Delta k 2 denotes the 2\Gammainduced norm of a
matrix argument (i.e., its maximum singular value) or the Euclidean norm of a vector
argument. We pose the following optimization problem.
Problem 1. Given A 2 R m\Thetan , with m  n, nonnegative real
number j. Determine, if possible, an "
x that solves
min
It turns out that the existence of a unique solution to this problem will require
a fundamental condition on the data (A; b; j), which we describe further ahead in
BOUNDED ERRORS-IN-VARIABLES MODEL 3
Lemma 3.1. When the condition is violated, the problem will become degenerate.
In fact, such existence and uniqueness conditions also arise in other formulations of
estimation problems (such as the TLS and H1 problems, which will be shown later
to have some relation to the above optimization problem). In the H1 context, for
instance, similar fundamental conditions arise, which when violated indicate that the
problem does not have a meaningful solution (see, e.g., [6, 7, 8, 9]).
2.1. Intuition and Explanation. Before discussing the solution of the optimization
problem we formulated above, it will be helpful to gain some intuition into
its significance.
Intuitively, the above formulation corresponds to "choosing" a perturbation ffiA,
within the bounded region, that would allow us to best predict the right-hand side
b from the column span of Comparing with the total-least-squares (TLS)
formulation, we see that in TLS there is not an a priori bound on the size of the
allowable perturbation ffiA. Still, the TLS solution finds the "smallest" ffiA (in a
Frobenius norm sense) that would allow to estimate b from the column span of
ffiA), viz., it solves the following problem [3]:
min
Nevertheless, although small in a certain sense, the resulting correction ffiA need not
satisfy an a priori bound on its size. The problem we formulated above explicitly
incorporates a bound on the size of the allowable perturbations. We may further add
that we have addressed a related estimation problem in the earlier work [10], where
we have posed and solved a min-max optimization problem; it allows us to guarantee
optimal performance in a worst-case scenario. Further discussion, from a geometric
point of view, of this related problem and others, along with examples of applications
in image processing, communications, and control, can be found in [11].
Returning to (2.3), we depict the situation in Fig. 2.1. Any particular choice for
x would lead to many residual norms,
one for each possible choice of ffiA. A second choice for "
x would lead to other residual
norms, the minimum value of which need not be the same as the first choice. We
want to choose an estimate "
x that minimizes the minimum possible residual norm.
Fig. 2.1. Two illustrative residual-norm curves.
2.2. A Geometric Interpretation. The optimization problem (2.3) admits
an interesting geometric formulation that highlights some of the issues involved in its
solution. We explain this by considering a scalar example. For the vector case see
[11].
Assume we have a unit-norm vector b, kbk that A is simply a column
vector, say a, with j 6= 0. Now problem (2.3) becomes
min
x
min
This situation is depicted in Fig. 2.2. The vectors a and b are indicated in thick
black lines. The vector a is shown in the horizontal direction and a circle of radius j
around its vertex indicates the set of all possible vertices for a
a
Fig. 2.2. Geometric construction of the solution for a simple example.
For any " x that we pick, the set f(a+ ffia)"xg describes a disc of center a"x and radius
j"x. This is indicated in the figure by the largest rightmost circle, which corresponds
to a choice of a positive "
x that is larger than one. The vector in f(a + ffia)"xg that
is the closest to b is the one obtained by drawing a line from b through the center
of the rightmost circle. The intersection of this line with the circle defines a residual
vector r 3 whose norm is the smallest among all possible residual vectors in the set
ffia)"xg.
Likewise, if we draw a line from b that passes through the vertex of a (which is
the center of the leftmost circle), it will intersect the circle at a point that defines a
residual vector r 1 . This residual will have the smallest norm among all residuals that
correspond to the particular choice "
More generally, for any "
x that we pick, it will determine a circle and the corresponding
smallest residual is obtained by finding the closest point on the circle to b.
This is the point where the line that passes through b and the center of the circle
intersects the circle on the side closer to b.
We need to pick an "
x that minimizes the smallest residual norm. The claim is that
we need to proceed as follows: we drop a perpendicular from b to the upper tangent
line denoted by ' 2 . This perpendicular intersects the horizontal line in a point where
BOUNDED ERRORS-IN-VARIABLES MODEL 5
we draw a new circle (the middle circle) that is tangent to both ' 1 and ' 2 . This circle
corresponds to a choice of " x such that the closest point on it to b is the foot of the
perpendicular from b to ' 2 . The residual indicated by r 2 is the desired solution; it
has the minimum norm among the smallest residuals.
3. An Equivalent Minimization Problem. To solve (2.3), we start by showing
how to reduce it to an equivalent problem. For this purpose, we note that
The lower bound on the right-hand side of the above inequality is a non-negative
quantity and, therefore, the least it can get is zero. This will in turn depend on how
big or how small the value of kffiAk 2 can be.
For example, if it happens that for all vectors " x we always have
then we conclude, using the triangle inequality of norms, that
It then follows from (3.1) that, under the assumption (3.2), we obtain
It turns out that condition (3.2) is the main (and only) case of interest in this pa-
per, especially since we shall argue later that a degenerate problem arises when it is
violated. For this reason, we shall proceed for now with our analysis under the assumption
(3.2) and shall postpone our discussion of what happens when it is violated
until later in this section.
Now the lower bound in (3.1) is in fact achievable. That is, there exists a ffiA for
which
To see that this is indeed the case, choose ffiA as the rank one matrix
This leads to a vector ffiA that is collinear with the vector (A"x \Gamma b). [Note that "
x in
the above definition for ffiA o cannot be zero since otherwise (3.2) cannot be satisfied.
cannot be zero. Hence, ffiA o is well-defined.]
We are therefore reduced to the solution of the following optimization problem.
Problem 2. Consider a matrix A 2 R m\Thetan , with m  n, a vector b
nonnegative real number j, and assume that for all vectors " x it holds that
Determine, if possible, an " x that solves
x
6 CHANDRASEKARAN, GOLUB, GU, AND SAYED
3.1. Connections to TLS and H1-Problems. Before solving Problem (3.4),
we elaborate on its connections with other formulations in the literature that also
attempt, in one way or another, to take into consideration uncertainties and perturbations
in the data.
First, cost functions similar to (3.4) but with squared distances, say
x
for some fl ? 0, often arise in the study of indefinite quadratic cost functions in
robust or H 1 estimation (see, e.g., the developments in [8, 9]). The major distinction
between this cost and the one posed in (3.4) is that the latter involves distance terms
and it will be shown to provide an automatic procedure for selecting a "regularization"
factor that plays the role of fl in (3.5).
Likewise, the TLS problem seeks a matrix ffiA and a vector " x that minimize the
following Frobenius norm:
min
The solution of the above TLS problem is well-known and is given by the following
construction [4][p. 36]. Let foe denote the singular values of A, with oe 1
denote the singular values of the
extended matrix
\Theta
A b

, with
x of
exists and is given by
For our purposes, it is more interesting to consider the following interpretation of
the TLS solution (see, e.g., [9]). Note that the condition  oe n+1 ! oe n assures that
n+1 I) is a positive-definite matrix, since oe 2
n is the smallest eigenvalue of
A T A. Therefore, we can regard (3.7) as the solution of the following optimization
problem, with an indefinite cost function,
x
This is a special form of (3.5) with a particular choice for fl. It again involves squared
distances, while (3.4) involves distance terms and it will provide another choice of a fl-
like parameter. In particular, compare (3.7) with the expression (4.4) derived further
ahead for the solution of (3.4). We see that the new problem replaces
n+1 with a
new parameter ff that will be obtained from the positive root of a secular (nonlinear)
equation.
3.2. Significance of the Fundamental Assumption. We shall solve Problem
(3.4) in the next section. Here, we elaborate on the significance of the condition
(3.3). So assume (3.3) is violated at some nonzero point "
x (1) , namely 1
and define the perturbation
2:
violation occurs for some zero "
x (1) this means that we must necessarily have
contradicts our assumption of a nonzero vector b.
BOUNDED ERRORS-IN-VARIABLES MODEL 7
It is clear that ffiA (1) is a valid perturbation since, in view of (3.8), we have kffiA (1) k 2
j. But this particular perturbation leads to
That is, the lower limit of zero is achieved for (ffiA (1) ; x (1) ) and x (1) can be taken as a
solution to (2.3). In fact, there are many possible solutions in this case. For example,
once one such x (1) has been found, an infinite number of others can be constructed
from it. To verify this claim, assume x (1) is a vector that satisfies (3.8), viz., it satisfies
for some ffl  0. Now assume we replace x (1) by x vector ffi to
be determined so as to violate condition (3.3) and, therefore, also satisfy a relation of
the form
If such an x (2) can be found, then constructing the corresponding ffiA (2) as in (3.9)
would also lead to a solution (ffiA
Condition (3.11) requires a choice for the vector ffi such that
But this can be satisfied by imposing the sufficient condition
where the left-hand side is the smallest jk"x (1) while the right-hand side
is the largest kA("x (1) get. Solving for kffik 2 we see that any vector ffi
that satisfies
will lead to a new vector "
x (2) that also violates (3.3). Consequently, given any single
nonzero violation " x (1) , many others can be obtained by suitably perturbing it.
We shall not treat the degenerate case in this paper (as well as the case when
(3.8) is violated only with equality). We shall instead assume throughout that the
fundamental condition (3.3) holds. Under this assumption, the problem will turn out
to always have a unique solution.
3.3. The Fundamental Condition for Non-Degeneracy. The fundamental
condtition (3.3) needs to be satisfied for all vectors "
x. This can be restated in terms of
conditions on the data (A; b; To see this, note that (3.3) implies, by squaring,
that we must have
That is, the quadratic form J("x) that is defined on the left hand-side of (3.13) must
be negative for any value of the independent variable "
x. This is only possible if:
(i) The quadratic form J("x) has a maximum with respect to " x, and
8 CHANDRASEKARAN, GOLUB, GU, AND SAYED
(ii) the value of J("x) at its maximum is negative.
The necessary condition for the existence of a unique maximum (since we have a
quadratic cost function) is
(j
which means that j should satisfy
Under this condition, the expression for the maximum point " xmax of J("x) is
Evaluating J("x) at "
xmax we obtain

Therefore, the requirment that J("x max ) be negative corresponds to
Lemma 3.1. Necessary and sufficient conditions in terms of (A; b; j) for the
fundamental relation (3.3) to hold are:
(j
and
Note that for a well-defined problem of the form (2.3) we need to assume j ? 0
which, in view of (3.17), means that A should be full rank so that oe min (A) ? 0. We
therefore assume, from now on, that
A is full rank :
We further introduce the singular value decomposition (SVD) of A:
where U 2 R m\Thetam and V 2 R n\Thetan are orthogonal, and
nal, with
being the singular values of A. We further partition the vector U T b into
m\Gamman .
While solving the minimization problem (3.4), we shall first assume that the two
smallest singular values of A are distinct and, hence, satisfy
Later in Sec. 4.6 we consider the case in which multiple singular values can occur.
BOUNDED ERRORS-IN-VARIABLES MODEL 9
4. Solving the Minimization Problem. To solve (3.4), we define the non-convex
cost function
which is continuous in " x and bounded from below by zero in view of (3.3). A minimum
point for L("x) can only occur at 1, at points where L("x) is not differentiable,
or at points where its gradient, 5L("x), is 0. In particular, note that L("x) is not
differentiable only at " and at any " x that satisfies A"x
satisfying are excluded by the fundamental condition (3.3). Also, we can
rule out "
lim
Now at points where L("x) is differentiable, the gradient of L is given by
where we have introduced the positive real number
In view of the fundamental condition (3.3) we see that the value of ff is necessarily
larger
Likewise, the Hessian of L is given by
3:
The critical points of L("x) (where the gradient is singular) satisfy
or, equivalently,
Equations (4.1) and (4.4) completely specify the stationary points of L("x). They
provide two equations in the unknowns (ff; "
x). We can use (4.4) to eliminate "
x from
(4.1) and, hence, obtain an equation in ff. Once we solve for ff, we can then use
equation (4.4) to determine the solution " x. The equation we obtain for ff will in
general be a nonlinear equation and the desired ff will be a root of it. The purpose
of the discussion in the sequel is to show where the root ff that corresponds to the
global minimizer of L lies and how to find it.
We know from (4.2) that ff ? j 2 . We shall show soon that we only need to look
for the solution ff in the interval (j
4.5. [Further analysis later in
the paper will in fact show that ff lies within the smaller interval (j
Hence, the
coefficient matrix in (4.4) is always nonsingular except for
or
n .
In summary, we see that the candidate solutions "
x to our minimization problem
are the following:
which is a point at which L is not differentiable. We shall show that
can not be a global minimizer of L.
2. to (4.1) and (4.4) when In this
case, we will see that ff can only lie in the open interval (j
3. Solutions (ff; "
x) to (4.1) and (4.4) when singular. We will see
that this can only happen for the choices
n .
The purpose of the analysis in the sequel is to rule out all the possibilities except
for one as a global minimum for L. In loose terms, we shall show that in general a
unique global minimizer (ff; "
exists and that the corresponding ff lies in the open
interval (j
Only in a degenerate case, the solution is obtained by taking
and by solving (4.4) for " x. In other words, the global minimum will be obtained from
the stationary points of L, which is why we continue to focus on them.
The final statement of the solution is summarized in Sec. 4.7.
4.1. Positivity of the Hessian Matrix. We are of course only interested in
those critical points of L that are candidates for local minima. Hence, the Hessian
matrix at these points must be positive semi-definite.
ff"x at a critical point, we conclude from equation (4.3) that
Now observe that the second term is a symmetric rank-1 matrix that is also positive-semidefinite
since ff ? j 2 . Hence, in view of the Cauchy interlacing theorem [3]
the smallest eigenvalue of \DeltaL("x) will lie between the two smallest eigenvalues of the
. This shows that the value of ff can not exceed oe 2
since otherwise the two smallest eigenvalues of
will be nonpositive and
the Hessian matrix will have a nonpositive eigenvalue.
The above argument explains why we only need to look for ff in the interval
4.2. Solving for "
x and the Secular Equation. Given that we only need consider
values of ff in the interval (j
we can now solve for "
x using (4.1) and (4.4).
Two cases should be considered since the coefficient matrix may be singular
for
n or
.
BOUNDED ERRORS-IN-VARIABLES MODEL 11
I. The case ff 62 foe 2
g. From Eq. (4.4) we see that among the ff's in the interval
(4.5), as long as ff is not equal to either oe 2
n or oe 2
, the critical point " x associated
with ff is given uniquely by
.
Moreover, from equations (4.1) and (4.4) we see that
0:
Substituing for "
x and using the SVD of A to simplify we obtain the equivalent expressions
Clearly the roots of G(ff) that lie in the interval (j
will correspond to critical
points that are candidates for local minima. Therefore we will later investigate the
roots of G(ff).
II. The case
n or
. From Eq. (4.4) we see that
n or
can correspond to a critical point " x, only if either u T
denote the columns of U that correspond to
i.e., the last two columns of U .
We only show here how to solve for "
x when
n . The technique for
is similar.
From equation (4.4) it is clear that
n is a candidate for a critical point if,
and only if, u T
In this case the associated "
x's (there may be more than one)
satisfy the equations
and
Now define y consider the following partitionings:
y
The quantities " x and y define each other uniquely and kyk
It follows from equation (4.8) that
I
Substituting this into equation (4.9) we have
oe 4
I
Solving for y 2
n we obtain
I
where we introduced the function
Comparing with the definition (4.7) for G(ff) we see that
Note that
G(ff) if u T
which is the case when
n is a possibility.
Therefore the possible values of yn are
It follows that
are the necessary conditions for
n to correspond to a stationary double point
at:
I
The global minimum. The purpose of the analysis in the following sections is to
show that in general the global minimum is given by (4.6) with the corresponding ff
lying in the interval (j
a root of the secular equation G(ff) in (4.7) does
not exist in the open interval (j
n ), we shall then show that the global minimum
is given by (4.15).
4.3. The Roots of the Secular Equation. We have argued earlier in (4.5)
that the roots ff of G(ff) that may lead to global minimizers "
x can lie in the interval
(j
We now determine how many roots can exist in this interval and later show
that only the root lying in the subinterval (j
corresponds to a global minimum
when it exists. Otherwise, we have to use (4.15). The details are given below.
To begin with, we establish some properties of G(ff). From the non-degeneracy
assumption (3.3) on the data it follows that G(j 2 Moreover, from the expression
(4.7) for G(ff) we see that it has a pole at oe 2
n provided that u T
b is not equal to zero
in which case
lim
BOUNDED ERRORS-IN-VARIABLES MODEL 13
Now observe from the expression for the derivative of G(ff),
that G 0 (ff) ? 0 for
n . We conclude from these facts that G(ff) has exactly
one root in the open interval (j
Actually, since also
lim
we conclude that when u T
exactly one root in the interval (0; oe 2
that this root lies in the subinterval (j
When u T
the function G(ff) does not have a pole at oe 2
does not hold. However, by using the still valid fact that lim ff!0+
that G 0 (ff) ? 0 over the larger interval (0; oe 2
we conclude the following:
1. If u T
hence, G(ff) has a unique root
in the interval (0; oe 2
2. If we also have u T
can have at most one root in the interval
). The root may or may not exist.
What about the interval (oe 2
We now establish that G(ff)
can have at most two roots in this interval. For this purpose, we first observe that
both G(ff) and ff 2 G(ff) have the same number of roots in (oe 2
added a double root at 0). Next we compute the first derivative of ff 2 G(ff) obtaining
d
dff
Using this we compute the second derivative obtaining
It is clear that the second derivative is strictly positive for non-negative ff. From this
we can conclude that ff 2 G(ff) and, hence, G(ff), have at most two zeros in (oe 2
We have therefore established the following result.
Lemma 4.1. The following properties hold for the function G(ff) defined in (4.7):
1. When u T
the function G(ff) has a single root in the interval (j
and at most two roots in the interval (oe 2
We label them as:
2. When u T
the function G(ff) has a unique root in the
interval (j
3. When u T
the function G(ff) has at most one root in the
interval (j
It is essential to remember that the roots ff 2 and ff 3 may not exist, though they
must occur as a pair (counting multiplicity) if they exist.
We now show that ff 3 cannot correspond to a local minimum if ff
the two roots in the interval (oe 2
are distinct. Indeed, assume ff 2 and ff 3 exist.
14 CHANDRASEKARAN, GOLUB, GU, AND SAYED
Then from the last lemma it must hold that u T
must also exist. Hence,
we must have G 0 (ff
If we assume ff 2 ! ff 3 , we shall use the fact that G 0 (ff 3 to show that ff 3 can
not correspond to a local minimum solution "
x. This will be achieved by showing that
the determinant of the Hessian of L("x) at ff 3 is negative. For this we note that
det
x
x
Introduce for convenience, the shorthand notation:
Then, using the SVD of A,
det
Evaluating at noting that
conclude that det(L) at the " x corresponding to ff 3 is negative. Hence, ff 3 cannot
correspond to a local minimum.
4.4. Candidates for Minima. We can now be more explicit about the candidates
for global minimizers of L, which we mentioned just prior to Sec. 4.1:
which corresponds to a point where L is not differentiable.
2. If ff 1 exists then the corresponding "
x is a candidate. Recall that ff is guaranteed
to exist if u T
It may or may not exist otherwise.
3. If u T
exists then the corresponding "
x is a candidate.
4. If u T
x associated with
n is a candidate.
5. If u T
x associated with
is a candidate.
We shall show that 2) is the global minimizer when ff 1 exists. Otherwise, 4) is the
global minimizer.
We start by showing that "
can not be the global minimizer of L. We divide
our argument into two cases: necessarily have
The
is the error vector due to projecting b onto u i . Hence,
and we obtain
BOUNDED ERRORS-IN-VARIABLES MODEL 15
We conclude that L(0) ? L(z), and " cannot correspond to a global minimum
Now we consider the case when b that by the non-degeneracy assumption
we must have b 2 6= 0. Now define again Then we can simplify L("x) to
obtain
Choose "
. The following sequence of inequalities then
holds:
Therefore "
can never be the global minimum.
4.5. Continuation Argument. We are now ready to show that if ff 1 exists
then the corresponding " x in (4.6) gives the global minimum. Otherwise, the "
x in
(4.15) that corresponds
n gives a double global minimum. The proof will be by
continuation on the parameter fi \Delta
We use (4.12) to write
We also recall from the definition of
G in (4.11) that it has a similar expression to
that of G in (4.7), except that the pole of G at oe 2
n has been extracted (as shown by
(4.18)). Hence, the derivative of
G has a form similar to that of the derivative of G in
(4.17) and we can conclude that
We continue our argument by considering separately the three cases:
I.
In this case, and because of (4.14),
n can not correspond to
a global minimum. By further noting that
that
using (4.18) we also have that G(ff) ? 0 over
n is either a pole of G(ff) (when u T
(when u T
that G has a unique root in (j
In this case the only contenders for global minima over (0; oe 2
are
. By an analysis similar to the one in Sec. 4.2 for
n it can be shown
that a necessary condition for
to correspond to a global minimum is that
These two conditions imply that we must have G(oe 2
This result is compatible
with the fact that G(ff) ? 0 over (oe 2
This in turn implies
from (4.18) that we must have
This is inconsistent with the facts
Therefore,
can not correspond to a global minimum and we conclude
that the only critical point we need to consider corresponds to the one associated with
the unique root of G(ff) in (j
n ), which must naturally correspond to the global
minimum.
In summary, the solution "
x in (4.6) that corresponds to ff 1 is the global minimum
in this case.
II.
In this case, and because of (4.14),
can correspond to a global
minimum only if which case we also deduce from (4.18) that G(oe 2
G. Hence, oe 2
n is a root of G. By using G(j 2
we conclude that G does not have any other root in (j
Therefore, when the only contenders for global minima over (0; oe 2
are
n and
. For
to correspond to a global minimum we
saw above that we must necessarily have G(oe 2
This is inconsistent with
We thus obtain that the solution "
x in (4.15)
that corresponds to oe 2
n is the global minimizer.
What about the case fi 6= 0? In this case, and because of (4.14),
n can not
correspond to a global minimum. By further noting that
we conclude that
using (4.18) we also have that
n is now a pole of G(ff) and since G(j 2
that G has a unique root in (j
In this
case the only contenders for global minima over (0; oe 2
.
By an analysis similar to the one in case I, we can rule out oe 2
.
In summary, we showed the following when
1. When u T
0, the solution " x in (4.6) that corresponds to ff 1 is the global
minimum.
2. When u T
x in (4.15) that corresponds to oe 2
n is the global
minimum.
III.
This is the most complex situation. Let ! be the largest number
such that oe 2
and G(ff) has no poles in the interval
By the given conditions it is obvious from the form of G(ff) that it has two roots
in (oe 2
sufficiently small fi. Now we find the largest number ffi such that for
all fi in the interval (0; ffi] the function G(ff) has two roots (counting multiplicity) in
We claim that for fi ? ffi there are no roots of G(ff) in (oe 2
To see this we
replace fi in G(ff) by
and observe that the term involving  is strictly positive in the interval (oe 2
strictly positive .
We continue our analysis by considering separately two cases:
BOUNDED ERRORS-IN-VARIABLES MODEL 17
We will show that at
the function L has a double
global minimum at
n , and that as fi is increased this double root at
bifurcates into the two roots ff 1 and ff 2 , and that L(ff 1
When
the function
G(ff) has exactly one root in (0; !]. This is because
By using the same proof that we used earlier to
show that ff 3 cannot correspond to a local minimum we can establish that this root
also cannot correspond to minimum. This leaves us with the double stationary points
that we computed in (4.15) and which corresponded to
n . It is an easy matter
to verify, using the formula that both the stationary points
yield the same value for L.
We now allow fi to increase. Let y(fi) denote the stationary point
x corresponding to ff 1 (fi). Also let z(fi) denote the stationary point " x corresponding
to ff 2 (fi). It is easy to see from the form of G(ff) that
lim
whenever
Now we will show that
lim
First we observe that the result is true for i 6= n directly from formulas (4.4)
and (4.10). Next we note that
G(ff) is continuous at
n . Therefore
lim
Now using formula (4.13) it can be verified that
lim
Therefore, L(y(fi)) and L(z(fi)) are continuous on the interval [0; 1), with
L(z(0)). We now compute the derivative of L with respective to fi at a stationary
point. We have already observed that at a stationary point "
x, corresponding to some
ff, the objective function L can be simplified To simplify the
derivation we actually take the derivative of j 2 L 2 , which can be expressed as
for Now we differentiate obtaining
d
Now we obtain an expression for dff=dfi by differentiating ff 2
to fi. Doing so we obtain
dff
Solving this equation for the term involving dff=dfi and substituting it into the above
equation for d
we obtain
d
From this expression we can immediately conclude that the smaller root ff 1 (fi)
decreases the objective function L(y(fi)), as fi increases from 0, and the larger root
increases the value of the objective function L(z(fi)), as fi increases. Since
L(z(0)), we can now conclude that L(y(fi))  L(z(fi)) for all non-negative
fi such that ff 2 (fi) ! oe 2
.
Therefore the choice for global minimum is between y(fi) and the critical points,
if any, corresponding to
. As mentioned before,
can correspond
to a critical point only if the condition (4.19) holds.
From the arguments in Sec. 4.3 we know that G(ff) has at most two roots in
Therefore it follows that under the condition
. This in turn
implies that ff 2 (fi
Using the condition (4.19) and carrying out an analysis similar to that of (4.15),
we can compute the critical point associated with
. From that it is easy to
verify that
lim
denotes the critical point associated with
.
Now from the continuation argument for L it follows that L(y(fi))
Therefore we do not need to consider
as a possibility
for the global minimum.
Furthermore, when fi ? ffi we argued earlier that there are not roots of G(ff) in
the interval (oe 2
Also, from the above argument it follows that
can not
correspond to a global minimum.
In summary, the " x in (4.6) that corresponds to ff 1 is the global minimizer.
4.6. Multiple Singular Values. So far in the analysis we have implicitly ignored
the possibility that oe . We now discuss how to take care of this
possibility. We only need to consider critical points ff situated in the interval (0; oe 2
Let Un denote a matrix with orthonormal columns that span the left singular
subspace associated with the smallest singular value of A. If kU T
it follows from equation (4.4) that
n is not a possibility for a critical point.
Furthermore G(ff) has a single root in (j
must give the global minimum.
If kU T
then either there exists a root of G(ff) in the interval (j
which corresponds to the global minimum, or there is no such root and
will
give rise to multiple global minima all of which can be calculated by the technique
that led to (4.15). The only difference is that
y in equation (4.10) will now denote
BOUNDED ERRORS-IN-VARIABLES MODEL 19
the components of y associated with the right singular vectors perpendicular to the
range space of Vn , where Vn is a matrix with orthonormal columns that span the
right singular subspace of A corresponding to oe n . The proofs of these statements are
similar to the non-multiple singular value case.
4.7. Statement of the Solution of the Optimization Problem. We collect
in the form of a theorem the conclusions of our earlier analysis.
Theorem 4.2. Given A 2 R m\Thetan , with m  n and A full rank, a nonzero
positive real number j satisfying j ! oe min (A). Assume further that
\Theta

The solution of the optimization problem:
min
min
can be constructed as follows.
ffl Introduce the SVD of A,
where U 2 R m\Thetam and V 2 R n\Thetan are orthogonal, and
is diagonal, with
being the singular values of A.
ffl Partition the vector U T b into
m\Gamman .
ffl Introduce the secular function
ffl Determine the unique positive root "
ff of G(ff) that lies in the interval (j
If it does not exist then set "
n .
ffl Then
1. If "
n , the solution " x is unique and is given by (4.6) or, equivalently,
2. If "
n and oe n ! oe then two solutions exist that are given by
(4.15). Otherwise, if A has multiple singular values at oe n , then multiple
solutions exist and we can use the same technique that led to (4.15) to
determine "
x as explained in the above section on multiple singular values.
We can be more explicit about the uniqueness of solutions. Assume A has multiple
singular values at oe n and let Un denote the matrix with singular vectors that spans
the left singular subspace of A associated with these singular values:
1. When kU T
n bk 6= 0, the solution " x is unique and it corresponds to a root "
as shown above.
2. When kU T
either an "
exists and the solution " x is unique.
Otherwise, "
n and multiple solutions "
x exist.
5. Restricted Perturbations. We have so far considered the case in which all
the columns of the A matrix are subject to perturbations. It may happen in practice,
however, that only selected columns are uncertain, while the remaining columns are
known precisely. This situation can be handled by the approach of this paper as we
now clarify.
Given A 2 R m\Thetan , we partition it into block columns,
\Theta

and assume, without loss of generality, that only the columns of A 2 are subject to
perturbations while the columns of A 1 are known exactly. We then pose the following
problem:
Given A 2 R m\Thetan , with m  n and A full rank, b 2 R m , and a nonnegative real
number
min
x
min
\Theta

If we partition " x accordingly with A 1 and A 2 , say
then we can write
\Theta

Assuming, for any vector ("x
we can follow the argument at the beginning of Sec. 3 to conclude that the minimum
over ffiA 2 is achievable and is equal to
In this way, statement (5.1) reduces to the minimization problem
\Theta
This statement can be further reduced to the problem treated in Theorem 4.2 as
follows. Introduce the QR decomposition of A, say
R 11 R 12
BOUNDED ERRORS-IN-VARIABLES MODEL 21
where we have partitioned R accordingly with the sizes of A 1 and A 2 . Define4
Then (5.2) is equivalent to
min
R 11 R 12
\Gamma4
which can be further rewritten as
min
This shows that once the optimal "
x 2 has been determined, the optimal choice for "
is necessarily the one that annihilates the entry R
That is,

The optimal "
x 2 is the solution of
R 22
This optimization is of the same form as the problem stated earlier in (3.4) with " x
replaced by "
replaced by j 2 , A replaced by
R 22
, and b replaced by
Therefore, the optimal " x 2 can be obtained by applying the result of Theorem 4.2.
Once " x 2 has been determined, the corresponding " x 1 follows from (5.5).
6. Conclusion. In this paper we have proposed and solved a new optimization
problem for parameter estimation in the presence of data uncertainties. The problem
incorporates a priori bounds on the size of the perturbations. It has a "closed" form
solution that is obtained by solving an "indefinite" regularized least-squares problem
with a regression parameter that is determined from the positive root of a secular
equation.
Several extensions are possible. For example, weighted versions with uncertainties
in the weight matrices are useful in several applications, as well as cases with
multiplicative uncertainties and applications to filtering theory. Some of these cases,
in addition to more discussion on estimation and control problems with bounded
uncertainties, can be found in [11, 12, 13, 14].

Acknowledgement

. The authors would like to thank one of the anonymous reviewers
for pointing out a mistake in an earlier version of the paper.



--R

Some modified matrix eigenvalue problems
An analysis of the total least squares problem
Matrix Computations
The Total Least Squares Problem: Computational Aspects and Analysis


Filtering and smoothing in an H 1
Recursive linear estimation in Krein spaces - Part I: Theory
Fundamental inertia conditions for the minimization of quadratic forms in indefinite metric spaces
Parameter estimation in the presence of bounded data uncertainties
Estimation and control in the presence of bounded data uncertainties
"Parameter estimation in the presence of bounded modeling errors,"
"Estimation in the presence of multiple sources of uncertainties with applications"
"Design criteria for uncertain models with structured and unstructured uncertainties,"
--TR
modeling errors;least-squares estimation;total least-squares;secular equation