Визуализация сжатия матрицы с помощью усечённого SVD

🤓 Теорема Эккарта - Янга - Мирского говорит, что для любой матрицы A её лучшим* приближением заданного наперёд ранга r является усечённое сингулярное разложение ранга r. То есть такая аппроксимация Aᵣ , которая получена путём суммирования r матриц ранга 1.

Aᵣ = ∑ σᵢ uᵢ vᵢᵀ

здесь σᵢ - сингулярные числа (важно, чтобы они были отсортированы по убыванию), а uᵢ vᵢ - левые и правые сингулярные вектора. Для анимации выше можно один раз посчитать SVD (A = U Σ Vᵀ) и после этого дергать соответствующие значения.

🗜️Почему это сжатие?
Потому что для того, чтобы нарисовать картинку выше для каждого ранга r нужно r строчек и r столбцов матрицы + r сингулярных чисел. То есть если раньше было, допустим 1920×1080 пикселей, то вместо 2 073 600 значений для ранга 50 надо хранить 150 050 то есть около 7% от исходной матрицы.

📝Обычно в таких демо показывают всегда черно-белые картинки, потому что это матрицы. Существует несколько способов сделать это с цветными изображениями. Напишите в комментариях как вы думаете какой из них в видосе выше?
📝Обратите внимание как быстро появляются геометрически простые формы (большие надписи, например) по сравнению с другими объектами. Маленькие надписи распознаются существенно даже медленее, чем лицо даже что напоминает как нейросети пытаются рисовать надписи - в некотором смысле это информация "высокого ранга".
📝Некоторые картинки в видосе выше сгенерированы, было интересно посмотреть есть ли какая-нибудь очевидная разница в спектрах между реальными изображениями и сгенерированными.

* по норме Фробениуса, спектральной норме и произвольной унитарно-инвариантной норме.