Search

A signature result in compressed sensing is that Gaussian random sampling achieves stable and robust recovery of sparse vectors under optimal conditions on the number of measurements. However, in the context of image reconstruction, it has been extensively documented that sampling strategies based on Fourier measurements outperform this purportedly optimal approach. Motivated by this seeming paradox, we investigate the problem of optimal sampling for compressed sensing. Rigorously combining the theories of wavelet approximation and infinite-dimensional compressed sensing, our analysis leads to new error bounds in terms of the total number of measurements m for the approximation of piecewise [Formula omitted]-Hölder functions. Our theoretical findings suggest that Fourier sampling outperforms random Gaussian sampling when the Hölder exponent [Formula omitted] is large enough. Moreover, we establish a provably optimal sampling strategy. This work is an important first step towards the resolution of the claimed paradox and provides a clear theoretical justification for the practical success of compressed sensing techniques in imaging problems., Author(s): Ben Adcock [sup.1] , Simone Brugiapaglia [sup.2] , Matthew King-Roskamp [sup.1] Author Affiliations: (1) grid.61971.38, 0000 0004 1936 7494, Department of Mathematics, Simon Fraser University, , Burnaby, Canada (2) [...]

In the context of sparse recovery, it is known that most of the existing regularizers such as [l.sub.1] suffer from some bias incurred by some leading entries (in magnitude) of the associated vector. To neutralize this bias, we propose a class of models with partial regularizers for recovering a sparse solution of a linear system. We show that every local minimizer of these models is substantially sparse or the magnitude of all of its nonzero entries is above a uniform constant depending only on the data of the linear system. Moreover, for a class of partial regularizers, any global minimizer of these models is a sparsest solution to the linear system. We also establish some sufficient conditions for local or global recovery of the sparsest solution to the linear system, among which one of the conditions is weaker than the best-known restricted isometry property condition for sparse recovery by [l.sub.1]. In addition, a first-order augmented Lagrangian (FAL) method is proposed for solving these models, in which each subproblem is solved by a nonmonotone proximal gradient (NPG) method. Despite the complication of the partial regularizers, we show that each proximal subproblem in NPG can be solved as a certain number of one-dimensional optimization problems, which usually have a closed-form solution. We also show that any accumulation point of the sequence generated by FAL is a first-order stationary point of the models. Numerical results on compressed sensing and sparse logistic regression demonstrate that the proposed models substantially outperform the widely used ones in the literature in terms of solution quality. Funding: This work was supported in part by a Natural Sciences and Engineering Research Council (NSERC) Discovery Grant. Keywords: sparse recovery * partial regularization * null space property * restricted isometry property * proximal gradient method * augmented Lagrangian method * compressed sensing * sparse logistic regression, 1. Introduction Over the last decade, seeking a sparse solution to a linear system has attracted a great deal of attention in science and engineering (e.g., see Baraniuk and Steeghs [...]

We present a new approach for constructing polytope Lyapunov functions for continuous-time linear switching systems (LSS). This allows us to decide the stability of LSS and to compute the Lyapunov exponent with a good precision in relatively high dimensions. The same technique is also extended for stabilizability of positive systems by evaluating a polytope concave Lyapunov function ('antinorm') in the cone. The method is based on a suitable discretization of the underlying continuous system and provides both a lower and an upper bound for the Lyapunov exponent. The absolute error in the Lyapunov exponent computation is estimated from above and proved to be linear in the dwell time. The practical efficiency of the new method is demonstrated in several examples and in the list of numerical experiments with randomly generated matrices of dimensions up to 10 (for general linear systems) and up to 100 (for positive systems). The development of the method is based on several theoretical results proved in the paper: the existence of monotone invariant norms and antinorms for positively irreducible systems, the equivalence of all contractive norms for stable systems and the linear convergence theorem., Author(s): Nicola Guglielmi [sup.1] [sup.2] , Linda Laglia [sup.1] , Vladimir Protasov [sup.3] Author Affiliations: (1) 0000 0004 1757 2611grid.158820.6Dipartimento di Ingegneria Scienze Informatiche e Matematica, University of L'Aquila, Via [...]

LU and Cholesky factorizations are computational tools for efficiently solving linear systems that play a central role in solving linear programs and several other classes of mathematical programs. In many [...]

Consider an Erdos-Renyi random graph in which each edge is present independently with probability [Formula omitted], except for a subset [Formula omitted] of the vertices that form a clique (a completely connected subgraph). We consider the problem of identifying the clique, given a realization of such a random graph. The algorithm of Dekel et al. (ANALCO. SIAM, pp 67-75, 2011 (See CR17)) provably identifies the clique [Formula omitted] in linear time, provided [Formula omitted]. Spectral methods can be shown to fail on cliques smaller than [Formula omitted]. In this paper we describe a nearly linear-time algorithm that succeeds with high probability for [Formula omitted] for any [Formula omitted]. This is the first algorithm that provably improves over spectral methods. We further generalize the hidden clique problem to other background graphs (the standard case corresponding to the complete graph on [Formula omitted] vertices). For large-girth regular graphs of degree [Formula omitted] we prove that so-called local algorithms succeed if [Formula omitted] and fail if [Formula omitted]., Author(s): Yash Deshpande[sup.1] , Andrea Montanari[sup.2] Author Affiliations: (1) Department of Electrical Engineering, Stanford University, Stanford, CA, USA (2) Departments of Electrical Engineering and Statistics, Stanford University, Stanford, CA, USA [...]

Given n points in [R.sup.d] and a maximum allowed tolerance € > 0, the minimum hyperplanes clustering problem consists in finding a minimum number of hyperplanes such that the Euclidean [...]

6 Computing the Lower Spectral Radius. Algorithm (L) In this section we describe a method for the exact computation of the LSR of a finite family of matrices. We begin [...]

Let us assume that f is a continuous function defined on the unit ball of [R.sup.d], of the form f(x) = g(Ax), where A is a k x d matrix and g is a function of k variables for k ≪ d. We are given a budget m e N of possible point evaluations f([x.sub.i]), i = 1, ..., m, of f, which we are allowed to query in order to construct a uniform approximating function. Under certain smoothness and variation assumptions on the function g, and an arbitrary choice of the matrix A, we present in this paper 1. a sampling choice of the points {xi} drawn at random for each function approximation; 2. algorithms (Algorithm 1 and Algorithm 2) for computing the approximating function, whose complexity is at most polynomial in the dimension d and in the number m of points. Due to the arbitrariness of A, the sampling points will be chosen according to suitable random distributions, and our results hold with overwhelming probability. Our approach uses tools taken from the compressed sensing framework, recent Chernoff bounds for sums of positive semidefinite matrices, and classical stability bounds for invariant subspaces of singular value decompositions. Keywords High-dimensional function approximation * Compressed sensing * Chernoff bounds for sums of positive semidefinite matrices * Stability bounds for invariant subspaces of singular value decompositions Mathematics Subject Classification (2010) 65D15 * 03D32 * 68Q30 * 60B20 * 60G50, 1 Introduction 1.1 Learning High-Dimensional Functions from Few Samples In large-scale data analysis and learning, several real-life problems can be formulated as capturing or approximating a function defined on Ω [...]

In this paper, we suggest how to enlarge the maximum controllable region for unstable linear systems with mixed control actions. Using the impulsive action as an alternating control input, it is shown how the collaborative control inputs (bang-bang and impulsive action) work to augment the controllable region of unstable second order systems. However, the weakness resides in the sensitivity to model uncertainty and the time-consuming work to construct the switch curves (bang-bang switch curve and impulse firing curve). We suggest an efficient way to approximate the switch curves. It overcomes the shortcomings from the use of original switch curves, which are constructed through time backward computation. Simulation results show how the approximate switch curves can be used to determine the optimal control values for an augmented maximum controllable region. [DOI: 10.1115/1.3155008]

The QZ algorithm gives a robust way of computing solutions to the generalized eigenvalue problem. The generalized eigenvalue problem is used in linear control theory to find solutions to Ricatti equations, as well as to determine system transmission zeros. In state-space linear system analysis, the system poles and transmission zeros are particularly important for determining system time and frequency response. Here, we embed calculation of the eigenvalue derivatives in the QZ algorithm such that the derivatives of system poles and transmission zeros are computed simultaneously with the poles and zeros themselves. The resulting method is further exercised in finding generalized eigenvalues and their sensitivities required for finding the derivatives of system residues. This technique should open the door to solutions of problems of interest by unconstrained gradient-based methods. Typical numerical results are presented. DOI: 10.2514/1.39759

The proximate time optimal servomechanism (PTOS) is a well established algorithm for the control of linear systems where control bounds and the speed of response are important. The PTOS approach modifies the time-optimal switching curve by including an unsaturated 'slab' region that leads to a linear control regime for small errors. The control parameters are required to satisfy the continuity and the stability constraints resulting in only a single independent design parameter. In this note, the PTOS theory is reviewed and the stability conditions are derived. An improved version of the PTOS algorithm, called the MPTOS, is presented that results in a performance improvement over the original PTOS by providing two independent control parameters in the design. As a result, the system response can be shaped in a more efficient way in both continuous and discrete time domains. The stability conditions are derived for the proposed MPTOS scheme for continuous and discrete time implementations. Further extensions are discussed including a new discrete algorithm suitable for systems with slow sampling and a model reference tracking method also known as a feedforward/feedback structure for reducing the response of flexible modes. The latter method can be extended to dual actuator systems as are being introduced to the disk drive read/write head assembly fabrication and control. An approach is also presented for combining the vibration reduction filters with the model reference structure to further enhance the performance. Index Terms--Hard disk drive (HDD), proximate time optimal servomechanism (PTOS), switching control.

The A-[phi] formulation, which is widely used in electromagnetic analysis, leads to a redundant linear system of equations that includes a substantial number of redundant degrees of freedom (DOF). We can derive a redundancy-reduced linear system of equations by eliminating the redundant DOF, thereby decreasing the computation costs per iteration for iterative solvers, such as the incomplete Cholesky conjugate gradient (ICCG) solver. This does not, however, result in a reduction in total computation time, due to significant convergence deterioration. In this paper, we present a solution to this problem in the form of folded preconditioners. First, the theorem presented reveals that, for any preconditioned Krylov subspace method for the original redundant linear systems, we can derive the equivalent Krylov subspace method for the redundancy-reduced linear systems by using the corresponding folded preconditioner. As an uncomplicated example, the standard ICCG solver for the original redundant systems has exactly the same convergence property as the CG solver for the redundancy-reduced systems using the folded variant of the IC preconditioner (the folded IC preconditioner). Furthermore, we discuss efficient computational procedures for the folded preconditioners and the design of Krylov subspace algorithms using the preconditioners. A sample full-wave analysis demonstrates the good performance of a newly developed solver, the conjugate orthogonal conjugate gradient (COCG) method with the folded IC preconditioner. The new solver not only lowers the computation costs per iteration by reducing the number of DOF, but also completely avoids the convergence deterioration. Index Terms--A-[phi] method, Krylov subspace method, preconditioning, singular linear system of equations.

The objective of this paper is to examine nonlinear normal modes and their bifurcations in cyclic periodic structures. The nonlinear normal modes are computed using a numerical technique that combines shooting and pseudoarclength continuation. Unlike perturbation techniques, the resulting algorithm can investigate strongly nonlinear regimes of motion. This study reveals that modal interactions may occur without necessarily having commensurate natural frequencies in the underlying linear system. In addition, a countable infinity of such modal interactions are shown to exist in the system.

A spatiotemporal framework for estimating trial-to-trial variability in evoked response (ER) data is presented. Spatial and temporal bases capture the aspects of the response that are consistent across trials, while the basis expansion coefficients represent the variable components of the response. We focus on the simplest case of constant spatiotemporal response shape and varying amplitude across trials. Two different constraints on the amplitude evolution are employed to effectively integrate the individual responses and improve robustness at low SNR. The linear dynamical system response constraint estimates the current trial amplitude as an unknown constant scaling of the estimate in the previous trial plus zero-mean Gaussian noise with unknown variance. The independent response constraint estimates response amplitudes across trials as independent Gaussian random variables having unknown mean and variance. We develop a generalized expectation-maximization algorithm to obtain the maximum-likelihood (ML) estimates of the signal waveform, noise covariance matrix, and unknown constraint parameters. ML source localization is achieved by scanning the likelihood over different sets of spatial bases. We demonstrate the variability estimation and source localization effectiveness of the proposed algorithms using both real and simulated ER data. Index Terms--Event-related magnetoencephalography (MEG)/ electroencephalography (EEG), expectation-maximization (EM), independent response (IR), linear dynamical system response (LDSR), maximum likelihood (ML), trial-to-trial variability.

This paper studies discrete-time impulsive hybrid systems. The comparison principle and uniform stability are established for discrete-time impulsive hybrid systems and this kind of systems with time delay. Moreover, the attractive regions of these kinds of systems are estimated. As theoretical applications, the comparison principle is used to study the stability problem for linear interval discrete-time impulsive hybrid systems, a class of nonlinear uncertain discrete-time impulsive hybrid systems, and affine discrete-time impulsive hybrid systems with time delay. Some examples are given to illustrate the results. Index Terms--Attractive region, comparison principle, discrete-time impulsive hybrid system, time-delay, uniform stability.

This paper deals with the problem of stabilizing a bilinear system via linear state-feedback control. The proposed procedures enable us to compute a static state-feedback controller such that the zero-equilibrium point of the closed-loop system is asymptotically stable; moreover, it ensure that an assigned polytopic region is enclosed into the domain of attraction of the equilibrium point. The controller design requires the solution of a convex optimization problem involving linear matrix inequalities. The applicability of the technique is illustrated through an example, dealing with the design of a controller for a Cuk dc-dc converter. Index Terms--Bilinear systems, domain of attraction (DA), linear matrix inequalities (LMIs), stabilization, state-feedback control.

By using a combination of 32-bit and 64-bit floating point arithmetic, the performance of many sparse linear algebra algorithms can be significantly enhanced while maintaining the 64-bit accuracy of the resulting solution. These ideas can be applied to sparse multifrontal and supernodal direct techniques and sparse iterative techniques such as Krylov subspace methods. The approach presented here can apply not only to conventional processors but also to exotic technologies such as Field Programmable Gate Arrays (FPGA), Graphical Processing Units (GPU), and the Cell BE processor. Categories and Subject Descriptors: B.2.4 [Arithmetic and Logic Structures]: High-Speed Arithmetic; F.2.1 [Analysis of Algorithms and Problem Complexity]: Numerical Algorithms and Problems--Computations on matrices; G.1.3 [Numerical Analysis]: Numerical Linear Algebra--Error analysis; linear systems; G.4 [Mathematical Software]: --Algorithms design and analysis General Terms: Algorithms, Performance Additional Key Words and Phrases: Linear systems, iterative refinement, floating point, precision

Functional magnetic resonance imaging (fMRI) enables sites of brain activation to be localized in human subjects. For auditory system studies, however, the acoustic noise generated by the scanner tends to interfere with the assessments of this activation. Understanding and modeling fMRI acoustic noise is a useful step to its reduction. To study acoustic noise, the MR scanner is modeled as a linear electroacoustical system generating sound pressure signals proportional to the time derivative of the input gradient currents. The transfer function of one MR scanner is determined for two different input specifications: 1) by using the gradient waveform calculated by the scanner software and 2) by using a recording of the gradient current. Up to 4 kHz, the first method is shown as reliable as the second one, and its use is encouraged when direct measurements of gradient currents are not possible. Additionally, the linear order and average damping properties of the gradient coil system are determined by impulse response analysis. Since fMRI is often based on echo planar imaging (EPI) sequences, a useful validation of the transfer function prediction ability can be obtained by calculating the acoustic output for the EPI sequence. We found a predicted sound pressure level (SPL) for the EPI sequence of 104 dB SPL compared to a measured value of 102 dB SPL. As yet, the predicted EPI pressure waveform shows similarity as well as some differences with the directly measured EPI pressure waveform. Index Terms--Acoustic noise, fMRI, gradient noise, linear system, SPL.

We consider a stabilization problem of approximately feedback linearizable systems. We introduce a perturbation parameter by applying high-gain feedback and use both the feedback linearization method and the singular perturbation method for the controller design. Through this, we can overcome the rigorous conditions of the feedback linearization method and can reduce the dimension of the slow model of the singularly perturbed system. Index Terms--Feedback linearization, Lyapunov method, nonlinear system, singular perturbation method.

This paper is concerned with the study of observability in a structural framework. It turns out that the system is structurally observable if and only if the system is output connected and contains no contraction. We focus our attention on the observability preservation under sensor failure. We consider linear observable systems and we wonder if a given system remains observable in case of sensor failure. More precisely, we will characterize among the sensors those which are critical, i.e., which failure leads to observability loss, those which are useless for observability purpose and the set of those which are useful without being critical. Using a graph approach we classify the sensors with respect to their importance for output connection preservation, contraction avoidance and then observability preservation under sensor failure. Index Terms--Linear structured systems, observability, sensor classification, sensor failure.

This note introduces a geometric solution to the problem of perfect elimination of regulation transients in discrete-time, linear systems subject to swift and wide, a priori-known, parameter variations. The constructive proof of the conditions for problem solvability requires a preliminary, strictly geometric interpretation of the multivariable autonomous regulator problem, specifically aimed at discrete-time, linear systems. The novel concept of internal stabilizability of a robust controlled invariant subspace plays a key role in the formulation of those conditions as well as in the synthesis of the control scheme. Index Terms--Geometric approach, linear parameter varying systems, robust controlled invariant subspaces.

A novel treatment for the stability of linear time invariant (LTI) systems with rationally independent multiple time delays is presented in this paper. The independence of delays makes the problem much more challenging compared to systems with commensurate time delays (where the delays have rational relations). We uncover some wonderful features for such systems. For instance, all the imaginary characteristic roots of these systems can be found exhaustively along a set of surfaces in the domain of the delays. They are called the 'kernel' surfaces (curves for two-delay cases), and it is proven that the number of the kernel surfaces is manageably small and bounded. All possible time delay combinations, which yield an imaginary characteristic root, lie either on this kernel or its infinitely many 'offspring' surfaces. Another hidden feature is that the root tendencies along these surfaces exhibit an invariance property. From these outstanding characteristics an efficient, exact, and exhaustive methodology results for the stability assessment. As an added uniqueness of this method, the systems under consideration do not have to be stable for zero delays. Several example case studies are presented, which are prohibitively difficult, if not impossible to solve using any other peer methodology known to the authors. [DOI: 10.1115/1.2718235]

In the present note, stability of linear neutral systems with multiple delays is investigated. By principle of the argument, stability criteria are derived which are necessary and sufficient for asymptotic stability of the neutral systems. The stability criteria need only to evaluate the characteristic function and the argument on the boundary of a certain rectangular region. Several numerical examples are given to illustrate the results. Index Terms--Neutral systems, principle of the argument, stability criteria. Digital Object Identifier 10.1109/TAC.2007.894539

This paper demonstrates the validity of a second-order closure for the ensemble-mean dynamics using the approach of direct numerical ensemble simulations of a linear barotropic model with stochastic basic flows. For various configurations of the stochastic basic flow and external forcing, the deterministic solutions under the second-order closure capture, with remarkable accuracy, the ensemble means and the associated eddy covariance fields of forced responses simulated by a 500-member numerical ensemble. Thus, the second-order closure is found to be adequate for describing the ensemble-mean linear dynamics with stochastic basic flows. Moreover, simple analytical solutions based on the second-order closure also demonstrate that the stochastic component of a superrotational basic flow not only damps the ensemble-mean Rossby waves, but also enhances their eastward propagation. Various examples of ensemble-mean solutions all show the important role played by the stochastic synoptic eddy component of the basic flow in determining the ensemble-mean responses to external forcing. This study supports the notion that linear frameworks of ensemble-mean dynamics under second-order closure are useful tools for describing and understanding the dynamics of the synoptic eddy and the low-frequency flow (SELF) feedback and extratropical atmospheric low-frequency variability.

We discuss the shifting magnetic field generated by a two-phase modulated wave composed of a basic wave of 60 Hz and a higher harmonic wave in terms of its use in a magnetic levitation induction linear motor. In addition, we present measurements of the propulsive and levitation forces generated by the modulated wave. When the order of the higher harmonic wave is 4, the basic wave mainly generates a propulsive force, while the higher harmonic wave generates a levitation force alone. Thus, the propulsive and levitation forces can be easily and almost independently controlled by changing the amplitude of the basic wave and that of the higher harmonic wave, respectively. When the order of the higher harmonic wave is 3 or 5, the forces can also be easily controlled, if the phase of the higher harmonic wave is the same between two phases. Index Terms--Higher harmonic wave, levitation force, linear motor, modulated wave, open core, propulsive force, two-phase electric source.

This note provides new necessary and sufficient conditions for an n-dimensional linear affine system with n - 1 inputs to reach an exit facet (or set of exit facets) of a simplex. The conditions reduce the original NP-hard necessary and sufficient conditions to a set of at most n LP problems. Index Terms--Hybrid systems, linear affine systems, reachability, simplex.

We present a method for constructing reduced-order state observers for linear systems with unknown inputs. Our approach provides a characterization of observers with delay, which eases the established necessary conditions for existence of unknown input observers with zero-delay. We develop a parameterization of the observer gain that decouples the unknown inputs from the estimation error, and we use the remaining freedom to ensure stability of the error dynamics. Our procedure is quite general in that it encompasses the design of full-order observers via appropriate choices of design matrices. Index Terms--State estimation, system inversion, unknown input observer.

The problem of designing an output feedback control law which exponentially achieves output regulation is considered for known stabilizable and detectable linear systems which are allowed to be non-minimum phase; output references and/or additive disturbances are both generated by a linear exosystem with unknown purely imaginary eigenvalues and uncertain order. The novelty of this note is to require only an upper bound on the exosystem order to achieve a global solution which includes exponentially convergent estimates of the exosystem unknown frequencies. Index Terms--Adaptive control, nonminimum phase systems, output regulation, sinusoidal disturbances.

This note presents a robust moving horizon [H.sub.[infinity]] control scheme that achieves disturbance attenuation with performance adaptation or for a prescribed level. The on-line solved optimization problem is a Lagrange relaxation of the constrained minimax problem, with the benefit of achieving feasibility in the moving horizon implementation. Uncertainties are incorporated by the use of the full block multiplier technique. Simulation and comparison results are given. Index Terms--Disturbance attenuation, feasibility, full block multiplier, moving horizon control, time-domain constraint.

A new robust control gain-scheduling scheme for uncertain linear parameter-varying (LPV) systems is proposed. The gain-scheduled controller consists of a set of minimax optimal robust controllers and incorporates a new interpolation rule to achieve continuity of the controller gain over a range of operating conditions. For every fixed system parameter, the proposed controller guarantees a certain bound on the worst-case performance of the corresponding uncertain closed loop system. Furthermore, a bound on the rate of parameter variations is obtained under which the closed loop LPV system is robustly stable. Index Terms--Controller interpolation, gain scheduling, minimax optimal, uncertain LPV system.

In this note, we show that min-max model predictive control (MPC) for linearly constrained polytopic systems with quadratic cost can be cast as a quadratically constrained quadratic program (QCQP). We use the rigorous closed loop formulation of min-max MPC, and show that any such min-max MPC problem with convex costs and constraints can be cast as a finite dimensional convex optimization problem, with the QCQP arising from quadratic costs as a special case. At the base of the proof is a lemma showing the convexity of the dynamic programming cost-to-go, which implies that the worst case on an infinite polytopic set is assumed on one of its finitely many vertices. As the approach is based on a scenario tree formulation, the number of variables in this problem grows exponentially with the horizon length. Fortunately, the QCQP is tree structured, and can thus be efficiently solved by specially tailored interior-point methods whose computational costs are linear in the number of variables. The new formulation as a tree sparse QCQP promises to facilitate online solution of the rigorous min-max MPC problem with quadratic costs. Index Terms--Constraints, convex programming, model predictive control (MPC), receding horizon control (RHC), robustness.

The properties of a system, proposed by Teel and Hespanha, which is globally exponentially stable but with state that can be driven to infinity by an arbitrarily small exponentially decaying disturbance, are discussed in detail. These are used to propose a family of systems with a similar property and to argue that unstable behavior may be nongeneric and not detected by means of simulations. Finally, sufficient conditions for the existence of unbounded trajectories in cascaded systems are given. Index Terms--Cascaded systems, nonlinear systems, stability.

A differential variational system is defined by an ordinary differential equation (ODE) parameterized by an algebraic variable that is required to be a solution of a finite-dimensional variational inequality containing the state variable of the system. This paper addresses two system-theoretic topics for such a non-traditional nonsmooth dynamical system; namely, (non-)Zenoness and local observability of a given state satisfying a blanket strong regularity condition. For the former topic, which is of contemporary interest in the study of hybrid systems, we extend the results in our previous paper, where we have studied Zeno states and switching times in a linear complementarity system (LCS). As a special case of the differential variational inequality (DVI), the LCS consists of a linear, time-invariant ODE and a linear complementarity problem. The extension to a nonlinear complementarity system (NCS) with analytic inputs turns out to be non-trivial as we need to use the Lie derivatives of analytic functions in order to arrive at an expansion of the solution trajectory near a given state. Further extension to a differential variational inequality is obtained via its equivalent Karush-Kuhn-Tucker formulation. For the second topic, which is classical in system theory, we use the non-Zenoness result and the recent results in a previous paper pertaining to the B-differentiability of the solution operator of a nonsmooth ODE to obtain a sufficient condition for the short-time local observability of a given strongly regular state of an NCS. Refined sufficient conditions and necessary conditions for local observability of the LCS satisfying the P-property are obtained. Index Terms--Complementarity systems, differential variational inequalities (DVIs), hybrid systems, observability, Zeno behavior.

The robust performance analysis problem is considered for linear time-invariant (LTI) systems subject to block-diagonal structured and bounded linear time-varying (LTV) perturbations with specified maximal rates-of-variation. Analysis methods are developed in terms of semidefinite programming for the computation of upper and lower bounds for the optimum robust performance level. The upper bound computation is based on an integral quadratic constraint (IQC) test developed using a generalized version of the so-called swapping lemma. The lower bound computation method employs an extended version of the power distribution theorem together with a generalized version of the Kalman-Yakubovich-Popov (KYP) lemma and serves as a means to assess the conservatism of the computed upper bounds in the case of dynamic LTV perturbations. As corollaries of the underlying result for lower bound computation, it is shown for general block-diagonal uncertainty structures that thefrequency-dependent/constant D-scaling tests are exact for robust performance analysis against arbitrarily slow/fast dynamic LTV perturbations, respectively. Index Terms--Bounded-rate parameter variations, integral quadratic constraints (IQC), Kalman-Yakubovich-Popov (KYP) lemma, linear matrix inequalities (LMI), robust performance analysis, slowly time-varying systems, structured uncertainty.

This paper focuses on the model reduction of non-stationary linear parameter-varying (NSLPV) systems. We provide a generalization of the balanced truncation procedure for the model reduction of stable NSLPV systems, along with a priori error bounds. Then, for illustration purposes, this method is applied to reduce the model of a two-mass translational system. Furthermore, we give an approach for the model reduction of stabilizable and detectable systems, which requires the development and use of co-prime factorizations for NSLPV models. For the general class of eventually periodic LPV systems, which includes periodic and finite horizon systems as special cases, our results can be explicitly computed using semidefinite programming. Index Terms--Balanced truncation, coprime factors reduction, linear parameter-varying (LPV) systems, model reduction, time-varying systems.

We consider here the fault detection and isolation (FDI) problem for linear systems. We are interested in designing a set of observer-based residuals, in such a way that the transfer from the faults to the residuals is diagonal and the transfer from the disturbances to the residuals is zero. We deal with this problem when the system under consideration is structured, that is, the entries of the system matrices are either fixed zeros or free parameters. This problem can be solved in terms of the graph that can be associated in a natural way with a structured system. When the FDI solvability conditions are not satisfied, we assume that internal variables can be measured at a cost and look into the question of wether the problem is solvable with these new measurements. We give solvability conditions for a solution with a minimal number of additional sensors and among such solutions provide a minimal cost solution for the sensor location problem under consideration. We pay particular attention to the internal analysis of the system, and we propose a structural decomposition of the system associated graph based on some particular separators. This analysis leads to the definition of a reduced system. We prove that some potential additional sensors are inefficient for solving our FDI problem and that the FDI problem can be solved using only measurements on the reduced system. Index Terms--Fault detection and isolation (FDI), graphs, structured systems.

The moderate complexity of low-density parity-check (LDPC) codes under iterative decoding is attributed to the sparseness of their parity-check matrices. It is therefore of interest to consider how sparse parity-check matrices of binary linear block codes can be a function of the gap between their achievable rates and the channel capacity. This issue was addressed by Sason and Urbanke, and it is revisited in this paper. The remarkable performance of LDPC codes under practical and suboptimal decoding algorithms motivates the assessment of the inherent loss in performance which is attributed to the structure of the code or ensemble under maximum-likelihood (ML) decoding, and the additional loss which is imposed by the suboptimality of the decoder. These issues are addressed by obtaining upper bounds on the achievable rates of binary linear block codes, and lower bounds on the asymptotic density of their parity-check matrices as a function of the gap between their achievable rates and the channel capacity; these bounds are valid under ML decoding, and hence, they are valid for any suboptimal decoding algorithm. The new bounds improve on previously reported results by Burshtein et al. and by Sason and Urbanke, and they hold for the case where the transmission takes place over an arbitrary memoryless binary-input output-symmetric (MBIOS) channel. The significance of these information-theoretic bounds is in assessing the tradeoff between the asymptotic performance of LDPC codes and their decoding complexity (per iteration) under message-passing decoding. They are also helpful in studying the potential achievable rates of ensembles of LDPC codes under optimal decoding; by comparing these thresholds with those calculated by the density evolution technique, one obtains a measure for the asymptotic suboptimality of iterative decoding algorithms. Index Terms--Block codes, iterative decoding, linear codes, low-density parity-check (LDPC) codes, maximum-likelihood (ML) decoding, thresholds.

Space-time transmit diversity results in coupling of transmitted symbols across different antennas, which increases the complexity of maximum-likelihood decoding. Symbol coupling can be completely or partially avoided if the space-time code (STC) satisfies specific decoupling conditions; examples of such codes are orthogonal space-time block codes and quasi-orthogonal codes. In this letter, we study decoupling conditions for a linear full-diversity STC. Quasi-decoupled codes are proposed as a partially decoupled full-diversity STC of any rate for any number of transmit antennas with minimum decoding delay. By optimizing the coding gain of quasi-decoupled codes, it is shown that quasi-orthogonal codes have competitive performance with respect to the Alamouti code, and the more-recent threaded algebraic space-time (TAST) codes and ABBA codes. A general full-diversity decoupling condition is considered, and the general solution to this case, which also encompasses previously known orthogonal STCs, is derived. Index Terms--Decoupling, linear codes, multiple antennas, space-time.

A dynamic feedforward scheme allows measurable signal decoupling to be solved independently of other problems simultaneously present in the design of a control system like, e.g., stabilization, robustness, insensitivity to disturbances. The synthesis procedure, based on the properties of self-bounded controlled invariant subspaces, ensures the minimal complexity of the feedforward unit, in terms of minimal unassignable dynamics and minimal dynamic order, in the case of left-invertible systems and, on some specific conditions, also in the case of non-left-invertible systems. The output dynamic feedback set up to guarantee stability (or, more generally, robustness or insensitivity properties) does not affect the complexity of the feedforward unit, since the peculiar layout where the feedback unit receives an additional input from the precompensator preserves, in the extended system, exactly the same set of unassignable internal eigenvalues of the minimal self-bounded controlled invariant subspace as that defined for the original system. The overall control structure turns out to be a two-degree-of-freedom controller completely devised in the geometric context. Index Terms--Decoupling, feedforward control, geometric approach, linear systems, self-bounded controlled invariant subspaces.

A continuous forward algorithm (CFA) is proposed for nonlinear modelling and identification using radial basis function (RBF) neural networks. The problem considered here is simultaneous network construction and parameter optimization, well-known to be a mixed integer hard one. The proposed algorithm performs these two tasks within an integrated analytic framework, and offers two important advantages. First, the model performance can be significantly improved through continuous parameter optimization. Secondly, the neural representation can be built without generating and storing all candidate regressors, leading to significantly reduced memory usage and computational complexity. Computational complexity analysis and simulation results confirm the effectiveness. Index Terms--radial basis function (RBF) neural network, parameter optimization, network construction, nonlinear systems, Modelling and identification.

The note presents a method for designing an output feedback law that stabilizes a linear system subject to actuator saturation with a large domain of attraction. This method applies to general linear systems including strictly unstable ones. A nonlinear output feedback controller is first expressed in the form of a quasi-LPV system. Conditions under which the closed-loop system is locally asymptotically stable are then established in terms of the coefficient matrices of the controller. The design of the controller (coefficient matrices) that maximizes an estimate of the domain of attraction is then formulated and solved as an optimization problem with LMI constraints. Index Terms--Actuator saturation, domain of attraction, invariant set, output feedback, stability.

In this correspondence, iteration-1 of bit flipping decoding based on a set of nonorthogonal check sums is analyzed for both regular and irregular models. In particular, the tradeoff between the Hamming weight (and overlapping) of the check sums and the number of redundant cheek sums required to start converging under iterative decoding is investigated. The model is then applied to an iterative attack of McEliece public-key cryptosystem since a successful attack of this system can be achieved by algebraic bounded distance decoding of a random code. Based on this model, the attack can be decomposed into two phases: a preprocessing phase which, for one particular key [kappa], consists of finding a sufficiently large set S of check sums up to a certain Hamming weight, and a bit flipping decoding phase which uses the set S for each message encrypted with the key [kappa]. Index Terms--Bit-flipping decoding, iterative decoding, linear block codes, McEliece cryptosystem, public key cryptography.