Дискретный универсальный шумоподавитель - Discrete Universal Denoiser

В теория информации и обработка сигналов, то Дискретный универсальный шумоподавитель (ЧУВАК) это шумоподавление схема восстановления последовательностей над конечным алфавитом, которые были повреждены дискретный канал без памяти. DUDE был предложен в 2005 году Цаки Вайсман, Эриком Ордентлихом, Гадиэлем Серусси, Серджио Верду и Марсело Дж. Вайнбергером.^[1]

Обзор

Дискретный универсальный шумоподавитель^[1] (DUDE) - это шумоподавление схема, которая оценивает неизвестный сигнал ${ displaystyle x ^ {n} = left (x_ {1} ldots x_ {n} right)}$ над конечным алфавитом из зашумленной версии ${ displaystyle z ^ {n} = left (z_ {1} ldots z_ {n} right)}$ .В то время как большинство шумоподавление схемы в литературе по обработке сигналов и статистике сигналы В бесконечном алфавите (особенно в сигналах с действительным знаком) DUDE обращается к регистру бесконечного алфавита. Шумная версия ${ Displaystyle г ^ {п}}$ предполагается, что генерируется путем передачи ${ Displaystyle х ^ {п}}$ через известный дискретный канал без памяти.

Для фиксированного длина контекста параметр ${ displaystyle k}$ , DUDE подсчитывает вхождения всех строк длины ${ displaystyle 2k + 1}$ появляясь в ${ Displaystyle г ^ {п}}$ . Ориентировочная стоимость ${ displaystyle { hat {x}} _ {i}}$ определяется исходя из двухсторонней длины ${ displaystyle k}$ контекст ${ Displaystyle влево (z_ {я-к}, ldots, z_ {я-1}, z_ {я + 1}, ldots, z_ {я + к} справа)}$ из ${ displaystyle z_ {i}}$ , учитывая все остальные токены в ${ Displaystyle г ^ {п}}$ с тем же контекстом, а также с известной матрицей канала и используемой функцией потерь.

Идея, лежащая в основе DUDE, лучше всего иллюстрируется, когда ${ Displaystyle х ^ {п}}$ является ареализацией случайного вектора ${ displaystyle X ^ {n}}$ . Если условное распределение ${ Displaystyle X_ {я} | Z_ {i-k}, ldots, Z_ {i-1}, Z_ {i + 1}, ldots, Z_ {i + k}}$ , а именно распределение бесшумного символа ${ displaystyle X_ {i}}$ зависит от его шумного контекста ${ displaystyle left (Z_ {i-k}, ldots, Z_ {i-1}, Z_ {i + 1}, ldots, Z_ {i + k} right)}$ был доступен, оптимизатор ${ displaystyle { hat {X}} _ {i}}$ будет Байесовский ответ к ${ Displaystyle X_ {я} | Z_ {i-k}, ldots, Z_ {i-1}, Z_ {i + 1}, ldots, Z_ {i + k}}$ К счастью, если матрица каналов известна и невырождена, это условное распределение может быть выражено через условное распределение ${ Displaystyle Z_ {я} | Z_ {i-k}, ldots, Z_ {i-1}, Z_ {i + 1}, ldots, Z_ {i + k}}$ , а именно распределение зашумленного символа ${ displaystyle Z_ {i}}$ обусловлено его зашумленным контекстом. Это условное распределение, в свою очередь, может быть оценено на основе индивидуального наблюдаемого зашумленного сигнала. ${ Displaystyle Z ^ {п}}$ в силу Закон больших чисел, при условии ${ displaystyle n}$ «достаточно большой».

Применение схемы DUDE с длиной контекста ${ displaystyle k}$ к последовательности длины ${ displaystyle n}$ над конечным алфавитом ${ Displaystyle { mathcal {Z}}}$ требует ${ Displaystyle О (п)}$ операции и пространство ${ Displaystyle О влево ( мин (п, | { mathcal {Z}} | ^ {2k}) вправо)}$ .

При определенных предположениях DUDE является универсальной схемой в смысле асимптотической работы, а также оптимальным шумоподавителем, который имеет доступ оракула к неизвестной последовательности. Более конкретно, предположим, что эффективность шумоподавления измеряется с использованием заданного критерия точности воспроизведения одного символа, и рассмотрим режим, в котором длина последовательности ${ displaystyle n}$ стремится к бесконечности, а длина контекста ${ Displaystyle к = к_ {п}}$ стремится к бесконечности «не слишком быстро». В стохастической постановке, где дважды бесконечная последовательность бесшумная последовательность ${ displaystyle mathbf {x}}$ реализация стационарного процесса ${ displaystyle mathbf {X}}$ , DUDE асимптотически работает, в ожидании, а также лучший шумоподавитель, который имеет доступ оракула к исходному распределению ${ displaystyle mathbf {X}}$ . В однопоследовательной или «полустохастической» настройке с фиксированный дважды бесконечная последовательность ${ displaystyle mathbf {x}}$ , DUDE асимптотически работает так же хорошо, как и лучший шумоподавитель «скользящего окна», а именно любой шумоподавитель, который определяет ${ displaystyle { hat {x}} _ {i}}$ из окна ${ Displaystyle влево (z_ {я-к}, ldots, z_ {я + к} вправо)}$ , у которого есть доступ оракула к ${ displaystyle mathbf {x}}$ .

Дискретная проблема шумоподавления

Описание блок-схемы дискретной задачи шумоподавления

Позволять ${ displaystyle { mathcal {X}}}$ - конечный алфавит фиксированной, но неизвестной исходной «бесшумной» последовательности ${ displaystyle x ^ {n} = left (x_ {1}, ldots, x_ {n} right) in { mathcal {X}} ^ {n}}$ . Последовательность вводится в дискретный канал без памяти (DMC). DMC работает с каждым символом ${ displaystyle x_ {i}}$ независимо, производя соответствующий случайный символ ${ displaystyle Z_ {i}}$ в конечном алфавите ${ Displaystyle { mathcal {Z}}}$ . DMC известен и представлен как ${ displaystyle { mathcal {X}}}$ -к- ${ Displaystyle { mathcal {Z}}}$ Матрица Маркова ${ displaystyle Pi}$ , чьи записи ${ displaystyle pi (x, z) = mathbb {P} left (Z = z , | , X = x right)}$ . Удобно писать ${ displaystyle pi _ {z}}$ для ${ displaystyle z}$ -колонка ${ displaystyle Pi}$ . DMC производит случайную последовательность с шумом ${ displaystyle Z ^ {n} = left (z_ {1}, ldots, z_ {n} right) in { mathcal {Z}} ^ {n}}$ . Конкретная реализация этого случайного вектора обозначим через ${ Displaystyle г ^ {п}}$ Шумоподавитель - это функция ${ displaystyle { hat {X}} ^ {n}: { mathcal {Z}} ^ {n} to { mathcal {X}} ^ {n}}$ который пытается восстановить бесшумную последовательность ${ Displaystyle х ^ {п}}$ из искаженной версии ${ Displaystyle г ^ {п}}$ . Конкретная шумоподавленная последовательность обозначается ${ displaystyle { hat {x}} ^ {n} = { hat {X}} ^ {n} left (z ^ {n} right) = left ({ hat {X}} _ { 1} (z ^ {n}), ldots, { hat {X}} _ {n} (z ^ {n}) right)}$ .Проблема выбора шумоподавителя. ${ Displaystyle { шляпа {X}} ^ {п}}$ известна как оценка сигналов, фильтрация или сглаживание. Для сравнения кандидатов в шумоподавители мы выбираем критерий однозначной верности ${ displaystyle Lambda: { mathcal {X}} times { mathcal {X}} to [0, infty)}$ (например, потери Хэмминга) и определим посимвольные потери шумоподавителя ${ Displaystyle { шляпа {X}} ^ {п}}$ в ${ Displaystyle (х ^ {п}, г ^ {п})}$ к

 ${ displaystyle { begin {align} L _ { hat {X}} ^ {n}} left (x ^ {n}, z ^ {n} right) = { frac {1} {n} } sum _ {i = 1} ^ {n} Lambda left (x_ {i} ,, , { hat {X}} _ {i} (z ^ {n}) right) , . end {выравнивается}}}$

Порядок элементов алфавита ${ displaystyle { mathcal {X}}}$ к ${ displaystyle { mathcal {X}} = left (a_ {1}, ldots, a_ {| { mathcal {X}} |} right)}$ , критерий верности может быть задан ${ displaystyle | { mathcal {X}} |}$ -к- ${ displaystyle | { mathcal {X}} |}$ матрица со столбцами вида

 ${ displaystyle { begin {align} lambda _ { hat {x}} = left ({ begin {array} {c} Lambda (a_ {1}, { hat {x}}) vdots Lambda (a_ {| { mathcal {X}} |}, { hat {x}}) end {array}} right) ,. end {align}}}$

Схема DUDE

Шаг 1: Расчет эмпирического распределения в каждом контексте

DUDE исправляет символы в соответствии с их контекстом. Длина контекста ${ displaystyle k}$ Используется параметр настройки схемы. Для ${ Displaystyle к + 1 Leq я Leq п-к}$ , определите левый контекст ${ displaystyle i}$ -й символ в ${ Displaystyle г ^ {п}}$ к ${ displaystyle l ^ {k} (z ^ {n}, i) = left (z_ {i-k}, ldots, z_ {i-1} right)}$ и соответствующий правый контекст как ${ Displaystyle г ^ {к} (z ^ {n}, i) = left (z_ {i + 1}, ldots, z_ {i + k} right)}$ . Двусторонний контекст - это комбинация ${ Displaystyle (л ^ {к}, г ^ {к})}$ левого и правого контекста.

Первым шагом схемы DUDE является вычисление эмпирического распределения символов в каждом возможном двустороннем контексте вдоль зашумленной последовательности. ${ Displaystyle г ^ {п}}$ . Формально данный двусторонний контекст ${ displaystyle (l ^ {k}, r ^ {k}) in { mathcal {Z}} ^ {k} times { mathcal {Z}} ^ {k}}$ который появляется один или несколько раз ${ Displaystyle г ^ {п}}$ определяет эмпирическое распределение вероятностей по ${ Displaystyle { mathcal {Z}}}$ , значение которого у символа ${ displaystyle z}$ является

 ${ Displaystyle { begin {align} mu left (z ^ {n}, l ^ {k}, r ^ {k} right) [z] = { frac {{ Big |} left {k + 1 leq i leq nk , , | , , (z_ {ik}, ldots, z_ {i + k}) = l ^ {k} zr ^ {k} right } { Big |}} {{ Big |} left {k + 1 leq i leq nk , , | , , l ^ {k} (z ^ {n}, i) = l ^ {k} { text {and}} r ^ {k} (z ^ {n}, i) = r ^ {k} right } { Big |}}} ,. end {выровнено} }}$

Таким образом, первый шаг схемы DUDE с длиной контекста ${ displaystyle k}$ сканировать входящую зашумленную последовательность ${ Displaystyle г ^ {п}}$ один раз и сохраните длину ${ displaystyle | { mathcal {Z}} |}$ вектор эмпирического распределения ${ displaystyle mu left (z ^ {n}, l ^ {k}, r ^ {k} right)}$ (или его ненормализованная версия, вектор счета) для каждого двустороннего контекста, найденного вдоль ${ Displaystyle г ^ {п}}$ . Поскольку существует не более ${ displaystyle N_ {n, k} = min left (n, | { mathcal {Z}} | ^ {2k} right)}$ возможные двусторонние контексты по ${ Displaystyle г ^ {п}}$ , этот шаг требует ${ Displaystyle О (п)}$ операции и хранение ${ displaystyle O (N_ {n, k})}$ .

Шаг 2: Расчет байесовского ответа на каждый контекст

Обозначим столбец критерия однозначной верности ${ displaystyle Lambda}$ , соответствующий символу ${ displaystyle { hat {x}} in { mathcal {X}}}$ , к ${ displaystyle lambda _ { hat {x}}}$ . Мы определяем Байесовский ответ к любому вектору ${ displaystyle mathbf {v}}$ длины ${ displaystyle | { mathcal {X}} |}$ с неотрицательными записями как

 ${ displaystyle { begin {align} { hat {X}} _ {Bayes} ( mathbf {v}) = { text {argmin}} _ {{ hat {x}} in { mathcal { X}}} lambda _ { hat {x}} ^ { top} mathbf {v} ,. End {align}}}$

Это определение мотивировано фон ниже.

Второй шаг схемы DUDE - вычислить для каждого двустороннего контекста ${ Displaystyle (л ^ {к}, г ^ {к})}$ наблюдалось на предыдущем шаге ${ Displaystyle г ^ {п}}$ , а для каждого символа ${ displaystyle z in { mathcal {Z}}}$ наблюдается в каждом контексте (а именно, любой ${ displaystyle z}$ такой, что ${ displaystyle l ^ {r} zr ^ {k}}$ это подстрока ${ Displaystyle г ^ {п}}$ ) байесовский ответ на вектор ${ displaystyle Pi ^ {- top} mu left (z ^ {n} ,, , l ^ {k} ,, , r ^ {k} right) odot pi _ { z}}$ , а именно

 ${ displaystyle { begin {align} g (l ^ {k}, z, r ^ {k}): = { hat {X}} _ {Bayes} left ( Pi ^ {- top} mu left (z ^ {n} ,, , l ^ {k} ,, , r ^ {k} right) odot pi _ {z} right) ,. end {выровнено }}}$

Обратите внимание, что последовательность ${ Displaystyle г ^ {п}}$ и длина контекста ${ displaystyle k}$ неявны. Здесь, ${ displaystyle pi _ {z}}$ это ${ displaystyle z}$ -колонка ${ displaystyle Pi}$ и для векторов ${ Displaystyle mathbf {а}}$ и ${ displaystyle mathbf {b}}$ , ${ Displaystyle mathbf {а} odot mathbf {b}}$ обозначает их произведение Шура (поэлементное), определяемое как ${ displaystyle left ( mathbf {a} odot mathbf {b} right) _ {i} = a_ {i} b_ {i}}$ . Умножение матриц оценивается перед произведением Шура, так что ${ displaystyle Pi ^ {- top} mu odot pi _ {z}}$ означает ${ Displaystyle ( Pi ^ {- top} mu) odot pi _ {z}}$ .

Эта формула предполагает, что матрица канала ${ displaystyle Pi}$ квадратный ( ${ Displaystyle | { mathcal {X}} | = | { mathcal {Z}} |}$ ) и обратимый. Когда ${ Displaystyle | { mathcal {X}} | leq | { mathcal {Z}} |}$ и ${ displaystyle Pi}$ необратим, при разумном предположении, что он имеет полный ранг строки, заменим ${ displaystyle ( Pi ^ { top}) ^ {- 1}}$ выше с его псевдообратной функцией Мура-Пенроуза ${ displaystyle left ( Pi Pi ^ { top} right) ^ {- 1} Pi}$ и вместо этого рассчитать

 ${ displaystyle { begin {align} g (l ^ {k}, z, r ^ {k}): = { hat {X}} _ {Bayes} left (( Pi Pi ^ { top }) ^ {- 1} Pi mu left (z ^ {n}, l ^ {k}, r ^ {k} right) odot pi _ {z} right) ,. End {выровнено}}}$

Путем кеширования обратного или псевдообратного ${ displaystyle Pi ^ {- top}}$ , а значения ${ displaystyle lambda _ { hat {x}} odot pi _ {z}}$ для соответствующих пар ${ displaystyle ({ hat {x}}, z) in { mathcal {X}} times { mathcal {Z}}}$ , этот шаг требует ${ displaystyle O (N_ {k, n})}$ операции и ${ displaystyle O (N_ {k, n})}$ место хранения.

Шаг 3. Оценка каждого символа по байесовской реакции на его контекст

Третий и последний шаг схемы DUDE - сканирование ${ Displaystyle г ^ {п}}$ снова и вычислить фактическую шумоподавленную последовательность ${ displaystyle { hat {X}} ^ {n} (z ^ {n}) = left ({ hat {X}} _ {1} (z ^ {n}), ldots, { hat {X}} _ {n} (z ^ {n}) right)}$ . Обозначенный символ, выбранный для замены ${ displaystyle z_ {i}}$ - это байесовский ответ на двусторонний контекст символа, а именно

 ${ Displaystyle { begin {align} { hat {X}} _ {i} (z ^ {n}): = g left (l ^ {k} (z ^ {n}, i) ,, , z_ {i} ,, , r ^ {k} (z ^ {n}, i) right) ,. end {align}}}$

Этот шаг требует ${ Displaystyle О (п)}$ операций и использовали структуру данных, построенную на предыдущем шаге.

Таким образом, весь DUDE требует ${ Displaystyle О (п)}$ операции и ${ displaystyle O (N_ {k, n})}$ место хранения.

Свойства асимптотической оптимальности

DUDE разработан так, чтобы быть универсально оптимальным, а именно оптимальным (в некотором смысле при некоторых предположениях) независимо от исходной последовательности. ${ Displaystyle х ^ {п}}$ .

Позволять ${ displaystyle { hat {X}} _ {DUDE} ^ {n}: { mathcal {Z}} ^ {n} to { mathcal {X}} ^ {n}}$ обозначают последовательность схем DUDE, как описано выше, где ${ displaystyle { hat {X}} _ {ЧУВК} ^ {n}}$ использует длину контекста ${ displaystyle k_ {n}}$ это подразумевается в обозначениях. Нам нужно только это ${ Displaystyle lim _ {п к infty} k_ {n} = infty}$ и это ${ displaystyle k_ {n} | { mathcal {Z}} | ^ {2K_ {n}} = o left ({ frac {n} { log n}} right)}$ .

Для стационарного источника

Обозначим через ${ displaystyle { mathcal {D}} _ {n}}$ набор всех ${ displaystyle n}$ -блочные шумоподавители, а именно все карты ${ displaystyle { hat {X}} ^ {n}: { mathcal {Z}} ^ {n} to { mathcal {X}} ^ {n}}$ .

Позволять ${ displaystyle mathbf {X}}$ быть неизвестным стационарным источником и ${ displaystyle mathbf {Z}}$ - распределение соответствующей зашумленной последовательности. потом

 ${ displaystyle { begin {align} lim _ {n to infty} mathbf {E} left [L _ {{ hat {X}} _ {DUDE} ^ {n}} left (X ^ {n}, Z ^ {n} right) right] = lim _ {n to infty} min _ {{ hat {X}} ^ {n} in { mathcal {D}} _ {n}} mathbf {E} left [L _ {{ hat {X}} ^ {n}} left (X ^ {n}, Z ^ {n} right) right] ,, конец {выровнено}}}$

и существуют оба предела. Если, кроме того, источник ${ displaystyle mathbf {X}}$ эргодичен, то

 ${ displaystyle { begin {align} limsup _ {n to infty} L _ {{ hat {X}} _ {DUDE} ^ {n}} left (X ^ {n}, Z ^ {n } right) = lim _ {n to infty} min _ {{ hat {X}} ^ {n} in { mathcal {D}} _ {n}} mathbf {E} left [L _ {{ hat {X}} ^ {n}} left (X ^ {n}, Z ^ {n} right) right] ,, , { text {почти наверняка}} ,. end {выровнено}}}$

Для индивидуальной последовательности

Обозначим через ${ displaystyle { mathcal {D}} _ {n, k}}$ набор всех ${ displaystyle n}$ -блокировать ${ displaystyle k}$ шумоподавители скользящего окна -го порядка, а именно все карты ${ displaystyle { hat {X}} ^ {n}: { mathcal {Z}} to { mathcal {X}}}$ формы ${ displaystyle { hat {X}} _ {i} (z ^ {n}) = f left (z_ {i-k}, ldots, z_ {i + k} right)}$ с участием ${ displaystyle f: { mathcal {Z}} ^ {2k + 1} to { mathcal {X}}}$ произвольный.

Позволять ${ displaystyle mathbf {x} in { mathcal {X}} ^ { infty}}$ - неизвестный стационарный источник бесшумной последовательности и ${ displaystyle mathbf {Z}}$ - распределение соответствующей зашумленной последовательности. потом

 ${ displaystyle { begin {align} lim _ {n to infty} left [L _ {{ hat {X}} _ {DUDE} ^ {n}} left (x ^ {n}, Z ^ {n} right) - min _ {{ hat {X}} ^ {n} in { mathcal {D}} _ {n, k}} L _ {{ hat {X}} ^ { n}} left (x ^ {n}, Z ^ {n} right) right] = 0 ,, , { text {почти наверняка}} ,. end {выровнено}}}$

Неасимптотическая производительность

Позволять ${ displaystyle { hat {X}} _ {k} ^ {n}}$ обозначают DUDE с длиной контекста ${ displaystyle k}$ определено на ${ displaystyle n}$ -блоки. Тогда существуют явные константы ${ displaystyle A, C> 0}$ и ${ displaystyle B> 1}$ это зависит от ${ Displaystyle влево ( Пи, Лямбда вправо)}$ один, такой, что для любого ${ displaystyle n, k}$ и любой ${ displaystyle x ^ {n} in { mathcal {X}} ^ {n}}$ у нас есть

 ${ displaystyle { begin {align} { frac {A} { sqrt {n}}} B ^ {k} , leq mathbf {E} left [L _ {{ hat {X}} _ {k} ^ {n}} left (x ^ {n}, Z ^ {n} right) - min _ {{ hat {X}} ^ {n} in { mathcal {D}} _ {n, k}} L _ {{ hat {X}} ^ {n}} left (x ^ {n}, Z ^ {n} right) right] leq { sqrt {k}} { frac {C} { sqrt {n}}} | { mathcal {Z}} | ^ {k} ,, end {выровнено}}}$

где ${ Displaystyle Z ^ {п}}$ зашумленная последовательность, соответствующая ${ Displaystyle х ^ {п}}$ (случайность которого обусловлена только каналом)^[2].

Фактически выполняется с теми же константами ${ displaystyle A, B}$ как указано выше для любой ${ displaystyle n}$ -блочный шумоподавитель ${ displaystyle { hat {X}} ^ {n} in { mathcal {D}} ^ {n}}$ .^[1] Доказательство нижней границы требует, чтобы матрица канала ${ displaystyle Pi}$ быть квадратным и пара ${ Displaystyle влево ( Пи, Лямбда вправо)}$ удовлетворяет определенному техническому состоянию.

Фон

Чтобы мотивировать конкретное определение DUDE, используя байесовский ответ на конкретный вектор, мы теперь находим оптимальный шумоподавитель в неуниверсальном случае, когда неизвестная последовательность ${ Displaystyle х ^ {п}}$ является реализацией случайного вектора ${ displaystyle X ^ {n}}$ , распространение которого известно.

Рассмотрим сначала случай ${ Displaystyle п = 1}$ . Поскольку совместное распространение ${ displaystyle (X, Z)}$ известно, учитывая наблюдаемый зашумленный символ ${ displaystyle z}$ , неизвестный символ ${ displaystyle X in { mathcal {X}}}$ распространяется согласно известному распределению ${ Displaystyle mathbb {P} (Х = х | Z = Z)}$ . Заказывая элементы ${ displaystyle { mathcal {X}}}$ , мы можем описать это условное распределение на ${ displaystyle { mathcal {X}}}$ используя вектор вероятности ${ displaystyle mathbf {P} _ {X | z}}$ , проиндексировано ${ displaystyle { mathcal {X}}}$ , чей ${ displaystyle x}$ -вход ${ Displaystyle mathbb {P} влево (Х = х | Z = г вправо)}$ . Очевидно, что ожидаемые убытки при выборе предполагаемого символа ${ displaystyle { hat {x}}}$ является ${ Displaystyle лямбда _ { шляпа {х}} ^ { top} mathbf {P} _ {X | z}}$ .

Определить Конверт Байеса вектора вероятности ${ displaystyle mathbf {v}}$ , описывающее распределение вероятностей на ${ displaystyle { mathcal {X}}}$ , как минимальный ожидаемый убыток ${ Displaystyle U ( mathbf {v}) = min _ {{ hat {x}} in { mathcal {X}}} mathbf {v} ^ { top} lambda _ { hat { Икс}}}$ , а Байесовский ответ к ${ displaystyle mathbf {v}}$ как прогноз, который достигает этого минимума, ${ displaystyle { hat {X}} _ {Bayes} ( mathbf {v}) = { text {argmin}} _ {{ hat {x}} in { mathcal {X}}} mathbf {v} ^ { top} lambda _ { hat {x}}}$ . Заметьте, что байесовский ответ инвариантен к масштабу в том смысле, что ${ displaystyle { hat {X}} _ {Bayes} ( mathbf {v}) = { hat {X}} _ {Bayes} ( alpha mathbf {v})}$ для ${ displaystyle alpha> 0}$ .

По делу ${ Displaystyle п = 1}$ , то оптимальный шумоподавитель ${ displaystyle { hat {X}} (z) = { hat {X}} _ {Bayes} left ( mathbf {P} _ {X | z} right)}$ . Этот оптимальный шумоподавитель можно выразить с помощью маргинального распределения ${ displaystyle Z}$ в одиночку, следующим образом. Когда матрица каналов ${ displaystyle Pi}$ обратимо, имеем ${ Displaystyle mathbf {P} _ {X | z} propto Pi ^ {- top} P_ {Z} odot pi _ {z}}$ где ${ displaystyle pi _ {z}}$ это ${ displaystyle z}$ -й столбец ${ displaystyle Pi}$ . Отсюда следует, что оптимальный шумоподавитель эквивалентно задается формулой ${ displaystyle { hat {X}} (z) = { hat {X}} _ {Bayes} left ( Pi ^ {- top} mathbf {P} _ {Z} odot pi _ {z} right)}$ . Когда ${ Displaystyle | { mathcal {X}} | leq | { mathcal {Z}} |}$ и ${ displaystyle Pi}$ необратим, при разумном предположении, что он имеет полный ранг строки, мы можем заменить ${ displaystyle Pi ^ {- 1}}$ с его псевдообратной функцией Мура-Пенроуза и получаем

 ${ displaystyle { hat {X}} (z) = { hat {X}} _ {Bayes} left (( Pi Pi ^ { top}) ^ {- 1} Pi mathbf {P } _ {Z} odot pi _ {z} right) ,.}$

Переходя теперь к произвольному ${ displaystyle n}$ , оптимальный шумоподавитель ${ displaystyle { hat {X}} ^ {opt} (z ^ {n})}$ (с минимальными ожидаемыми потерями), таким образом, определяется байесовским ответом на ${ displaystyle mathbf {P} _ {X_ {i} | z ^ {n}}}$

 ${ displaystyle { begin {align} { hat {X}} _ {i} ^ {opt} (z ^ {n}) = { hat {X}} _ {Bayes} mathbf {P} _ { X_ {i} | z ^ {n}} = { text {argmin}} _ {{ hat {x}} in { mathcal {X}}} lambda _ { hat {x}} ^ { top} mathbf {P} _ {X_ {i} | z ^ {n}} ,, end {align}}}$

где ${ displaystyle mathbf {P} _ {X_ {i} | z ^ {n}}}$ вектор, индексированный ${ displaystyle { mathcal {X}}}$ , чей ${ displaystyle x}$ -вход ${ displaystyle mathbb {P} left (X_ {i} = x | Z ^ {n} = z ^ {n} right)}$ . Вектор условной вероятности ${ displaystyle mathbf {P} _ {X_ {i} | z ^ {n}}}$ сложно вычислить. Вывод, аналогичный случаю ${ Displaystyle п = 1}$ выше показывает, что оптимальный шумоподавитель допускает альтернативное представление, а именно ${ displaystyle { hat {X}} _ {i} ^ {opt} (z ^ {n}) = { hat {X}} _ {Bayes} left ( Pi ^ {- top} mathbf {P} _ {Z_ {i}, z ^ {n backslash i}} odot pi _ {z_ {i}} right)}$ , куда ${ displaystyle z ^ {n backslash i} = left (z_ {1}, ldots, z_ {i-1}, z_ {i + 1}, ldots, z_ {n} right) in { mathcal {Z}} ^ {n-1}}$ - заданный вектор и ${ displaystyle mathbf {P} _ {Z_ {i}, z ^ {n обратная косая черта i}}}$ вектор вероятности, индексированный ${ Displaystyle { mathcal {Z}}}$ чья ${ displaystyle z}$ -вход ${ Displaystyle mathbb {P} left ((Z_ {1}, ldots, Z_ {n}) = (z_ {1}, ldots, z_ {i-1}, z, z_ {я + 1} , ldots, z_ {n}) right) ,.}$ Опять таки, ${ displaystyle Pi ^ {- top}}$ заменяется псевдообратным, если ${ displaystyle Pi}$ не является квадратным или необратимым.

Когда распределение ${ displaystyle X}$ (и, следовательно, из ${ displaystyle Z}$ ) недоступен, DUDE заменяет неизвестный вектор ${ displaystyle mathbf {P} _ {Z_ {i}, z ^ {n обратная косая черта i}}}$ с эмпирической оценкой, полученной вдоль зашумленной последовательности ${ Displaystyle г ^ {п}}$ сам, а именно с ${ displaystyle mu left (Z_ {i}, l ^ {k} (Z ^ {n}, i), r ^ {k} (Z ^ {n}, i) right)}$ . Это приводит к приведенному выше определению DUDE.

Хотя аргументы сходимости, лежащие в основе приведенных выше свойств оптимальности, более тонкие, отметим, что приведенное выше в сочетании сЭргодическая теорема Биркгофа., достаточно, чтобы доказать, что для стационарного эргодического источника DUDE с контекстной длиной ${ displaystyle k}$ асимптотически оптимально все ${ displaystyle k}$ шумоподавители с раздвижными окнами.

Расширения

Базовый DUDE, описанный здесь, предполагает сигнал с одномерным набором индексов по конечному алфавиту, известному каналу без памяти и заранее фиксированной длине контекста. Рассмотрены ослабления каждого из этих предположений по очереди.^[3] В частности:

Бесконечные алфавиты^[4]^[5]^[6]^[7]
Каналы с памятью^[8]^[9]
Матрица неизвестного канала^[10]^[11]
Переменный контекст и адаптивный выбор длины контекста^[12]^[13]^[14]^[15]
Двумерные сигналы^[16]

Приложения

Применение к шумоподавлению изображений

Фреймворк для градаций серого на основе DUDE шумоподавление изображения^[6] обеспечивает современное шумоподавление для шумовых каналов импульсного типа (например, «соль и перец» или «M-симметричный» шум) и хорошие характеристики на гауссовском канале (сравнимые с Неместные средства схема шумоподавления изображения на этом канале). Другой вариант DUDE, применимый к изображениям в градациях серого, представлен в.^[7]

Приложение для канального декодирования несжатых источников

DUDE привел к универсальным алгоритмам канального декодирования несжатых источников.^[17]