Random header image... Refresh for more!

Problema de mate-info

Updated

De cateva zile ma chinui cu urmatoarea problema. Poate reusiti sa-mi dati ceva pointeri buni.

Se da un un set de puncte (> 10k evenimente) de forma (x1,x2,x3,...,xn, w), unde xi,i=1,n sunt coordonatele axelor ortogonale Oi iar w greutatea punctului. Se cer vectorii x0i care definesc marginile binilor pe axele Oi astfel incat in fiecare bin n-dimensional se indeplineste conditia sqrt(sum(w^2))/sum(w) < w0 (unde primul factor e insumat peste toate evenimentele din bin) si unde w0 este cunoscut. Sunt interesat in rezolvarea problemei in 3-4 dimensiuni dar daca exista un algoritm mai general sunt bucuros sa-l aflu. Daca nu e clara problema semnalati si o sa incerc sa dau o explicatie mai buna. HELP! Incerc sa fiu mai clar si sa dau un exemplu 1D. [caption id="attachment_1640" align="aligncenter" width="400"]Variable Variable [/caption]

In imaginea de mai sus avem 3k evenimente caracterizate de vectorul (var,w). Valoarea var este reprezentata pe axa Ox iar w corespunde segmentelor verticale. Prima histograma este "rebinned" de la dreapta la stanga astfel incat in fiecare bin functia descrisa mai sus este <0.2 (se insumeaza peste toate evenimentele care cad in intervalul unui bin. Conditia de pornire este o histograma cu 100k bini egal echidistanti in intervalul [0.1,0.3] si se ajunge la urmatorul vector al binilor 1D [0.1, 0.192334, 0.199014, 0.205538, 0.22110200000000002, 0.222138, 0.223216, 0.224592, 0.22581, 0.226992, 0.228162, 0.3].

www.pdf24.org    Send article as PDF   

6 comments

1 lektor { 12.12.12 at 7:58 pm }

Da-mi pe mail textul precis al problemei. Deocamdata n-am inteles nimic:)

2 Lucian { 12.12.12 at 8:01 pm }

Revin cu text cu explicatii ­čÖé

3 lektor { 12.13.12 at 1:06 pm }

Problema este puternic dependenta de constanta w_0 precum si de numarul de evenimente. Daca w_0 e prea mic, nicio alegere de bini nu poate functiona, iar daca w_0 e destul de mare, atunci orice alegere de bini e la fel de buna. E in legatura cu faptul ca intr-un spatiu finit dimensional normele l^2 si l^1 sint echivalente.

Daca nu introduci mai multe restrictii, problema nu are intotdeauna o solutie. Daca are, atunci niciodata nu e unica.

4 Lucian { 12.13.12 at 4:18 pm }

Daca w_0 este prea mic atunci rezultatul e binul maxim .... Nu este o problema daca nu exista o solutie, w_0 poate fi ajustat. Cat despre un w_0 mare : e suficienta o singura solutie .... nu trebuie gasite toate.

Poti sa explici un pic mai mult ce intelegi prin normele l^2 si l^1?

5 lektor { 12.13.12 at 8:32 pm }

Mai jos formule sint in latex. Daca $A=\{a_j\}_{j=1}^N$ e un vector cu coeficienti reali de dimensiune $N$, atunci
$||A||_2=\sqrt{\sum_{j=1}^N a_j^2}$ este norma $l^2$, iar $||A||_1=\sum_{j=1}^N|a_j|}$ este norma $l^1$. Intr-un spatiu finit dimensional, toate normele sint echivalente. Asta inseamna ca exista doua constante pozitive $c_1$ si $c_2$ depinzind de dimensiunea $N$, astfel incit

\(\)

Cu alte cuvinte, pentru un $N$ dat (marginit superior de numarul de evenimente), daca $w_0$ e mai mic decit $c_1$, nicio alegere de bini nu poate fi o solutie.

Problema nu e bine formulata. Lipsesc conditii suplimentare care sa asigure existenta unei solutii.

6 lektor { 12.13.12 at 8:34 pm }

e ceva nasol cu wordpresul asta, mi-a taiat din text.

Leave a Comment