Декодирование при помощи линейных программ: различия между версиями

Заметим, что <math>N_{\dot{y}}(\mathcal{P})</math> соответствует множеству векторов стоимости <math>\gamma</math>, таких, что <math>\dot{y}</math> является оптимальным решением (2). Множество <math>N_{\dot{y}}(\mathcal{C})</math> имеет аналогичную интерпретацию как множество векторов стоимости <math>\gamma</math>, для которых <math>\dot{y}</math> является кодовым словом при декодировании по принципу максимального правдоподобия (ML). Поскольку <math>\mathcal{P} \subset \mathcal{C}</math>, из определения следует, что <math>N_y(\mathcal{C}) \supset N_y(\mathcal{P})</math> для всех <math>y \in C</math>. На рис. 1 показаны эти два конуса и их взаимосвязь.

Вероятность успеха LP-декодера равна общей вероятностной мере <math>N_{\dot{y}}(\mathcal{P})</math> при распределении на векторах стоимости, определяемом каналом. Вероятность успеха ML-декодирования аналогичным образом связана с вероятностной мерой в нормальном конусе <math>N_y(\mathcal{C})</math>. Таким образом, расхождение между нормальными конусами <math>\mathcal{P}</math> и <math>\mathcal{C}</math> является мерой разрыва между точным ML- и расслабленным LP-декодированием.

Для доказательства успешности LP-декодирования необходимо показать, что <math>\dot{y}</math> является оптимальным решением линейной программы (2). Если код C линейный, а релаксация – правильная и C-симметричная, то можно предположить, что <math>\dot{y} = 0^n</math>, а затем показать, что <math>0^n</math> является оптимальным. Рассмотрим ''двойственную задачу'' LP-декодирования в (2). Если существует допустимая точка двойственной линейной программы, имеющая ту же (т. е. нулевую) стоимость, что и точка <math>0^n</math> прямой линейной программы, то <math>0^n</math> должна быть оптимальной точкой в задаче LP-декодирования. Поэтому, чтобы доказать успешность LP-декодера, достаточно показать точку с нулевой стоимостью двойственной задачи.

''(На самом деле, поскольку существование точки двойственной задачи с нулевой стоимостью доказывает только то, что <math>0^n</math> является одной из возможно многих оптимальных точек решения прямой задачи, необходимо проявить несколько большую осторожность; в данной статье рассмотрение этого вопроса не предусматривается).''