Лінійне та квадратичне програмування для відновлення розрідженого сигналу
Анастасія О. Стороженко ${}^{1,\,2}$, Петро І. Стецюк ${}^{2}$
${}^1$ Київський академічний університет, Україна
${}^2$ Інститут кібернетики імені В.М. Глушкова НАН України, Київ, Україна
Отримано 9 квiтня 2026, у фiнальнiй формi 1 червня 2026, опубліковано 13 липня 2026.
Анотація
У роботі розглядається задача відновлення розрідженого сигналу за допомогою $\ell_1$-мінімізації.
Показано, як задачу $\ell_1$-мінімізації (також відому як basis pursuit) можна перетворити на еквівалентну задачу лінійного програмування (ЛП), та наведено доведення еквівалентності цих двох задач.
Проведено експериментальне порівняння сучасних розв'язувачів (Gurobi, HiGHS, CPLEX та Clarabel) для розв'язання ЛП-задачі на тестових даних, згенерованих відповідно до теоретичних гарантій відновлення для матриць з нормально розподіленими елементами. Результати показують, що відкритий розв'язувач Clarabel є конкурентоспроможною альтернативою пропрієтарним розв'язувачам за швидкодією.
Також запропоновано метод перевірки єдиності отриманого розв'язку за допомогою допоміжної задачі квадратичного програмування зі строго опуклою цільовою функцією.
Наведено геометричну інтерпретацію умов єдиності та продемонстровано застосування методу на прикладі матриці з цілочисельними елементами.
Ключові слова: розріджений сигнал; відновлення сигналу; лінійне програмування; квадратичне програмування.
[ pdf ] (447 kb)
[ tex ] (38 kb)
