algorithm - Constrained random solution of an underspecified system of linear equations -

premise

i've system of linear equations dot(a,x) = y solutions have many degrees of freedom: indeed number of linearly independent equations (e) less dimension of x, a.k.a. number of variables (n).

the number of degrees of freedom left constrains solutions hyperplane n-e of overall space r^n. given (unimportant) characteristics of a, able write solutions x (a vector n x 1)

x=dot(b,t)+q 

where b n x (n-e) matrix, t (n-e) x 1 vector , q n x 1 vector. define hyperplane of solutions of original problem, x = y in parametric form.

i need extract random solution, uniform probability on possible point of hyperplane, such x positive (we refer a positive solution). note that, specific problem dealing with, space of positive solutions of x exists , bounded (that's how notion of uniform probability reasonable specific case, clarify suggested @petr comment). in beginning, once able write x=bt+q, thought extremely simple. starting doubt it.

proposed solution

by this:

1. for each dimension in range(n-e) compute maximum , minimum value of t[i]: t_min[i] , t_max[i]. intervals big enough not exclude possible positive solution. algebraically computed, existing , defining limited space.
2. i extract n-e uniform random values t[i], each comprised between t_min [i] , t_max[i].
3. i compute x = dot(b,t)+q
4. if x[j] positives, accept solution. if x[j] negative, go point 2.

an example visible 2 dimensional space n-e in next figure.

caption: problem in n dimension reduced n-e=2 space. yellow diamond space of positive solutions of n-dimensional problem. randomly sample points in orange box between (t1(min),t2(min)) , (t1(max),t2(max)) until find point in yellow box.

i think enough solution, but...

problem

when n-e big, space of hyperparallelogram bounded inside hypercube can small. in general small^(n-e), can small. how small? while sure infinite number of positive solutions original problem exist, space of solutions can have measure 0 in n-e dimensional space. can happen if positive solutions of original problem have 1 dimension of x = 0. borders of diamond make contact, transforming diamond of solutions line. of course never randomly pick line in 2d, let alone in 5d.

a obvious idea further reduce dimensionality n-e smaller number, i.e. extract directly points aforementioned line instead of square. algebra not easy, i'm working on it. i'm not positive able solve it.

note choosing first 1 dimension (for example t1), computing new limits of t2 conditional value of t1 extracted , extract possible value of t2 in boundary, while faster, not give uniform probability among possible solutions.

i know problem specific, general ideas or thoughts gladly received. doubtful if there computing technique extract directly solution in diamond...