Minimum ℓ1, ℓ2, and ℓ∞ Norm Approximate Solutions to an Overdetermined System of Linear Equations

Cadzow, J. A., Minimum ℓ₁, ℓ₂, and ℓ_∞ Norm Approximate Solutions to an Overdetermined System of Linear Equations, Digital Signal Processing12 (2002) 524–560Many practical problems encountered in digital signal processing and other quantitative oriented disciplines entail finding a best approximate solution to an overdetermined system of linear equations. Invariably, the least squares error approximate solution (i.e., minimum ℓ₂ norm) is chosen for this task due primarily to the existence of a convenient closed expression for its determination. It should be noted, however, that in many applications a minimum ℓ₁ or ℓ_∞ norm approximate solution is preferable. For example, in cases where the data being analyzed contain a few data outliers a minimum ℓ₁ approximate solution is preferable since it tends to ignore bad data points. In other applications one may wish to determine an approximate solution whose largest error magnitude is the smallest possible (i.e., a minimum ℓ_∞ norm approximate solution). Unfortunately, there do not exist convenient closed form expressions for either the minimum ℓ₁ or the minimum ℓ_∞ norm approximate solution and one must resort to nonlinear programming methods for their determination. Effective algorithms for determining these two solutions are herein presented (see Cadzow, J. A., Data Analysis and Signal Processing: Theory and Applications).     

Worst-case identification in ℓ2: linear and nonlinear algorithms

We consider worst-case identification in the ℓ₂ norm. Given an unknown system h ε ℓ₁ one wishes to choose bounded inputs u ε ℓ∞ such that given finitely many corrupted output measurements {y(k): 0 ≤ k}of Y = h*u + η, where η is noise, assumed small, one can construct an approximation g with g - h₂ → 0 as η∞ → 0 and n → ∞. It is shown that inputs can be chosen such that to identify a sequence of length n with an ℓ₂ error of O(η∞) one requires only O(n) measurements. A numerical example is inclu     

Tight error bounds for projection algorithms in conditional set membership estimation

In set membership estimation, conditional problems arise when the estimate must belong to a given set of assigned structure. Conditional projection algorithms provide estimates that are suboptimal in terms of the worst-case estimation error. In order to precisely evaluate the suboptimality level of these estimators, tight upper bounds on the estimation errors must be computed as a function of the conditional radius of information, which represents the minimum achievable error. In this paper, tight bounds are derived for ℓ_∞ and ℓ₁ estimation errors, in a general setting which allows to consider any compact set of feasible problem elements and linearly parameterized estimates.     

On computing the worst-case peak gain of linear systems

Based on the bounds due to Doyle and Boyd, we present simple upper and lower bounds for the l¹-norm of the ‘tail’ of the impulse response of finite-dimensional discrete-time linear time-invariant systems. Using these bounds, we may in turn compute the l^∞-gain of these systems to any desired accuracy. By combining these bounds with results due to Khammash and Pearson, we derive upper and lower bounds for the worst-case l^∞-gain of discrete-time systems with diagonal perturbations.     

Nonlinear H∞ control around periodic orbits

In this paper, we study the nonlinear H_∞ control of systems with periodic orbits. We develop the notion of an induced L₂ gain (so-called nonlinear H_∞ norm) for systems where the no-disturbance behavior of the system is a periodic orbit and provide conditions under which the induced L₂ gain of the system (around the orbit) can be made less than a specified value by state feedback. This work is a natural extension of results on nonlinear H_∞ control of nonlinear systems in a neighborhood of a stable equilibrium point to the periodic orbit case. Synthesis of a nonlinear H_∞ state feedback controller is facilitated by the use of transverse coordinates and, in particular, the transverse linearization of the system.     

On the 2-induced norm of a sampled-data system

Formulas are given for the norms of SG and GH: G is a linear continuous-time system, S an ideal sampler, and H a zero-order hold; the signal spaces are ₂(−∞, ∞) (continuous-time) and l₂(Z) (discrete-time). These formulas are then applied to problems of uniformly optimal control of sampled-data systems.     

Stabilization and H control of symmetric systems: an explicit solution

In this paper we address the H^∞ control analysis, the output feedback stabilization, and the output feedback H^∞ control synthesis problems for state-space symmetric systems. Using a particular solution of the Bounded Real Lemma for an open-loop symmetric system we obtain an explicit expression to compute the H^∞ norm of the system. For the output feedback stabilization problem we obtain an explicit parametrization of all asymptotically stabilizing control gains of state-space symmetric systems. For the H^∞ control synthesis problem we derive an explicit expression for the optimally achievable closed-loop H^∞ norm and the optimal control gains. Extension to robust and positive real control of such systems are also examined. These results are obtained from the linear matrix inequality formulations of the stabilization and the H^∞ control synthesis problems using simple matrix algebraic tools.     

Robust H∞ control for linear discrete-time systems with norm-bounded time-varying uncertainty

The problem of robust H_∞ analysis and synthesis for linear discrete-time systems with norm-bounded time-varying uncertainty is studied in this paper. It will be shown that this problem is equivalent to the problem of H_∞ analysis and synthesis of an auxiliary system. The necessary and sufficient conditions for the equivalency are proved. Thus the original problem can be solved by existing H_∞ control methods.     

Coprime factors reduction methods for linear parameter varying and uncertain systems

We present a generalization of the coprime factors model reduction method of Meyer and propose a balanced truncation reduction algorithm for a class of systems containing linear parameter varying and uncertain system models. A complete derivation of coprime factorizations for this class of systems is also given. The reduction method proposed is thus applicable to linear parameter varying and uncertain system realizations that do not satisfy the structured ℓ₂-induced stability constraint required in the standard nonfactored case. Reduction error bounds in the ℓ₂-induced norm of the factorized mapping are given.     

filtering for uncertain stochastic time-delay systems with sector-bounded nonlinearities

In this paper, we deal with the robust H_∞ filtering problem for a class of uncertain nonlinear time-delay stochastic systems. The system under consideration contains parameter uncertainties, Itô-type stochastic disturbances, time-varying delays, as well as sector-bounded nonlinearities. We aim at designing a full-order filter such that, for all admissible uncertainties, nonlinearities and time delays, the dynamics of the filtering error is guaranteed to be robustly asymptotically stable in the mean square, while achieving the prescribed H_∞ disturbance rejection attenuation level. By using the Lyapunov stability theory and Itô’s differential rule, sufficient conditions are first established to ensure the existence of the desired filters, which are expressed in the form of a linear matrix inequality (LMI). Then, the explicit expression of the desired filter gains is also characterized. Finally, a numerical example is exploited to show the usefulness of the results derived.     

Optimal input design for worst-case system identification in l1/l2/l∞

In this paper, we examine optimal sequences that generate worst-case parameters estimation errors in the l₁, l₂ and l_∞ norm context for algorithms identifying linear, time-invariant discrete-time, finite impulse response systems excited by bounded sequences and with l_∞ norm measurement error.     

Nonlinear state feedback for ℓ optimal control

This paper considers ℓ¹ optimal control problems with full state feedback. In contrast to ^∞ optimal control, previous work has shown that linear ℓ¹ optimal controllers can be dynamic and arbitrarily high order. However, this paper shows that continuous memoryless nonlinear state feedback perform as well as dynamic linear state feedback. The derivation, which is nonconstructive, relies on concepts from viability theory.     

Reduced-order filtering for singular systems

This paper solves the problem of reduced-order H_∞ filtering for singular systems. The purpose is to design linear filters with a specified order lower than the given system such that the filtering error dynamic system is regular, impulse-free (or causal), stable, and satisfies a prescribed H_∞ performance level. One major contribution of the present work is that necessary and sufficient conditions for the solvability of this problem are obtained for both continuous and discrete singular systems. These conditions are characterized in terms of linear matrix inequalities (LMIs) and a coupling non-convex rank constraint. Moreover, an explicit parametrization of all desired reduced-order filters is presented when these inequalities are feasible. In particular, when a static or zeroth-order H_∞ filter is desired, it is shown that the H_∞ filtering problem reduces to a convex LMI problem. All these results are expressed in terms of the original system matrices without decomposition, which makes the design procedure simple and directly. Last but not least, the results have generalized previous works on H_∞ filtering for state-space systems. An illustrative example is given to demonstrate the effectiveness of the proposed approach.     

Robust control of a class of uncertain nonlinear systems

This paper considers the robust control of a class of nonlinear systems with real time-varying parameter uncertainty. Interest is focused on the design of linear dynamic output feedback control and two problems are addressed. The first one is the robust stabilization and the other is the problem of robust performance in an H_∞ sense. A technique is proposed for designing stabilizing controllers for both problems by converting them into ‘scaled’ H_∞ control problems which do not involve parameter uncertainty.     

Robust stabilization of nonlinear systems via stable kernel representations with L2-gain bounded uncertainty

The approach to robust stabilization of linear systems using normalized left coprime factorizations with _∞ bounded uncertainty is generalized to nonlinear systems. A nonlinear perturbation model is derived, based on the concept of a stable kernel representation of nonlinear systems. The robust stabilization problem is then translated into a nonlinear disturbance feedforward _∞ optimal control problem, whose solution depends on the solvability of a single Hamilton-Jacobi equation.     

H∞ filtering for a class of uncertain nonlinear systems

This paper investigates the problem of H_∞ filtering for a class of uncertain continuous-time nonlinear systems with real time-varying parameter uncertainty and unknown initial state. We develop an infinite horizon H_∞ filtering methodology which provides both robust stability and a guaranteed H_∞ performance for the filtering error irrespective of the parameter uncertainty.     

Asynchronous hybrid systems with jumps – analysis and synthesis methods

In this paper we show that the H_∞ synthesis problem for a class of linear systems with asynchronous jumps can be reduced to a purely discrete-time synthesis problem. The system class considered includes continuous-time systems with discrete jumps, or discontinuities, in the state. New techniques are developed for the analysis of asynchronous time-varying hybrid systems which allow a particularly simple treatment, and provide an elementary proof for the sampled-data H_∞ problem.     

Computation of the ∞ norm for nonlinear systems A convergence result

In this paper we show that _∞ norm for a class of nonlinear continuous-time systems is the limit of the _∞ norm for approximating discrete-time systems. The convergence result is proved by means of a characterization of the _∞ norm in terms of the value for an ergodic control problem.     

Delay-dependent robust stability and control for jump linear systems with delays

This paper considers robust stochastic stability, stabilization and H_∞ control problems for a class of jump linear systems with time delays. By using some zero equations, neither model transformation nor bounding for cross terms is required to obtain the delay-dependent results, which are given in terms of linear matrix inequalities (LMIs). Maximum sizes of time delays are also studied for system stability. Furthermore, solvability conditions and corresponding H_∞ control laws are given which provide robust stabilization with a prescribed H_∞ disturbance attenuation level. Numerical examples show that the proposed methods are much less conservative than existing results.