Какова точная мера разреженности?

В настоящее время я работаю над сжатием и разреженным представлением сигналов, в частности изображений.

Меня часто спрашивают «что такое определение редкости?». Я отвечаю: «Если большинство элементов сигнала равны нулю или близки к нулю, в некоторой области, такой как Фурье или Вейвлет, то этот сигнал в этом базисе редок». но в этом определении всегда есть проблема: «что означает большинство элементов? Это 90 процентов? 80 процентов? 92,86 процента ?!” Вот где возникает мой вопрос, есть ли точное, то есть числовое определение разреженности?

« Есть ли какое-то точное, то есть числовое определение разреженности? » И под числовым я понимаю как вычислимое , так и практически «пригодное для использования». Мое мнение таково: пока нет, как минимум, консенсуса нет, но есть достойные соперники. Первый вариант « считать только ненулевые члены » точен, но неэффективен (чувствителен к числовому приближению и шуму, и очень сложен для оптимизации). Второй вариант « большинство элементов сигнала - ноль или близок к нулю » довольно неточен, либо для «большинства», либо «близко к».

Таким образом, « точная мера редкости » остается неуловимой, без более формальных аспектов. Одна из недавних попыток определить разреженность была проведена в Hurley and Rickard, 2009, Сравнение мер разреженности , IEEE транзакции по теории информации.

Их идея состоит в том, чтобы предоставить набор аксиом, которые должна выполнять хорошая мера разреженности ; например, сигнал $x$ умножается на ненулевой константы, $\alpha x$ , должны иметь один и тот же разреженность. Другими словами, мера разреженности должна быть $0$ однородной. Как ни странно, прокси $\ell_1$ ощущении сжатия или регрессии лассо является $1$ однородным. Это действительно так для любой нормы или квази-нормы $\ell_p$ , даже если они стремятся к (не робастной) мере счета $\ell_0$ при $p\to 0$ .

Таким образом, они детализируют свои шесть аксиом, выполнили вычисления, заимствованные из анализа богатства:

• Робин Гуд (бери у богатых, дай бедным снижает редкость),
• Масштабирование (постоянное умножение сохраняет разреженность),
• Rising Tide (добавление того же ненулевого аккаунта уменьшает разреженность),
• Клонирование (дублирование данных сохраняет разреженность),
• Билл Гейтс (один человек становится богаче, увеличивает редкость),
• Младенцы (добавление нулевых значений увеличивает разреженность)

$\ell_1/\ell_2$$p$$q$ $\ell_p/\ell_q$$x$$0< p\le q$

$1$$x$

$c_{(k)}$$C_\alpha .(k)^{-\alpha}$$\alpha$