Jaka jest dokładna miara rzadkości?

Obecnie pracuję nad skompresowanym wykrywaniem i rzadką reprezentacją sygnałów, a konkretnie obrazów.

Często zadawane mi jest pytanie „co to jest definicja sparsity?”. Odpowiadam „jeśli większość elementów sygnału jest zerowa lub bliska zeru, w niektórych dziedzinach, takich jak Fourier lub Wavelet, wówczas sygnał ten jest rzadki na tej podstawie”. ale w tej definicji zawsze pojawia się problem: „co oznacza większość elementów? Czy to 90 procent? 80 procent? 92,86 procent ?!” Oto, gdzie powstaje moje pytanie, czy istnieje jakaś dokładna, tj. Liczbowa, definicja rzadkości?

sparsity M.Jalali
źródło

Myślę, że przekonasz się, że rzadkość to termin podobny do przepustowości . Nie mają jednej definicji, która obowiązywałaby we wszystkich kontekstach. Odpowiedź jest niezadowalająca „to zależy”.

Jason R

@JasonR Myślę, że tak, ale czy istnieje wzmianka o tym?

M.Jalali

To zależy również od twoich planów odbudowy.

MimSaad

@Jason R Twoje połączenie z przepustowością jest dość inspirujące. Oba mają pojęcie pozbawione amplitudy w stosunku do pewnego wsparcia. Wydaje mi się, że przepustowość wymusza pewne pojęcie o „wystarczającym” powiązaniu ponad rzadkością

Laurent Duval,

„ Czy istnieje jakaś dokładna, tj. Liczbowa, definicja rzadkości? ”. I liczbowo rozumiem zarówno obliczalną , jak i praktycznie „użyteczną”. Uważam, że: przynajmniej jeszcze nie ma konsensusu, ale jest kilku godnych pretendentów. Pierwsza opcja „ licz tylko wyrażenia niezerowe ” jest precyzyjna, ale nieefektywna (wrażliwa na przybliżenie liczbowe i szum oraz bardzo skomplikowana w optymalizacji). Druga opcja „ większość elementów sygnału jest zerowa lub bliska zeru ” jest raczej niedokładna, zarówno w przypadku „większości”, jak i „bliskiej”.

Zatem „ dokładna miara rzadkości ” pozostaje nieuchwytna, bez bardziej formalnych aspektów. Jedna ostatnia próba zdefiniowania rzadkości przeprowadzona w Hurley i Rickard, 2009 Porównując miary rzadkości , Transakcje IEEE dotyczące teorii informacji.

Ich celem jest dostarczenie zestawu aksjomatów, które powinna spełnić dobra miara rzadkości ; na przykład sygnał pomnożony przez niezerową stałą powinien mieć tę samą rzadkość. Innymi słowy, miara sparsity powinno być -homogeneous. Co proxy w wykrywaniu kompresji lub w regresji lasso jest -jednorodne. Jest tak w rzeczywistości w przypadku każdej normy lub quasi-normy , nawet jeśli mają tendencję do ( ) miary liczenia jako . $x$ $\alpha x$ $0$ $\ell_1$ $1$ $\ell_p$ $\ell_0$ $p\to 0$

Wyszczególniają więc swoje sześć aksjomatów, wykonują obliczenia, zapożyczone z analizy bogactwa:

Robin Hood (zabrać bogatym, dać biednym zmniejsza rzadkość),
Skalowanie (stałe mnożenie zachowuje rzadkość),
Rising Tide (dodanie tego samego niezerowego konta zmniejsza rzadkość),
Klonowanie (duplikowanie danych zachowuje rzadkość),
Bill Gates (bogacenie się jednego człowieka zwiększa rzadkość),
Niemowlęta (dodanie wartości zerowych zwiększa rzadkość)

i zbadaj znane miary przeciwko nim, ujawniając, że indeks Gini i niektóre stosunki norm lub quasi-norm mogą być dobrymi kandydatami (w przypadku tych ostatnich niektóre szczegóły podano w Euclid w Taxicab: Sparse Blind Deconvolution with Smoothed Regularization $\ell_1/\ell_2$ , 2005, IEEE Signal Processing Letters). Czuję, że roboty powinny być rozwinięte (dzień dostosować w SPOQ, Wygładzone przez quasi-normy / Wskaźniki normy $p$ $q$ $\ell_p/\ell_q$ ). Ponieważ dla sygnału , nierówność stosunku norm daje: $x$ $0< p\le q$

1 \leq \frac{ℓ_{p} (x)}{ℓ_{q} (x)} \leq ℓ_{0} (x)^{1 / p - 1 / q}

$1\le \frac{\ell_p(x)}{\ell_q(x)}\le \ell_0(x)^{1/p-1/q}$

i ma tendencję do (lewa strona, LHS), gdy jest rzadki, i do prawej strony (RHS), gdy nie. Ta praca jest teraz przedrukiem: SPOQ: płynna regulacja p-Over-q dla rzadkiego odzyskiwania sygnału zastosowana do spektrometrii mas . Jednak rozsądna miara rzadkości nie informuje, czy przekształcone dane są wystarczająco rzadkie, czy nie, zgodnie z twoim celem. $1$ $x$

Wreszcie, inną koncepcją stosowaną w wykrywaniu kompresyjnym jest koncepcja ściśliwości sygnałów, w której ponownie uporządkowane (malejące) wielkości współczynników zgodne z prawem mocy , a im większa , tym ostrzejszy rozkład. $c_{(k)}$ $C_\alpha .(k)^{-\alpha}$ $\alpha$

Laurent Duval
źródło

Jaka jest dokładna miara rzadkości?

Odpowiedzi: