Witam

Mam specyficzne dane doświadczalne - głównie zera i trochę
jedynek. Zastanawia mnie czy można dokonać aproksymacji
liniowej w prostszy sposób niż przy pomocy rozwiązania układu
równań liniowych?

Jest wektor v_i, gdzie 1<= i <=N
Na wektorze v_i jest określona F( v ).
Trzeba znaleźć współczynniki liniowe a_i
aby suma kwadratów po wszystkich wektorach
była minimalna ( F( v ) - suma( v_i * a_i ) ) ^ 2

Każdy wektor v składa się z K części. Każda część
ma M elementów, czyli N = K*M. Co ciekawe
każda część składa się dokładnie z samych zer i
tylko jednej jedynki
Np. N = 12; K=3; M=4
F( (1 0 0 0) (0 1 0 0) (0 0 0 1) ) = 5
F( (0 1 0 0) (1 0 0 0) (0 1 0 0) ) = 2

Muszę ułożyć pełny układ równań, czy da się
jakoś prościej/szybciej albo na mniejszej pamięci?

Pozdrawiam

do góry

On 6 Wrz, 11:51, Mariusz Marszałkowski <m...@g...com> wrote:
> Witam
>
> Mam specyficzne dane doświadczalne - głównie zera i trochę
> jedynek. Zastanawia mnie czy można dokonać aproksymacji
> liniowej w prostszy sposób niż przy pomocy rozwiązania układu
> równań liniowych?
>
> Jest wektor v_i, gdzie 1<= i <=N
> Na wektorze v_i jest określona F( v ).
> Trzeba znaleźć współczynniki liniowe a_i
> aby suma kwadratów po wszystkich wektorach
> była minimalna  ( F( v ) - suma( v_i * a_i ) ) ^ 2

Ile jest wektorów? powiedzmy n >> N.


> Każdy wektor v składa się z K części. Każda część
> ma M elementów, czyli N = K*M. Co ciekawe
> każda część składa się dokładnie z samych zer i
> tylko jednej jedynki
> Np. N = 12; K=3; M=4
> F( (1 0 0 0) (0 1 0 0) (0 0  0 1) ) = 5
> F( (0 1 0 0) (1 0 0 0) (0 1  0 0) ) = 2

Rozumiem, ze podział na cześci jest stały.

> Muszę ułożyć pełny układ równań, czy da się
> jakoś prościej/szybciej albo na mniejszej pamięci?

Idzmy po lini najmniejszego oporu.
M*x=f .
f to wektor pomairow F(), M to macierz złozona
z leżących wektorów V ma rozmiar (n*N),
x to wektor parametrow a_i.

Rownanie normalne to A' A x= A' b

Macierz A'A ma rozmair tylko N*N i jest szybka do policzenia
(wykorzysztując wspomnianą własnosc). Podobnie A' *b.

Pewnie da się wyciagnąc wiecej, to na szybko.
Napisz, ile tych wektorkow i jakie to są konkretnie liczby.

pozdrawiam
bartekltg

do góry

On 6 Wrz, 17:33, bartekltg <b...@g...com> wrote:
> Ile jest wektorów? powiedzmy n >> N.
Będą generowane podczas monitorowania stanu pewnego
algorytmu. Mam do wyboru, albo mniej i
dokładniejsze, albo więcej mniej dokładne. Powiedzmy
że N = n/1000.

> Rozumiem, ze podział na cześci jest stały.
Tak, każdy wektor w każdej części ma dokładnie jedną
jedynkę i reszta zera.

> > Muszę ułożyć pełny układ równań, czy da się
> > jakoś prościej/szybciej albo na mniejszej pamięci?
>
> Idzmy po lini najmniejszego oporu.
> M*x=f .
> f to wektor pomairow F(), M to macierz złozona
> z leżących wektorów V ma rozmiar (n*N),
> x to wektor parametrow a_i.
>
> Rownanie normalne to A' A x= A' b
>
> Macierz A'A ma rozmair tylko N*N i jest szybka do policzenia
A jeśli N jest równe milion? :)

> Pewnie da się wyciagnąc wiecej, to na szybko.
> Napisz, ile tych wektorkow i jakie to są konkretnie liczby.

Rozmiaru zadania jeszcze nie znam, najpierw zrobię na małym
rozmiarze, sprawdzę co się dzieje, zrobię na większym
znów sprawdzę, itd. Dane są z monitoringu pracy algorytmu, więc
po roku mogę ich mieć nawet cały dysk.

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.

Sprawdziłem algorytm zachłanny na losowych zerach i jedynkach
( z zachowaniem jednej jedynki w każdej części ). Na kilku zbiorach
dał rozwiązanie gorsze od optymalnego o 0.5%. Zrobiłem mniej/więcej
tak:
1) Wszystkie współczynniki a_i <-- 0
2) j <--0
2) Rozwiąż układ tylko dla grupy j
3) Odejmij do żądanej wartości F(x) -= suma a_i * v_i : j*ilosc_grup
<= i <= (j+1)*ilosc_grup
4) skocz 2 jeśli j < ilosc_grup.

Pozdrawiam

do góry

Mariusz Marszałkowski <m...@g...com> wrote:
> Witam
>
> Mam specyficzne dane doświadczalne - głównie zera i trochę
> jedynek. Zastanawia mnie czy można dokonać aproksymacji
> liniowej w prostszy sposób niż przy pomocy rozwiązania układu
> równań liniowych?
>
> Jest wektor v_i, gdzie 1<= i <=N
> Na wektorze v_i jest określona F( v ).
> Trzeba znaleźć współczynniki liniowe a_i
> aby suma kwadratów po wszystkich wektorach
> była minimalna ( F( v ) - suma( v_i * a_i ) ) ^ 2
>
> Każdy wektor v składa się z K części. Każda część
> ma M elementów, czyli N = K*M. Co ciekawe
> każda część składa się dokładnie z samych zer i
> tylko jednej jedynki
> Np. N = 12; K=3; M=4
> F( (1 0 0 0) (0 1 0 0) (0 0 0 1) ) = 5
> F( (0 1 0 0) (1 0 0 0) (0 1 0 0) ) = 2
>
> Muszę ułożyć pełny układ równań, czy da się
> jakoś prościej/szybciej albo na mniejszej pamięci?
... poszukaj googlem "macierzy zadkich", wiekszosc jezykow
powinna cos do obrobki tego miec (np. python). Z powazaniem
Adam Przybyla

do góry

On 7 Wrz, 13:08, Adam Przybyla <a...@r...pl> wrote:
>         ... poszukaj googlem "macierzy zadkich", wiekszosc jezykow
> powinna cos do obrobki tego miec (np. python). Z powazaniem

Macierz nie będzie rzadka. Dane są specyficzne, rzadkie i
zero-jedynkowe. Chyba pozostaną przybliżone metody
rozwiązywania dużych układów równań.

Pozdrawiam

do góry

Mariusz Marszałkowski <m...@g...com> wrote:
> On 7 Wrz, 13:08, Adam Przybyla <a...@r...pl> wrote:
>>         ... poszukaj googlem "macierzy zadkich", wiekszosc jezykow
>> powinna cos do obrobki tego miec (np. python). Z powazaniem
>
> Macierz nie będzie rzadka. Dane są specyficzne, rzadkie i
> zero-jedynkowe. Chyba pozostaną przybliżone metody
> rozwiązywania dużych układów równań.
... masz duzo zer, to wykorzystaj. Z powazaniem
Adam Przybyla

do góry

On 8 Wrz, 19:21, Adam Przybyla <a...@r...pl> wrote:
>         ... masz duzo zer, to wykorzystaj. Z powazaniem
>                                                                 Adam Przybyla
Obawiam się że nie można tego faktu z istotnym zyskiem
wykorzystać, przynajmniej mi nic istotnego nie przychodzi
do głowy. Macierz układu równań już nie będzie miała zer.
Pozdrawiam

do góry

On 8 Wrz, 19:35, Mariusz Marszałkowski <m...@g...com> wrote:
> On 8 Wrz, 19:21, Adam Przybyla <a...@r...pl> wrote:>         ... masz duzo zer,
to wykorzystaj. Z powazaniem
> >                                                                 Adam Przybyla
>
> Obawiam się że nie można tego faktu z istotnym zyskiem
> wykorzystać, przynajmniej mi nic istotnego nie przychodzi
> do głowy. Macierz układu równań już nie będzie miała zer.

Jak to nie. Macierz układu rownań
zminimalizuj norm(Ax-b), czyli macierz A sklada
sie z tych wektorkow, czyli glownie z jedynek.
Dopiero macierz 'rownania normalnego' A'A bedzie pełna.

Poszperaj za metodami dla pierwotnego zagadnienia,
czyli najmniejszych kwadratow dla rzedkiej macierzy.
Cos takiego widzialem (ale nie wiem czy dokladnie to
i czy sie przyda).wiecej popisze jak bede
miec troche czasu.

pozdrawiam
bartekltg

do góry

On 8 Wrz, 23:15, bartekltg <b...@g...com> wrote:
> On 8 Wrz, 19:35, Mariusz Marszałkowski <m...@g...com> wrote:
> > Obawiam się że nie można tego faktu z istotnym zyskiem
> > wykorzystać, przynajmniej mi nic istotnego nie przychodzi
> > do głowy. Macierz układu równań już nie będzie miała zer.
>
> Jak to nie.
To mówimy o jakimś innym układzie :) W takim razie z
Twoich słów wynika że jest szybsza metoda od tej którą
to zadanie zawsze liczyłem. Na razie nic o niej nie wiem.

Zajrzałem do Cormena, strona 864, widzę jakąś metodę z
macierzą pseudo-odwrotną. Wzór na policzenie macierzy
pseudoodwrotnej: ( ( A^t x A ) ^ -1 ) x A^t - hmmm nie
widzę tutaj przyspieszenia.

Na stronie 864 mam " W praktyce równanie normalne
rozwiązujemy mnożąc y przez A^t, a następnie znajdując
rozkład LU macierzy A^t x A" - wydaje mi się że zawsze
tak to robiłem. Macierz A^t x A nie będzie miała zer, tzn
będzie je miała z bardzo małym prawdopodobieństwem.

Nie rozumiem o czym mówicie.
Pozdrawiam








> Macierz układu rownań
> zminimalizuj norm(Ax-b), czyli macierz A sklada
> sie z tych wektorkow, czyli glownie z jedynek.
Ja to widzę tak, że elementy macierzy A równania Ax=b
w postaci normalnej będą się składały z odpowiednich
sum iloczynów, zsumują się do dużych wartości.

> Dopiero macierz 'rownania normalnego' A'A bedzie pełna.


>
> Poszperaj za metodami dla pierwotnego zagadnienia,
> czyli najmniejszych kwadratow dla rzedkiej macierzy.
> Cos takiego widzialem (ale nie wiem czy dokladnie to
> i czy sie przyda).wiecej popisze jak bede
> miec troche czasu.
>
> pozdrawiam
> bartekltg

do góry

On 9 Wrz, 00:58, Mariusz Marszałkowski <m...@g...com> wrote:
> On 8 Wrz, 23:15, bartekltg <b...@g...com> wrote:> On 8 Wrz, 19:35, Mariusz
Marszałkowski <m...@g...com> wrote:
> > > Obawiam się że nie można tego faktu z istotnym zyskiem
> > > wykorzystać, przynajmniej mi nic istotnego nie przychodzi
> > > do głowy. Macierz układu równań już nie będzie miała zer.
>
> > Jak to nie.
>
> To mówimy o jakimś innym układzie :) W takim razie z
> Twoich słów wynika że jest szybsza metoda od tej którą
> to zadanie zawsze liczyłem. Na razie nic o niej nie wiem.

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.

> Na stronie 864 mam " W praktyce równanie normalne
> rozwiązujemy mnożąc y przez A^t, a następnie znajdując
> rozkład LU macierzy A^t x A" - wydaje mi się że zawsze
> tak to robiłem.

Cormen nie jest podręcznikiem do numerkow;)

Ta metoda nazywa się rownaniem normalnym i ma
pewne wady. Są inne metody. [chociaz ostatnio
ta polecalem, bo ladnie pasowala do 'poprzedniego'
problemu].


> Nie rozumiem o czym mówicie.

:(

> Ja to widzę tak, że elementy macierzy A równania Ax=b
> w postaci normalnej będą się składały z odpowiednich
> sum  iloczynów, zsumują się do dużych wartości.

Nazywasz dwie macierze ta samną literką? To sie nie dogadamy;)
Nazwijmy B=A^t*A.

B rzeczywiscie jest gęsta, ale A jest rzadka.

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

Nie kazda metoda zminimalizowania norm(Ax-b)
opiera sie na operacjach na maczierzy B.

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_methods_for_l
inear_least_squares#Orthogonal_decomposition_methods


QR jest czasem lepsze, bo "operujemy na A" a nie na "A kwadarat".
Uwarunkowanie!
No, ta metoda (ani SVD) do tego zagadnienia tez sie nie specjalnie nie
nadadza.


Zeby nie mnozyc bytów:

On 6 Wrz, 18:26, Mariusz Marszałkowski <m...@g...com> wrote:
> 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:)


> po roku mogę ich mieć nawet cały dysk.
>
> 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.

Dosc interesujace, co moze sie za tym kryć;)
Pewnie znowu nie opowiesz, to moze powtorze to co
ostatnio napisalem: zatrudnijcie jakiegos matematyka/numeryka;-)
U mnie jak potrzebny do powaznej rzeczy elektronik,
to sie bierze elektronika (jak do malo powaznej, to studenta,
co sie nie zawsze dobrze konczy;).

> Sprawdziłem algorytm zachłanny na losowych zerach i jedynkach
> ( z zachowaniem jednej jedynki w każdej części ). Na kilku zbiorach
> dał rozwiązanie gorsze od optymalnego o 0.5%. Zrobiłem mniej/więcej
> tak:
> 1) Wszystkie współczynniki a_i <-- 0
> 2) j <--0
> 2) Rozwiąż układ tylko dla grupy j
> 3) Odejmij do żądanej wartości F(x) -= suma a_i * v_i : j*ilosc_grup
> <= i <= (j+1)*ilosc_grup
> 4) skocz 2 jeśli j < ilosc_grup.

A nie działa to dlagtego, ze jest ladnie losowo i na kazdą
z grup przypada 'tele samo wektora'?

Są algorytmy 'iteracyjne', w tym 'randomizowane'.
mozna pojsc w tym kierunku, zwlaszcza, ze dane
naplywają stopniowo.

Na szybko. Mamy Ax-b=r
Popatrzmy na losową składową wektora wspołczynnikow,
x_i. Sprobujmy ja poprawić. Niech korekta w=(0,0..1..0,0).

A(x+c*w)-b=r-c*Aw
r-c*v; v=Aw; c-liczb rzeczywista.

powstalo 'jednowymiarowe' zagadnienie najmniejszych kwadratow:)
c=<v,r>/<v,v>.

Losujemy kolejny element do poprawki i tak w kolko.
To algorytm z naswiskiem, uzywany nawet, ale nie pamietam
namiarow.

Mozna 'na raz' optymalizować wiecej niz jeden skladnik
wektora wspolczynnikow x, ale na oko nie jest to oplacalne.

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;)

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)

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.

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.

Przy okazji, Y. Saad na swojej stronie wystawił wielka ksiązke do
matod iteracyjnych:)



pozdrawiam
bartekltg

do góry