  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.
