On 9 Wrz, 12:11, bartekltg <b...@g...com> wrote:
> Mówiłem to ostatnio, mialem to raz jeszcze napisać
> w odpowiedzi ktorą powolitku pisze dla drugiej odnogi wątku,
> ale wspomne o tym teraz: moze jednak zatrudnijcie jakiegos
> matematyka/numeryka.
Żałuję, ale to nie przejdzie z dwóch powodów:
1) nie ma funduszy choćby na przeciętne wynagrodzenie
2) bardzo specyficzne wymagania co do poufności

> Cormen nie jest podręcznikiem do numerkow;)
Ale Cormena najłatwiej trawię. W Cormenie jest
probabilistyczny algorytm mnożenia macierzy
bolowskich, może to nasunie jakieś rozwiązanie.

> Nazywasz dwie macierze ta samną literką? To sie nie dogadamy;)
> Nazwijmy B=A^t*A.
>
> B rzeczywiscie jest gęsta, ale A jest rzadka.
Teraz wszystko jasne.

> Dla przypomnienia, zagadnienie jest n*N  n>N (n=1000N)
> N=K*M.
> A ma n*K niezerowych elementow.
Zgadza się

> Nie kazda metoda zminimalizowania norm(Ax-b)
> opiera sie na operacjach na maczierzy B.
Świetnie, tego szukam.

> Jest druga 'szkolna' metoda, przez rozklad QR.
>
> A=QR
> R=[R_1; 0]
> liczymy Q^t *b, powstaly wektor obcianmy
> no N wspolrzednych (wektor w) i rozwiazujemy
> uklad trojkatny
>
> R_1 x = w.
>
> Jako zalazek do poszukiwan:http://en.wikipedia.org/wiki/Numerical_me
thods_for_linear_least_squar...
>
> QR jest czasem lepsze, bo  "operujemy na A" a nie na "A kwadarat".
Dokładnie czegoś takiego potrzebuję.

> Uwarunkowanie!
> No, ta metoda (ani SVD) do tego zagadnienia tez sie nie specjalnie nie
> nadadza.
Hmmmm

> > On 6 Wrz, 17:33, bartekltg <b...@g...com> wrote:> Ile jest wektorów?
powiedzmy n >> N.
> > A jeśli N jest równe milion? :)
>
> Hmm, to ciezko bedzie:) Skąd wezmiesz 8 pata(10^15) bajtow dysku:)
Nawet 10^15 by nie starczyło :)

> > Oryginalny wektor ma niecałe 100 wartości ze małego zbioru
> > liczb całkowitych, np. <-7,+7>. Wektor ten będzie mapowany
> > przy pomocy nieliniowej funkcji  w dużo większy wektor
> > zero-jedynkowy o takich własnościach jak napisałem - tylko
> > jedna jedynka w każdej części.
>
> A nie działa to dlagtego, ze jest ladnie losowo i na kazdą
> z grup przypada 'tele samo wektora'?
Całkiem możliwe.

> Są algorytmy 'iteracyjne', w tym 'randomizowane'.
> mozna pojsc w tym kierunku, zwlaszcza, ze dane
> naplywają stopniowo.
>
> Mozna 'na raz' optymalizować wiecej niz jeden skladnik
> wektora wspolczynnikow x, ale na oko nie jest to oplacalne.
Można próbować gradientów sprzężonych, ale to się
skończy ogromną ilością iteracji...

> Uzywamy wlasciwie tylko mnozenia przez rzadką A
> (musisz ja zapisać rozsadnie, aby nie iterowc po zerach).
> ilosc potrzebnych interacji to juz inna sprawa, jesli masz
> gigabajty, to nie spodziewaj sie szybko wyniku;)
Jeśli nie da się szybko, to będę musiał zrobić inne mapowanie
wektorów, nie będzie wyjścia.


> Powinno sie wygoglac bardziej zaawansowane tego typu metody,
> poszukaj po least squares, sparse, moze cos o iterowaniu i wariacje.
>
> Zupelnie inna metoda. Reszta r=Ax-b spełnia dla optymalnego x
> A^t * r =0.
> Uklad rownan mozemy zapisać lacznie jako
> [    I     A]  [x]
> [ A^t    0 ]  [r]
>                        =
> [b]
> [0]
>
> I -macierz jednostkowa. Zagadnienie jest znacznie wieksze,
> ale macierz jest nadal rzadka (rzedu n*(2*K+1) elementow ).
> Jesli K jest małe, jakaś sprytniejsza metoda iteracyjna rozwiazywania
> rownan liniowych da wynik szybko (pewnei precondicioner by sie
> przydal)
Hmmmm wygląda sensownie. W pamięci tylko dane, a dane dadzą
się skompresować 1000 krotnie. Może to dobry kierunek.


> Zaletą jest, ze (w wersji bez prec.) nie trzymamy w pamieci zadnej
> macierzy,
> tylko iterowany wektor (rozmiar n+N). A mnozenie, jesli odpowqiednio
> zapiszesz swoją macierz (wektory z pomiarow), zajmuje tylko tyle
> czasu,
> ile jest niezerowych elementow.
Będę musiał to sprawdzić.


> Bardzo mozliwe, ze w tym przypadku da sie zastosowac albo wymyslic
> jakis prosty (aby dal sie w biegu liczyc, byl oparty na A etc, aby nie
> trzymac
> duzej macierzy w pamieci) precondiconer, przez co mozemy dostać
> przyzwoite
> rozwiązania przy niewielkiej ilosci iteracji. Ale to juz na dłuzsze
> głowkowanie.
> Zaletą metod iteracyjnych bedize tez to, ze jesli dojdą nowe wektory
> (skladniki A)
> to juz mamy obliczony wczesniej przyzwoity punkt startowy.
Ta zaleta się nie przyda, przy nowym mapowaniu nieliniowym wszystkie
całkowicie się zmienia i metoda musi liczyć na nowo :)

> Przy okazji, Y. Saad na swojej stronie wystawił wielka ksiązke do
> matod iteracyjnych:)
Ok, dzięki może to dobry ślad :)

> pozdrawiam
również