Fast inference of ill-posed problems within a convex space

Abstract

In multiple scientific and technological applications we face the problem of having low dimensional data to be justified by a linear model defined in a high dimensional parameter space. The difference in dimensionality makes the problem ill-defined: the model is consistent with the data for many values of its parameters. The objective is to find the probability distribution of parameter values consistent with the data, a problem that can be cast as the exploration of a high dimensional convex polytope. In this work we introduce a novel algorithm to solve this problem efficiently. It provides results that are statistically indistinguishable from currently used numerical techniques while its running time scales linearly with the system size. We show that the algorithm performs robustly in many abstract and practical applications. As working examples we simulate the effects of restricting reaction fluxes on the space of feasible phenotypes of a {\em genome} scale E. Coli metabolic network and infer the traffic flow between origin and destination nodes in a real communication network.

25 pages, 11 figures

References in corpus (4)

• Efficient supervised learning in networks with binary synapses
• A Sampling Strategy for High-Dimensional Spaces Applied to Free-Form Gravitational Lensing
• A Novel Methodology to Estimate Metabolic Flux Distributions in Constraint-Based Models
• A weighted belief-propagation algorithm to estimate volume-related properties of random polytopes

Cited by in corpus (7)

• Statistical mechanics for metabolic networks during steady-state growth
• An analytic approximation of the feasible space of metabolic networks
• Characterizing steady states of genome-scale metabolic networks in continuous cell cultures
• Maximum entropy and population heterogeneity in continuous cell cultures
• Spin Glass Theory of Interacting Metabolic Networks
• The free lunch of a scale-free metabolism
• Volume of the steady-state space of financial flows in a monetary stock-flow-consistent model