ДЕКОМПОЗИЦІЯ СИНГУЛЯРНОГО ЗНАЧЕННЯ (SVD)

Розкладання матриці за сингулярним значенням (SVD) — це розкладання цієї матриці на три матриці. Він має деякі цікаві алгебраїчні властивості та передає важливі геометричні та теоретичні ідеї щодо лінійних перетворень. Він також має деякі важливі застосування в науці про дані. У цій статті я спробую пояснити математичну інтуїцію SVD та її геометричне значення.

Математика за СВД:

SVD mxn матриці A задається формулою A = USigma V^T

де:

В: mxm матриця ортонормованих власних векторів $AA^{T}$ .
IN ^Т : транспонувати a nxn матриця, що містить ортонормовані власні вектори .
: діагональна матриця з r елементів, що дорівнюють кореню додатних власних значень AAᵀ або Aᵀ A (обидві матриці все одно мають однакові додатні власні значення).

Приклади

Знайти SVD для матриці A =
Щоб обчислити SVD, спочатку нам потрібно обчислити сингулярні значення, знайшовши власні значення AA^{T}.

$A cdot A^{T} =egin{bmatrix} 3& 2 & 2 2& 3& -2 end{bmatrix} cdot egin{bmatrix} 3 & 2 2 & 3 2 & -2 end{bmatrix} = egin{bmatrix} 17 & 8 8 & 17 end{bmatrix}$

Характеристичне рівняння для наведеної вище матриці:

$W - lambda I =0 A A^{T} - lambda I =0$

$lambda^{2} - 34 lambda + 225 =0$

= (лямбда-25)(лямбда -9)

тому наші одиничні значення: sigma_1 = 5 , ; sigma_2 = 3

Тепер ми знаходимо правильні сингулярні вектори, тобто ортонормований набір власних векторів A ^Т A. Власні значення A ^Т А дорівнює 25, 9 і 0, а оскільки А ^Т A є симетричним, ми знаємо, що власні вектори будуть ортогональними.

для лямбда =25,

$A^{T}A - 25 cdot I = egin{bmatrix} -12 & 12& 2 12 & -12 & -2 2& -2 & -17 end{bmatrix}$

який можна скоротити рядком до:

egin{bmatrix} 1& -1& 0 0& 0& 1 0& 0& 0 end{bmatrix}

Одиничний вектор у напрямку до нього:

$v_1 = egin{bmatrix} frac{1}{sqrt{2}} frac{1}{sqrt{2}} 0 end{bmatrix}$

Аналогічно, для lambda = 9 власний вектор дорівнює:

$v_2 =egin{bmatrix} frac{1}{sqrt{18}} frac{-1}{sqrt{18}} frac{4}{sqrt{18}} end{bmatrix}$

Для третього власного вектора ми можемо використати властивість, що він перпендикулярний до v1 і v2 так, що:

$v_1^{T} v_3 =0 v_2^{T} v_3 =0$

Розв’язування наведеного вище рівняння для створення третього власного вектора

$v_3 = egin{bmatrix} a b c end{bmatrix} = egin{bmatrix} a -a -a/2 end{bmatrix} = egin{bmatrix} frac{ 2}{3} frac{-2}{3} frac{-1}{3} end{bmatrix}$

Тепер ми обчислюємо U за формулою u_i = frac{1}{sigma} A v_i, і це дає U = $egin{bmatrix} frac{1}{sqrt{2}} &frac{1}{sqrt{2}} frac{1}{sqrt{2}}& frac{-1 }{sqrt{2}} end{bmatrix}$ . Отже, наше остаточне рівняння SVD виглядає так:

$A = egin{bmatrix} frac{1}{sqrt{2}} &frac{1}{sqrt{2}} frac{1}{sqrt{2}}& frac{ -1}{sqrt{2}} end{bmatrix} egin{bmatrix} 5 & 0& 0 0 & 3& 0 end{bmatrix} egin{bmatrix} frac{1}{sqrt{2 }}& frac{1}{sqrt{2}} &0 frac{1}{sqrt{18}}& frac{-1}{sqrt{18}} & frac{4} {sqrt{18}} frac{2}{3}&frac{-2}{3} &frac{1}{3} end{bmatrix}$

Додатки

Розрахунок псевдоінверсії: Псевдообернена або обернена Мура-Пенроуза — це узагальнення оберненої матриці, яка може бути необоротною (наприклад, матриці низького рангу). Якщо матриця оборотна, то її обернена буде дорівнювати Псевдооберненій, але псевдообернена існує для матриці, яка не є оборотною. Позначається А ⁺ .

Suppose, we need to calculate the pseudo-inverse of a matrix M: Then, the SVD of M can be given as: Multiply both sides by M^{-1}.Multiply both side by V:Multiply by W^{-1}Since the W is the singular matrix, the inverse of W  is Multiply by

Наведене вище рівняння дає псевдообернене.

Розв’язування системи однорідного лінійного рівняння (Mx =b): якщо b=0, обчисліть SVD і візьміть будь-який стовпець V ^Т пов'язане з одиничним значенням (в IN ) дорівнює 0.

If , Multiply by

З псевдоінверсії ми це знаємо $M^{-1} = V W^{-1} U^{T}$

Отже,

$x = V W^{-1} U^{T} b$

Ранг, діапазон і нульовий простір:
- Ранг матриці M можна обчислити з SVD за кількістю ненульових сингулярних значень.
- Діапазоном матриці M є ліві сингулярні вектори U, що відповідають ненульовим сингулярним значенням.
- Нульовий простір матриці M є правими сингулярними векторами V, що відповідають обнуленим сингулярним значенням.

$M = U W V^{T}$

Проблема підгонки кривої: Сингулярне розкладання можна використовувати для мінімізації помилки найменших квадратів. Для його апроксимації використовується псевдоінверсія.
Окрім вищезазначеного застосування, сингулярне розкладання та псевдоінверсія також можуть бути використані в цифровій обробці сигналів та обробці зображень

Реалізація:

У цьому коді ми спробуємо обчислити декомпозицію сингулярного значення за допомогою Numpy і Scipy. Ми будемо обчислювати SVD, а також виконувати псевдоінверсію. Зрештою, ми можемо застосувати SVD для стиснення зображення

Python3

# Imports> from> skimage.color> import> rgb2gray> from> skimage> import> data> import> matplotlib.pyplot as plt> import> numpy as np> from> scipy.linalg> import> svd> '''> Singular Value Decomposition> '''> # define a matrix> X> => np.array([[> 3> ,> 3> ,> 2> ], [> 2> ,> 3> ,> -> 2> ]])> print> (X)> # perform SVD> U, singular, V_transpose> => svd(X)> # print different components> print> (> 'U: '> , U)> print> (> 'Singular array'> , singular)> print> (> 'V^{T}'> , V_transpose)> '''> Calculate Pseudo inverse> '''> # inverse of singular matrix is just the reciprocal of each element> singular_inv> => 1.0> /> singular> # create m x n matrix of zeroes and put singular values in it> s_inv> => np.zeros(X.shape)> s_inv[> 0> ][> 0> ]> => singular_inv[> 0> ]> s_inv[> 1> ][> 1> ]> => singular_inv[> 1> ]> # calculate pseudoinverse> M> => np.dot(np.dot(V_transpose.T, s_inv.T), U.T)> print> (M)> '''> SVD on image compression> '''> cat> => data.chelsea()> plt.imshow(cat)> # convert to grayscale> gray_cat> => rgb2gray(cat)> # calculate the SVD and plot the image> U, S, V_T> => svd(gray_cat, full_matrices> => False> )> S> => np.diag(S)> fig, ax> => plt.subplots(> 5> ,> 2> , figsize> => (> 8> ,> 20> ))> curr_fig> => 0> for> r> in> [> 5> ,> 10> ,> 70> ,> 100> ,> 200> ]:> > cat_approx> => U[:, :r] @ S[> 0> :r, :r] @ V_T[:r, :]> > ax[curr_fig][> 0> ].imshow(cat_approx, cmap> => 'gray'> )> > ax[curr_fig][> 0> ].set_title(> 'k = '> +> str> (r))> > ax[curr_fig,> 0> ].axis(> 'off'> )> > ax[curr_fig][> 1> ].set_title(> 'Original Image'> )> > ax[curr_fig][> 1> ].imshow(gray_cat, cmap> => 'gray'> )> > ax[curr_fig,> 1> ].axis(> 'off'> )> > curr_fig> +> => 1> plt.show()>

Вихід:

[[ 3 3 2]  [ 2 3 -2]] --------------------------- U: [[-0.7815437 -0.6238505]  [-0.6238505 0.7815437]] --------------------------- Singular array [5.54801894 2.86696457] --------------------------- V^{T} [[-0.64749817 -0.7599438 -0.05684667]  [-0.10759258 0.16501062 -0.9804057 ]  [-0.75443354 0.62869461 0.18860838]] -------------------------- # Inverse  array([[ 0.11462451, 0.04347826],  [ 0.07114625, 0.13043478],  [ 0.22134387, -0.26086957]]) ---------------------------