SVD на собеседовании Data Scientist

Зачем разбирать на собесе

SVD — основа PCA, latent semantic analysis, классических recsys, image compression. На собесе DS: «формула SVD», «как связано с PCA», «truncated SVD для recsys». Senior — нюансы numerical SVD, randomized SVD.

Главная боль без понимания — DS использует PCA, не понимает, что под капотом SVD, путает eigen-decomposition с SVD.

Формула SVD

Singular Value Decomposition. Любая матрица A размерности m×n представима как:

A = U · Σ · Vᵀ

• U — m×m, ортогональная матрица (UᵀU = I). Колонки — left singular vectors.
• Σ — m×n, диагональная (на диагонали — singular values σ₁ ≥ σ₂ ≥ ... ≥ 0).
• Vᵀ — n×n, ортогональная. Колонки V — right singular vectors.

Свойства:

• SVD существует для любой матрицы (не требует симметрии или квадратности).
• Singular values неотрицательны и упорядочены по убыванию.
• Если σ_k+1 = ... = σ_n = 0, ранг матрицы = k.
• Rank-k truncation: оставить только первые k singular values — оптимальная low-rank аппроксимация в смысле Frobenius / spectral норм (теорема Eckart-Young).

import numpy as np
A = np.random.rand(5, 3)
U, s, Vt = np.linalg.svd(A, full_matrices=False)
# A ≈ U @ np.diag(s) @ Vt

Геометрическая интерпретация

Линейное преобразование A можно разложить на три:

1. Vᵀ — ротация в пространстве входа.
2. Σ — растяжение по осям (с коэффициентами σᵢ).
3. U — ротация в пространстве выхода.

Любое линейное преобразование = «ротация → растяжение → ротация».

Singular values говорят, на сколько растягивается каждая ось. Самые большие — главные направления варьирования.

Связь с PCA

PCA = SVD центрированной матрицы данных.

X (n samples × d features), центрированный (mean=0)

X = U Σ Vᵀ

Principal components = столбцы V (или строки Vᵀ)
Variance explained = σᵢ² / (n-1)

Projection X на k главных компонент = U[:, :k] · Σ[:k, :k] = X · V[:, :k]

В sklearn:

from sklearn.decomposition import PCA, TruncatedSVD

pca = PCA(n_components=10).fit(X)            # требует центрированные данные
# pca.components_ = Vt[:k]
# pca.explained_variance_ ratio_ = σᵢ² / sum(σ²)

tsvd = TruncatedSVD(n_components=10).fit(X)  # без центрирования
# работает для sparse matrix (text data)

Почему SVD предпочтительнее eigen-decomposition XᵀX:

• Численно стабильнее (особенно для near-singular).
• Работает для не-квадратных матриц.
• XᵀX — потеря точности.

Truncated SVD и low-rank

Truncated SVD — оставить топ-k singular values:

A_k = U[:, :k] · Σ[:k, :k] · V[:, :k]ᵀ

Eckart-Young theorem. A_k — лучшая аппроксимация ранга k в смысле Frobenius / spectral норм.

Применения:

• Image compression. Картинка m×n → 3 матрицы общим размером (m+n+1)·k. Если k << min(m,n) — хорошо сжимается.
• Latent Semantic Analysis (LSA). Матрица термин-документ → SVD → семантические темы.
• Recsys (matrix factorization). см. ниже.
• Denoising. Малые singular values — шум, обнуляем.
• Speed-up для линейных моделей с k << d.

Randomized SVD. Для огромных матриц — приближение через рандомные проекции. sklearn.decomposition.randomized_svd. В тысячи раз быстрее на больших разреженных.

Matrix factorization для recsys

Классический подход к коллаборативной фильтрации.

R (users × items, рейтинги, sparse) ≈ U · Vᵀ
            shape (n_users × k)   ·   (k × n_items)

Каждый user → k-мерный embedding. Каждый item → k-мерный embedding. Рейтинг = скалярное произведение.

Прямой SVD не работает на sparse. В R пустые ячейки означают «не оценено», не «оценка 0». Лечение — Funk SVD / SGD-MF / ALS:

# минимизация только по наблюдённым:
loss = Σ_{(u, i) ∈ obs} (R_ui - U_u · V_iᵀ)²  +  λ (||U||² + ||V||²)

Optimisation: SGD или ALS (alternating least squares).

Современная альтернатива — нейросетевые approaches: two-tower, BPR, neural matrix factorization. Для tabular-recsys классический MF всё ещё силён.

Численная устойчивость и стоимость

Стоимость: O(min(m·n², m²·n)) для full SVD. На матрице 10000×10000 — медленно.

Randomized SVD: O(m·n·k + (m+n)·k²) — линейно по размеру для маленького k.

LAPACK. Реализации SVD используют lapack (DGESDD, DGESVD). Быстрые, стабильные. NumPy под капотом — это они.

Условие. Условное число матрицы κ(A) = σ₁ / σₙ. Большое κ → плохо обусловлена, плохая численная стабильность linear system.

np.linalg.svd vs scipy.sparse.linalg.svds:

• numpy — dense, full SVD.
• scipy svds — sparse, partial (только k top singular values).

Частые ошибки

SVD на нецентрированной матрице для PCA. Получишь главную компоненту = направление среднего, не направление варьирования. Всегда центрируй для PCA.

Использовать SVD на разреженной матрице как dense. OOM. Используй scipy.sparse.linalg.svds или TruncatedSVD.

Не нормировать фичи перед SVD/PCA. Колонки с большим scale доминируют. Стандартизация обязательна.

Считать eigen(XᵀX) дешевле svd(X). Численно XᵀX теряет точность из-за квадратирования condition number. SVD стабильнее.

Все singular values хранить. Зачем k = full_rank, если нужно k << r? Truncated.

Не помнить про U, V в truncated. В sklearn TruncatedSVD.fit_transform(X) даёт X·V_k — projection. Сами U, V_k могут быть нужны отдельно.

Использовать SVD для классификации напрямую. SVD — unsupervised. Для классификации используй после: проекция → классификатор.

Negative singular values. Не бывает — σ ≥ 0 by definition. Если получаешь отрицательное — это не SVD, а eigen-decomposition с отрицательным eigenvalue.

Связанные темы

• PCA — снижение размерности для DS
• NumPy vectorization на собесе DS
• Embeddings на собесе DS
• Linear vs logistic regression на собесе DS
• Подготовка к собесу Data Scientist

FAQ

Truncated SVD и Randomized SVD — это одно?

Нет. Truncated — оставить top-k. Randomized — алгоритм быстрого приближения top-k через random projections. Они часто комбинируются.

Зачем full_matrices=False?

np.linalg.svd(A, full_matrices=False) возвращает усечённые U, V (только до min(m,n) колонок). Иначе U размером m×m, V — n×n, что огромно при m≠n.

Eigenvalue vs singular value?

Для симметричных PSD матриц совпадают. Для общей матрицы — нет. SVD даёт singular, eigen-decomposition — eigen.

Что такое спектральная норма?

||A||₂ = σ₁ (наибольшее singular value). Эквивалентна максимальному коэффициенту растяжения матрицы.

linalg.svd ledelle медленный — есть быстрее?

scipy.sparse.linalg.svds (для top-k), sklearn.utils.extmath.randomized_svd, JAX/CuPy на GPU. Можно ускорить в 10-100×.

Это официальная информация?

Нет. Статья основана на классических работах (Golub-Van Loan «Matrix Computations»), документации NumPy / scikit-learn.

Тренируйте Data Science — откройте тренажёр с 1500+ вопросами для собесов.