Robust Solutions to Least-Squares Problems with Uncertain Data.
We consider least-squares problems where the coefficient matrices A,b are unknown but bounded. We minimize the worst-case residual error using (convex) second-order cone programming, yielding an algorithm with complexity similar to one singular value decomposition of A. The method can be interpreted as a Tikhonov regularization procedure, with the advantage that it provides an exact bound on the robustness of solution and a rigorous way to compute the regularization parameter. When the perturbation has a known (e.g., Toeplitz) structure, the same problem can be solved in polynomial-time using semidefinite programming (SDP). We also consider the case when A,b are rational functions of an unknown-but-bounded perturbation vector. We show how to minimize (via SDP) upper bounds on the optimal worst-case residual. We provide numerical examples, including one from robust identification and one from robust interpolation.
Introduction
. Consider the problem of finding a solution x to an overdetermined
set of equations Ax ' b, where the data matrices A 2 R n\Thetam , b 2 R n are given.
The Least Squares (LS) fit minimizes the residual k\Deltabk subject to resulting
in a consistent linear model of the form \Deltab) that is closest to the original
one (in Euclidean norm sense). The Total Least Squares (TLS) solution described by
Golub and Van Loan [17] finds the smallest error subject to the consistency
equation \Deltab. The resulting closest consistent linear model
\Deltab) is even more accurate than the LS one, since modifications of A are
allowed.
Accuracy is the primary aim of LS and TLS, so it is not surprising that both
solutions may exhibit very sensitive behavior to perturbations in the data matrices
b). Detailed sensitivity analyses for the LS and TLS problems may be found
in [12, 18, 2, 44, 22, 14]. Many regularization methods have been proposed to de-
To appear in SIAM Journal on Matrix Analysis and Applications, 1997.
y Ecole Nationale Sup'erieure de Techniques Avanc'ees, 32, Bd. Victor, 75739 Paris, France. Internet:
(elghaoui, lebret)@ensta.fr
L. EL GHAOUI AND H. LEBRET
crease sensitivity, and make LS and TLS applicable. Most regularization schemes for
LS, including Tikhonov regularization [43], amount to solve a weighted LS problem for
an augmented system. As pointed out in [18], the choice of weights (or regularization
parameter) is usually not obvious, and application-dependent. Several criteria for optimizing
the regularization parameter(s) have been proposed (see e.g. [23, 11, 15]). These
criteria are chosen according to some additional a priori information, of deterministic
or stochastic nature. The extensive surveys [31, 8, 21] discuss these problems and some
applications.
In contrast with the extensive work on sensitivity and regularization, relatively
little has been done on the subject of deterministic robustness of LS problems, in which
the perturbations are deterministic, and unknown-but-bounded (not necessarily small).
Some work has been done on a qualitative analysis of the problem, where entries of
are unspecified but by their sign [26, 39]. In many papers mentioning least-squares
and robustness, the latter notion is understood in some stochastic sense, see
e.g. [20, 47, 37]. A notable exception concerns the field of identification, where subject
has been explored using a framework used in control system analysis [40, 9], or using
regularization ideas combined with additional a priori information [34, 42].
In this paper, we assume that the data matrices are subject to (non necessarily
small) deterministic perturbations. First, we assume that the given model is not a
single pair (A; b), but a family of matrices is an
unknown-but-bounded matrix, precisely, k\Deltak - ae, where ae - 0 is given. For x fixed,
we define the worst-case residual as
(1)
We say that x is a Robust Least Squares (RLS) solution if x minimizes the worst-case
residual r(A; b; ae; x). The RLS solution trades accuracy for robustness, at the expense
of introducing bias. In our paper, we assume that the perturbation bound ae is known,
but in x3.5, we also show that TLS can be used as a preliminary step to obtain a value
of ae that is consistent with data matrices A; b.
In many applications, the perturbation matrices \DeltaA, \Deltab have a known structure.
For instance, \DeltaA might have a Toeplitz structure inherited from A. In this case, the
worst-case residual (1) might be a very conservative estimate. We are led to consider
the following Structured RLS (SRLS) problem. Given A
(2)
For ae - 0, and x we define the structured worst-case residual as
kffik-ae
We say that x is a Structured Robust Least Squares (SRLS) solution if x minimizes the
worst-case residual r S (A; b; ae; x).
ROBUST LEAST SQUARES 3
Our main contribution is to show that we can compute the exact value of the optimal
worst-case residuals using convex, second-order cone or semidefinite programming
(SOCP or SDP). The consequence is that the RLS and SRLS problems can be solved
in polynomial-time, and great practical efficiency, using e.g. recent interior-point methods
[33, 46]. Our exact results are to be contrasted with those of Doyle et. al [9], which
also use SDP to compute upper bounds on the worst-case residual for identification
problems. In the preliminary draft [5], sent to us shortly after submission of this paper,
the authors provide a solution to an (unstructured) RLS problem, which is similar to
that given in x3.2.
Another contribution is to show that the RLS solution is continuous in the data
matrices A; b. RLS can thus be interpreted as a (Tikhonov) regularization technique for
ill-conditioned LS problems: the additonal a priori information is ae (the perturbation
level), and the regularization parameter is optimal for robustness. Similar regularity
results hold for the SRLS problem.
We also consider a generalisation of the SRLS problem, referred to as the linear-
fractional SRLS problem in the sequel, in which the matrix functions A(ffi), b(ffi) in (2)
depend rationally on the parameter vector ffi. (We describe a robust interpolation problem
that falls in this class in x7.6.) Using the framework of [9], we show that the problem
is NP-complete in this case, but that we may compute, and optimize, upper bounds on
the worst-case residual using SDP. In parallel with RLS, we interpret our solution as
one of a weighted LS problem for an augmented system, the weights being computed
via SDP.
The paper's outline is as follows. Next section is devoted to some technical lemmas.
Section 3 is devoted to the RLS problem. In section 4, we consider the SRLS problem.
Section 5 studies the linear-fractional SRLS problem. Regularity results are given in
Section 6. Section 7 shows numerical examples.
2. Preliminary results.
2.1. Semidefinite and second-order cone programs. We briefly recall some
important results on semidefinite programs (SDPs) and second-order cone programs
(SOCPs). These results can be found in e.g. [4, 33, 46].
A linear matrix inequality is a constraint on a vector x of the form
where the symmetric matrices F
are given. The minimization
problem
subject to F(x) - 0
called a semidefinite program (SDP). SDPs are convex optimization
problems and can be solved in polynomial-time with e.g. primal-dual interior-point
methods [33, 45].
4 L. EL GHAOUI AND H. LEBRET
The problem dual to problem (5) is
maximize \GammaTrF 0 Z
subject to Z - 0; TrF i
where Z is a symmetric N \Theta N matrix and c i is the i-th coordinate of vector c. When
both problems are strictly feasible (that is, when there exists x; Z which satisfy the
constraints strictly), the existence of optimal points is guaranteed [33, thm.4.2.1], and
both problems have equal optimal objectives. In this case, the optimal primal-dual
pairs (x; Z) are those pairs (x; Z) such that x is feasible for the primal problem, Z is
feasible for the dual one, and
A second-order cone programming problem is one of the form
subject to kC
L. The dual problem of
problem (7) is
subject to
are the dual variables. Optimality conditions
similar to those for SDPs can be obtained for SOCPs. SOCPs can be expressed as
SDPs, therefore they can be solved in polynomial-time using interior-point methods for
SDPs. However the SDP formulation is not the most efficient numerically, as special
interior-point methods can be devised for SOCPs [33, 28, 1].
complexity results on interior-point methods for SOCPs and SDPs are given
by Nesterov and Nemirovsky [33, p.224,236]. In practice, it is observed that the number
of iterations is almost constant, independent of problem size [46]. For the SOCP, each
iteration has complexity O((n for the SDP, we refer the reader
to [33].
2.2. S-procedure. The following lemma can be found e.g. in [4, p.24]. It is
widely used, e.g. in control theory, and in connection with trust region methods in
optimization [41].
Lemma 2.1 (S-procedure). Let F be quadratic functions of the variable
. The following condition on F
ROBUST LEAST SQUARES 5
holds if
there exist
0:
When the converse holds, provided that there is some i 0 such that F 1 (i
The next lemma is a corollary of the above result, in the case
Lemma 2.2. Let T
real matrices of appropriate size. We have
for every \Delta, k\Deltak - 1, if and only if kT 4 k ! 1, and there exists a scalar - 0 such that
0:
Proof. If T 2 or T 3 equal zero, the result is obvious. Now assume
which in turn implies kT 4 k ! 1. Thus, for a given - , (10) holds if
and only if kT 4 k ! 1 and for every (u; p), we have
4 p. Since T 2 6= 0, the constraint q T q - p T p is qualified, that is,
satisfied strictly for some
Using
the S-procedure, we obtain that there exists - 2 R such that (10) holds if and only if
1, and for every (u; p) such that q T q - p T p, we have u
our proof by noting that for every pair (p; q),
only if p T p - q T q.
Next lemma is a "structured" version of the above, which can be traced back to [13].
Lemma 2.3. Let T
real matrices of appropriate size. Let D
be a subspace of R N \ThetaN , and denote by S (resp. G) the set of symmetric (resp. skew-
symmetric) matrices that commute with every element of D. We have
and (9) for every \Delta 2 D, k\Deltak - 1, if there exist S 2 S, G 2 G such that
If the condition is necessary and sufficient.
Proof. The proof follows the scheme of that of lemma 2.2, except that p T p - q T q
is replaced with p T G. Note that
0, the above result is a simple application of lemma 2.2 to the scaled matrices
6 L. EL GHAOUI AND H. LEBRET
2.3. Elimination lemma. The last lemma is proven in [4, 24].
Lemma 2.4 (Elimination). Given real matrices of appropriate
size, there exists a real matrix X such that
if and only if
~
U T W ~
where ~
U , ~
are orthogonal complements of U; V . If U; V are full column-rank, and (12)
holds, a solution X to the inequality (11) is
oe is any scalar such that Q ? 0 (the existence of which is
guaranteed by (12)).
3. Unstructured Robust Least-Squares. In this section, we consider the RLS
problem, which is to compute
For we recover the standard LS problem. For every ae ? 0, OE(A; b;
aeOE(A=ae; b=ae; 1), so we take in the sequel, unless otherwise stated. In the remainder
of this paper, OE(A; b) (resp. r(A; b; x)) denotes OE(A; b; 1) (resp. r(A; b; 1; x)). In
the definition above, the norm used for the perturbation bound is the Frobenius norm.
As seen shortly, the worst-case residual is the same when the norm used is the largest
singular value norm.
3.1. Optimizing the worst-case residual. The following results yield a numerically
efficient algorithm for solving the RLS problem in the unstructured case.
Theorem 3.1. When ae = 1, the worst-case residual (1) is given by
The problem of minimizing r(A; b; x) over x has a unique solution x RLS , referred to
as the RLS solution. This problem can be formulated as the second-order cone program
subject to kAx \Gamma bk
x#
Proof. Fix x . Using the triangle inequality, we have
ROBUST LEAST SQUARES 7
Now choose
if Ax 6= b;
any unit-norm vector otherwise.
Since \Delta is rank-one, we have k\Deltak In addition, we have
which implies that \Delta is a worst-case perturbation (for both the Frobenius and maximum
singular value norms), and that equality always holds in (16). Finally, unicity of the
x follows from the strict convexity of the worst-case residual.
Using an interior-point primal-dual potential reduction method for solving the unstructured
RLS problem (15), the number of iterations is almost constant [46]. Further-
more, each iteration takes O((n+m)m 2 ) operations. A rough summary of this analysis
is that the method has the same order of complexity as one SVD of A.
3.2. Analysis of the optimal solution. Using duality results for SOCPs, we
have the following theorem.
Theorem 3.2. When ae = 1, the (unique) solution x RLS to the RLS problem is
given by
A y b else,
where (-) are the (unique) optimal points for problem (15).
Proof. Using the results of x2.1, we obtain that the problem dual to (15) is
subject to A T z
Since both primal and dual problems are strictly feasible, there exist optimal points
for both of them. If - at the optimum, then
In this case, the optimal x is the (unique) minimum-norm solution to
Now assume - . Again, both primal and dual problems are strictly feasible,
therefore the primal and dual optimal objectives are equal:
Using
and
8 L. EL GHAOUI AND H. LEBRET
Replace these values in A T z to obtain the expression of the optimal x:
A T b; with
Remark 3.1. When - , The RLS solution can be interpreted as the solution
of a weighted LS problem for an augmented system:
A
I3
\Theta
where -). The RLS method amounts to compute the weighting
matrix \Theta that is optimal for robustness, via the SOCP (15). We shall encounter a
generalization of the above formula for the linear-fractional SRLS problem of x5.
Remark 3.2. It is possible to solve the problem when only A is perturbed
In this case, the worst-case residual is kAx kxk, and the optimal x is determined
by (17), where bk. (See the example in x7.2).
3.3. Reduction to a one-dimensional search. When the SVD of A is available,
we can use it to reduce the problem to a one-dimensional convex differentiable problem.
The following analysis will also be useful in x6.
Introduce the SVD of A and a related decomposition for b:
Assume that - at the optimum of problem (15). From (18), we have
never feasible, we may define Multiplying by -, we obtain that
From
1). Thus, the optimal
worst-case residual is
ROBUST LEAST SQUARES 9
where f is the following function
The function f is convex and twice differentiable on [' min 1[. If b 62 Range(A), f
is infinite at twice differentiable on the closed interval [' min 1].
Therefore, the minimization of f can be done using standard Newton methods for
differentiable optimization.
Theorem 3.3. When ae = 1, the solution of the unstructured RLS can be computed
by solving the one-dimensional convex differentiable problem (19), or by computing the
unique real root inside [' min 1] (if any) of the equation' 2
r
The above theorem yields an alternative method for computing the RLS solution.
This method is similar to the one given in [5]. A related approach was used for quadratically
constrained LS problems in [19].
The above solution, which requires one SVD of A, has cost O(nm 2 +m 3 ). The SOCP
method is only a few times more costly (see the end of x3.1), with the advantage that
we can include all kinds of additional constraints on x (nonnegativity and/or quadratic
constraints, etc) in the SOCP (15), with low additional cost. Also, the SVD solution
does not extend to the structured case considered in x4.
3.4. Robustness of LS solution. It is instructive to know when the RLS and
LS solutions coincide, in which case we can say the LS solution is robust. This happens
if and only if the optimal ' in problem (19) is equal to 1. The latter implies b
(that is, b 2 Range(A)). In this case, f is differentiable at its minimum over
[' min 1] is at only if
df
d'
We obtain a necessary and sufficient condition for the optimal ' to be equal to 1. This
condition is
If (21) holds, then the RLS and LS solutions coincide. Otherwise, the optimal ' ! 1, and
x is given by (17). We may write the latter condition in the case when the norm-bound
of the perturbation ae is different from 1 as: ae ? ae min , where
ae min
Thus, ae min can be interpreted as the perturbation level that the LS solution allows. We
note that, when b 2 Range(A), the LS and TLS solution also coincide.
Corollary 3.4. The LS, TLS and RLS solutions coincide whenever the norm-
bound on the perturbation matrix ae satisfies ae - ae min (A; b), where ae min (A; b) is defined
in (22). Thus, ae min (A; b) can be seen as a robustness measure of the LS (or TLS)
solution.
When A is full rank, the robustness measure aemin is non zero, and decreases as the
condition number of A increases.
Remark 3.3. We note that the TLS solution x TLS is the most accurate, in the
sense it minimizes the distance function (see [18]),
and the least robust, in the sense of the worst-case residual. The LS solution, x
is intermediate (in the sense of accuracy and robustness). In fact, it can be shown that
3.5. Robust and Total Least-Squares. The RLS framework assumes that the
data matrices (A; b) are the "nominal" values of the model, which are subject to unstructured
perturbation, bounded in norm by ae. Now, if we think of (A; b) as "mea-
sured" data, the assumption that (A; b) correspond to a nominal model may not be
judicious. Also, in some applications, the norm-bound ae on the perturbation may be
hard to estimate. The Total Least-Squares (TLS) solution, when it exists, can be used
in conjunction with RLS to address this issue.
Assume that the TLS problem has a solution. Let \DeltaA TLS , \Deltab TLS , x TLS be minimizers
of the TLS problem
minimize subject to
and let
ae
TLS finds a consistent, linear system that is closest (in Frobenius norm sense) to the
observed data (A; b). The underlying assumption is that the observed data (A; b) is the
result of a consistent, linear system which, under the measurement process, has been
subjected to unstructured perturbations, unknown but bounded in norm by ae TLS . With
this assumption, any point of the ball
ROBUST LEAST SQUARES 11
can be observed, just as well as (A; b). Thus, TLS computes an "uncertain linear
system" representation of the observed phenomenon: is the nominal model,
and ae TLS is the perturbation level.
Once this uncertain system representation choosing
x TLS as a "solution" to Ax ' b amounts to finding the exact solution to the nominal
system. Doing so, we compute a very accurate solution (with zero residual), which does
not take into account the perturbation level ae TLS . A more robust solution is given by
the solution to the following RLS problem
The solution to the above problem coincides with the TLS one (that is, in our case,
with x TLS ) when ae TLS - ae min
is stricly positive, except when A
With standard LS, the perturbations that account for measurement errors are structured
(with To be consistent with LS, one should consider the following RLS
problem instead of (23):
k\Deltabk-ae LS
It turns out that the above problem yields the same solution as LS itself.
To summarize, RLS can be used in conjunction with TLS for "solving" a linear
system Ax ' b. Solve the TLS problem to build an ``uncertain linear system'' re-presentation
of the observed data. Then, take the solution x RLS to
the RLS problem with the nominal matrices ae TLS .
Note that computing the TLS solution (precisely, A TLS , b TLS and ae TLS ) only requires the
computation of the smallest singular value and associated singular subspace [17].
4. Structured Robust Least Squares. In this section, we consider the SRLS
problem, which is to compute
kffik-ae
where A; b are defined in (2). As before, we assume with no loss of generality that
by r S (A; b; x). Throughout the section, we use the
following
4.1. Computing the worst-case residual. We first examine the problem of
computing the worst-case residual r S (A; b; x) for a given x
With the above notation, we have
F
Now let - 0. Using the S-procedure (lemma 2.1), we have
F
for every ffi, only if there exists a scalar - 0 such that
\Gammag
Using the fact that - 0 is implied by -I - F , we may rewrite the above condition as
\Gammag
0:
The consequence is that the worst-case residual is computed by solving a SDP with
two scalar variables. A bit more analysis shows how to reduce the problem to a one-
dimensional, convex differentiable problem, and obtain the corresponding worst-case
perturbation.
Theorem 4.1. For every x fixed, the squared worst-case residual (for
can be computed by solving the SDP in two variables
subject to (29);
or, alternatively, by minimizing a one-dimensional convex differentiable function:
where
If - is optimal for problem (30), the equations in ffi
have a solution, any of which is a worst-case perturbation.
Proof. See Appendix A, where we also show how to compute a worst-case perturbation

4.2. Optimizing the worst-case residual. Using theorem 4.1, the expression
of F; g; h given in (27), and Schur complements, we obtain following result.
Theorem 4.2. When ae = 1, the Euclidean-norm SRLS can be solved by computing
an optimal solution (-; x) of the SDP
subject to6 4
ROBUST LEAST SQUARES 13
where M(x) is defined in (26).
Remark 4.1. Straightforward manipulations show that the result are coherent with
the unstructured case.
Although the above SDP is not directly amenable to the more efficient SOCP
formulation, we may devise special interior-point methods for solving the problem.
These special-purpose methods will probably have much greater efficiency than general-purpose
SDP solvers. This study is left for the future.
Remark 4.2. The discussion of x3.5 extends to the case when the perturbations are
structured. TLS problems with (affine) structure constraints on perturbation matrices
are discussed in [7]. While the structured version of the TLS problem becomes very hard
to solve, the SRLS problem retains polynomial-time complexity.
5. Linear-Fractional SRLS. In this section, we examine a generalization of the
SRLS problem. Our framework encompasses the case when the functions A(ffi), b(ffi)
are rational. We show that the computation of the worst-case residual is NP-complete,
but that upper bounds can be computed (and optimized) using SDP. First, we need
to motivate the problem, and develop a formalism for posing it. This formalism was
introduced by Doyle and coauthors [9] in the context of robust identification.
5.1. Motivations. In some structured robust least-squares problems such as (3),
it may not be convenient to measure the perturbation size with Euclidean norm. Indeed,
the latter implies a correlated bound on the perturbation. One may instead consider a
SRLS problem, in which the bounds are not correlated, that is, the perturbation size
in (3) is measured by the maximum norm:
kffik 1-1
Also, in some RLS problems, we may assume that some columns of [A b] are perfectly
known, for instance the error [\DeltaA \Deltab] has the form
and otherwise unknown. More generally, we may be interested in SRLS problems, where
the perturbed data matrices write
A(\Delta) b(\Delta)
A b
are given matrices, and \Delta is a (full) norm-bounded matrix. In
such a problem, the perturbation is not structured, except via the matrices L; RA
(Note that a special case of this problem is solved in [5].)
Finally, we may be interested in SRLS problems in which the matrix functions
A(ffi), b(ffi) in (3) are rational functions of the parameter vector ffi. One example is given
in x7.6.
It turns out that the above three extensions can be addressed using the same
formalism, which we detail now.
5.2. Problem definition. Let D be a subspace of R N \ThetaN , A 2 R n\Thetam
R n\ThetaN , RA 2 R N \Thetam , R b 2 R N , D 2 R N \ThetaN . For every \Delta 2 D such that det(I \GammaD\Delta) 6= 0,
14 L. EL GHAOUI AND H. LEBRET
we define the matrix functions
A(\Delta) b(\Delta)
A b
For a given x we define the worst-case residual by
r D (A; b; ae; x) \Delta
\Delta2D; k\Deltak-ae
We say that x is a Structured Robust Least Squares (SRLS) solution if x minimizes the
worst-case residual above. As before, we assume no loss of generality, and
denote r D (A; b; 1; x) by r D (A; b; x).
The above formulation encompasses the three situations referred to in x5.1. First,
the maximum-norm SRLS problem (33) is readily transformed into problem (35), as
follows. Let n\ThetaN be such that [A i b i
R T
Problem (33) can be formulated as the minimization of (35), with D defined as above.
Also, we recover the case when the perturbed matrices write as in (34), when we
allow \Delta to be any full matrix (that is, In particular, we recover the
unstructured RLS problem of x3, as follows. Assume n ? m. We have
\Deltab \Theta
refers to dummy elements that are added to
the perturbation matrix in order to make it a square, n \Theta n matrix.) In this case, the
perturbation set D is R n\Thetan .
Finally, the case when A(ffi) and b(ffi) are rational functions of a vector ffi (well-
defined over the unit ball fffi j kffik 1 - 1g) can be converted (in polynomial time) into
the above framework (see e.g. [48] for a conversion procedure). We give an example of
such a conversion in x7.6.
5.3. Complexity analysis. In comparison with the SRLS problem of x4, the
linear-fractional SRLS problem offers two levels of increased complexity.
First, checking whether the worst-case residual is finite is NP-complete [6]. The
linear-fractional dependence (that is, D 6= 0) is a first cause of increased complexity.
The SRLS problem above remains hard even when matrices A(ffi), b(ffi) depend
affinely on the perturbation elements 0). Consider for instance the SRLS problem,
with and in which D is defined as in (36). In this case, the problem of computing
the worst-case residual can be formulated as
kffik 1-1
F
ROBUST LEAST SQUARES 15
for appropriate F; g; h. The only difference with the wost-case residual defined in (28)
is the norm used to measure perturbation. Computing the above quantity is NP-complete
(it is equivalent to a MAX CUT problem [36, 38]). The following lemma,
which we provide for the sake of completeness, is a simple corollary of a result by
Nemirovskii [32].
Lemma 5.1. The problem P(A;b; D; x):
Given a positive rational number -, matrices A; b; L; RA of appropriate
size, and an m-vector x, all with rational entries, and a linear
subset D, determine whether r D (A; b; x) -
is NP-complete.
Proof. See appendix B.
5.4. An upper bound on the worst-case residual. Although our problem is
NP-complete, we can minimize upper bounds in polynomial-time, using SDP. Introduce
the following linear subspaces:
R. The inequality - ? r D (A; b; x) holds if and only if, for every \Delta 2 D,
0:
Using Lemma 2.3, we obtain that - ? r D (A; b; x) holds if there exist S 2 S, G 2 G,
such that
G; x) =6 4 \Theta Ax \Gamma b
where
\Theta \Delta
Minimizing - subject to the above semidefinite constraint yields an upper bound for
r D (A; b; x). It turns out that the above estimate of the worst-case residual is actually
exact, in some "generic" sense.
Theorem 5.2. When ae = 1, an upper bound on the worst-case residual r D (A; b; x)
can be obtained by solving the SDP
- subject to S 2 G; (38):
The upper bound is exact when D = R N \ThetaN . If \Theta ? 0 at the optimum, the upper bound
is also exact.
Proof. See appendix C.
L. EL GHAOUI AND H. LEBRET
5.5. Optimizing the worst-case residual. Since x appears linearly in the constraint
(38), we may optimize the worst-case residual's upper bound using SDP. We may
reduce the number of variables appearing in the previous problem, using the elimination
lemma 2.4. Inequality in (38) can be written as in (11), with
\GammaR b
A
where \Theta is defined in (39).
Denote by N the orthogonal complement of [A T R T
. Using the elimination
lemma 2.4, we obtain an equivalent condition for (38) to hold for some x namely
G; \Theta ? 0; (N
\GammaR b
\Gammab \GammaR b -7 5 (N
For every -; S; G that are stricly feasible for the above constraints, an x that satisfies (38)
is given, when RA is full-rank, by
A
A
\Theta \Gamma1
A
RA
A
A
\Theta \Gamma1
(To prove this, we applied formula (13), and took oe !1.)
Theorem 5.3. When ae = 1, an upper bound on the optimal worst-case residual
can be obtained by solving the SDP
- subject to S 2 G; (38);
or, alternatively, the SDP
- subject to (41):
The upper bound is always exact when D = R N \ThetaN . If \Theta ? 0 at the optimum, the
upper bound is also exact. The optimal x is then unique, and given by (42) when RA is
full-rank.
Proof. See appendix C.
Remark 5.1. In parallel to the unstructured case (see remark 3.1), the linear-
fractional SRLS can be interpreted as a weighted LS for an augmented system. Precisely,
when \Theta ? 0, the linear-fractional SRLS solution can be interpreted as the solution of a
weighted LS problem:
A
RA
The SRLS method amounts to compute the weighting matrix \Theta that is optimal for
robustness.
ROBUST LEAST SQUARES 17
Remark 5.2. Our results are coherent with the unstructured case: replace L by I,
R by [I 0] T , variable S by -I, and set G = 0. The parameter - of theorem 3.2 can be
interpreted as the Schur complement of -I \Gamma LSL T in the matrix \Theta.
Remark 5.3. We emphasize that the above results are exact (non conservative)
when the perturbation structure is full. In particular, we recover (and generalize) the
results of [5] in the case when only some columns of A are affected by otherwise unstructured
perturbations.
Remark 5.4. When is possible to use the approximation method of [16] to
obtain solutions (based on the SDP relaxations given in theorem 5.3) that have expected
value within 14% of the true value.
6. Link with regularization. The standard LS solution x LS is very sensitive to
errors in A; b when A is ill-conditioned. In fact, the LS solution might not be a continuous
function of A; b when A is near-deficient. This has motivated many researchers
for ways to regularize the LS problem, which is to make the solution x unique and
continuous in the data matrices (A; b). In this section, we briefly examine the links of
our RLS and SRLS solution with regularization methods for standard LS.
Beforehand, we note that since all our problems are formulated as SDPs, we could
invoke the quite complete sensitivity analysis results obtained by Bonnans, Cominetti
and Shapiro [3]. The application of these general results to our SDPs is considered
in [35].
6.1. Regularization methods for LS. Most regularization methods for LS amount
to impose an additional bound on the solution vector x. One way is to minimize
where\Omega is some squared-norm (see [23, 43, 8]). Another way is to
use constrained least-squares (see [18, p.561-571]).
In a classical Tikhonov regularization method, \Omega\Gamma
some "regularization" parameter. The modified value of x is obtained by solving an
augmented LS problem
and is given by
(Note that for every - ? 0, the above x is continuous in (A; b).)
The above expression also arises in the Levenberg-Marquardt method for optimiza-
tion, or in the Ridge regression problem [17]. As mentioned in [18], the choice of an
appropriate - is problem-dependent, and in many cases, not obvious.
In more elaborate regularization schemes of the Tikhonov type, the identity matrix
in (46) is replaced with a positive semidefinite weighting matrix (see for instance [31, 8]).
Again, this can be interpreted as a (weighted) least-squares method for an augmented
system.
L. EL GHAOUI AND H. LEBRET
6.2. RLS and regularization. Noting the similarity between (17) and (46), we
can interpret the (unstructured) RLS method as one of Tikhonov regularization. The
following theorem yields an estimate of the "smoothing effect" of the RLS method.
Note that improved regularity results are given in [35].
Theorem 6.1. The (unique) RLS solution x RLS and the optimal worst-case residual
are continuous functions of the data matrices A; b. Furthermore, if K is a compact set
of R n , and then for every uncertainty size ae ? 0, the function
R n\Thetam \Theta K \Gamma! [1 dK
is Lipschitzian, with Lipschitz constant 1
Theorem 6.1 shows that any level of robustness (that is, any norm-bound on perturbations
ae ? regularization. We describe in x7 some numerical examples
that illustrate our results.
Remark 6.1. In the RLS method, the Tikhonov regularization parameter - is
chosen by solving a second-order cone problem, in such a way that - is optimal for
robustness. The cost of the RLS solution is equal to the cost of solving a small number
of least-squares problems of the same size as the classical Tikhonov regularization
problem (45).
Remark 6.2. The equation that determines - in the RLS method is
ae
This choice has resemblance with Miller's choice [30], where - is determined recursively
by the equations
This formula arises in RLS when there is no perturbation in b (see remark 3.2). Thus,
Miller's solution corresponds to a RLS problem in which the perturbation affects only
the columns of A. We note that this solution is not necessarily regular (continuous).
Total least-squares (TLS) deserves a special mention here. When the TLS problem
has a solution, it is given by x oe is the smallest singular
value of [A b]. This corresponds to (46). The negative value of - implies
that the TLS is a "deregularized" LS, a fact noted in [17]. In view of our link between
regularization and robustness, the above is consistent with the fact that RLS trades off
the accuracy of TLS with robustness and regularity, at the expense of introducing bias
in the solution. See also remark 3.3.
6.3. SRLS and regularization. Similarly, we may ask whether the solution to
the SRLS problem of x4 is continuous in the data matrices A as was the case
for unstructured RLS problems. We only discuss continuity of the optimal worst-case
ROBUST LEAST SQUARES 19
residual with respect to problems, the coefficient matrices A
are fixed).
In view of Theorem 4.2, continuity holds if the feasible set of the SDP (32) is
bounded. Obviously, the objective - is bounded above by
Thus the variable - is also bounded, as (32) implies 0 -. With - bounded
above, we see that (32) implies that x is bounded if
bounded implies x bounded.
The above property holds if and only if [A T
Theorem 6.2. A sufficient condition for continuity of the optimal worst-case
residual (as a function of
6.4. Linear-fractional SRLS and regularization. Precise conditions for continuity
of the optimal upper bound on worst-case residual in the linear-fractional case
are not known. We may however regularize this quantity using a method described
in [29] for a related problem. For a given ffl ? 0, define the bounded set
ae
ffl I
oe
where S is defined in (37). It is easy to show that restricting the condition number of
variable S also bounds the variable G in the SDP (44). This yields the following result.
Theorem 6.3. An upper bound on the optimal worst-case residual can be obtained
by computing the optimal value -(ffl) of the SDP
min
- subject to S 2 G; (41):
The corresponding upper bound is a continuous function of [A b]. As ffl ! 0, the
corresponding optimal value -(ffl) has a limit, equal to the optimal value of SDP (44).
As noted in remark 5.1, the linear-fractional SRLS can be interpreted as a weighted
LS, and so can the above regularization method. Thus, the above method belongs to
the class of Tikhonov (or weighted LS) regularization methods referred to in 6.1, the
weighting matrix being optimal for robustness.
7. Numerical examples. The following numerical examples were obtained using
two different codes: for SDPs, we used the code SP [45], and a matlab interface to SP
called [10]. For the (unstructured) RLS problems, we used the second-order
cone program described in [28].
L. EL GHAOUI AND H. LEBRET
#iter
Vertical bars indicate deviation
for 20 trials, with
mean
min
#iter
Vertical bars indicate deviation
for 20 trials, with
mean
min
Fig. 1. Average, minimum and maximum number of iterations for various RLS problems using the
SOCP formulation. In the left figure, we show these numbers for values of n ranging from 100 to 1000.
For each value of n, the vertical bar indicates the minimum and maximum values obtained with 20
trials of A; b, with In the right figure, we show these numbers for values of m ranging from
11 to 100. For each value of n, the vertical bar indicates the minimum and maximum values obtained
with 20 trials of A; b, with 1000. For both plots, the plain curve is the mean value.
7.1. Complexity estimates of RLS. We first did "large-scale" experiments for
the RLS problem of x3. As mentioned in x2.1, the number of iterations is almost independent
of the size of the problem for SOCPs. We have solved problem (15) for
uniformly generated random matrices A and vectors b with various sizes of n; m. Figure
1 shows the average number of iterarions as well as the minimum and maximum
number of iterations for various values of n; m. The experiments confirm the fact the
number of iterations is almost independent of problem size for the RLS problem.
7.2. LS, TLS and RLS. We now compare the LS, TLS and RLS solutions for
On the left and right plots in Fig. 2, we show the four points
signs and the corresponding linear fits for LS problems (solid line), TLS problems
(dotted line) and RLS problems for (dashed lines). The left plot gives the RLS
solution with perturations [A+\DeltaA; b+\Deltab] whereas the right plot considers perturbation
in A only, [A In both plots, the worst-case points for the RLS solution are
indicated by 0 2. As ae increases, the slope of the RLS solution
decreases, and goes to zero when ae ! 1. The plot confirms remark 3.3: the TLS
solution is the most accurate and the least robust, and LS is intermediate.
In the case when we have perturbations in A only (right plot), we obtain an instance
of a linear-fractional SRLS (with a full perturbation matrix), as mentioned in x5.1. (It
is also possible to solve this problem directly, as in x3.) In this last case of course, the
worst-case perturbation can only move along the A-axis.
ROBUST LEAST SQUARES 21
A
TLS
RLS
A
TLS
RLS
Fig. 2. Least-squares (solid), total least-squares (dotted) and robust least-squares (dashed) solutions.
The signs + correspond to the nominal [A b]. The left plot gives RLS solution with perturations
the right plot considers perturbation in A only, [A b]. The worst-case
perturbed points for the RLS solution are indicated by 0 2.
7.3. RLS and regularization. As mentioned in x6, we may use RLS to regularize
an ill-conditioned LS problem. Consider the RLS problem for
The matrix A is singular when
Fig. 3 shows the regularizing effect of the RLS solution. The left (resp. right) figure
shows the optimal worst-case residual (resp. norm of RLS solution) as a function of the
parameter ff, for various values of ae. When ae = 0, we obtain the LS solution. The latter
is not a continuous function of ff, and both the solution norm and residual exhibit a
spike for becomes singular). For ae ? 0, the RLS solution is smooth.
The spike is more and more flattened as ae grows, which illustrates theorem 6.1. For
1, the optimal worst-case residual becomes flat (independent of ff), and equal to
7.4. Robustness of LS solution. The next example illustrates that sometimes
(precisely, if b 2 Range(A)), the LS solution is robust, up to the perturbation level
ae min defined in (22). This "natural" robustness of the LS solution degradates as the
condition number of A grows. For " A ? 0, consider the RLS problem for
":1
We have considered six values of " A (which equals the inverse of the condition
number of A) from .05 to .55. Table 1 shows the values of ae min (as defined in (22)) for
22 L. EL GHAOUI AND H. LEBRET
ff
dashed
dashed dotted
ff
Fig. 3. Optimal worst-case residual and norm of RLS solution vs. ff for various values of perturbation
level ae. For the optimal residual and solution are discontinuous. The spike is
smoothed as more robustness is asked for (that is, when ae increases). On the right plot the curves for
are not visible.

Table
Values of ae min for various " A .
curve
ae min 0.06 0.34 0.78 1.12 1.28 1.35
the six values of " A . When the condition number of A grows, the robustness of the LS
solution (measured by ae min ) decreases.
The right plot of Fig. 4 gives the worst-case residual vs. the robustness parameter
ae for the six values of " A . The plot illustrates that for ae ? ae min , the LS solution (in
our case, A differs from the RLS one. Indeed, for each curve, the residual remains
equal to zero as long as ae - ae min . For example, the curve labeled '1' (corresponding to
quits the x-axis for ae - ae
The left plot of Fig. 4 corresponds to the RLS problem with
of " A . This plot shows the various functions f(') as defined in (20). For each value of
" A , the optimal ' (hence the RLS solution) is obtained by minimizing the function f .
The three smallest values of " A induce functions f (as defined in (20)) that are minimal
1. For the three others, the optimal ' is 1. This means that ae min is smaller
than 1 in the first three cases and larger than 1 in the other cases. This is confirmed in

Table

1.
7.5. Robust identification. Consider the following system identification prob-
lem. We seek to estimate the impulse response h of a discrete-time system from its input
u and output y. Assuming that the system is single-input and single-ouput, linear, and
of order m, and that u is zero for negative time indices, y, u and h are related by the
ROBUST LEAST SQUARES 23
6 531
Fig. 4. The left plot shows function f(') (as defined in (20)) for the six values of " A (for ae = 1).
The right plot gives the optimal RLS residuals versus ae for the same values of " A . The labels
correspond to values of " A given in Table 1.
convolution equations y, where
and U is a lower triangular Toeplitz matrix whose first column is u. Assuming are
known exactly leads to a linear equation in h, which can be computed with standard
LS.
In practive however, both y and u are subject to errors. We may assume for
instance that the actual value of y is y ffiy, and that of u is u are
unknown-but-bounded perturbations. The perturbed matrices U; y write
is the i-th column of the m \Theta m identity matrix, and U i are lower
triangular Toeplitz matrices with first column equal to e i .
We first assume that the sum of the input and output energies is bounded, that is
We adress the following
min
kffik-ae
As an example, we consider the following nominal values for
In Fig. 5, we have shown the optimal worst-case residual and that corresponding to
the LS solution, as given by solving problems (30) and (32), respectively. Since the LS
L. EL GHAOUI AND H. LEBRET
solution has zero residual (U is invertible), we can prove (and check on the figure) that
the worst-case residual grows linearly with ae. In contrast, the RLS optimal worst-case
residual has a finite limit as ae !1.
RLS
ae
Fig. 5. Worst-case residuals of LS and euclidean-norm SRLS solutions for various values of perturbation
level ae. The worst-case residual for LS has been computed by solving problem (30), with
fixed.
We now assume that the perturbation bounds on y; u are not correlated. For
instance, we consider problem (48), with the bound kffik - ae replaced with
Physically, the above bounds mean that the output energy and peak input are bounded.
This problem can be formulated as minimizing the worst-case residual (35), with
[A
and \Delta has the following structure:
Here, the symbols \Theta denote dummy elements of \Delta that were added in order to work with
a square perturbation matrix. The above structure corresponds to the set D in (36),
with
In Fig.6, we show the worst-case residual vs. ae, the uncertainty size. We show the
curves corresponding to the values predicted by solving the SDP (43), with x variable
ROBUST LEAST SQUARES 25
upper bound (LS solution)
lower bound (LS solution)
upper bound (RLS solution)
lower bound (RLS solution)
ae
Fig. 6. Upper and lower bounds on worst-case residuals for LS and RLS solutions. The upper bound
for LS has been computed by solving the SDP (38), with fixed. The lower bounds corresponds
to the largest residuals kU(ffi trial )x \Gamma y(ffi trial )k among 100 trial points ffi trial , with
(RLS solution), and x fixed to the LS solution x LS . We also show lower bounds on the
worst-case, obtained using 100 trial points. This plot shows that, for the LS solution,
our estimate of the worst-case residual is not exact, and the discrepancy grows linearly
with uncertainty size. In contrast, for the RLS solution the estimate appears to be
exact for every value of ae.
7.6. Robust interpolation. The following example is a robust interpolation
problem that can be formulated as a linear-fractional SRLS problem. For given integers
a polynomial of degree
interpolates given points (a that is
If we assume that (a are known exactly, we obtain a linear equation in the unknown
x, with a Vandermonde structure:6 6 4
which can be solved via standard LS.
Now assume that the interpolation points are not known exactly. For instance, we
may assume that the b i 's are known, while the a i 's are parameter-dependent:
a
where the ffi i 's are unknown-but-bounded: jffi
We seek a robust interpolant, that is, a solution x that minimizes
kffik 1-ae
26 L. EL GHAOUI AND H. LEBRET
where
The above problem is a linear-fractional SRLS problem. Indeed, it can be shown
that
where
and, for each i,
. a i
. a i
. 1
(Note that det(I \Gamma D\Delta) 6= 0, since D is stricly upper triangular.)
In Fig. 7, we have shown the result
a 1 =6 423
The LS solution is very accurate (zero nominal residual: every point is interpolated ex-
actly), but has a (predicted) worst-case residual of 1:7977. The RLS solution trades off
this accuracy (only one point interpolated, and nominal residual of 0:8233) for robustness
(with a worst-case residual less than 1:1573). As ae ! 1, the RLS interpolation
polynomial becomes more and more horizontal. (This is consistent with the fact that
we allow perturbations on vector a only.) In the limit, the interpolation polynomial is
the solid line
ROBUST LEAST SQUARES 27
Fig. 7. Interpolation polynomials: LS and RLS solutions for 0:2. The LS solution interpolates the
points exactly, while the RLS one guarantees a worst-case residual error less than 1:1573. For
the RLS solution is the zero polynomial.
8. Conclusions. This paper shows that several robust least-squares (RLS) problems
with unknown-but-bounded data matrices are amenable to (convex) second-order
cone or semidefinite programming (SOCP or SDP). The implication is that these RLS
problems can be solved in polynomial-time, and efficiently in practice.
When the perturbation enters linearly in the data matrices, and its size is measured
by Euclidean norm, or in a linear-fractional problem with full perturbation matrix \Delta,
the method yields the exact value of the optimal worst-case residual. In the other
cases we have examined (such as arbitrary rational dependence of data matrices on the
perturbation parameters), computing the worst-case residual is NP-complete. We have
shown how to compute, and optimize, using SDP, an upper bound on the worst-case
residual, that takes into account structure information.
In the unstructured case, we have shown that both the worst-case residual and
the (unique) RLS solution are continuous. The unstructured RLS can be interpreted
as a regularization method for ill-conditioned problems. A striking fact is that the
cost of the RLS solution is equal to a small number of least-squares problems arising
in classical Tikhonov regularization approaches. This method provides a rigorous way
to compute the optimal parameter from the data and associated perturbation bounds.
Similar (weighted) least-squares interpretations and continuity results were given for
the structured case.
In our examples, we have demonstrated the use of a SOCP code [27], and a general-purpose
semidefinite programming code, SP [45]. Future work could be devoted to
writing special code that exploits the structure of these problems, in order to further
increase the efficiency of the method. For instance, it seems that, in many problems,
the perturbation matrices are sparse, and/or have special (e.g., Toeplitz) structure.
The method can be used for several related problems.
Constrained RLS. We may consider problems where additional (convex) constraints
are added on the vector x. (Such constraints arise naturally in e.g.,
image processing). For instance, we may consider problem (1) with an addi-
28 L. EL GHAOUI AND H. LEBRET
tional linear (resp. quadratic convex) constraint (Cx) i - 0,
To solve such a problem, it suffices
to add the related constraint to corresponding SOCP or SDP formulation.
(Note that the SVD approach of x3.3 fails in this case.)
ffl RLS problems with other norms. We may consider RLS problems in which the
worst-case residual error in measured in other norms, such as the maximum
ffl Matrix RLS. We may of course, derive similar results when the constant term
b is a matrix. The worst-case error can be evaluated in a variety of norms.
ffl Error-in-Variables RLS. We may consider problems where the solution x is
also subject to uncertainty (due to implementation and/or quantization errors).
That is, we may consider a worst-case residual of the form
are given. We may compute (and optimize) upper bounds
on the above quantity using SDP. This subject is examined in [25].

Acknowledgments

. The authors wish to thank the anonymous reviewers for their
precious comments, which led to many improvements over the first version of this paper.
We are particularly indebted to the reviewer who pointed out the SOCP formulation
for the unstructured problem. We also thank G. Golub and R. Tempo for providing
us with some related references, and A. Sayed for sending us the preliminary draft [5].
The paper has also benefited from many fruitful discussions with S. Boyd, F. Oustry,
B. Rottembourg and L. Vandenberghe.
A. Proof of Theorem 4.1. Introduce the eigendecomposition of F and a related
decomposition for g:
writes
at the optimum, then there exists a nonzero vector
u such that (-I \Gamma F From inequality (29), we conclude that g T In
other words, - g)-controllable, and u is an eigenvector that proves this
uncontrollability. Using in (49), we obtain the optimal value of - in this case:
Thus, the worst-case residual can be computed as claimed in the theorem.
ROBUST LEAST SQUARES 29
For every pair (-) that is optimal for problem (29), we can compute a worst-case
perturbation as follows. Define
We have - at the optimum if and only -
(that is, g)-controllable and the function f defined
in (31) satisfies
df
d-
0:
In this case, the optimal - satisfies
that is, kffi 1. Using this and (50), we obtain
F
This proves that ffi 0 is a worst-case perturbation.
at the optimum, then
df
d-
which implies that kffi 0 k - 1. Since - max there exists a vector u such that
loss of generality, we may assume that the vector
We have
F
This proves that ffi defined above is a worst-case perturbation.
In both cases seen above (- equals - worst-case perturbation is
any vector ffi such that
(We have just shown that the above equations always have a solution ffi when - is
optimal.) This ends our proof.
B. Proof of Lemma 5.1. We use the following result, due to Nemirovsky [32].
Lemma B.1. Let \Gamma(p; a) be a scalar function of positive integer p and p-dimensional
vector a, such that, first, \Gamma is well-defined and takes rational values from (0; kak \Gamma2 )
for all positive integers p and all p-dimensional vectors a with kak - 0:1, and second,
the value of this function at a given pair (p; a) can be computed in time polynomial in
p and the length of the standard representation of the (rational) vector a. Then the
problem
L. EL GHAOUI AND H. LEBRET
Given an integer p - 0 and a 2 R p , kak - 0:1, with rational positive
entries, determine whether
kffik 1-1
is NP-complete. Besides this, either (51) holds, or
kffik 1-1
where d(a) is the smallest common denominator of the entries of a.
To prove our result, it suffices to show that for some appropriate function \Gamma satisfying
to the conditions of lemma B.1, we can reduce, for any given p; a, problem
to ours, in polynomial time. Set
2a T a
(a T a
This function satisfies all requirements of lemma B.1, so problem P \Gamma (p; a) is NP-hard.
Given rational positive entries, set A, b, D and x as follows.
First, set D to be the set of diagonal matrices of R p\Thetap . Set
Finally, set A, b as in (34) and 1, the worst-case
residual for this problem is
r D (A; b;
kffik 1-1
kffik 1-1
Our proof is now complete.
C. Proof of Theorem 5.3. In this section, we only prove theorem 5.3. The proof
of theorem 5.2 follows the same lines. We start from problem (43), the dual of which is
the maximization of 2(b T w +R T
b u) subject to
and the linear constraints
A
G; TrG(Y
ROBUST LEAST SQUARES 31
Since both primal and dual problems are strictly feasible, every primal and dual
feasible points are optimal if and only if ZF(-; G; is defined in (38)
(see [46]). One obtains, in particular,
G.
Using equation (58) and (55), we obtain
which implies that from equality of the primal and dual objectives (the trivial
case can be easily ruled out).
Assume that the matrix \Theta defined in (39) is positive-definite at the optimum. From
equations (57)-(59), we deduce that the dual variable Z is rank-one:
w
Using (57) and (59), we obtain
\Theta
From (55), it is easy to derive the expression (42) for the optimal x in the case when
\Theta ? 0 at the optimum, and RA is full-rank.
We now show that the upper bound is exact at the optimum in this case. If we use
condition (54), and the expression for Z; V deduced from (53), we obtain
This implies that there exists I, such that
\Theta ? 0, a straightforward application of lemma 2.3 shows that det(I \Gamma D\Delta) 6= 0, so we
obtain
(from (61)) and
(from (53)), we have 1=2. We can now compute
(from (55) and (60)).
L. EL GHAOUI AND H. LEBRET
Therefore,
(from
We obtain which proves that the matrix \Delta is a worst-case
perturbation.



--R

An efficient newton barrier method for minimizing a sum of euclidean norms

Pertubed optimization under the second order regularity hypothesis
Linear Matrix Inequalities in System and Control Theory
A new linear least-squares type model for parameter estimation in the presence of data uncertainties
Computing the real structured singular value is NP-hard
Structured total least squares and L 2 approximation problems
Image reconstruction and restoration: overview of common estimation problems
Unifying robustness analysis and system ID
LMITOOL: A front-end for LMI op- timization
Algorithms for the regularization of ill conditioned least-squares problems

Robustness in the presence of mixed parametric uncertainty and unmodeled dynamics
Collinearity and total least squares
Optimization of weighting constant for regularization in least squares system identification

An analysis of the total least squares problem

Quadratically constrained least squares and quadratic prob- lems
The robust generalized least-squares estimator
Regularization methods for large-scale problems
Backward error and condition of structured linear systems
The application of constrained least-squares estimation to image restoration by digital computer
All controllers for the general H1 control problem: LMI existence conditions and state space formulas

Social Sciences
Synth'ese de diagrammes de r'eseaux d'antennes par optimisation convexe

On continuity/discontinuity in robustness indicators
Least squares methods for ill-posed problems with a prescribed bound

Several NP-hard problems arising in robust stability analysis
Interior point polynomial methods in convex programming: Theory and applications
and application of bounded parameter models
Robust solutions to uncertain semidefinite pro- grams


Checking robust nonsingularity is NP-hard
Matrix Anal.
a connection between robust control and identifica- tion
Indefinite trust region subproblems and nonsymmetric eigenvalue perturbations

Solutions of Ill-Posed Problems
The total least squares problem: computational aspects and analysis


Robust estimation techniques in regularized image restora- tion
Robust and Optimal Control
--TR

--CTR
Michele Covell , Sumit Roy , Beomjoo Seo, Predictive modeling of streaming servers, ACM SIGMETRICS Performance Evaluation Review, v.33 n.2, p.33-35, September 2005
Jos F. Sturm , Shuzhong Zhang, On cones of nonnegative quadratic functions, Mathematics of Operations Research, v.28 n.2, p.246-267, May
Alexei R. Pankov , Konstantin V. Siemenikhin, Minimax estimation for singular linear multivariate models with mixed uncertainty, Journal of Multivariate Analysis, v.98 n.1, p.145-176, January 2007
Arvind Nayak , Emanuele Trucco , Neil A. Thacker, When are Simple LS Estimators Enough? An Empirical Study of LS, TLS, and GTLS, International Journal of Computer Vision, v.68 n.2, p.203-216, June 2006
Mohit Kumar , Regina Stoll , Norbert Stoll, Robust Solution to Fuzzy Identification Problem with Uncertain Data by Regularization, Fuzzy Optimization and Decision Making, v.3 n.1, p.63-82, March 2004
Jianchao Yao, Estimation of 2D displacement field based on affine geometric invariance and scene constraints, International Journal of Computer Vision, v.46 n.1, p.25-50, January 2002
Budi Santosa , Theodore B. Trafalis, Robust multiclass kernel-based classifiers, Computational Optimization and Applications, v.38 n.2, p.261-279, November  2007
Dimitris Bertsimas , Dessislava Pachamanova, Robust multiperiod portfolio management in the presence of transaction costs, Computers and Operations Research, v.35 n.1, p.3-17, January, 2008
Juan Liu , Ying Zhang , Feng Zhao, Robust distributed node localization with error management, Proceedings of the seventh ACM international symposium on Mobile ad hoc networking and computing, May 22-25, 2006, Florence, Italy
D. Goldfarb , G. Iyengar, Robust portfolio selection problems, Mathematics of Operations Research, v.28 n.1, p.1-38, February
Pannagadatta K. Shivaswamy , Chiranjib Bhattacharyya , Alexander J. Smola, Second Order Cone Programming Approaches for Handling Missing and Uncertain Data, The Journal of Machine Learning Research, 7, p.1283-1314, 12/1/2006
Ivan Markovsky , Sabine Van Huffel, Overview of total least-squares methods, Signal Processing, v.87 n.10, p.2283-2302, October, 2007
Mung Chiang, Geometric programming for communication systems, Communications and Information Theory, v.2 n.1/2, p.1-154, July 2005
uncertainty;robustness;ill-conditioned problem;regularization;least-squares problems;second-order cone programming;robust identification;robust interpolation;semidefinite programming