Search

We consider the problem of ensuring stability in a DC microgrid by means of decentralized conditions. Such conditions are derived which are formulated as input-output properties of locally defined subsystems. These follow from various decompositions of the microgrid and corresponding properties of the resulting representations. It is shown that these stability conditions can be combined together by means of appropriate homotopy arguments, thus reducing the conservatism relative to more conventional decentralized approaches that often rely on a passivation of the bus dynamics. Examples are presented to demonstrate the applicability and the efficiency of the results derived.

We revisit the statistical foundation of the celebrated context tree weighting (CTW) algorithm, and we develop a Bayesian modelling framework for the class of higher-order, variable-memory Markov chains, along with an associated collection of methodological tools for exact inference for discrete time series. In addition to deterministic algorithms that learn the a posteriori most likely models and compute their posterior probabilities, we introduce a family of variable-dimension Markov chain Monte Carlo samplers, facilitating further exploration of the posterior. The performance of the proposed methods in model selection, Markov order estimation and prediction is illustrated through simulation experiments and real-world applications.

We estimate the minimum mean square error (MMSE) of the linear model under hidden Markov priors. Our estimates are based on the replica method in statistical physics. We show that under the MMSE estimator, the linear model with hidden Markov sources is decoupled into single-input AWGN channels with state information available at both encoder and decoder where the state distribution follows the left Perron-Frobenius eigenvector with unit Manhattan norm of the stochastic matrix of Markov chains.

By extending type theory with a universe of definitionally associative and unital polynomial monads, we show how to arrive at a definition of opetopic type which is able to encode a number of fully coherent algebraic structures. In particular, our approach leads to a definition of ∞-groupoid internal to type theory and we prove that the type of such ∞-groupoids is equivalent to the universe of types. That is, every type admits the structure of an ∞-groupoid internally, and this structure is unique.

We report the results of several theoretical studies into the convergence rate for certain random series representations of α-stable random variables, which are motivated by and find application in modelling heavy-tailed noise in time series analysis, inference, and stochastic processes. The use of α-stable noise distributions generally leads to analytically intractable inference problems. The particular version of the Poisson series representation invoked here implies that the resulting distributions are “conditionally Gaussian,” for which inference is relatively straightforward, although an infinite series is still involved. Our approach is to approximate the residual (or “tail”) part of the series from some point, c > 0, say, to ∞, as a Gaussian random variable. Empirically, this approximation has been found to be very accurate for large c. We study the rate of convergence, as c → ∞, of this Gaussian approximation. This allows the selection of appropriate truncation parameters, so that a desired level of accuracy for the approximate model can be achieved. Explicit, nonasymptotic bounds are obtained for the Kolmogorov distance between the relevant distribution functions, through the application of probability-theoretic tools. The theoretical results obtained are found to be in very close agreement with numerical results obtained in earlier work.

We study the discovery of cliques (or "complete" subgraphs) in heterogeneous information networks (HINs). Existing clique-finding solutions often ignore the rich semantics of HINs. We propose motif clique, or m-clique, which redefines subgraph completeness with respect to a given motif. A motif, essentially a small subgraph pattern, is a fundamental building block of an HIN. The m-clique concept is general and allows us to analyse "complete" subgraphs in an HIN with respect to desired high-order connection patterns. We further investigate the maximal m-clique enumeration problem (MMCE), which finds all maximal m-cliques not contained in any other m-cliques. Because MMCE is NP-hard, developing an accurate and efficient solution for MMCE is not straightforward. We thus present the META algorithm, which employs advanced pruning strategies to effectively reduce the search space. We also design fast techniques to avoid generating duplicated maximal m-clique instances. Our extensive experiments on large real and synthetic HINs show that META is highly effective and efficient.

A good measure of the rate of convergence of path-vector protocols is the number of synchronous iterations required for convergence in the worst case. From an algebraic perspective, the rate of convergence depends on the expressive power of the routing algebra associated with the protocol. For example in a network of $n$ nodes, shortest-path protocols are guaranteed to converge in $O(n)$ iterations. In contrast the algebra underlying the Border Gateway Protocol (BGP) is in some sense too expressive and the protocol is not guaranteed to converge. There is significant interest in finding well-behaved algebras that still have enough expressive power to satisfy network operators. Recent theoretical results have shown that by constraining routing algebras to those that are ``strictly increasing'' we can guarantee the convergence of path-vector protocols. Currently the best theoretical worst-case upper bound for the convergence of such algebras is $O(n!)$ iterations. However in practice it is difficult to find examples that do not converge in $n$ iterations. In this paper we close this gap. We first present a family of network configurations that converges in $\Theta(n^2)$ iterations, demonstrating that the worst case is $\Omega(n^2)$ iterations. We then prove that path-vector protocols with a strictly increasing algebra are guaranteed to converge in $O(n^2)$ iterations. Together these results establish a tight $\Theta(n^2)$ bound. This is another piece of the puzzle in showing that ``strictly increasing" is, at least on a technical level, a reasonable constraint for practical policy-rich protocols. {In memory of Abha Ahuja.

© 2016 IEEE. A method based on a quantifier elimination algorithm is suggested for obtaining explicit model predictive control (MPC) laws for linear time invariant systems with quadratic objective and polytopic constraints. The structure of the control problem considered allows Weispfenning's 'quantifier elimination by virtual substitution' algorithm to be used. This is applicable to first order formulas in which quantified variables appear at most quadratically. It has much better practical computational complexity than general quantifier elimination algorithms, such as cylindrical algebraic decomposition. We show how this explicit MPC solution, together with Weispfenning's algorithm, can be used to check recursive feasibility of the system, for both nominal and disturbed systems. Extension to cases beyond linear MPC using Weispfenning's algorithm is part of future work.

© 2017 IEEE. We report the results of a series of numerical studies examining the convergence rate for some approximate representations of α-stable distributions, which are a highly intractable class of distributions for inference purposes. Our proposed representation turns the intractable inference for an infinite-dimensional series of parameters into an (approximately) conditionally Gaussian representation, to which standard inference procedures such as Expectation-Maximization (EM), Markov chain Monte Carlo (MCMC) and Particle Filtering can be readily applied. While we have previously proved the asymptotic convergence of this representation, here we study the rate of this convergence for finite values of a truncation parameter, c. This allows the selection of appropriate truncations for different parameter configurations and for the accuracy required for the model. The convergence is examined directly in terms of cumulative distribution functions and densities, through the application of the Berry theorems and Parseval theorems. Our results indicate that the behaviour of our representations is significantly superior to that of representations that simply truncate the series with no Gaussian residual term.

The problem of estimating a high-dimensional sparse vector θ ∈ ℝ n from an observation in i.i.d. Gaussian noise is considered. An empirical Bayes shrinkage estimator, derived using a Bernoulli-Gaussian prior, is analyzed and compared with the well-known soft-thresholding estimator using squared-error loss as a measure of performance. We obtain concentration inequalities for the Stein's unbiased risk estimate and the loss function of both estimators. Depending on the underlying θ, either the proposed empirical Bayes (eBayes) estimator or soft-thresholding may have smaller loss. We consider a hybrid estimator that attempts to pick the better of the soft-thresholding estimator and the eBayes estimator by comparing their risk estimates. It is shown that: i) the loss of the hybrid estimator concentrates on the minimum of the losses of the two competing estimators, and ii) the risk of the hybrid estimator is within order 1/√n of the minimum of the two risks. Simulation results are provided to support the theoretical results.

Bundle adjustment is a nonlinear refinement method for camera poses and 3D structure requiring sufficiently good initialization. In recent years, it was experimentally observed that useful minima can be reached even from arbitrary initialization for affine bundle adjustment problems (and fixed-rank matrix factorization instances in general). The key success factor lies in the use of the variable projection (VarPro) method, which is known to have a wide basin of convergence for such problems. In this paper, we propose the Pseudo Object Space Error (pOSE), which is an objective with cameras represented as a hybrid between the affine and projective models. This formulation allows us to obtain 3D reconstructions that are close to the true projective reconstructions while retaining a bilinear problem structure suitable for the VarPro method. Experimental results show that using pOSE has a high success rate to yield faithful 3D reconstructions from random initializations, taking one step towards initialization-free structure from motion.

The identification of useful temporal dependence structure in discrete time series data is an important component of algorithms applied to many tasks in statistical inference and machine learning, and used in a wide variety of problems across the spectrum of biological studies. Most of the early statistical approaches were ineffective in practice, because the amount of data required for reliable modelling grew exponentially with memory length. On the other hand, many of the more modern methodological approaches that make use of more flexible and parsimonious models result in algorithms that do not scale well and are computationally ineffective for larger data sets. In this paper we describe a class of novel methodological tools for effective Bayesian inference for general discrete time series, motivated primarily by questions regarding data originating from studies in genetics and neuroscience. Our starting point is the development of a rich class of Bayesian hierarchical models for variable-memory Markov chains. The particular prior structure we adopt makes it possible to design effective, linear-time algorithms that can compute most of the important features of the relevant posterior and predictive distributions without resorting to Markov chain Monte Carlo simulation. The origin of some of these algorithms can be traced to the family of Context Tree Weighting (CTW) algorithms developed for data compression since the mid-1990s. We have used the resulting methodological tools in numerous application-specific tasks (including prediction, segmentation, classification, anomaly detection, entropy estimation, and causality testing) on data from different areas of application. The results obtained compare quite favourably with those obtained using earlier approaches, such as Probabilistic Suffix Trees (PST), Variable-Length Markov Chains (VLMC), and the class of Markov Transition Distributions (MTD).

The presence of ‘inverse response’ in the step response of a linear time-invariant system is closely associated with the presence of right-half plane zeros. Various links between the two are known: real positive zeros are sufficient to produce inverse response, and an odd number of positive real zeros is necessary and sufficient to give a particular form of inverse response. On the other hand, the presence of complex right-half plane zeros can result in inverse response, or not. The remaining question is whether the presence of right-half plane zeros is necessary for the presence of inverse response. This paper shows that it is not. This is demonstrated by the generation of a number of counter-examples, using an optimisation algorithm and a particular parametrisation of Hurwitz polynomials. We show that the result holds for a strengthened form of inverse response, which we call $\rho$-inverse response’, and if the system poles are constrained to be real.

Nullclines provide a convenient way of characterising and understanding the behaviour of low dimensional nonlinear deterministic systems, but are, perhaps not unsurprisingly, a poor predictor of the behaviour of discrete state stochastic systems in the low numbers regime. Such models are appropriate in many biological systems. In this paper we propose a graphical discrete ‘nullcline-like’ construction, inspired by the Markov chain tree theorem, and investigate its application to the original genetic toggle switch, which is a feedback interconnection of two mutually repressing genes. When the feedback gain (the ‘cooperativity’) is sufficiently large, the deterministic system exhibits bistability, which shows itself as a bimodal stationary distribution in the discrete stochastic system for sufficiently large numbers. However, at small numbers a third mode appears corresponding to roughly equal numbers of each molecule. Without cooperativity, on the other hand (i.e. low feedback gain), the deterministic system has just one stable equilibrium. Nevertheless, the stochastic system can still exhibit bimodality. In this paper, we illustrate that the discrete ‘nullclines’ proposed can, without the need to calculate the steady state distribution, provide an efficient graphical way of predicting the shape of the stationary probability distribution in different parameter regimes, thus allowing for greater insights in the observed behaviours.

This paper considers the problem of estimating a high-dimensional vector θ ∈ ℝn from a noisy one-time observation. The noise vector is assumed to be i.i.d. Gaussian with known variance. For the squared-error loss function, the James-Stein (JS) estimator is known to dominate the simple maximum-likelihood (ML) estimator when the dimension n exceeds two. The JS-estimator shrinks the observed vector towards the origin, and the risk reduction over the ML-estimator is greatest for θ that lie close to the origin. JS-estimators can be generalized to shrink the data towards any target subspace. Such estimators also dominate the ML-estimator, but the risk reduction is significant only when θ lies close to the subspace. This leads to the question: in the absence of prior information about θ, how do we design estimators that give significant risk reduction over the ML-estimator for a wide range of θ? In this paper, we attempt to infer the structure of θ from the observed data in order to construct a good attracting subspace for the shrinkage estimator. We provide concentration results for the squared-error loss and convergence results for the risk of the proposed estimators, as well as simulation results to support the claims. The estimators give significant risk reduction over the ML-estimator for a wide range of θ, particularly for large n.

Variable Projection (VarPro) is a framework to solve op- timization problems efficiently by optimally eliminating a subset of the unknowns. It is in particular adapted for Separable Nonlinear Least Squares (SNLS) problems, a class of optimization problems including low-rank matrix factorization with missing data and affine bundle adjustment as instances. VarPro-based methods have received much attention over the last decade due to the experimentally observed large convergence basin for certain problem classes, where they have a clear advantage over standard methods based on Joint optimization over all unknowns. Yet no clear answers have been found in the literature as to why VarPro outperforms others and why Joint optimization, which has been successful in solving many computer vision tasks, fails on this type of problems. Also, the fact that VarPro has been mainly tested on small to medium-sized datasets has raised questions about its scalability. This paper intends to address these unsolved puzzles.

We consider the problem of quantifying the variance in the number of molecules of a species, in biochemical reactions with nonlinear reaction rates. We address this problem for a particular configuration where a species is formed with bursts, with a nonlinear rate that depends on another spontaneously formed species. By making use of an appropriately formulated expansion based on the Newton series, in conjunction with spectral properties of the master equation, we derive an analytical expression that provides a hard bound for the variance. We also show that this bound is exact when the propensities are linear. Furthermore, numerical simulations demonstrate that this is very close to the actual variance.