Weighted Average Errors in Set-Membership Estimation

Average-case analysis provides knowledge about the quality of estimation algorithms in the case when the influence of outliers (exceptionally difficult elements) is to be neglected. This is in contrast with the worst-case analysis, where exceptionally difficult elements are of particular interest. In this paper we consider the average behavior of estimation algorithms based on corrupted information, with values in a subspace of the problem element space. We study two local average errors, with respect to probability measures defined by a class of weight functions. We define the optimal algorithm and derive exact error formulas, in Euclidean norms in problem element and information spaces. The formulas explicitly show the dependence of the errors on basic components of the problem, in particular on the weights. Attention is paid to the class of isotropic weight functions, examples of which are provided by truncated Gaussian weight functions. An extension of the results to non-Euclidean norms in the information space in a special case is shown. Date received: July 19, 2002. Date revised: January 9, 2003. This research was partly supported by AGH Grant No. 10.420.03.     

Linear Quadratic Optimal Control of Time-Varying Systems with Indefinite Costs on Hilbert Spaces

In this paper we consider time-varying linear systems on Hilbert spaces and study the linear quadratic optimal control problem with an indefinite performance criterion over an infinite time interval. An example shows that in contrast to the finite-dimensional situation, in general, the solvability of the optimal control problem does not imply the solvability of the associated integral Riccati equation. Using an operator theoretic approach towards the time-varying integral Riccati equation, we derive equivalent conditions for the solvability of both problems. Date received: October 8, 1997. Date revised: August 10, 1998.     

Distributed primal–dual stochastic subgradient algorithms for multi‐agent optimization under inequality constraints

We consider the multi‐agent optimization problem where multiple agents try to cooperatively optimize the sum of their local convex objective functions, subject to global inequality constraints and a convex constraint set over a network. Through characterizing the primal and dual optimal solutions as the saddle points of the associated Lagrangian function, which can be evaluated with stochastic errors, we propose the distributed primal–dual stochastic subgradient algorithms for two cases: (i) the time model is synchronous and (ii) the time model is asynchronous. In the first case, we obtain bounds on the convergence properties of the algorithm for a diminishing step size. In the second case, for a constant step size, we establish some error bounds on the algorithm's performance. In particular, we prove that the error bounds scale as in the number of n agents. Copyright © 2012 John Wiley & Sons, Ltd.     

Continuous-Time Blind Channel Deconvolution Using Laguerre Shifts

The objective of this paper is to study the problem of continuous-time blind deconvolution of a pulse amplitude modulated signal propagated over an unknown channel and perturbed by additive noise. The main idea is to use so-called Laguerre filters to estimate a continuous-time model of the channel. Laguerre-filter-based models can be viewed as an extension of finite-impulse-response (FIR) models to the continuous-time case, and lead to compact and parsimonious linear-in-the-parameters models.? Given an estimate of the channel, different symbol estimation techniques are possible. Here, the shift property of Laguerre filters is used to derive a minimum mean square error estimator to recover the transmitted symbols. This is done in a way that closely resembles recent FIR-based schemes for the corresponding discrete-time case.? The advantage of this concept is that physical a priori information can be incorporated in the model structure, like the transmitter pulse shape. Date received: July 23, 1998. Date revised: August 26, 1999.     

Erratum: An Approximation Algorithm for Minimum-Cost Vertex-Connectivity Problems

Abstract. There is an error in our paper ``An Approximation Algorithm for Minimum-Cost Vertex- Connectivity Problems' (Algorithmica (1997), 18:21—43). In that paper we considered the following problem: given an undirected graph and values r _ij for each pair of vertices i and j , find a minimum-cost set of edges such that there are r _ij vertex-disjoint paths between vertices i and j . We gave approximation algorithms for two special cases of this problem. Our algorithms rely on a primal—dual approach which has led to approximation algorithms for many edge-connectivity problems. The algorithms work in a series of stages; in each stage an augmentation subroutine augments the connectivity of the current solution. The error is in a lemma for the proof of the performance guarantee of the augmentation subroutine. In the case r _ij = k for all i,j , we described a polynomial-time algorithm that claimed to output a solution of cost no more than 2 H (k) times optimal, where H = 1 + 1/2 + · · · + 1/n . This result is erroneous. We describe an example where our primal—dual augmentation subroutine, when augmenting a k -vertex connected graph to a (k+1) -vertex connected graph, gives solutions that are a factor Ω(k) away from the minimum. In the case r _ij ∈ {0,1,2} for all i,j , we gave a polynomial-time algorithm which outputs a solution of cost no more than three times the optimal. In this case we prove that the statement in the lemma that was erroneous for the k -vertex connected case does hold, and that the algorithm performs as claimed.     

Mendelian Error Detection in Complex Pedigrees Using Weighted Constraint Satisfaction Techniques

With the arrival of high throughput genotyping techniques, the detection of likely genotyping errors is becoming an increasingly important problem. In this paper we are interested in errors that violate Mendelian laws. The problem of deciding if a Mendelian error exists in a pedigree is NP-complete (Aceto et al., J Comp Sci Technol 19(1):42–59, 2004). Existing tools dedicated to this problem may offer different level of services: detect simple inconsistencies using local reasoning, prove inconsistency, detect the source of error, propose an optimal correction for the error. All assume that there is at most one error. In this paper we show that the problem of error detection, of determining the minimum number of errors needed to explain the data (with a possible error detection) and error correction can all be modeled using soft constraint networks. Therefore, these problems provide attractive benchmarks for weighted constraint network (WCN) solvers. Because of their sheer size, these problems drove us into the development of a new WCN solver toulbar2 which solves very large pedigree problems with thousands of animals, including many loops and several errors.     

New Algorithms for Polynomial J-Spectral Factorization

In this paper new algorithms are developed for J-spectral factorization of polynomial matrices. These algorithms are based on the calculus of two-variable polynomial matrices and associated quadratic differential forms, and share the common feature that the problem is lifted from the original one-variable polynomial context to a two-variable polynomial context. The problem of polynomial J-spectral factorization is thus reduced to a problem of factoring a constant matrix obtained from the coefficient matrices of the polynomial matrix to be factored. In the second part of the paper, we specifically address the problem of computing polynomial J-spectral factors in the context of H _∞ control. For this, we propose an algorithm that uses the notion of a Pick matrix associated with a given two-variable polynomial matrix. Date received: January 1, 1998. Date revised: October 15, 1998.     

Strategy Under the Unknown Stochastic Environment: the Nonparametric Lob—Pass Problem

The bandit problem consists of two factors, one being exploration or the collection of information on the environment and the other being the exploitation or taking benefit by choosing the optimal action in the uncertain environment. It is desirable to choose only the optimal action for the exploitation, while the exploration or collection of information requires taking a variety of (nonoptimal) actions as trials. Hence, in order to obtain the maximal cumulative gain, we need to compromise between the exploration and exploitation processes. We treat a situation where our actions change the structure of the environment, of which a simple example is formulated as the lob—pass problem by Abe and Takeuchi. Usually, the environment is specified by a finite number of unknown parameters in the bandit problem, so that the information collection part is to estimate their true values. This paper treats a more realistic situation of nonparametric estimation of the environment structure which includes an infinite number (a functional degree) of unknown parameters. A strategy is given under such a circumstance, proving that the cumulative regret can be made of the order O(log t) , O((log t) ² ) , or O(t ^1-σ ) (0< σ <1) depending on the dynamics of the environment, where t is the number of trials, in contrast with the optimal order O(log t) in the parametric case. Received December 14, 1996; revised June 14, 1997, and July 24, 1997.     

Order Reduction Is Invalid for Singularly Perturbed Control Problems with a Vector Fast Variable

The order reduction method for singularly perturbed optimal control systems consists of employing the system obtained while setting the small parameter to zero. In many situations the differential-algebraic system thus obtained indeed provides an appropriate approximation to the singularly perturbed optimal control problem under consideration. In this paper we show, however, that the set of singularly perturbed optimal control systems for which the order reduction approach is invalid is dense (in the L ^∞ norm) in the class of systems which we consider. This is established under the assumption that the fast variable in the singularly perturbed system is not a scalar. Date received: June 8, 2001. Date revised: December 30, 2001.     

On the asymptotic performance of IDA*

Since best‐first search algorithms such as A* require large amounts of memory, they sometimes cannot run to completion, even on problem instances of moderate size. This problem has led to the development of limited‐memory search algorithms, of which the best known is IDA*. This paper presents the following results about IDA* and related algorithms: 1) The analysis of asymptotic optimality for IDA* in [R.E. Korf, Optimal path finding algorithms, in: Search in Artificial Intelligence, eds. L. Kanal and V. Kumar (Springer‐Verlag, 1988) pp. 200-222] is incorrect. There are trees satisfying the asymptotic optimality conditions given in [R.E. Korf, Optimal path finding algorithms, in: Search in Artificial Intelligence, eds. L. Kanal and V. Kumar (Springer‐Verlag, 1988) pp. 200-222] for which IDA* is not asymptotically optimal. 2) To correct the above problem, we state and prove necessary and sufficient conditions for asymptotic optimality of IDA* on trees. On trees not satisfying our conditions, we show that no best‐first limited‐memory search algorithm can be asymptotically optimal. 3) On graphs, IDA* can perform quite poorly. In particular, there are graphs on which IDA* does Ω(2^2N) node expansions where N is the number of nodes expanded by A*. This revised version was published online in June 2006 with corrections to the Cover Date.     

Optimal binary search trees with costs depending on the access paths

We describe algorithms for constructing optimal binary search trees, in which the access cost of a key depends on the k preceding keys which were reached in the path to it. This problem has applications to searching on secondary memory and robotics. Two kinds of optimal trees are considered, namely optimal worst case trees and weighted average case trees. The time and space complexities of both algorithms are O(n^k+2) and O(n^k+1), respectively. The algorithms are based on a convenient decomposition and characterizations of sequences of keys which are paths of special kinds in binary search trees. Finally, using generating functions, we present an exact analysis of the number of steps performed by the algorithms.     

Induced Convolution Operator Norms of Linear Dynamical Systems

In this paper we develop explicit formulas for induced convolution operator norms and their bounds. These results generalize established induced operator norms for linear dynamical systems with various classes of input–output signal pairs. Date received: April 1, 1999. Date revised: February 21, 2000.     

Exploring the Suitability of Virtual Environments for Safety Training: Signals, Norms and Ambiguity in a Simulated Emergency Escape

This study aims at exploring the suitability of virtual environments for safety training in large public spaces. A virtual library was constructed which simulated many of the physical and normative characteristics of the ‘real’ university library which was the target of the virtual safety training project. In the virtual library, two different types of signals (fixed red signs vs. moving green arrows) for guiding people to the emergency exits were presented, and their efficacy on escape times was tested in three different conditions, differing with respect to the distance of participants from the escape exits (measured according to the number of corners separating participants from direct visual discovery of the emergency exit). No significant differences between the different kinds of signals were found, whereas surprising discrepancies among the three conditions appeared. The differences in performance in the three conditions were contingent upon the presence in the virtual library of peculiar environmental features embodying social norms – like a red ribbon indicating no transit. Uncertainty about the sense of such normative features in the context of the simulated emergency made some participants prone to peculiar knowledge-based errors consisting of inadequate sense-making of the normative aspects of the ongoing situation. This kind of error shows that the simulation succeeded in capturing one of the crucial characteristics of ‘real’ social context: ambiguity, which mostly depends on the fact that the social norms structuring public spaces and defining their legitimate uses are often ill defined and context dependent. Every valid experience in safety training requires coping with ambiguity in situations.     

Input-to-State Stability for Nonlinear Time-Varying Systems via Averaging

 We introduce two definitions of an averaged system for a time-varying ordinary differential equation with exogenous disturbances (“strong average” and “weak average”). The class of systems for which the strong average exists is shown to be strictly smaller than the class of systems for which the weak average exists. It is shown that input-to-state stability (ISS) of the strong average of a system implies uniform semi-global practical ISS of the actual system. This result generalizes the result of [TPA] which states that global asymptotic stability of the averaged system implies uniform semi-global practical stability of the actual system. On the other hand, we illustrate by an example that ISS of the weak average of a system does not necessarily imply uniform semi-global practical ISS of the actual system. However, ISS of the weak average of a system does imply a weaker semi-global practical “ISS-like” property for the actual system when the disturbances w are absolutely continuous and . ISS of the weak average of a system is shown to be useful in a stability analysis of time-varying cascaded systems. Date received: April 6, 1999. Date revised: April 11, 2000.     

New Algorithms for Disk Scheduling

Abstract. Processor speed and memory capacity are increasing several times faster than disk speed. This disparity suggests that disk I/ O performance could become an important bottleneck. Methods are needed for using disks more efficiently. Past analysis of disk scheduling algorithms has largely been experimental and little attempt has been made to develop algorithms with provable performance guarantees. We consider the following disk scheduling problem. Given a set of requests on a computer disk and a convex reachability function that determines how fast the disk head travels between tracks, our goal is to schedule the disk head so that it services all the requests in the shortest time possible. We present a 3/2 -approximation algorithm (with a constant additive term). For the special case in which the reachability function is linear we present an optimal polynomial-time solution. The disk scheduling problem is related to the special case of the Asymmetric Traveling Salesman Problem with the triangle inequality (ATSP-Δ ) in which all distances are either 0 or some constant α . We show how to find the optimal tour in polynomial time and describe how this gives another approximation algorithm for the disk scheduling problem. Finally we consider the on-line version of the problem in which uniformly distributed requests arrive over time. We present an algorithm related to the above ATSP-Δ .     

Time-Constrained Scheduling of Weighted Packets on Trees and Meshes

Abstract. The time-constrained packet routing problem is to schedule a set of packets to be transmitted through a multinode network, where every packet has a source and a destination (as in traditional packet routing problems) as well as a release time and a deadline. The objective is to schedule the maximum number of packets subject to deadline constraints. This problem is studied in [1], where it is shown that the problem is NP-Complete even when the underlying topology is a linear array. Approximation algorithms are also provided in [1] for the linear array and the unidirectional ring for both the case where packets may be buffered in transit and the case where they may not be. In this paper we extend the results of [1] in two directions. First, we consider the more general network topologies of trees and two-dimensional meshes. Second, we associate with each packet a measure of utility, called a weight, and study the problem of maximizing the total weight of the packets that are scheduled subject to their timing constraints. For the bufferless case, we provide constant factor approximation algorithms for the time-constrained scheduling problem with weighted packets on trees and meshes. We also provide logarithmic approximations for the same problems in the buffered case. These results are complemented by new lower bounds, which demonstrate that we cannot hope to achieve the same results for general network topologies. For example, we show that if k packets are required to follow prescribed paths in an arbitrary graph, then unless NP = ZPP, there is no polynomial-time k ^1-ε -approximation, for any ε > 0 , to the optimal set of packets that can be scheduled.     

Reduced Basis Method and Error Estimation for Parametrized Optimal Control Problems with Control Constraints

We propose a Reduced Basis method for the solution of parametrized optimal control problems with control constraints for which we extend the method proposed in Dedè, L. (SIAM J. Sci. Comput. 32:997, 2010) for the unconstrained problem. The case of a linear-quadratic optimal control problem is considered with the primal equation represented by a linear parabolic partial differential equation. The standard offline–online decomposition of the Reduced Basis method is employed with the Finite Element approximation as the “truth” one for the offline step. An error estimate is derived and an heuristic indicator is proposed to evaluate the Reduced Basis error on the optimal control problem at the online step; also, the indicator is used at the offline step in a Greedy algorithm to build the Reduced Basis space. We solve numerical tests in the two-dimensional case with applications to heat conduction and environmental optimal control problems.     

含理想控制策略和期望轨道的最优控制

研究合理想控制策略和期望轨道的二次型最优控制问题．通过把控制问题转化为估计问题，从信息融合估计的角度，使原问题转化为求控制量的“最优估计”问题．通过实际算例表明。该算法所得二次性能指标值优于现有算法．     

Reasoning about faulty quantum programs

We show how to use a programming language for formally describing and reasoning about errors in quantum computation. The formalisation is based on the concept of performing the correct operation with probability at least p, and the erroneous one with probability at most 1 − p. We apply the concept to two examples: Bell’s inequalities and the Deutsch–Jozsa quantum algorithm. The former is a fundamental thought experiment aimed at showing that Quantum Mechanics is not “local and realist”, and it is used in quantum cryptography protocols. We study it assuming faulty measurements, and we derive hardware reliability conditions that must be satisfied in order for the experiment to support its conclusions. The latter is a quantum algorithm for efficiently solving a classification problem for Boolean functions. The algorithm solves the problem with no error, but when we introduce faulty operations it becomes a two-sided error algorithm. Reasoning is accomplished via standard programming laws and quantum laws.     

遗传算法在曲线多边形近似中的应用

在平面数字曲线的多边形近似中,为克服顶点的检测只依靠部区域,缺 乏全局信息的弱点,文中把多边形近似问题作了寻找在满足一定的近似误差下使顶点数最少,或者使顶点数和近似误差都尽可能少的最优化问题来处理。