Ранг матрицы: сколько информации выжила

Матрица рейтингов Netflix 480K пользователей x 17K фильмов почти вся - нули (пользователь видел 0.01% фильмов). Но ранг этой матрицы мал - потому что вкусы людей определяются десятками скрытых факторов, а не миллионами. Понять ранг - значит понять, сколько реальной информации в матрице.

• Netflix Prize: матрица рейтингов имеет низкий ранг - ~20 скрытых факторов объясняют большинство
• LoRA: обновление весов ΔW при fine-tuning имеет низкий ранг эмпирически
• Компьютерное зрение: матрица изображений лиц - ранг ~40 (eigenfaces)
• Диагностика: ранг матрицы Якоби определяет, сколько параметров идентифицируемо
• Сжатие: хранить матрицу ранга r через AB (m+n)r вместо mn элементов

Ранг и метод Гаусса

**PCA на ImageNet сжимает матрицу 224×224×3 = 150 528 признаков до нескольких десятков компонент - и теряет менее 5% дисперсии.** За этим феноменом стоит одно число: ранг. Матрица 150 528 столбцов содержит не 150 528 независимых направлений, а значительно меньше. Ранг - это и есть это меньшее число: **размерность пространства столбцов**, то количество по-настоящему независимой информации, которую матрица несёт.

Реальные данные почти всегда низкоранговые по природе. 1.2M изображений ImageNet лежат не в 150 528-мерном пространстве, а в многообразии значительно меньшей размерности. Матрица оценок Netflix (480K пользователей × 17K фильмов) имеет эффективный ранг около 40. Матрицы весов трансформеров после обучения - тоже. Ранг измеряет этот разрыв между формой матрицы и её истинной информационной ёмкостью.

Определение: геометрический смысл

Матрица A размера m×n задаёт линейное преобразование из ℝⁿ в ℝᵐ. Образ Im A - это множество всех векторов вида Ax. Этот образ является подпространством ℝᵐ, и его размерность и есть ранг.

A (3×3), rank(A) = r - матрица отображает R^3 в подпространство размерности r: r = 3: Im A = всё R^3. Преобразование обратимо, информация не теряется. r = 2: Im A = плоскость внутри R^3. Одна ось «схлопнулась» в точку. r = 1: Im A = прямая. Два измерения уничтожены. r = 0: A = 0. Вся информация потеряна. Потерянные измерения невозвратимы: обратная матрица не существует при r < n. rank(A) = dim(Im A) = dim(col A)

Ключевое равенство: **ранг строк = ранг столбцов**. Это не заметим, что - одно и то же число описывает и размерность пространства строк, и пространства столбцов. Доказывается через ступенчатую форму: элементарные преобразования строк не меняют ни пространство строк, ни ранг столбцов.

Как считать ранг: метод Гаусса

Алгоритм вычисления ранга: привести матрицу к ступенчатому виду (Row Echelon Form) элементарными преобразованиями строк, затем подсчитать ненулевые строки. Элементарные преобразования не меняют ранг - они изменяют базис пространства строк, но не его размерность.

**Численный vs алгебраический ранг**: матрица [[1, 0], [0, 1e-16]] алгебраически имеет ранг 2, но в float64 при порог tol ≈ 2e-15 второе сингулярное значение считается нулевым - ранг 1. В реальных данных с шумом это правильное поведение: `np.linalg.matrix_rank` с дефолтным tol автоматически делает правильный выбор.

Теорема о ранге и дефекте

Теорема о ранге и дефекте

Входное пространство матрицы A (m×n) имеет размерность n. Часть этого пространства отображается в Im A (размерность rank), оставшаяся часть «схлопывается» в нулевой вектор - это ядро ker A. Теорема о ранге-дефекте фиксирует этот баланс.

**Мультиколлинеарность = низкий ранг матрицы признаков.** Если в датасете есть «площадь в кв.м» и «площадь в кв.футах», они линейно зависимы - rank(X) < n. Нормальное уравнение X^T X x = X^T y теряет обратимость: det(X^T X) = 0. Ridge regression исправляет это, добавляя λI: rank(X^T X + λI) = n при λ > 0.

Ранг и разрешимость системы Ax = b

(A|b) - расширенная матрица. Если добавление столбца b поднимает ранг, значит b лежит вне образа A: вектор правой части «вышел за пределы» того, что матрица способна произвести.

Ранг, определитель и применения в ML

LoRA: low-rank adaptation нейросетей

LoRA (Low-Rank Adaptation, Microsoft 2021) - метод дообучения больших моделей с экономией памяти в 100 - 1000 раз. Ключевое наблюдение: обновление матрицы весов при fine-tuning лежит на низкоранговом подпространстве. Вместо хранения ΔW ∈ ℝ^{m×n} факторизуют его как произведение двух тонких матриц.

Полное обновление: ΔW ∈ R^{4096 × 4096} → 16 777 216 параметров LoRA при r = 8: A ∈ R^{8 × 4096} → 32 768 параметров B ∈ R^{4096 × 8} → 32 768 параметров Итого: 65 536 (в 256 раз меньше) При r = 16 (QLoRA-стандарт): 2 × 4096 × 16 = 131 072 (в 128 раз меньше) Ранг дельты: rank(BA) ≤ r по теореме о ранге произведения.

**Почему это работает**: эмпирически задача fine-tuning лежит на low-rank подпространстве весового пространства. Модели, дообученные с r=8, почти неотличимы по качеству от полного fine-tuning при r=4096. Это указывает на фундаментальную избыточность нейросетей.

SVD-разложение и теорема Экарта - Янга

Любую вещественную матрицу можно разложить в произведение трёх матриц: A = UΣVᵀ. Здесь U и V - ортогональные, Σ - диагональная с неотрицательными элементами (сингулярными значениями). Теорема Экарта - Янга говорит, что обрезание до первых k сингулярных значений даёт **оптимальное** приближение ранга k по норме Фробениуса.

Свойства ранга: что нужно знать

• **rank(A) = rank(Aᵀ)** - ранг строк равен рангу столбцов
• **rank(A) ≤ min(m, n)** - ограничен наименьшим измерением
• **rank(AB) ≤ min(rank(A), rank(B))** - произведение не поднимает ранг
• **rank(A + B) ≤ rank(A) + rank(B)** - сложение ограничено суммой рангов
• Элементарные преобразования строк и столбцов не меняют ранг
• rank(A) = число ненулевых сингулярных значений = число ведущих элементов в REF

Где ранг работает в ML

Ранг матрицы в индустрии Ключевые применения концепции ранга LoRA / QLoRA: Fine-tuning через ΔW = BA, rank(BA) ≤ r. Llama, Mistral, Stable Diffusion. r = 4..64. Экономия памяти в 100 - 1000 раз. PCA / SVD: Rank-k аппроксимация - оптимальное сжатие. ImageNet: 150 528 → 50 компонент. Объяснённая дисперсия ∝ σᵢ². Рекомендательные системы: Matrix factorization: R ≈ UVᵀ, rank = r. Netflix, Spotify. Пользователи и айтемы в общем low-rank пространстве. Диагностика данных: rank(X) < n → мультиколлинеарность. Обнаружение дублирующихся / зависимых признаков. Ridge/Lasso как fix. Сжатие нейросетей: SVD веса → top-k компонент → edge inference. Ускорение на iOS/Android без переобучения модели.

Практика: матрица малого ранга

Матрица X^T X встречается в нормальном уравнении линейной регрессии. Что произойдёт, если rank(X) < n? - X^T X станет вырожденной (det = 0), обратной матрицы не существует - Нормальное уравнение имеет бесконечно много решений - коэффициенты неопределены - Причина: мультиколлинеарность, некоторые признаки линейно зависимы - Ridge regression добавляет λI: rank(X^T X + λI) = n гарантировано при λ > 0 В LoRA ранг выбирают равным 8 вместо 4096. Почему это работает, если матрица весов имеет размер 4096×4096? - ΔW = BA имеет rank ≤ 8 по теореме о ранге произведения - Эмпирически задача fine-tuning лежит на low-rank подпространстве - Параметров: 2×4096×8 = 65K вместо 16M - экономия в 256 раз - Нейросети избыточны: они способны выучить задачу с намного меньшим числом параметров Почему теорема Экарта - Янга важна для PCA и сжатия изображений? - Среди всех матриц ранга k именно Aₖ = UₖΣₖVₖᵀ ближайшая к A по норме Фробениуса - Ошибка = √(σ_{k+1}² + … + σ_r²) - определяется отброшенными σᵢ - Если σᵢ быстро убывают (как в реальных данных), маленький k даёт малую ошибку - PCA - это SVD матрицы данных: первые k компонент объясняют максимум дисперсии

Главное

• **Ранг = размерность образа**: сколько независимых направлений матрица сохраняет на выходе
• **rank + nullity = n**: баланс между образом и ядром - теорема о ранге-дефекте
• **Метод Гаусса**: привести к ступенчатому виду, подсчитать ненулевые строки
• **SVD**: rank(A) = число ненулевых σᵢ; Aₖ = оптимальная rank-k аппроксимация (теорема Экарта - Янга)
• **LoRA**: rank(ΔW) ≤ r ≪ min(m,n) - fine-tuning задачи лежат на low-rank подпространстве
• **rank(AB) ≤ min(rank(A), rank(B))**: bottleneck-слой ограничивает ранг всей цепочки

Куда дальше

Ранг связывает почти всё в линейной алгебре

• SVD (сингулярное разложение) — SVD явно показывает ранг через сингулярные значения; основа low-rank аппроксимации
• LU-разложение — Метод Гаусса для вычисления ранга - это LU в основе
• Обратная матрица — Существует тогда и только тогда, когда rank = n (полный ранг)
• PCA и собственные векторы — rank(A) = число ненулевых собственных значений для симметричных матриц; PCA ищет главные компоненты

Связанные уроки

• stat-09-regression
• stat-05-hypothesis