Svd.el

Εισαγωγή #

Η SVD αποσυνθέτει τα δεδομένα σε ανεξάρτητους τρόπους ταξινομημένους κατά ισχύ. Η διατήρηση μόνο των ισχυρών τρόπων δίνει συμπαγείς αναπαραστάσεις με ελεγχόμενη απώλεια πληροφορίας.

Αναλυτική Επεξήγηση #

1. Γιατί SVD; #

• Οποιοσδήποτε ορθογώνιος πίνακας (A) μπορεί να αποσυντεθεί σε ερμηνεύσιμα κομμάτια: περιστροφές συν κλιμάκωση.
• Με την αποκοπή των ιδιαζουσών τιμών παίρνουμε τη βέλτιστη προσέγγιση χαμηλής τάξης υπό την έννοια της νόρμας Frobenius.
• Η SVD είναι αριθμητικά σταθερή και αποτελεί τη ραχοκοκαλιά πολλών αλγορίθμων (LSA, PCA, συνεργατικό φιλτράρισμα).

2. Ορισμός #

Για (A \in \mathbb{R}^{m \times n}):

• (U): αριστερά ιδιάζοντα διανύσματα (ορθοκανονικά, μέγεθος (m \times m))
• (\Sigma): διαγώνιος πίνακας με ιδιάζουσες τιμές (\sigma_1 \ge \sigma_2 \ge \dots)
• (V): δεξιά ιδιάζοντα διανύσματα (ορθοκανονικά, μέγεθος (n \times n))

Οι κορυφαίες ιδιάζουσες τιμές συλλαμβάνουν το μεγαλύτερο μέρος της ενέργειας του πίνακα.

3. Προετοιμασία εικόνας #

1
2
3
4
5
6
7
8

import numpy as np
import matplotlib.pyplot as plt
import japanize_matplotlib
from scipy import linalg
from PIL import Image

img = Image.open("./sample.png").convert("L").resize((163, 372)).rotate(90, expand=True)
img

4. Υπολογισμός της SVD #

1
2
3
4

X = np.asarray(img)
U, Sigma, VT = linalg.svd(X, full_matrices=True)

print(f"A: {X.shape}, U: {U.shape}, Σ:{Sigma.shape}, V^T:{VT.shape}")

5. Προσέγγιση χαμηλής τάξης / συμπίεση #

1
2
3
4
5
6
7
8
9

for rank in [1, 2, 3, 4, 5, 10, 20, 50]:
    U_i = U[:, :rank]
    Sigma_i = np.matrix(linalg.diagsvd(Sigma[:rank], rank, rank))
    VT_i = VT[:rank, :]
    temp_image = np.asarray(U_i * Sigma_i * VT_i)

    plt.title(f"rank={rank}")
    plt.imshow(temp_image, cmap="gray")
    plt.show()

Ένας μικρός αριθμός ιδιαζουσών τιμών αρκεί ήδη για μια λογική ανακατασκευή της εικόνας.

6. Εξέταση ιδιαζόντων διανυσμάτων #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

total = np.zeros((163, 372))
for rank in [1, 2, 3, 4, 5]:
    U_i = U[:, :rank]
    Sigma_i = np.matrix(linalg.diagsvd(Sigma[:rank], rank, rank))
    VT_i = VT[:rank, :]

    if rank > 1:
        for ri in range(rank - 1):
            Sigma_i[ri, ri] = 0

    temp_image = np.asarray(U_i * Sigma_i * VT_i)
    total += temp_image

    plt.figure(figsize=(5, 5))
    plt.suptitle(f"Contribution of $u_{rank}$")
    plt.subplot(211)
    plt.imshow(temp_image, cmap="gray")
    plt.subplot(212)
    plt.plot(VT[0])
    plt.show()

plt.imshow(total)

Κάθε ζεύγος ιδιαζόντων διανυσμάτων κωδικοποιεί ένα συγκεκριμένο μοτίβο στην εικόνα· η προσθήκη περισσότερων ζευγών βελτιώνει τη λεπτομέρεια.

7. Πρακτικές συμβουλές #

• Συμπίεση: επιλέξτε (k) ώστε (\sum_{i=1}^k \sigma_i / \sum_j \sigma_j) να φτάνει στην επιθυμητή ενέργεια.
• Μείωση θορύβου: η αφαίρεση μικρών ιδιαζουσών τιμών λειτουργεί συχνά ως αποθορυβοποιητής.
• PCA: απλά εφαρμόστε SVD στον κεντραρισμένο πίνακα δεδομένων· τα δεξιά ιδιάζοντα διανύσματα αντιστοιχούν σε κύριους άξονες.
• Κόστος: η πλήρης SVD είναι (O(mn \min(m,n)))· χρησιμοποιήστε αποκομμένη ή τυχαιοποιημένη SVD για μεγάλους πίνακες.