Научные вычисления

Собственные значения и SVD

Netflix тратит $1 млрд в год на рекомендации. Spotify создаёт персональные плейлисты для 500 миллионов пользователей. Google ранжирует 8 миллиардов страниц. В основе всего - разложение матриц на собственные компоненты.

**Netflix/Spotify:** матрица рейтингов пользователь×контент через low-rank SVD выявляет латентные вкусы и предсказывает рейтинги непросмотренного контента
**PCA в биоинформатике:** геномные данные содержат миллионы SNP для тысяч пациентов. PCA сжимает до 10-50 компонент, сохраняя популяционную структуру для GWAS анализа
**Сжатие изображений:** JPEG использует DCT (родственник SVD) на блоках 8×8. Rank-10 SVD изображения 1000×800 даёт приемлемое качество при сжатии в 8 раз

Исторический контекст

В 1936 году Эккарт и Янг доказали теорему об оптимальной матричной аппроксимации: truncated SVD ранга k минимизирует норму Фробениуса ошибки среди всех матриц ранга k. Это фундаментальный результат: никакое другое разложение ранга k не даёт лучшего приближения в смысле суммы квадратов ошибок. Сам SVD был открыт независимо Бельтрами (1873) и Жорданом (1874) для вещественных матриц, и Аутонне (1915) в комплексном случае. Применение к данным и рекомендательным системам пришло лишь в 2000-х с задачей Netflix Prize.

Собственные значения и векторы: что они значат

**Google PageRank, 1998. Ларри Пейдж и Сергей Брин строят поисковик на задаче нахождения собственного вектора матрицы переходов между страницами.** Матрица - граф интернета: строка i, столбец j - вероятность перехода со страницы j на страницу i. Собственный вектор для λ=1 даёт стационарное распределение случайного блуждания - это и есть PageRank.

**Определение:** вектор v называется собственным вектором матрицы A с собственным значением λ, если Av = λv. Умножение на A не меняет направление v, только масштабирует его в λ раз. Для квадратной матрицы N×N существует N собственных значений (с учётом кратностей), из которых симметричные матрицы имеют все вещественные λ.

**np.linalg.eig** для несимметричных матриц возвращает комплексные собственные значения. Для ковариационных матриц (симметричных, положительно определённых) используйте **np.linalg.eigh** - быстрее и гарантированно вещественные результаты.

Матрица A имеет собственное значение λ=3 и собственный вектор v=[1, 2]. Что равно A@[2, 4]?

SVD: разложение любой матрицы

**Eigendecomposition работает только для квадратных матриц.** Реальные данные - матрицы M×N (1000 пользователей × 500 фильмов). SVD (Singular Value Decomposition) обобщает eigendecomposition на произвольные матрицы: A = U Σ Vᵀ. Здесь U (M×M) и V (N×N) - ортогональные матрицы, Σ (M×N) - диагональная матрица сингулярных значений σ₁ ≥ σ₂ ≥ ... ≥ 0.

Метод	Входная матрица	Результат	Применение
Eigendecomposition	Квадратная A (N×N)	A = Q Λ Q⁻¹	ковариационные матрицы, Markov chains
SVD (полный)	Любая A (M×N)	A = U Σ Vᵀ	рекомендательные системы, LSA
Truncated SVD (rank-k)	Любая A (M×N)	A ≈ Uₖ Σₖ Vₖᵀ	сжатие данных, noise reduction
EVD симметричной	Симметричная A (N×N)	A = Q Λ Qᵀ	PCA, spectral clustering

Матрица A (100×50) имеет SVD: U(100×100), Σ(100×50), Vᵀ(50×50). Для rank-5 аппроксимации сколько чисел нужно хранить?

PCA через SVD: уменьшение размерности

**PCA (Principal Component Analysis)** - проекция данных на оси максимальной дисперсии. Это eigendecomposition ковариационной матрицы - или equivalently, SVD центрированной матрицы данных. Sklearn использует именно SVD для вычисления PCA: более численно стабильный и не требует явного вычисления ковариационной матрицы (N×N при N признаках).

**Выбор числа компонент:** график explained variance ratio (scree plot). Ищем «локоть» - точку где добавление компоненты даёт минимальный прирост. Практическое правило: хранить 95% объяснённой дисперсии. sklearn: `PCA(n_components=0.95)` делает это автоматически.

Почему sklearn реализует PCA через SVD, а не через eigendecomposition ковариационной матрицы?