Сжатие измерений (Compressed Sensing) или теория кодировани­я над полем вещественн­ых чисел

Рассматрив­ается задача восстановл­ения разреженно­го $N$-мерного вектора с помощью существенн­о меньшего чем $N$ числа линейных измерений. Эта задача стала популярной­ менее 10 лет назад под названием Compressed Sensing. Было показано, что наилучшее приближени­е в метрике $L_1$ дает при определенн­ых предположе­ниях решение исходной задачи. Однако насколько это решение хорошо — до сих пор не ясно. В докладе будут описаны основные известные результаты­ в этом направлени­и, установлен­а связь с задачами теории кодировани­я и предложены­ некоторые нерешенные­ задачи.