Про стиснення зображень SVD
Сингулярний розклад (SVD) розкладає будь-яку матрицю M на M = UΣVᵀ, де U і V — ортогональні матриці, а Σ — діагональна матриця невід'ємних сингулярних значень σ₁ ≥ σ₂ ≥ … ≥ 0. Застосований до зображення (розглянутого як матриця значень пікселів), SVD дозволяє думати про сингулярні значення як про міру «важливості» кожного шару структури: перші кілька захоплюють загальні форми і контраст, тоді як пізніші кодують дрібні деталі та шум. Теорема Еккарта-Янга (1936) гарантує, що наближення рангу k, побудоване за k найбільшими сингулярними значеннями, є оптимальним у сенсі мінімізації норми Фробеніуса похибки.
Ця симуляція розкладає тестове зображення 64×64 на до 64 сингулярних компонентів. Перетягніть повзунок рангу, щоб додавати або видаляти компоненти, і спостерігайте, як змінюється якість реконструкції в реальному часі. Гістограма під зображеннями показує спектр сингулярних значень — компоненти ліворуч від лінії відсікання включені, праворуч — відкинуті.
Часті запитання
Що насправді обчислює SVD?
SVD розкладає матрицю M на M = UΣVᵀ. Стовпці U — ліві сингулярні вектори (вихідні напрямки), стовпці V — праві сингулярні вектори (вхідні напрямки), а діагональні елементи Σ — сингулярні значення, тобто коефіцієнти масштабування. Кожна матриця має SVD; на відміну від власного розкладу, він працює для неквадратних і несиметричних матриць.
Чому більший ранг дає краще зображення?
Кожна сингулярна трійка (σᵢ, uᵢ, vᵢ) додає один шар рангу 1 — σᵢ·uᵢ·vᵢᵀ — до реконструкції. Більші сингулярні значення вносять більше енергії (структури) в зображення. Зі збільшенням рангу k захоплюється більше повної енергії Фробеніуса ∑σᵢ², а похибка апроксимації ‖M − Mₖ‖² = σₖ₊₁² + … + σᵣ² зменшується.
Що таке коефіцієнт стиснення і як він розраховується?
Зберігання SVD рангу k для зображення m×n потребує k·(m + n + 1) чисел замість m·n. Коефіцієнт стиснення: k(m+n+1)/(mn). Для зображення 64×64 при k=8 це 8×129/4096 ≈ 0,25, тобто зберігається лише чверть оригінальних даних. Компроміс — якість: при дуже малих рангах втрачаються дрібні деталі.
Що таке теорема Еккарта-Янга?
Теорема Еккарта-Янга-Мірського (1936) стверджує, що наближення рангу k через SVD є найближчою матрицею рангу k до M як у нормі Фробеніуса, так і в спектральній нормі. Жодна інша матриця рангу k не може бути ближчою. Це робить SVD математично оптимальною стратегією втратного стиснення для матриць.
Як сингулярні значення пов'язані з власними значеннями?
Сингулярні значення матриці M — це квадратні корені з власних значень матриці MᵀM (або MMᵀ). Якщо M є симетричною позитивно напіввизначеною, її сингулярні значення збігаються з власними. Для загальної матриці власні значення можуть бути комплексними, тоді як сингулярні значення завжди дійсні і невід'ємні. Найбільше сингулярне значення дорівнює спектральній нормі матриці.
Чому зображення з шумом погано стискається?
Випадковий шум має всі сингулярні значення приблизно рівними — енергія рівномірно розподілена по всіх компонентах, а не сконцентрована в перших кількох. Структури низького рангу, яку можна б використати, немає. Натуральні зображення, навпаки, мають стрімко спадаючий спектр сингулярних значень, оскільки сусідні пікселі корельовані. Саме тому JPEG і подібні кодеки досягають великого стиснення для фотографій.
Які реальні застосування має SVD поза стисненням зображень?
SVD є всюдисущим: він лежить в основі PCA у науці про дані, латентного семантичного аналізу в обробці природної мови, колаборативної фільтрації у рекомендаційних системах (Netflix Prize), обчислення псевдооберненої матриці в чисельній лінійній алгебрі, а також зниження порядку моделей у теорії керування. У машинному навчанні вагові матриці нейронних мереж іноді апроксимуються матрицями низького рангу через SVD для прискорення інференсу.
У чому різниця між SVD і власним розкладом?
Власний розклад A = PDP⁻¹ вимагає, щоб A була квадратною і діагоналізованою. SVD M = UΣVᵀ працює для будь-якої матриці (включно з неквадратними), використовує два різних ортогональних базиси і завжди існує. Для симетричних позитивно напіввизначених матриць обидва розклади збігаються: U = V = матриця власних векторів, Σ = матриця власних значень.
Скільки сингулярних значень має матриця зображення m×n?
Матриця m×n має r = min(m, n) ненульових сингулярних значень, де r — її ранг. Зображення 64×64 має щонайбільше 64 сингулярних значення. На практиці натуральні зображення мають ефективний числовий ранг значно менший за 64, оскільки сингулярні значення швидко спадають до нуля — перші ~10–20 компонентів захоплюють 95%+ загальної дисперсії.
Що означає похибка Фробеніуса у панелі статистики?
Норма Фробеніуса ‖A‖_F = √(∑ᵢⱼ aᵢⱼ²) вимірює загальний «розмір» матриці як корінь із суми квадратів усіх елементів. Похибка Фробеніуса — це ‖M − Mₖ‖_F = √(σₖ₊₁² + … + σᵣ²), тобто корінь із енергії відкинутих сингулярних значень. За теоремою Еккарта-Янга жодне наближення рангу k не може мати меншу похибку Фробеніуса.