Минимальное разложение W=VVᵀ для двух PSD-матриц

Задача источника

Для двух положительно полуопределённых матриц найдите W=VVᵀ с матрицей V минимального размера по числу столбцов.

Первая матрица

W₁=[[2,2],[2,2]]. Источник берёт

V₁=(√2,√2)ᵀ.

Действительно, V₁V₁ᵀ=[[2,2],[2,2]]. W₁ ненулевая и rank=1, поэтому меньше одного столбца невозможно.

Вторая матрица

W₂=[[4,0,4],[0,9,0],[4,0,4]]. Ключ предлагает

V₂=[[2,0],[0,3],[2,0]].

Outer products двух столбцов дают

(2,0,2)(2,0,2)ᵀ + (0,3,0)(0,3,0)ᵀ = W₂.

Почему два столбца минимальны

У W₂ есть два линейно независимых ненулевых направления: (1,0,1) и (0,1,0). Следовательно, rank(W₂)=2.

Для любой факторизации W=VVᵀ выполняется rank(W)=rank(V). Поэтому V должна иметь хотя бы rank(W) столбцов. Конструкция источника достигает этой нижней границы.

Связь со спектральным разложением

Вообще для PSD-матрицы W=QΛQᵀ можно взять V=Q_rΛ_r^{1/2}, оставив только положительные eigenvalues. Минимальное число столбцов равно rank(W).

Борис Демешев и участники · mlearn_pro, задача 135 · CC BY 4.0. Обе факторизации источника сохранены; минимальность доказана через rank.