Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
24works
0followers
22topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

24 published item(s)

preprint2026arXiv

Analytic Bridge Diffusions for Controlled Path Generation

Most modern bridge-diffusion methods achieve finite-time transport by specifying an interpolation, Schrödinger-bridge, or stochastic-control objective and then learning the associated score or drift field with a neural network. In contrast, we identify a restricted but sufficiently broad and analytically solvable class in which the score, intermediate marginals, and protocol gradients are available in closed form without inner stochastic simulation loops and without neural networks in the optimization loop. We recast the classical linear--quadratic--Gaussian (LQG) stochastic-control structure as a transport problem of the Path Integral Diffusion (PID) type. In classical LQG control, linear dynamics, Gaussian noise, and quadratic costs lead to Riccati equations and closed-form optimal feedback. In LQ-GM-PID, we retain the linear--quadratic stochastic-control backbone, but replace terminal state regulation by a prescribed terminal probability density and allow both the initial and terminal laws to be Gaussian Mixtures (GM). Moreover, LQ-GM-PID turns bridge diffusion from a tool for terminal target matching alone into a tool for path shaping. We demonstrate this on a 2D corridor task, a 2D multi-entrance transport task, and a high-dimensional scaling study with $d=32$ and $M=16$ Gaussian-mixture terminal modes, all with sub-50\,ms analytic precompute on a laptop. We position LQ-GM-PID as an analytically solvable reference model for the state-of-the-art neural bridge-diffusion and generative-transport methods: a controlled setting in which neural approximations, score estimates, path-shaping objectives, and protocol-learning procedures can be tested against exact quantities.

preprint2022arXiv

Lagrangian Large Eddy Simulations via Physics Informed Machine Learning

High Reynolds Homogeneous Isotropic Turbulence is fully described within the Navier-Stokes (NS) equations, which are notoriously difficult to solve numerically. Engineers, interested primarily in describing turbulence at a reduced range of resolved scales, have designed heuristics, known as Large Eddy Simulation (LES). LES is described in terms of the temporally evolving Eulerian velocity field defined over a spatial grid with the mean-spacing correspondent to the resolved scale. This classic Eulerian LES depends on assumptions about effects of sub-grid scales on the resolved scales. Here, we take an alternative approach and design novel LES heuristics stated in terms of Lagrangian particles moving with the flow. Our Lagrangian LES, thus L-LES, is described by equations generalizing the weakly compressible Smoothed Particle Hydrodynamics formulation with extended parametric and functional freedom, which is then resolved via Machine Learning training on Lagrangian data from Direct Numerical Simulations of the NS equations. The L-LES model includes physics-informed parameterization and functional form, by combining physics-based parameters and physics-inspired Neural Networks to describe the evolution of turbulence within the resolved range of scales. The sub-grid scale contributions are modeled separately with physical constraints to account for the effects from un-resolved scales. We build the resulting model under the Differentiable Programming framework to facilitate efficient training. We experiment with loss functions of different types, including physics-informed ones accounting for statistics of Lagrangian particles. We show that our Lagrangian LES model is capable of reproducing Eulerian and unique Lagrangian turbulence structures and statistics over a range of turbulent Mach numbers.

preprint2022arXiv

Machine Learning for Electricity Market Clearing

This paper seeks to design a machine learning twin of the optimal power flow (OPF) optimization, which is used in market-clearing procedures by wholesale electricity markets. The motivation for the proposed approach stems from the need to obtain the digital twin, which is much faster than the original, while also being sufficiently accurate and producing consistent generation dispatches and locational marginal prices (LMPs), which are primal and dual solutions of the OPF optimization, respectively. Availability of market-clearing tools based on this approach will enable computationally tractable evaluation of multiple dispatch scenarios under a given unit commitment. Rather than direct solution of OPF, the Karush-Kuhn-Tucker (KKT) conditions for the OPF problem in question may be written, and in parallel the LMPs of generators and loads may be expressed in terms of the OPF Lagrangian multipliers. Also, taking advantage of the practical fact that many of the Lagrangian multipliers associated with lines will be zero (thermal limits are not binding), we build and train an ML scheme which maps flexible resources (loads and renewables) to the binding lines, and supplement it with an efficient power-grid aware linear map to optimal dispatch and LMPs. The scheme is validated and illustrated on IEEE models. We also report a trade of analysis between quality of the reconstruction and number of samples needed to train the model.

preprint2022arXiv

Prediction and Prevention of Pandemics via Graphical Model Inference and Convex Programming

Hard-to-predict bursts of COVID-19 pandemic revealed significance of statistical modeling which would resolve spatio-temporal correlations over geographical areas, for example spread of the infection over a city with census tract granularity. In this manuscript, we provide algorithmic answers to the following two inter-related public health challenges. (1) Inference Challenge: assuming that there are $N$ census blocks (nodes) in the city, and given an initial infection at any set of nodes, what is the probability for a subset of census blocks to become infected by the time the spread of the infection burst is stabilized? (2) Prevention Challenge: What is the minimal control action one can take to minimize the infected part of the stabilized state footprint? To answer the challenges, we build a Graphical Model of pandemic of the attractive Ising (pair-wise, binary) type, where each node represents a census track and each edge factor represents the strength of the pairwise interaction between a pair of nodes. We show that almost all attractive Ising Models on dense graphs result in either of the two modes for the most probable state: either all nodes which were not infected initially became infected, or all the initially uninfected nodes remain uninfected. This bi-modal solution of the Inference Challenge allows us to re-state the Prevention Challenge as the following tractable convex programming: for the bare Ising Model with pair-wise and bias factors representing the system without prevention measures, such that the MAP state is fully infected for at least one of the initial infection patterns, find the closest, in $l_1$ norm, set of factors resulting in all the MAP states of the Ising model, with the optimal prevention measures applied, to become safe.

preprint2022arXiv

Statistical Mechanics of Thermostatically Controlled Multi-Zone Buildings

We study the collective phenomena and constraints associated with the aggregation of individual cooling units from a statistical mechanics perspective. These units are modelled as Thermostatically Controlled Loads (TCLs) and represent zones in a large commercial or residential building. Their energy input is centralized and controlled by a collective unit -- the Air Handling Unit (AHU) -- delivering cool air to all TCLs, thereby coupling them together. Aiming to identify representative qualitative features of the AHU-to-TCL coupling, we build a realistic but also sufficiently simple model and analyze it in two distinct regimes: the Constant Supply Temperature (CST) and the Constant Power Input (CPI) regimes. In both cases, we center our analysis on the relaxation dynamics of individual TCL temperatures to a statistically steady state. We observe that while the dynamics are relatively fast in the CST regime, resulting in all TCLs evolving around the control setpoint, the CPI regime reveals emergence of a \emph{bi-modal probability distribution and two, possibly strongly separated, time scales}. We observe that the two modes in the CPI regime are associated with all TCLs being in the same low and high-temperature states, respectively, with occasional (and therefore possibly rare) collective transition between the modes akin in the Kramer's phenomenon of statistical physics. To the best of our knowledge, this phenomenon was overlooked in the context of the multi-zone energy building engineering, even thought it has direct implications on the operations of centralized cooling systems in buildings. It teaches us that a balance needs to be struck between occupational comfort -- related to variations in the individual temperatures -- and power output predictability -- the main focus of the DR schemes.

preprint2022arXiv

Towards Model Reduction for Power System Transients with Physics-Informed PDE

This manuscript reports the first step towards building a robust and efficient model reduction methodology to capture transient dynamics in a transmission level electric power system. Such dynamics is normally modeled on seconds-to-tens-of-seconds time scales by the so-called swing equations, which are ordinary differential equations defined on a spatially discrete model of the power grid. Following Seymlyen (1974) and Thorpe, Seyler, and Phadke (1999), we suggest to map the swing equations onto a linear, inhomogeneous Partial Differential Equation (PDE) of parabolic type in two space and one time dimensions with time-independent coefficients and properly defined boundary conditions. We illustrate our method on the synchronous transmission grid of continental Europe. We show that, when properly coarse-grained, i.e., with the PDE coefficients and source terms extracted from a spatial convolution procedure of the respective discrete coefficients in the swing equations, the resulting PDE reproduces faithfully and efficiently the original swing dynamics. We finally discuss future extensions of this work, where the presented PDE-based modeling will initialize a physics-informed machine learning approach for real-time modeling, $n-1$ feasibility assessment and transient stability analysis of power systems.

preprint2021arXiv

Message Passing Descent for Efficient Machine Learning

We propose a new iterative optimization method for the {\bf Data-Fitting} (DF) problem in Machine Learning, e.g. Neural Network (NN) training. The approach relies on {\bf Graphical Model} (GM) representation of the DF problem, where variables are fitting parameters and factors are associated with the Input-Output (IO) data. The GM results in the {\bf Belief Propagation} Equations considered in the {\bf Large Deviation Limit} corresponding to the practically important case when the number of the IO samples is much larger than the number of the fitting parameters. We suggest the {\bf Message Passage Descent} algorithm which relies on the piece-wise-polynomial representation of the model DF function. In contrast with the popular gradient descent and related algorithms our MPD algorithm rely on analytic (not automatic) differentiation, while also (and most importantly) it descents through the rugged DF landscape by \emph{making non local updates of the parameters} at each iteration. The non-locality guarantees that the MPD is not trapped in the local-minima, therefore resulting in better performance than locally-updated algorithms of the gradient-descent type. We illustrate superior performance of the algorithm on a Feed-Forward NN with a single hidden layer and a piece-wise-linear activation function.

preprint2021arXiv

Neural Particle Image Velocimetry

In the past decades, great progress has been made in the field of optical and particle-based measurement techniques for experimental analysis of fluid flows. Particle Image Velocimetry (PIV) technique is widely used to identify flow parameters from time-consecutive snapshots of particles injected into the fluid. The computation is performed as post-processing of the experimental data via proximity measure between particles in frames of reference. However, the post-processing step becomes problematic as the motility and density of the particles increases, since the data emerges in extreme rates and volumes. Moreover, existing algorithms for PIV either provide sparse estimations of the flow or require large computational time frame preventing from on-line use. The goal of this manuscript is therefore to develop an accurate on-line algorithm for estimation of the fine-grained velocity field from PIV data. As the data constitutes a pair of images, we employ computer vision methods to solve the problem. In this work, we introduce a convolutional neural network adapted to the problem, namely Volumetric Correspondence Network (VCN) which was recently proposed for the end-to-end optical flow estimation in computer vision. The network is thoroughly trained and tested on a dataset containing both synthetic and real flow data. Experimental results are analyzed and compared to that of conventional methods as well as other recently introduced methods based on neural networks. Our analysis indicates that the proposed approach provides improved efficiency also keeping accuracy on par with other state-of-the-art methods in the field. We also verify through a-posteriori tests that our newly constructed VCN schemes are reproducing well physically relevant statistics of velocity and velocity gradients.

preprint2021arXiv

Physics-Informed Graphical Neural Network for Parameter & State Estimations in Power Systems

Parameter Estimation (PE) and State Estimation (SE) are the most wide-spread tasks in the system engineering. They need to be done automatically, fast and frequently, as measurements arrive. Deep Learning (DL) holds the promise of tackling the challenge, however in so far, as PE and SE in power systems is concerned, (a) DL did not win trust of the system operators because of the lack of the physics of electricity based, interpretations and (b) DL remained illusive in the operational regimes were data is scarce. To address this, we present a hybrid scheme which embeds physics modeling of power systems into Graphical Neural Networks (GNN), therefore empowering system operators with a reliable and explainable real-time predictions which can then be used to control the critical infrastructure. To enable progress towards trustworthy DL for PE and SE, we build a physics-informed method, named Power-GNN, which reconstructs physical, thus interpretable, parameters within Effective Power Flow (EPF) models, such as admittances of effective power lines, and NN parameters, representing implicitly unobserved elements of the system. In our experiments, we test the Power-GNN on different realistic power networks, including these with thousands of loads and hundreds of generators. We show that the Power-GNN outperforms vanilla NN scheme unaware of the EPF physics.

preprint2021arXiv

Super-relaxation of space-time-quantized ensemble of energy loads to curtail their synchronization after demand response perturbation

Ensembles of thermostatically controlled loads (TCL) provide a significant demand response reserve for the system operator to balance power grids. However, this also results in the parasitic synchronization of individual devices within the ensemble leading to long post-demand-response oscillations in the integrated energy consumption of the ensemble. The synchronization is eventually destructed by fluctuations, thus leading to the (pre-demand response) steady state; however, this natural desynchronization, or relaxation to a statistically steady state, is too long. A resolution of this problem consists in measuring the ensemble's instantaneous consumption and using it as a feedback to stochastic switching of the ensemble's devices between on- and off- states. A simplified continuous-time model showed that carefully tuned nonlinear feedback results in a fast (super-) relaxation of the ensemble energy consumption. Since both state information and control signals are discrete, the actual TCL devices operation is space-time quantized, and this must be considered for realistic TCL ensemble modelling. Here, assuming that states are characterized by indoor temperature (quantifying comfort) and air conditioner regime (on, off), we construct a discrete model based on the probabilistic description of state transitions. We demonstrate that super-relaxation holds in such a more realistic setting, and that while it is stable against randomness in the stochastic matrix of the quantized model, it remains sensitive to the time discretization scheme. Aiming to achieve a balance between super-relaxation and customer's comfort, we analyze the dependence of super-relaxation on details of the space-time quantization, and provide a simple analytical criterion to avoid undesirable oscillations in consumption.

preprint2020arXiv

A Hierarchical Approach to Multi-Energy Demand Response: From Electricity to Multi-Energy Applications

Due to proliferation of energy efficiency measures and availability of the renewable energy resources, traditional energy infrastructure systems (electricity, heat, gas) can no longer be operated in a centralized manner under the assumption that consumer behavior is inflexible, i.e. cannot be adjusted in return for an adequate incentive. To allow for a less centralized operating paradigm, consumer-end perspective and abilities should be integrated in current dispatch practices and accounted for in switching between different energy sources not only at the system but also at the individual consumer level. Since consumers are confined within different built environments, this paper looks into an opportunity to control energy consumption of an aggregation of many residential, commercial and industrial consumers, into an ensemble. This ensemble control becomes a modern demand response contributor to the set of modeling tools for multi-energy infrastructure systems.

preprint2020arXiv

Data-Driven Learning and Load Ensemble Control

Demand response (DR) programs aim to engage distributed small-scale flexible loads, such as thermostatically controllable loads (TCLs), to provide various grid support services. Linearly Solvable Markov Decision Process (LS-MDP), a variant of the traditional MDP, is used to model aggregated TCLs. Then, a model-free reinforcement learning technique called Z-learning is applied to learn the value function and derive the optimal policy for the DR aggregator to control TCLs. The learning process is robust against uncertainty that arises from estimating the passive dynamics of the aggregated TCLs. The efficiency of this data-driven learning is demonstrated through simulations on Heating, Cooling & Ventilation (HVAC) units in a testbed neighborhood of residential houses.

preprint2020arXiv

Embedding Hard Physical Constraints in Neural Network Coarse-Graining of 3D Turbulence

In the recent years, deep learning approaches have shown much promise in modeling complex systems in the physical sciences. A major challenge in deep learning of PDEs is enforcing physical constraints and boundary conditions. In this work, we propose a general framework to directly embed the notion of an incompressible fluid into Convolutional Neural Networks, and apply this to coarse-graining of turbulent flow. These physics-embedded neural networks leverage interpretable strategies from numerical methods and computational fluid dynamics to enforce physical laws and boundary conditions by taking advantage the mathematical properties of the underlying equations. We demonstrate results on three-dimensional fully-developed turbulence, showing that this technique drastically improves local conservation of mass, without sacrificing performance according to several other metrics characterizing the fluid flow.

preprint2020arXiv

Gauges, Loops, and Polynomials for Partition Functions of Graphical Models

Graphical models represent multivariate and generally not normalized probability distributions. Computing the normalization factor, called the partition function, is the main inference challenge relevant to multiple statistical and optimization applications. The problem is of an exponential complexity with respect to the number of variables. In this manuscript, aimed at approximating the PF, we consider Multi-Graph Models where binary variables and multivariable factors are associated with edges and nodes, respectively, of an undirected multi-graph. We suggest a new methodology for analysis and computations that combines the Gauge Function technique with the technique from the field of real stable polynomials. We show that the Gauge Function has a natural polynomial representation in terms of gauges/variables associated with edges of the multi-graph. Moreover, it can be used to recover the Partition Function through a sequence of transformations allowing appealing algebraic and graphical interpretations. Algebraically, one step in the sequence consists in application of a differential operator over gauges associated with an edge. Graphically, the sequence is interpreted as a repetitive elimination of edges resulting in a sequence of models on decreasing in size graphs with the same Partition Function. Even though complexity of computing factors in the sequence models grow exponentially with the number of eliminated edges, polynomials associated with the new factors remain bi-stable if the original factors have this property. Moreover, we show that Belief Propagation estimations in the sequence do not decrease, each low-bounding the Partition Function.

preprint2020arXiv

Graphical Models in Meshed Distribution Grids: Topology estimation, change detection and limitations

Graphical models are a succinct way to represent the structure in probability distributions. This article analyzes the graphical model of nodal voltages in non-radial power distribution grids. Using algebraic and structural properties of graphical models, algorithms exactly determining topology and detecting line changes for distribution grids are presented along with their theoretical limitations. We show that if distribution grids have cycles/loops of size greater than three, then nodal voltages are sufficient for efficient topology estimation without additional assumptions on system parameters. In contrast, line failure or change detection using nodal voltages does not require any structural assumption. Under noisy measurements, we provide the first non-trivial bounds on the maximum noise that the system can tolerate for asymptotically correct topology recovery. The performance of the designed algorithms is validated with nonlinear AC power flow samples generated by Matpower on test grids, including scenarios with injection correlations and system noise.

preprint2020arXiv

Joint Estimation of Topology and Injection Statistics in Distribution Grids with Missing Nodes

Optimal operation of distribution grid resources relies on accurate estimation of its state and topology. Practical estimation of such quantities is complicated by the limited presence of real-time meters. This paper discusses a theoretical framework to jointly estimate the operational topology and statistics of injections in radial distribution grids under limited availability of nodal voltage measurements. In particular we show that our proposed algorithms are able to provably learn the exact grid topology and injection statistics at all unobserved nodes as long as they are not adjacent. The algorithm design is based on novel ordered trends in voltage magnitude fluctuations at node groups, that are independently of interest for radial physical flow networks. The complexity of the designed algorithms is theoretically analyzed and their performance validated using both linearized and non-linear AC power flow samples in test distribution grids.

preprint2020arXiv

Learning with End-Users in Distribution Grids: Topology and Parameter Estimation

Efficient operation of distribution grids in the smart-grid era is hindered by the limited presence of real-time nodal and line meters. In particular, this prevents the easy estimation of grid topology and associated line parameters that are necessary for control and optimization efforts in the grid. This paper studies the problems of topology and parameter estimation in radial balanced distribution grids where measurements are restricted to only the leaf nodes and all intermediate nodes are unobserved/hidden. To this end, we propose two exact learning algorithms that use balanced voltage and injection measured only at the end-users. The first algorithm requires time-stamped voltage samples, statistics of nodal power injections and permissible line impedances to recover the true topology. The second and improved algorithm requires only time-stamped voltage and complex power samples to recover both the true topology and impedances without any additional input (e.g., number of grid nodes, statistics of injections at hidden nodes, permissible line impedances). We prove the correctness of both learning algorithms for grids where unobserved buses/nodes have a degree greater than three and discuss extensions to regimes where that assumption doesn't hold. Further, we present computational and, more importantly, the sample complexity of our proposed algorithm for joint topology and impedance estimation. We illustrate the performance of the designed algorithms through numerical experiments on the IEEE and custom power distribution models.

preprint2020arXiv

MCMC assisted by Belief Propagation

Markov Chain Monte Carlo (MCMC) and Belief Propagation (BP) are the most popular algorithms for computational inference in Graphical Models (GM). In principle, MCMC is an exact probabilistic method which, however, often suffers from exponentially slow mixing. In contrast, BP is a deterministic method, which is typically fast, empirically very successful, however in general lacking control of accuracy over loopy graphs. In this paper, we introduce MCMC algorithms correcting the approximation error of BP, i.e., we provide a way to compensate for BP errors via a consecutive BP-aware MCMC. Our framework is based on the Loop Calculus (LC) approach which allows expressing the BP error as a sum of weighted generalized loops. Although the full series is computationally intractable, it is known that a truncated series, summing up all 2-regular loops, is computable in polynomial-time for planar pair-wise binary GMs and it also provides a highly accurate approximation empirically. Motivated by this, we first propose a polynomial-time approximation MCMC scheme for the truncated series of general (non-planar) pair-wise binary models. Our main idea here is to use the Worm algorithm, known to provide fast mixing in other (related) problems, and then design an appropriate rejection scheme to sample 2-regular loops. Furthermore, we also design an efficient rejection-free MCMC scheme for approximating the full series. The main novelty underlying our design is in utilizing the concept of cycle basis, which provides an efficient decomposition of the generalized loops. In essence, the proposed MCMC schemes run on transformed GM built upon the non-trivial BP solution, and our experiments show that this synthesis of BP and MCMC outperforms both direct MCMC and bare BP schemes.

preprint2020arXiv

Mean Field Control for Efficient Mixing of Energy Loads

We pose an engineering challenge of controlling an Ensemble of Energy Devices via coordinated, implementation-light and randomized on/off switching as a problem in Non-Equilibrium Statistical Mechanics. We show that Mean Field Control} with nonlinear feedback on the cumulative consumption, assumed available to the aggregator via direct physical measurements of the energy flow, allows the ensemble to recover from its use in the Demand Response regime, i.e. transition to a statistical steady state, significantly faster than in the case of the fixed feedback. Moreover when the nonlinearity is sufficiently strong, one observes the phenomenon of "super-relaxation" -- where the total instantaneous energy consumption of the ensemble transitions to the steady state much faster than the underlying probability distribution of the devices over their state space, while also leaving almost no devices outside of the comfort zone.

preprint2018arXiv

Bucket Renormalization for Approximate Inference

Probabilistic graphical models are a key tool in machine learning applications. Computing the partition function, i.e., normalizing constant, is a fundamental task of statistical inference but it is generally computationally intractable, leading to extensive study of approximation methods. Iterative variational methods are a popular and successful family of approaches. However, even state of the art variational methods can return poor results or fail to converge on difficult instances. In this paper, we instead consider computing the partition function via sequential summation over variables. We develop robust approximate algorithms by combining ideas from mini-bucket elimination with tensor network and renormalization group methods from statistical physics. The resulting "convergence-free" methods show good empirical performance on both synthetic and real-world benchmark models, even for difficult instances.

preprint2016arXiv

Operator Splitting Method for Simulation of Dynamic Flows in Natural Gas Pipeline Networks

We develop an operator splitting method to simulate flows of isothermal compressible natural gas over transmission pipelines. The method solves a system of nonlinear hyperbolic partial differential equations (PDEs) of hydrodynamic type for mass flow and pressure on a metric graph, where turbulent losses of momentum are modeled by phenomenological Darcy-Weisbach friction. Mass flow balance is maintained through the boundary conditions at the network nodes, where natural gas is injected or withdrawn from the system. Gas flow through the network is controlled by compressors boosting pressure at the inlet of the adjoint pipe. Our operator splitting numerical scheme is unconditionally stable and it is second order accurate in space and time. The scheme is explicit, and it is formulated to work with general networks with loops. We test the scheme over range of regimes and network configurations, also comparing its performance with performance of two other state of the art implicit schemes.

preprint2010arXiv

Predicting Failures in Power Grids: The Case of Static Overloads

Here we develop an approach to predict power grid weak points, and specifically to efficiently identify the most probable failure modes in static load distribution for a given power network. This approach is applied to two examples: Guam's power system and also the IEEE RTS-96 system, both modeled within the static Direct Current power flow model. Our algorithm is a power network adaption of the worst configuration heuristics, originally developed to study low probability events in physics and failures in error-correction. One finding is that, if the normal operational mode of the grid is sufficiently healthy, the failure modes, also called instantons, are sufficiently sparse, i.e. the failures are caused by load fluctuations at only a few buses. The technique is useful for discovering weak links which are saturated at the instantons. It can also identify generators working at the capacity and generators under capacity, thus providing predictive capability for improving the reliability of any power network.

preprint2008arXiv

Fermions and Loops on Graphs. I. Loop Calculus for Determinant

This paper is the first in the series devoted to evaluation of the partition function in statistical models on graphs with loops in terms of the Berezin/fermion integrals. The paper focuses on a representation of the determinant of a square matrix in terms of a finite series, where each term corresponds to a loop on the graph. The representation is based on a fermion version of the Loop Calculus, previously introduced by the authors for graphical models with finite alphabets. Our construction contains two levels. First, we represent the determinant in terms of an integral over anti-commuting Grassman variables, with some reparametrization/gauge freedom hidden in the formulation. Second, we show that a special choice of the gauge, called BP (Bethe-Peierls or Belief Propagation) gauge, yields the desired loop representation. The set of gauge-fixing BP conditions is equivalent to the Gaussian BP equations, discussed in the past as efficient (linear scaling) heuristics for estimating the covariance of a sparse positive matrix.

preprint2008arXiv

Fermions and Loops on Graphs. II. Monomer-Dimer Model as Series of Determinants

We continue the discussion of the fermion models on graphs that started in the first paper of the series. Here we introduce a Graphical Gauge Model (GGM) and show that : (a) it can be stated as an average/sum of a determinant defined on the graph over $\mathbb{Z}_{2}$ (binary) gauge field; (b) it is equivalent to the Monomer-Dimer (MD) model on the graph; (c) the partition function of the model allows an explicit expression in terms of a series over disjoint directed cycles, where each term is a product of local contributions along the cycle and the determinant of a matrix defined on the remainder of the graph (excluding the cycle). We also establish a relation between the MD model on the graph and the determinant series, discussed in the first paper, however, considered using simple non-Belief-Propagation choice of the gauge. We conclude with a discussion of possible analytic and algorithmic consequences of these results, as well as related questions and challenges.