A nonsmooth strict bounded real lemma

In the theory of linear H^∞ control, the strict bounded real lemma plays a critical role because it provides a connection between the stabilizing solutions to the H^∞ Riccati equations and the stability and disturbance attenuation of the closed-loop system. Nonlinear versions of the strict bounded real lemma are also important in nonlinear H^∞ control theory. In this paper, we investigate the extension of the linear strict bounded real lemma and its smooth nonlinear generalization to cases where the solutions of the associated nonlinear PDE are not necessarily differentiable.     

Spectral properties of infinite-dimensional closed-loop systems

We consider feedback systems obtained from infinite-dimensional well-posed linear systems by output feedback. Thus, our framework allows for unbounded control and observation operators. Our aim is to investigate the relationship between the open-loop system, the feedback operator K and the spectrum (in particular, the eigenvalues and eigenvectors) of the closed-loop generator A^K. We give a useful characterization of that part of the spectrum σ(A^K) which lies in the resolvent set of A, the open-loop generator, via the “characteristic equation” involving the open-loop transfer function. We show that certain points of σ(A) cannot be eigenvalues of A^K if the input and output are scalar (so that K is a number) and K≠0. We devote special attention to the case when the output feedback operator K is compact. It is relatively easy to prove that in this case, σ_e(A), the essential spectrum of A, is invariant, that is, it is equal to σ_e(A^K). A related but much harder problem is to determine the largest subset of σ(A) which remains invariant under compact output feedback. This set, which we call the immovable spectrum of A, strictly contains σ_e(A). We give an explicit characterization of the immovable spectrum and we investigate the consequences of our results for a certain class of well-posed systems obtained by interconnecting an infinite chain of identical systems.     

Semigroup generation and stabilization by A-bounded feedback perturbations

Let A be a generator of a strongly continuous semigroup of operators, and assume that C and H are operators such that A + CH generates a strongly continuous semigroup S_H(t) on X. Let λ₀ be a real number in the resolvent set of A, and let ε [−1, 1]. Then there are some fairly unrestrictive conditions under which A+(λ₀ − A)CH(λ₀ − A)⁻ also generates a strongly continuous semigroup S_K(t) on X which has the same exponential growth rate as S_H(t). Given an input operator B, we can use this to identify a class of feedback perturbations K such that A + BK generates a strongly continuous semigroup. We can also use this result to identify classes of feedbacks which can and cannot uniformly stabilize a system. For example, we show that if the control on a cantilever beam in the state space H₀²[0, 1] × L²[0, 1] is a moment force on the free end, then we cannot stabilize the beam with an A^−1/2-bounded feedback, but we can find an A^−1/4-bounded feedback, for any > 0, which does stabilize the beam.     

Linearity, Persistence and Testing Semantics in the Asynchronous Pi-Calculus

In [C. Palamidessi, V. Saraswat, F. Valencia and B. Victor. On the Expressiveness of Linearity vs Persistence in the Asynchronous Pi Calculus. LICS 2006:59–68, 2006] the authors studied the expressiveness of persistence in the asynchronous π-calculus (Aπ) wrt weak barbed congruence. The study is incomplete because it ignores the issue of divergence. In this paper, we present an expressiveness study of persistence in the asynchronous π-calculus (Aπ) wrt De Nicola and Hennessy's testing scenario which is sensitive to divergence. Following [C. Palamidessi, V. Saraswat, F. Valencia and B. Victor. On the Expressiveness of Linearity vs Persistence in the Asynchronous Pi Calculus. LICS 2006:59–68, 2006], we consider Aπ and three sub-languages of it, each capturing one source of persistence: the persistent-input calculus (PIAπ), the persistent-output calculus (POAπ) and persistent calculus (PAπ). In [C. Palamidessi, V. Saraswat, F. Valencia and B. Victor. On the Expressiveness of Linearity vs Persistence in the Asynchronous Pi Calculus. LICS 2006:59–68, 2006] the authors showed encodings from Aπ into the semi-persistent calculi (i.e., POAπ and PIAπ) correct wrt weak barbed congruence. In this paper we prove that, under some general conditions, there cannot be an encoding from Aπ into a (semi)-persistent calculus preserving the must testing semantics.     

Conditional mean estimation under asymmetric and heteroscedastic error by linear combination of quantile regressions

In this paper we propose a new estimator for regression problems in the form of the linear combination of quantile regressions. The proposed estimator is helpful for the conditional mean estimation when the error distribution is asymmetric and heteroscedastic.It is shown that the proposed estimator has the consistency under heteroscedastic regression model: Y=μ(X)+σ(X)·e, where X is a vector of covariates, Y is a scalar response, e is a zero mean random variable independent of X and σ(X) is a positive value function. When the error term e is asymmetric, we show that the proposed estimator yields better conditional mean estimation performance than the other estimators. Numerical experiments both in synthetic and real data are shown to illustrate the usefulness of the proposed estimator.     

Riccati equations and normalized coprime factorizations for strongly stabilizable infinite-dimensional systems

The first part of the paper concerns the existence of strongly stabilizing solutions to the standard algebraic Riccati equation for a class of infinite-dimensional systems of the form Σ(A,B,S^−1/2B^*,D), where A is dissipative and all the other operators are bounded. These systems are not exponentially stabilizable and so the standard theory is not applicable. The second part uses the Riccati equation results to give formulas for normalized coprime factorizations over H_∞ for positive real transfer functions of the form D+S^−1/2B^*(author−A)⁻¹,B.     

Inapproximability of the Tutte polynomial

The Tutte polynomial of a graph G is a two-variable polynomial T(G;x,y) that encodes many interesting properties of the graph. We study the complexity of the following problem, for rationals x and y: take as input a graph G, and output a value which is a good approximation to T(G;x,y). Jaeger et al. have completely mapped the complexity of exactly computing the Tutte polynomial. They have shown that this is #P-hard, except along the hyperbola (x-1)(y-1)=1 and at four special points. We are interested in determining for which points (x,y) there is a fully polynomial randomised approximation scheme (FPRAS) for T(G;x,y). Under the assumption RP≠NP, we prove that there is no FPRAS at (x,y) if (x,y) is in one of the half-planes x<-1 or y<-1 (excluding the easy-to-compute cases mentioned above). Two exceptions to this result are the half-line x<-1,y=1 (which is still open) and the portion of the hyperbola (x-1)(y-1)=2 corresponding to y<-1 which we show to be equivalent in difficulty to approximately counting perfect matchings. We give further intractability results for (x,y) in the vicinity of the origin. A corollary of our results is that, under the assumption RP≠NP, there is no FPRAS at the point (x,y)=(0,1-λ) when λ>2 is a positive integer. Thus, there is no FPRAS for counting nowhere-zero λ flows for λ>2. This is an interesting consequence of our work since the corresponding decision problem is in P for example for λ=6. Although our main concern is to distinguish regions of the Tutte plane that admit an FPRAS from those that do not, we also note that the latter regions exhibit different levels of intractability. At certain points (x,y), for example the integer points on the x-axis, or any point in the positive quadrant, there is a randomised approximation scheme for T(G;x,y) that runs in polynomial time using an oracle for an NP predicate. On the other hand, we identify a region of points (x,y) at which even approximating T(G;x,y) is as hard as #P.     

An optimal strategy for a conflict resolution problem

Relevant to the design of multiple access protocols is the problem of finding the largest of N i.i.d. numbers X₁,…,X_N uniformly distributed over [0,1] using the minimum number of questions of the following type. We pick a set A(1) [0, 1] and ask which X_i ε A(1). Depending on the response, we pick another subset A(2) and ask which X_i ε A(2), and so on, until we identify the largest X_i. It is shown that the optimum sequence of questions must be of the type A(k) = (a(k), 1]; the best sequence {a(k)} can then be determined by dynamic programming following the work of Arrow, Pesotchinsky and Sobel.     

A generalization of the Curtis–Hedlund theorem

Let A be a set and let G be a group, and equip A^G with its prodiscrete uniform structure. Let τ:A^G→A^G be a map. We prove that τ is a cellular automaton if and only if τ is uniformly continuous and G-equivariant. We also give an example showing that a continuous and G-equivariant map τ:A^G→A^G may fail to be a cellular automaton when the alphabet set A is infinite.     

Rank and eigenvalues of a supersymmetric tensor, the multivariate homogeneous polynomial and the algebraic hypersurface it defines

A real n-dimensional homogeneous polynomial f(x) of degree m and a real constant c define an algebraic hypersurface S whose points satisfy f(x)=c. The polynomial f can be represented by Ax^m where A is a real mth order n-dimensional supersymmetric tensor. In this paper, we define rank, base index and eigenvalues for the polynomial f, the hypersurface S and the tensor A. The rank is a nonnegative integer r less than or equal to n. When r is less than n, A is singular, f can be converted into a homogeneous polynomial with r variables by an orthogonal transformation, and S is a cylinder hypersurface whose base is r-dimensional. The eigenvalues of f, A and S always exist. The eigenvectors associated with the zero eigenvalue are either recession vectors or degeneracy vectors of positive degree, or their sums. When c⁄=0, the eigenvalues with the same sign as c and their eigenvectors correspond to the characterization points of S, while a degeneracy vector generates an asymptotic ray for the base of S or its conjugate hypersurface. The base index is a nonnegative integer d less than m. If d=k, then there are nonzero degeneracy vectors of degree k−1, but no nonzero degeneracy vectors of degree k. A linear combination of a degeneracy vector of degree k and a degeneracy vector of degree j is a degeneracy vector of degree k+j−m if k+j≥m. Based upon these properties, we classify such algebraic hypersurfaces in the nonsingular case into ten classes.     

On the weighted sensitivity minimization problem for delay systems

We consider the H^∞-optimal sensitivity problem for delay systems. In particular, we consider computation of μ:= inf {|W-φq|_∞ : q ε H^∞(j )} where W(s) is any function in RH^∞(j ), and φ in H^∞(j ) is any inner function. We derive a new explicit solution in the pure delay case where φ = e^−sh, h > 0.     

Trivial Reals

Solovay showed that there are noncomputable reals α such that H(α n) ≤ H(1ⁿ)+O(1), where H is prefix-free Kolmogorov complexity. Such H-trivial reals are interesting due to the connection between algorithmic complexity and effective randomness. We give a new, easier construction of an H-trivial real. We also analyze various computability-theoretic properties of the H-trivial reals, showing for example that no H-trivial real can compute the halting problem (which means that our construction of an H-trivial computably enumerable set is a particularly easy, injury-free construction of an incomplete c.e. set). Finally, we relate the H-trivials to other classes of “highly nonrandom” reals that have been previously studied.     

QFT template generation for time-delay plants based on zero-inclusion test

Plant template generation is the key step in applying quantitative feedback theory (QFT) to design robust control for uncertain systems. In this paper we propose a technique for generating plant templates for a class of linear systems with an uncertain time delay and affine parameter perturbations in coefficients. The main contribution lies in presenting a necessary and sufficient condition for the zero inclusion of the value set f(T,Q)={f(τ,q): τT[τ⁻,τ⁺], qQ∏_k=0^m−1[q_k⁻,q_k⁺]}, where f(τ,q)=g(q)+h(q)e^−jτω*, g(q) and h(q) are both complex-valued affine functions of the m-dimensional real vector q, and ω^* is a fixed frequency. Based on this condition, an efficient algorithm which involves, in the worst case, evaluation of m algebraic inequalities and solution of m2^m−1 one-variable quadratic equations, is developed for testing the zero inclusion of the value set f(T,Q). This zero-inclusion test algorithm allows one to utilize a pivoting procedure to generate the outer boundary of a plant template with a prescribed accuracy or resolution. The proposed template generation technique has a linear computational complexity in resolution and is, therefore, more efficient than the parameter gridding and interval methods. A numerical example illustrating the proposed technique and its computational superiority over the interval method is included.     

Empirical Bayes estimation of the scale parameter in a Pareto distribution

Let f(xθ) = αθ^αx^−(α+1)I(x>θ) be the pdf of a Pareto distribution with known shape parameter α>0, and unknown scale parameter θ. Let {(X_i, θ_i)} be a sequence of independent random pairs, where X_i's are independent with pdf f(xα_i), and θ_i are iid according to an unknown distribution G in a class of distributions whose supports are included in an interval (0, m), where m is a positive finite number. Under some assumption on the class and squared error loss, at (n + 1)th stage we construct a sequence of empirical Bayes estimators of θ_n+1 based on the past n independent observations X₁,…, X_n and the present observation X_n+1. This empirical Bayes estimator is shown to be asymptotically optimal with rate of convergence O(n^−1/2). It is also exhibited that this convergence rate cannot be improved beyond n^−1/2 for the priors in class .     

Maximum flow and critical cutset as descriptors of multi-state systems with randomly capacitated components

Let G = (V, E, s, t) denote a directed network with node set V, arc set E = {1,…, n}, source node s and sink node t. Let Γ denote the set of all minimal s−t cutsets and b₁(τ), …, B_n(τ), the random arc capacities at time τ with known joint probability distribution function. Let Λ(τ) denote the maximum s−t flow at time τ and D(τ), the corresponding critical minimal s−t cutset. Let Ω denote a set of minimal s−t cutsets. This paper describes a comprehensive Monte Carlo sampling plan for efficiently estimating the probability that D(τ)εΩ-Γ and x<λ(τ)y at time τ and the probability that D(τ) Ω given that x < Λ(τ) y at time τ. The proposed method makes use of a readily obtainable upper bound on the probability that Λ(τ) > x to gain its computational advantage. Techniques are described for computing confidence intervals and credibility measures for assessing that specified accuracies have been achieved. The paper includes an algorithm for performing the Monte Carlo sampling experiment, an example to illustrate the technique and a listing of all steps needed for implementation.     

Stability radii of differential algebraic equations with structured perturbations

This paper deals with a formula for computing stability radii of a differential algebraic equation of the form AX^′(t)−BX(t)=0, where A,B are constant matrices. A computable formula for the complex stability radius is given and a key difference between the ordinary differential equation (ODEs for short) and the differential algebraic equation (DAEs for short) is pointed out. A special case where the real stability radius and the complex one are equal is considered.     

A necessary condition for quantitative exponential stability of linear state-space systems

For an arbitrary n×n constant matrix A the two following facts are well known:

• (1/n)Re(traceA)−max_j=1,…,nRe λ_j(A)0;

• If U is a unitary matrix, one can always find a skew-Hermitian matrix A so that U=e^A.

In this note we present the extension of these two facts to the context of linear time-varying dynamical systemsAs a by-product, this result suggests that, the notion of “slowly varying state-space systems”, commonly used in literature, is mathematically not natural to the problem of exponential stability.     

Branching programs provide lower bounds on the areas of multilective deterministic and nondeterministic VLSI-circuits

Each (nondeterministic) multilective VLSI-circuit C of area A can be simulated by an oblivious (disjunctive) branching program of width exp(O(A)) which has the same multiplicity of reading as C. That is why exponential lower bounds on the width of (disjunctive) oblivious branching programs of linear depth provide lower bounds of order Ω(n^1–2α), , on the area of (nondeterministic) multilective VLSI-circuits computing explicitly defined one-output Boolean functions, if the multiplicity of reading is bounded by O(log^αn). Lower bounds are derived for the sequence equality problem (SEQ) and the graph accessibility problem (GAP).     

On the non-existence of stationary diffusions which satisfy the Bene condition

The one-dimensional diffusion x_t satisfying dx_t = f(x_t)dt + dw_t, where w_t is a standard Brownian motion and f(x) satisfies the Bene condition f′(x) + f²(x) = ax² + bx + c for all real x, is considered. It is shown that this diffusion does not admit a stationary probability measure except for the linear case f(x) = αx + β, α < 0.