Asymptotically efficient parameter estimation using quantized output observations

This paper studies identification of systems in which only quantized output observations are available. An identification algorithm for system gains is introduced that employs empirical measures from multiple sensor thresholds and optimizes their convex combinations. Strong convergence of the algorithm is first derived. The algorithm is then extended to a scenario of system identification with communication constraints, in which the sensor output is transmitted through a noisy communication channel and observed after transmission. The main results of this paper demonstrate that these algorithms achieve the Cramér-Rao lower bounds asymptotically, and hence are asymptotically efficient algorithms. Furthermore, under some mild regularity conditions, these optimal algorithms achieve error bounds that approach optimal error bounds of linear sensors when the number of thresholds becomes large. These results are further extended to finite impulse response and rational transfer function models when the inputs are designed to be periodic and full rank.     

Computing L2 -Gain of Finite-Horizon Systems With Boundary Conditions

A bisection algorithm is developed for computing the L₂-gain of a finite-horizon system with boundary conditions. Upper and lower bounds of the gain are also derived for the initial step of the algorithm     

New closed-form bounds on the partition function

Estimating the partition function is a key but difficult computation in graphical models. One approach is to estimate tractable upper and lower bounds. The piecewise upper bound of Sutton et al. is computed by breaking the graphical model into pieces and approximating the partition function as a product of local normalizing factors for these pieces. The tree reweighted belief propagation algorithm (TRW-BP) by Wainwright et al. gives tighter upper bounds. It optimizes an upper bound expressed in terms of convex combinations of spanning trees of the graph. Recently, Globerson et al. gave a different, convergent iterative dual optimization algorithm TRW-GP for the TRW objective. However, in many practical applications, particularly those that train CRFs with many nodes, TRW-BP and TRW-GP are too slow to be practical. Without changing the algorithm, we prove that TRW-BP converges in a single iteration for associative potentials, and give a closed form for the solution it finds. The closed-form solution obviates the need for complex optimization. We use this result to develop new closed-form upper bounds for MRFs with arbitrary pairwise potentials. Being closed-form, they are much faster to compute than TRW-based bounds. We also prove similar convergence results for loopy belief propagation (LBP) and use it to obtain closed-form solutions to the LBP pseudomarginals and approximation to the partition function for associative potentials. We then use recent results proved by Wainwright et al for binary MRFs to obtain closed-form lower bounds on the partition function. We then develop novel lower bounds for arbitrary associative networks. We report on experiments with synthetic and real-world graphs. Our new upper bounds are considerably tighter than the piecewise bounds in practice. Moreover, we can compute our bounds on several graphs where TRW-BP does not converge. Our novel lower bound, in spite of being closed-form and much faster to compute, outperforms more complicated popular algorithms for computing lower bounds like mean-field on densely connected graphs by wide margins although it does worse on sparsely connected graphs like chains.     

An exact bit-parallel algorithm for the maximum clique problem

This paper presents a new exact maximum clique algorithm which improves the bounds obtained in state of the art approximate coloring by reordering the vertices at each step. Moreover, the algorithm can make full use of bit strings to sort vertices in constant time as well as to compute graph transitions and bounds efficiently, exploiting the ability of CPUs to process bitwise operations in blocks of size the ALU register word. As a result it significantly outperforms a current leading algorithm.     

An iterative bounding method for stochastic automata networks

A method to bound stationary distributions of large Markov chains resulting from networks of stochastic automata is presented. It combines the concepts for bounding the stationary distribution using eigenvector polyhedra with the exploitation of the specific structure of Markov chains resulting from stochastic automata networks. The quality of the bounds depends on the coupling between automata. Three consecutive steps of the method are presented. In the first step bounds are computed using information about single automata in isolation. Bounds for single automata are refined in a second step by considering the environment of an automaton given by the other automata in the network. In a third step, bounds are further improved using a disaggregation step. By means of two small examples it is shown that the method yields tight bounds for loosely coupled automata and that the approach is extremely efficient compared to other bounding methods, let alone compared to an exact numerical analysis.     

Nonlinear kinematic tolerance analysis of planar mechanical systems

This paper presents a nonlinear kinematic tolerance analysis algorithm for planar mechanical systems comprised of higher kinematic pairs. The part profiles consist of line and circle segments. Each part translates along a planar axis or rotates around an orthogonal axis. The part shapes and motion axes are parameterized by a vector of tolerance parameters with range limits. A system is analyzed in two steps. The first step constructs generalized configuration spaces, called contact zones, that bound the worst-case kinematic variation of the pairs over the tolerance parameter range. The zones specify the variation of the pairs at every contact configuration and reveal failure modes, such as jamming, due to changes in kinematic function. The second step bounds the worst-case system variation at selected configurations by composing the zones. Case studies show that the algorithm is effective, fast, and more accurate than a prior algorithm that constructs and composes linear approximations of contact zones.     

Correctness and efficiency of pattern matching algorithms

A few lines pattern matching algorithm is obtained by using the correctness proof of programs as a tool to the design of efficient algorithms. The new algorithm is obtained from a brute force algorithm by three refinement steps. The first step leads to the algorithm of Knuth, Morris, and Pratt that performs 2n character comparisons in the worst case and (1 + α)n comparisons in the average case (0<α≤0.5). Two more steps give a faster algorithm that performs 1.5n character comparisons in the worst case and is sublinear on a random text for all patterns. Moreover, those bounds are less than the corresponding bounds of the Boyer and Moore algorithm because the Boyer and Moore algorithm performs more than 2n character comparisons in the worst case and because there exist some patterns that require more than n character comparisons on a random text. However, if we consider the average on all the patterns of a given length, then on a random text the Boyer and Moore algorithm is sublinear too, with better performance the longer the pattern gets.     

Some statistical bounds for the accuracy of distance-based pattern classification

Before implementing a pattern recognition algorithm, a rational step is to estimate its validity by bounding the probability of error. The ability to make such an estimate impacts crucially on the satisfactoriness of the particular features used, on the number of samples required to train and test the system and on the overall paradigm. This study develops statistical upper and lower bounds for estimating the probability of error, in the one-dimensional case. The bounds are distribution-free except for requiring the existence of the relevant statistics and can be evaluated easily by hand or by computer. Many of the results are also applicable to other problems involving the estimation of an arbitrary distribution of a random variable. Some multidimensional generalizations may be feasible.     

A heuristic algorithm for optimal location of flow‐refueling capacitated stations

Constructing refueling stations in the transportation network is one of the most important steps toward the promotion of alternative‐fuel vehicles. The capacity of these stations is usually limited. In this paper, a new capacitated refueling station location model and a solution algorithm are proposed. The algorithm is divided into two main steps. At first step, a restricted capacitated problem on core sets is constructed. Then, a modified Lagrangean iterative method is used for obtaining solutions. The Lagrangean method decomposes the restricted problem into two subproblems that are easy to solve. Information from subproblems is used to generate valid inequalities for tightening the upper and lower bounds. The approach is evaluated by considering a set of networks and randomly generated instances. The obtained results indicate that the large problems are efficiently tractable by the proposed algorithm in a reasonable time.     

Techniques for reducing Boolean evaluation time in CSG scan-line algorithms

Atherton's scan-line hidden surface algorithm for Boolean combinations of plane-faced primitives is intended for fast image generation of complex models.

An important step in the algorithm is the Boolean evaluation at the required positions on each scan-line. This step, however, can be very time consuming if performed in a straightforward way.

Some techniques are presented here that considerably reduce the time needed for the Boolean evaluation. These include a fast bottom-up evaluation technique and partial backface elimination.     

An exact approach for scheduling jobs with regular step cost functions on a single machine

This paper studies a single-machine scheduling problem whose objective is to minimize a regular step total cost function. Lower and upper bounds, obtained from linear and Lagrangian relaxations of different Integer Linear Programming formulations, are compared. A dedicated exact approach is presented, based on a Lagrangian relaxation. It consists of finding a Constrained Shortest Path in a specific graph designed to embed a dominance property. Filtering rules are developed for this approach in order to reduce the size of the graph, and the problem is solved by successively removing infeasible paths from the graph. Numerical experiments are conducted to evaluate the lower and upper bounds. Moreover, the exact approach is compared with a standard solver and a naive branch-and-bound algorithm.     

Identification of Systems With Regime Switching and Unmodeled Dynamics

This paper is concerned with persistent identification of systems that involve deterministic unmodeled dynamics and stochastic observation disturbances, and whose unknown parameters switch values (possibly large jumps) that can be represented by a Markov chain. Two classes of problems are considered. In the first class, the switching parameters are stochastic processes modeled by irreducible and aperiodic Markov chains with transition rates sufficiently faster than adaptation rates of the identification algorithms. In this case, tracking real-time parameters by output observations becomes impossible and we show that an averaged behavior of the parameter process can be derived from the stationary measure of the Markov chain and can be estimated with periodic inputs and least-squares type algorithms. Upper and lower error bounds are established that explicitly show impact of unmodeled dynamics. In contrast, the second class of problems represents systems whose state transitions occur infrequently. An adaptive algorithm with variable step sizes is introduced for tracking the time-varying parameters. Convergence and error bounds are derived. Numerical results are presented to illustrate the performance of the algorithm.     

An improved regression analysis for automatic surface tension measurements

Estimates of surface tension are generally based on the information provided by the surface contour of sessile and pendant drops. We have developped a new procedure for data reduction by taking advantage of the particular features of the mathematical model that describes the complex functional form relating contour and surface tension, when the apex coordinates and the corresponding radius of curvature are also only partially known.This procedure results in a two level optimization algorithm. The first step implies the optimization of a general dynamic model and to this purpose both objective function and sensitivity equations are set up. The second step is a local minimization, in that each datum point is assigned a particular position on the curve generated with certain values of the four parameters with respect to which the outer optimization loop is carried out.We have coded this method into an algorithm that uses the Gauss-Newton approximation to the hessian matrix and constrains the parameters to lie within specified bounds. It has been checked extensively for efficiency and robustness and both are quite satisfactory.     

Leave One Out Error, Stability, and Generalization of Voting Combinations of Classifiers

We study the leave-one-out and generalization errors of voting combinations of learning machines. A special case considered is a variant of bagging. We analyze in detail combinations of kernel machines, such as support vector machines, and present theoretical estimates of their leave-one-out error. We also derive novel bounds on the stability of combinations of any classifiers. These bounds can be used to formally show that, for example, bagging increases the stability of unstable learning machines. We report experiments supporting the theoretical findings.     

Recursive computation of inner bounds for the parameters of linear models

Minimum-volume ellipsoidal outer bounds on the parameters of linear regression-type models with bounded model-output error can be computed by an established algorithm. A complementary algorithm to compute maximum-volume ellipsoidal inner bounds is derived. It is little more complicated than the existing outer-bounding algorithm. In conjunction with that algorithm, it allows parameter values to be classified as acceptable, dubious or unacceptable. It is also found to be effective in determining output-error bounds by trial and error during development of parameter-bounding models.     

A trust region method based on a new affine scaling technique for simple bounded optimization

In this paper, we propose a new trust region affine scaling method for nonlinear programming with simple bounds. Our new method is an interior-point trust region method with a new scaling technique. The scaling matrix depends on the distances of the current iterate to the boundaries, the gradient of the objective function and the trust region radius. This scaling technique is different from the existing ones. It is motivated by our analysis of the linear programming case. The trial step is obtained by minimizing the quadratic approximation to the objective function in the scaled trust region. It is proved that our algorithm guarantees that at least one accumulation point of the iterates is a stationary point. Preliminary numerical experience on problems with simple bounds from the CUTEr collection is also reported. The numerical performance reveals that our method is effective and competitive with the famous algorithm LANCELOT. It also indicates that the new scaling technique is very effective and might be a good alternative to that used in the subroutine fmincon from Matlab optimization toolbox.     

Semi-Online Preemptive Scheduling: One Algorithm for All Variants

We present a unified optimal semi-online algorithm for preemptive scheduling on uniformly related machines with the objective to minimize the makespan. This algorithm works for all types of semi-online restrictions, including the ones studied before, like sorted (decreasing) jobs, known sum of processing times, known maximal processing time, their combinations, and so on. Based on the analysis of this algorithm, we derive some global relations between various semi-online restrictions and tight bounds on the approximation ratios for a small number of machines.     

A flooding algorithm for multirobot exploration

In this paper, we present a multirobot exploration algorithm that aims at reducing the exploration time and to minimize the overall traverse distance of the robots by coordinating the movement of the robots performing the exploration. Modeling the environment as a tree, we consider a coordination model that restricts the number of robots allowed to traverse an edge and to enter a vertex during each step. This coordination is achieved in a decentralized manner by the robots using a set of active landmarks that are dropped by them at explored vertices. We mathematically analyze the algorithm on trees, obtaining its main properties and specifying its bounds on the exploration time. We also define three metrics of performance for multirobot algorithms. We simulate and compare the performance of this new algorithm with those of our multirobot depth first search (MR-DFS) approach presented in our recent paper and classic single-robot DFS.     

Relative Loss Bounds for On-Line Density Estimation with the Exponential Family of Distributions

We consider on-line density estimation with a parameterized density from the exponential family. The on-line algorithm receives one example at a time and maintains a parameter that is essentially an average of the past examples. After receiving an example the algorithm incurs a loss, which is the negative log-likelihood of the example with respect to the current parameter of the algorithm. An off-line algorithm can choose the best parameter based on all the examples. We prove bounds on the additional total loss of the on-line algorithm over the total loss of the best off-line parameter. These relative loss bounds hold for an arbitrary sequence of examples. The goal is to design algorithms with the best possible relative loss bounds. We use a Bregman divergence to derive and analyze each algorithm. These divergences are relative entropies between two exponential distributions. We also use our methods to prove relative loss bounds for linear regression.     

Efficient algorithm for computing QFT bounds

This article presents an efficient algorithm for computing quantitative feedback theory (QFT) bounds for frequency-domain specifications from plant templates which are approximated by a finite number of points. To develop the algorithm, an efficient procedure is developed for testing, at a given frequency, whether or not a complex point lies in the QFT bound. This test procedure is then utilised along with a pivoting procedure to trace out, with a prescribed accuracy or resolution, the boundary of the QFT bound. The developed algorithm for computing QFT bounds has the advantages that it is efficient and can compute QFT bounds with multi-valued boundaries. A numerical example is given to show the computational superiority of the proposed algorithm.