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...


Comments

Post a Comment

Popular posts from this blog

powershell Start-Process exit code -1073741502 when used with Credential from a windows service environment -

i'm running strange behavior powershell start-process call. here call: $process = start-process ` "c:\somepath\mybinary.exe" ` -passthru ` -credential $defaultcredential ` -wait ` -workingdirectory "c:\somepath" ` -loaduserprofile if ($process.exitcode -ne 0) { #do } this call return exit code - 1073741502 . after quick search, exit code seems related generic error when program not load required dll (aka. status_dll_init_failed ). when run without -credential $credential program runs correctly. in order isolate problem, manually launched some.exe in prompt target credential , runs smoothly. so problem seems come way start-process cmdlet launch process. i found potential solutions problem tried apply no luck : link , link . would have idea of what's going on here ? edit 1: run proc mon monitoring program activities when launched directly or via powershell script. problem seems occur when loading kernelbase
Read more

twig - Using Twigbridge in a Laravel 5.1 Package -

i'm trying create laravel 5.1 package uses twigbridge instead of .php views. can normal .php views display fine, when try make use of .twig templates i'm met error. possible use twigbridge templates when creating views laravel package or pretty stuck blade , php ? edit 1: loading twig template without extending works. it's when start using {% extends 'file' %} error comes out. i error error loading /virtual/laravel/packages/username/mypackage/src/views/sample.twig: template "templates.master" not defined () in "/virtual/laravel/packages/username/mypackage/src/views/sample.twig" @ line 1. my folders username |_ mypackage |_ src |_ controllers - samplecontroller.php |_ views |_ templates - master.twig - sample.twig twig template sample.twig {% extends 'templates.master' %} {% block content %} {{ parent()
Read more

c# - LINQ join Entities from HashSet's, Join vs Dictionary vs HashSet performance -

i have hashset's each stores t, have written test application compares different relation algorithms can think of, i'm not pleased results getting. does there exist more efficient ways of achieving object relations, once testing? using system; using system.collections.generic; using system.linq; using system.text; using system.threading.tasks; using system.diagnostics; namespace linqtests { class program { static void main(string[] args) { hashset<user> usertable = new hashset<user>(); hashset<userproperty> userpropertytable = new hashset<userproperty>(); #region lets create dummy data. console.writeline("please wait while creating dummy data, can take while..."); console.writeline(""); int rows = 1000000; for(int x = 0; x < rows; x++) { random rnd = new random(); // ad
Read more