Алгоритмы передачи сообщений на основе проверки при сжатом распознавании

передачи сообщений на основе проверки Алгоритмы ( VB-MPA ) при сжатом зондировании ( CS ), отрасли цифровой обработки сигналов , которая занимается измерением разреженных сигналов , представляют собой некоторые методы эффективного решения проблемы восстановления при сжатом зондировании. Одной из основных целей сжатого зондирования является процесс восстановления. Вообще говоря, процесс восстановления при сжатом зондировании — это метод, с помощью которого исходный сигнал оценивается с использованием знаний о сжатом сигнале и матрице измерений. ^{[ 1 ]} С математической точки зрения процесс восстановления в сжатом зондировании заключается в поиске самого разреженного возможного решения недоопределенной системы линейных уравнений . В зависимости от характера матрицы измерений можно использовать различные методы реконструкции. Если матрица измерений также разрежена, одним из эффективных способов является использование алгоритмов передачи сообщений для восстановления сигнала. Хотя существуют подходы передачи сообщений, работающие с плотными матрицами, природа этих алгоритмов в некоторой степени отличается от алгоритмов, работающих с разреженными матрицами. ^{[ 1 ]}^{[ 2 ]}

Обзор

Основная проблема в процессе восстановления в CS состоит в том, чтобы найти как можно более разреженное решение следующей недоопределенной системы линейных уравнений: $Ax=y$ где $A$ – матрица измерений, $x$ исходный сигнал, который необходимо восстановить, и $y$ — сжимает известный сигнал. Когда матрица $A$ разрежена, эту матрицу можно представить в виде двудольного графа $G=(V_{l}\cup V_{r},E)$ для лучшего понимания. ^{[ 2 ]}^{[ 3 ]}^{[ 4 ]}^{[ 5 ]} $V_{l}$ это набор переменных узлов в $G$ который представляет собой набор элементов $x$ а также $V_{r}$ – набор проверочных узлов, соответствующий множеству элементов $y$ . Кроме того, есть преимущество $e=(u,v)$ между $u\in V_{l}$ и $v\in V_{r}$ если соответствующие элементы в $A$ не равно нулю, т.е. $A_{v,u}\neq 0$ . Кроме того, вес края $w(e)=A_{v,u}$ . ^{[ 6 ]} Вот пример двоичной разреженной матрицы измерений, где веса ребер равны нулю или единице.

$A=\left[{\begin{array}{c c c c c c c c c c c c}0&0&1&0&0&0&0&0&1&0&1&0\\0&0&0&1&0&1&0&1&0&0&0&0\\1&0&0&0&0&1&0&0&0&0&1&0\\1&1&1&0&0&0&0&0&0&0&0&0\\0&0&0&1&0&0&1&0&0&0&0&1\\0&0&0&0&1&0&1&0&0&0&0&1\\0&0&0&0&0&0&0&1&1&1&0&0\\0&1&0&0&1&0&0&0&0&1&0&0\end{array}}\right]$

Основная идея алгоритмов передачи сообщений в CS заключается в итеративной передаче соответствующих сообщений между узлами переменных и узлами проверки для эффективного поиска сигнала. $x$ . Эти сообщения различны для узлов переменных и узлов проверки. Однако основная природа сообщений для всех узлов переменных и проверочных узлов одинакова во всех алгоритмах передачи сообщений, основанных на проверке. ^{[ 6 ]} Сообщения $\mu ^{v}(v_{i}):~V_{l}\mapsto \mathbb {R} \times \{0,1\}$ исходящий из узла переменной $v_{i}$ содержит значение проверочного узла и индикатор, показывающий, проверен ли узел переменной или нет. Более того, сообщения $\mu ^{c}(c_{i}):~V_{r}\mapsto \mathbb {R} \times \mathbb {Z} ^{+}$ исходящий из контрольного узла $c_{i}$ содержит значение проверочного узла и оставшуюся степень проверочного узла в графе. ^{[ 6 ]}^{[ 7 ]}

На каждой итерации каждый узел переменной и узел проверки создают новое сообщение для передачи всем своим соседям на основе сообщений, полученных ими от своих соседей. Это локальное свойство алгоритмов передачи сообщений позволяет реализовать их как алгоритмы параллельной обработки и делает временную сложность этих алгоритмов настолько эффективной. ^{[ 8 ]}

Правила передачи сообщений ^{[ 9 ]}

Общим правилом для всех алгоритмов передачи сообщений, основанных на проверке, является тот факт, что как только узел переменной становится проверенным, этот узел переменной может быть удален из графа, и алгоритм может быть выполнен для решения остальной части графа. Алгоритмы передачи сообщений разных баз проверки используют разные комбинации правил проверки. ^{[ 6 ]}

Правила проверки следующие:

Узел нулевой проверки (ZCN): ^{[ 8 ]} Если в окрестности переменного узла есть хотя бы один контрольный узел с нулевым значением, то этот переменный узел должен быть проверен с нулевым значением.
Контрольный узел степени 1: (D1CN): ^{[ 8 ]} Если в окрестностях узла переменной имеется один или несколько проверочных узлов степени 1, то узел переменной следует проверять со значением, выбранным случайным образом из значений этих проверочных узлов степени 1.
Узел проверки равенства: (ECN): ^{[ 8 ]} Если существует один узел переменной, соединенный по крайней мере с двумя или более проверочными узлами с одинаковым ненулевым значением, то значение узла переменной должно быть проверено с общим значением этих проверочных узлов. Кроме того, все остальные узлы переменных, частично связанные с этими проверочными узлами (не все), должны быть проверены нулевым значением.

Приведенные выше правила передачи сообщений являются основными и единственными правилами, которые следует использовать в любом алгоритме передачи сообщений, основанном на проверке. Показано, что эти простые правила позволяют эффективно восстановить исходный сигнал при выполнении определенных условий. ^{[ 8 ]}^{[ 6 ]}

Алгоритмы

Существует четыре алгоритма, известные как VB-MPA, а именно Genie, LM, XH и SBB. ^{[ 6 ]} Все эти алгоритмы используют одну и ту же стратегию восстановления исходного сигнала; однако они используют другую комбинацию правил передачи сообщений для проверки узлов переменных.

Джинн Алгоритм ^{[ 6 ]}

Алгоритм Genie является эталоном в этой теме. Во-первых, предполагается, что алгоритм Genie знает опорный набор сигнала, то есть набор ненулевых элементов исходного сигнала. Используя эти знания, Genie не должен заботиться о нулевых переменных узлах в графе, и единственной задачей алгоритма Genie является восстановление значений ненулевых элементов исходного сигнала. Хотя у Genie нет никакого практического аспекта, его можно рассматривать как эталон проблемы, особенно в том смысле, что этот алгоритм превосходит другие алгоритмы в этой категории, и можно измерить, насколько успешен один алгоритм, сравнивая его с алгоритмом Genie.

Поскольку Genie хочет найти только значение ненулевых элементов сигнала, нет необходимости использовать правила, которые отвечают за узел переменной с нулевым значением в этом алгоритме. Поэтому Genie использует в качестве правила проверки только D1CN.

алгоритм LM ^{[ 6 ]}^{[ 8 ]}

Этот алгоритм, в отличие от алгоритма Genie, не имеет никаких знаний о поддерживаемом наборе сигналов и использует D1CN и ZCN вместе для решения процесса восстановления в CS. Фактически, ZCN — это правило, которое пытается проверить узлы переменных с нулевым значением, а D1CN отвечает за узлы переменных с ненулевым значением. Такое использование этого алгоритма происходит тогда, когда нет недвоичной матрицы. В таких случаях применение третьего правила нарушало локальность алгоритмов. Этот вопрос будет учтен в алгоритме SBB. ^{[ 6 ]}

Алгоритм XH ^{[ 6 ]}

Этот алгоритм аналогичен LM, но для проверки ненулевых переменных узлов он использует только ECN вместо D1CN. Если ненулевые элементы матрицы измерений являются двоичными , то этот алгоритм не может быть эффективно реализован и локальность алгоритма будет нарушена.

Алгоритм SBB ^{[ 6 ]}^{[ 9 ]}

Самым мощным практическим алгоритмом среди всех алгоритмов передачи проверочных сообщений является алгоритм SBB, который использует все правила проверки для восстановления исходного сигнала. В этом алгоритме D1CN и ECN отвечают за проверку ненулевых элементов сигнала, а ZCN и ECN проверяют узлы нулевых переменных.

Псевдокод . VB-MPA выглядит следующим образом В следующем алгоритме $\mu _{i}$ представляет собой $i^{th}$ компонент сообщений, исходящих от переменных и проверочных узлов. $VN$ на самом деле это переменная, в которой хранятся метки проверенных узлов переменных. $VN'$ также используется для хранения набора проверенных узлов переменных на предыдущей итерации. Используя эти две переменные, можно увидеть, есть ли какой-либо прогресс в количестве проверенных узлов переменных в алгоритме, а если прогресса нет, алгоритм завершится. ^{[ 6 ]}^{[ 9 ]}

1  function VB_MPA(Measurement Matrix A, Compressed Vector y):^[7]
2       $\mu ^{c}(c):=(y(c),d_{c})~~\forall c\in V_{r}$            // Initializations
3       $\mu ^{v}(v):=(0,0)~~\forall v\in V_{l}$                 // Initializations
4       $VN:=\emptyset$                                      // Initializations
5       $VN':=\{-1\}$                                        // Initializations
6      While ( $VN'\neq VN$ )               // Main Loop
7           $VN':=VN$ 
9          /*============================= Half round 1 of round 1 ============================ */    
10         for every  $c\in V_{r}$ 
11              $value:=y(c)-\sum _{v\in {\mathcal {N}}(c)}{\mu _{2}^{v}(v)\mu _{1}^{v}(v)A(c,v)}$ 
12              $degree:=d_{c}-\sum _{v\in {\mathcal {N}}(c)}{\mu _{2}^{v}(v)}$ 
13              $\mu ^{c}(c):=(value,degree)$ 
14         end for
15         /*============================= Half round 2 of round 1 ============================ */
16         for every  $v\in V_{r}\setminus VN$ 
17             update_rule(v,Algorithm)
18             If a variable node v is verified then
19                 add v to VN
20             end if
21         end for
22         /*============================= Half round 1 of round 2 ============================ */
23         for every  $c\in V_{r}$ 
24              $value:=y(c)-\sum _{v\in {\mathcal {N}}(c)}{\mu _{2}^{v}(v)\mu _{1}^{v}(v)A(c,v)}$ 
25              $degree:=d_{c}-\sum _{v\in {\mathcal {N}}(c)}{\mu _{2}^{v}(v)}$ 
26              $\mu ^{c}(c):=(value,degree)$ 
27         end for
28         /*============================= Half round 2 of round 2 ============================ */
29         for every  $v\in V_{l}\setminus VN$ 
30             if  $\exists c\in {\mathcal {N}}(v):~\mu _{1}^{c}(c)=0$  then
31                  $\mu ^{v}(v):=(0,1)$ 
32                 add v to VN
33             end if
34         end for
35     end while 
36     return  $\mu _{1}^{v}(v)~~\forall v\in V_{l}$

Во всех алгоритмах сообщения, исходящие от проверочных узлов, одинаковы; однако, поскольку правила проверки различны для разных алгоритмов, сообщения, создаваемые узлами переменных, будут разными в каждом алгоритме. ^{[ 6 ]} Приведенный выше алгоритм работает для всех VB-MPA, и разные алгоритмы используют разные правила в полураунде 2 раунда 1 и 2. Например, алгоритм Genie использует правило D1CN в полураунде 2 раунда 1, и фактически половина раунда раунд 2 из раунда 2, в котором используется правило ZCN, бесполезен в алгоритме Genie. Алгоритм LM использует D1CN во второй половине раунда 2 раунда 1, а алгоритм XH использует правило ECN на этом этапе вместо D1CN. Алгоритм SBB также использует правила D1CN и ECN во второй половине раунда 1. Все эти правила могут быть эффективно реализованы в функции update_rule во второй половине раунда 1.

Доказательство правильности

Хотя нет никакой гарантии, что эти алгоритмы будут успешными во всех случаях, мы можем гарантировать, что если некоторые из узлов переменных будут проверены в ходе этих алгоритмов, то значения этих узлов переменных почти наверняка будут правильными . Для того, чтобы это доказать, достаточно показать, что все правила проверки работают идеально и без ложной проверки . ^{[ 6 ]}^{[ 8 ]}

Корректность ZCN

Алгебраическая точка зрения правила ZCN заключается в том, что если в системе линейных уравнений правая часть уравнения равна нулю, то почти наверняка все неизвестные в этих уравнениях равны нулю. Это связано с тем, что исходный сигнал предполагается разреженным, кроме того, у нас также должно быть предположение, что ненулевые элементы сигналов выбираются из непрерывного распределения . Предположим, что существуют $d$ переменные в этом уравнении, если некоторые из них в $d-1$ элементы ненулевые, то остальные $d^{th}$ значение узла переменной должно иметь в точности отрицательное значение суммы этих $d-1$ переменные узлы. Если ненулевые элементы исходного сигнала выбраны из непрерывного распределения , то вероятность этого равна нулю. Следовательно, правило ZCN работает отлично. ^{[ 6 ]}^{[ 8 ]}

Корректность D1CN

D1CN говорит, что если переменный узел является единственной неизвестной переменной в уравнении, то значение этой переменной равно правой части этого уравнения . Фактически уравнение всего с одной неизвестной переменной представляет собой проверочный узел степени один, т.е. проверочный узел, в окрестности которого находится только один узел непроверенной переменной. ^{[ 6 ]}^{[ 8 ]}

Корректность ECN

Это правило состоит из двух частей: первая часть касается ненулевых элементов сигнала, а вторая отвечает за нулевые элементы исходного сигнала. В первой части говорится, что если у нас есть два или более уравнений с одинаковой правой частью и если у нас есть только одна неизвестная переменная $v$ является общим во всех этих уравнениях, то значение этой общей переменной должно быть значением правой части этих уравнений. Кроме того, там говорится, что все остальные переменные в этих уравнениях должны быть равны нулю. Предположим, что одна из этих переменных $v'$ не равно нулю, то правая часть уравнения, которое содержит оба $v,v'$ должно быть $x(v')+x(v)$ (Для простоты предположим, что все веса ребер равны 1 или нулю). Кроме того, поскольку мы знаем, что $v$ является единственной уникальной переменной во всех этих уравнениях, то должно быть одно уравнение $c$ в котором $v$ существует и $v'$ не существует. С другой стороны, мы знаем, что правые части этих уравнений одинаковы; следовательно, правая часть уравнения $c$ также должно быть $x(v)+x(v')$ . Если мы удалим $v'$ из этого уравнения мы должны получить сумму некоторых неизвестных переменных, которая будет иметь ненулевое значение. $x(v')$ . Поскольку ненулевые элементы $x$ выбираются случайным образом из непрерывного распределения, вероятность того, что эта сумма в точности равна $x(v')$ равен нулю. Поэтому почти наверняка значение $v$ равно нулю, а все остальные переменные в этих уравнениях имеют нулевое значение. ^{[ 6 ]}^{[ 8 ]}^{[ 7 ]}

Для второй части правила ECN остался только один сценарий, поскольку большая его часть была рассмотрена в первой части. В этом сценарии у нас есть несколько уравнений с одинаковой правой частью , но во всех этих уравнениях есть два или более переменных узла. В этом случае мы ничего не можем сказать об этих общих узлах переменных; однако мы можем сказать, что все остальные узлы переменных в этих уравнениях равны нулю. Доказательство этого утверждения может быть достигнуто путем замены переменной в этих уравнениях. Предположим, что $v_{1},v_{2},...,v_{q}$ являются общими переменными узлами в этих уравнениях. Если мы установим $v'=v_{1}+v_{2}+...+v_{q}$ тогда проблема будет изменена на первую часть, где у нас есть только один узел общей переменной во всех этих уравнениях. Следовательно, используя те же рассуждения, что и в первой части, мы видим, что все остальные узлы переменных, которые не являются общими во всех этих уравнениях, почти наверняка могут быть проверены с нулевым значением . ^{[ 6 ]}^{[ 8 ]}^{[ 7 ]}

Когда ненулевые элементы матрицы измерений выбираются случайным образом из непрерывного распределения , можно показать, что если один узел переменной получает равные сообщения, разделенные на веса ребер от его соседей, то этот узел переменной является единственной уникальной переменной, связанной с все эти проверочные узлы, следовательно, правило может применяться с использованием подхода локального принятия решения, и узел переменной может проверять себя без дополнительных знаний о других соединениях этих проверочных узлов. Более того, вторую часть правила ECN не обязательно реализовывать, поскольку ненулевой проверенный узел переменной в правиле ECN будет удален из двудольного графа на следующей итерации , а правила ZCN будет достаточно для проверки всех нулевых значений. из этих уравнений остались переменные узлы с той же правой частью . В целом, когда ненулевые элементы матрицы измерений выбираются из непрерывного распределения , алгоритмы SBB и XH, использующие правило ECN, могут быть реализованы эффективно. ^{[ 6 ]}

Анализ времени выполнения

Каждый второстепенный цикл в основном цикле алгоритма может выполняться на параллельных процессорах , если рассматривать каждую переменную и проверочный узел как отдельный процессор. Следовательно, каждый второстепенный цикл алгоритма может выполняться за постоянное время. $O(1)$ . Более того, поскольку алгоритм завершится, когда не будет прогресса в проверке узлов переменных, то если в худшем случае на каждой итерации основного цикла проверяемому будет только один узел переменных, то максимальное количество раз, которое основной цикл будет выполнен $|V_{l}|$ . Поэтому весь алгоритм будет выполняться в $O(|V_{l}|)$ время . ^{[ 7 ]}

Ссылки

^ Jump up to: ^а ^б Д.Л. Донохо, А. Джаванмард и А. Монтанари, «Оптимальное с точки зрения теории информации сжатое зондирование посредством пространственной связи и приблизительной передачи сообщений», в Information Theory Proceedings (ISIT), Международный симпозиум IEEE, 2012 г., 2012 г., стр. 1231–1235.
^ Jump up to: ^а ^б Чандар, Венкат, Деваврат Шах и Грегори В. Уорнелл. «Простой алгоритм передачи сообщений для сжатого восприятия». Труды по теории информации (ISIT), Международный симпозиум IEEE 2010 г. ИИЭР, 2010.
^ Индик, Петр . «Явные конструкции для сжатого восприятия разреженных сигналов». Материалы девятнадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам. Общество промышленной и прикладной математики, 2008.
^ Гилберт, Анна С. и др. «Один эскиз для всех: быстрые алгоритмы для измерения сжатых данных». Материалы тридцать девятого ежегодного симпозиума ACM по теории вычислений. АКМ, 2007.
^ Сарвотам, Шрирам, Дрор Барон и Ричард Г. Баранюк. «Судокоды – быстрое измерение и реконструкция разреженных сигналов». Теория информации, Международный симпозиум IEEE 2006 г. ИИЭР, 2006.
^ Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж ^к ^л ^м ^н ^тот ^п ^д ^р ^с Ю. Эфтехари, А. Хейдарзаде, А. Х. Банихашеми и И. Ламбадарис, «Анализ эволюции плотности узловых алгоритмов проверки на основе сжатого зондирования», Теория информации, IEEE Transactions on, vol. 58, нет. 10, стр. 6616–6645, 2012.
^ Jump up to: ^а ^б ^с ^д ^и ^ж ^г Фархандуст, Сейед Мохаммад Эбриам. «Алгоритмы передачи сообщений» (PDF) .
^ Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж ^к Ф. Чжан и Х.Д. Пфистер, «Об итеративном декодировании высокоскоростных кодов LDPC с приложениями в области сжатия данных», препринт arXiv arXiv:0903.2232 , 2009.
^ Jump up to: ^а ^б ^с Луби, Майкл Г. и Майкл Митценмахер. «Декодирование на основе проверки для пакетных кодов проверки четности с низкой плотностью». Транзакции IEEE по теории информации 51.1 (2005): 120–127.

[donoho2012information-1] Jump up to: ^а ^б Д.Л. Донохо, А. Джаванмард и А. Монтанари, «Оптимальное с точки зрения теории информации сжатое зондирование посредством пространственной связи и приблизительной передачи сообщений», в Information Theory Proceedings (ISIT), Международный симпозиум IEEE, 2012 г., 2012 г., стр. 1231–1235.

[Chandar2010simple-2] Jump up to: ^а ^б Чандар, Венкат, Деваврат Шах и Грегори В. Уорнелл. «Простой алгоритм передачи сообщений для сжатого восприятия». Труды по теории информации (ISIT), Международный симпозиум IEEE 2010 г. ИИЭР, 2010.

[3] Индик, Петр . «Явные конструкции для сжатого восприятия разреженных сигналов». Материалы девятнадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам. Общество промышленной и прикладной математики, 2008.

[4] Гилберт, Анна С. и др. «Один эскиз для всех: быстрые алгоритмы для измерения сжатых данных». Материалы тридцать девятого ежегодного симпозиума ACM по теории вычислений. АКМ, 2007.

[Sarvotham2006Sudocodes-5] Сарвотам, Шрирам, Дрор Барон и Ричард Г. Баранюк. «Судокоды – быстрое измерение и реконструкция разреженных сигналов». Теория информации, Международный симпозиум IEEE 2006 г. ИИЭР, 2006.

[Eftekhari2012Density-6] Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж ^к ^л ^м ^н ^тот ^п ^д ^р ^с Ю. Эфтехари, А. Хейдарзаде, А. Х. Банихашеми и И. Ламбадарис, «Анализ эволюции плотности узловых алгоритмов проверки на основе сжатого зондирования», Теория информации, IEEE Transactions on, vol. 58, нет. 10, стр. 6616–6645, 2012.

[Farhangdoust-7] Jump up to: ^а ^б ^с ^д ^и ^ж ^г Фархандуст, Сейед Мохаммад Эбриам. «Алгоритмы передачи сообщений» (PDF) .

[Zhang2009Iterative-8] Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж ^к Ф. Чжан и Х.Д. Пфистер, «Об итеративном декодировании высокоскоростных кодов LDPC с приложениями в области сжатия данных», препринт arXiv arXiv:0903.2232 , 2009.

[Luby2005Verification-9] Jump up to: ^а ^б ^с Луби, Майкл Г. и Майкл Митценмахер. «Декодирование на основе проверки для пакетных кодов проверки четности с низкой плотностью». Транзакции IEEE по теории информации 51.1 (2005): 120–127.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]