Orthogonal projections

Из геометрии мы знаем, что для нахождения проекции вектора на прямую или плоскость, надо из его конца опустить перпендикуляр. Вектор, указывающий в точку пересечения перпенидкуляра с прямой/плоскостью, и будет искомой (ортогональной) проекцией. В этом разделе мы займёмся ортогональным проектированием на произвольное подпространство \(\mathbb R^n\).

Проекции хороши тем, что позволяют находить ближайшую точку из заданного подпространства. На этом свойстве основан метод наименьших квадратов и такой классический метод машинного обучения как линейная регрессия.

Projection onto a line

Пусть прямая в \(\mathbb R^n\) задана ненулевым вектором \(\boldsymbol a = (a_1, \ldots, a_n)^\mathsf{T}\), и мы хотим найти на этой прямой точку \(\boldsymbol p\), ближайшую к заданной точке \(\boldsymbol x\). Для этого вектор \(\boldsymbol x\) надо спроектировать на прямую \(\mathrm{span}(\boldsymbol a)\); результатом проекции и будет вектор \(\boldsymbol p = c \boldsymbol a\). Проекция \(\boldsymbol p\) характеризуется свойством \(\boldsymbol x - \boldsymbol p \perp \boldsymbol a\), из которого мы и найдём число \(c\):

(49)\[ \boldsymbol a^\mathsf{T}(\boldsymbol x - \boldsymbol p) = 0 \iff \boldsymbol a^\mathsf{T}\boldsymbol x - c\boldsymbol a^\mathsf{T}\boldsymbol a = 0 \iff c = \frac{\boldsymbol a^\mathsf{T}\boldsymbol x}{\boldsymbol a^\mathsf{T}\boldsymbol a}. \]

Итак, наша проекция равна \(\boldsymbol p = \frac{\boldsymbol a^\mathsf{T}\boldsymbol x}{\boldsymbol a^\mathsf{T}\boldsymbol a} \boldsymbol a\). Если вектор \(\boldsymbol a\) единичный, то формула для проекции упрощается до \(\boldsymbol p = \langle \boldsymbol a, \boldsymbol x\rangle \boldsymbol a\).

Отметим два простых, но важных частных случая проекции на прямую:

1. Если точка \(\boldsymbol x\) уже лежит на прямой \(\mathrm{span}(\boldsymbol a)\), \(\boldsymbol x = d \boldsymbol a\), то

   \[ \boldsymbol p = \frac{d\boldsymbol a^\mathsf{T}\boldsymbol a}{\boldsymbol a^\mathsf{T}\boldsymbol a} \boldsymbol a = d \boldsymbol a = \boldsymbol b. \]

   В этом случае проектируемая точка уже лежит на прямой, поэтому ничего искать не надо: её проекция совпадает с ней самой.

2. Если \(\boldsymbol x \perp a\), то \(\boldsymbol a^\mathsf{T}\boldsymbol x = 0\) и \(\boldsymbol p = \boldsymbol 0\). Это хорошо известное из геометрии и физики свойство: проекция перпендикулярного вектора равна нулю.

Проектирование вектора \(\boldsymbol x\) на прямую \(\mathrm{span}(\boldsymbol a)\) можно записать в виде умножения на одноранговую матрицу \(\boldsymbol P\):

\[ \boldsymbol p = \boldsymbol {Px}, \quad \boldsymbol P = \frac{\boldsymbol a \boldsymbol a^\mathsf{T}}{\boldsymbol a^\mathsf{T} \boldsymbol a}. \]

Матрица \(\boldsymbol P\) является частным случаем матрицы проекции и обладает свойством \(\boldsymbol P^2 = \boldsymbol P\).

Simple linear regression

Consider a simple linear regression model without intercept: \(y = a x\). Given training dataset \(\mathcal D = \{(x_i, y_i)\}_{i=1}^n\), how to find optimal value of \(a\)?

In linear regression we minimize the distance from the target vector \(\boldsymbol y = (y_1, \ldots, y_n)\) and the line specified by the feature vector \(\boldsymbol x = (x_1, \ldots, x_n)\). According (49) we can achieve this by putting

(50)\[ \widehat a = \frac{\boldsymbol x^\mathsf{T} \boldsymbol y}{\boldsymbol x^\mathsf{T} \boldsymbol x} = \frac{\sum\limits_{i=1}^n x_i y_i}{\sum\limits_{i=1}^n x_i^2}\]

Note

Linear regression with bias \(y = ax + b\) is described here. The optimal parameters are given by (11). See also this plot.

Projection onto a subspace

Теперь займёмся поиском проекции вектора \(\boldsymbol x \in \mathbb R^m\) на подпространство \(\mathrm{span}(\boldsymbol a_1, \ldots, \boldsymbol a_n)\), \(n\leqslant m\). Будем считать, что все векторы \(\boldsymbol a_1, \ldots, \boldsymbol a_n\) линейно независимы (в противном случае выкинем лишние). Проекция \(\boldsymbol p\) вектора \(\boldsymbol x\) представляет собой линейную комбинацию

\[ \boldsymbol p = c_1 \boldsymbol a_1 + \ldots + c_n\boldsymbol a_n, \]

что эквивалентно матрично-векторному умножению

\[ \boldsymbol p = \boldsymbol {Ac}, \quad \boldsymbol A = [\boldsymbol a_1 \ldots \boldsymbol a_n], \quad \boldsymbol c = (c_1,\ldots, c_n)^\mathsf{T}. \]

Вектор \(\boldsymbol x - \boldsymbol p\) должен быть ортогонален подпространству \(\mathrm{span(\boldsymbol a_1, \ldots, \boldsymbol a_n)}\), поэтому \(\boldsymbol x - \boldsymbol{Ac} \perp \boldsymbol a_j\) при всех \(j=1, \ldots, n\), т.е.

\[ \boldsymbol a_j^\mathsf{T} (\boldsymbol x - \boldsymbol{Ac}) = 0, \; 1 \leqslant j \leqslant n, \;\iff\; \boldsymbol A^\mathsf{T} (\boldsymbol x - \boldsymbol{Ac}) = \boldsymbol 0. \]

Таким образом, справедливо равенство \(\boldsymbol A^\mathsf{T} \boldsymbol x = \boldsymbol A^\mathsf{T} \boldsymbol{Ac}\). Поскольку \(\mathrm{rank}(\boldsymbol A) =n\), матрица \(\boldsymbol A^\mathsf{T} \boldsymbol A\) обратима, и можно домножить предыдущее равенство на \((\boldsymbol A^\mathsf{T} \boldsymbol A)^{-1}\).

В результате получаем, что

(51)\[\boldsymbol c = (\boldsymbol A^\mathsf{T} \boldsymbol A)^{-1} \boldsymbol A^\mathsf{T} \boldsymbol x,\]

а сама проекция равна

\[ \boldsymbol p = \boldsymbol{Ac} = \boldsymbol A(\boldsymbol A^\mathsf{T} \boldsymbol A)^{-1} \boldsymbol A^\mathsf{T} \boldsymbol x. \]

Отметим, что проекция на прямую является частным случаем проекции на подпространство, когда матрица \(\boldsymbol A\) состоит из одного столбца \(\boldsymbol a\). Проекция на подпространство записывается в виде \(\boldsymbol p = \boldsymbol {Px}\) с помощью матрицы проекции

(52)\[ \boldsymbol P = \boldsymbol A (\boldsymbol A^\mathsf{T} \boldsymbol A)^{-1} \boldsymbol A^\mathsf{T}. \]

Note

The matrix \((\boldsymbol A^\mathsf{T} \boldsymbol A)^{-1} \boldsymbol A^\mathsf{T}\) is also called Moore–Penrose pseudo inverse matrix and denotes as \(\boldsymbol A^\dagger\). Thus, (51) can be rewritten as \(\boldsymbol c = \boldsymbol A^\dagger \boldsymbol x\).

Linear regression

Цель задачи регрессии — смоделировать зависимость целевой переменной \(y \in \mathbb R\) от признаков объекта \(\boldsymbol x \in \mathbb R^d\) (\(d\) — число признаков). Линейная регрессия строит линейную модель, которая предполагает линейную зависимость \(y\) от \(\boldsymbol x\). Как мы знаем, всякий линейный функционал из \(\mathbb R^d\) в \(\mathbb R\) может быть записан в виде скалярного произведения

(53)\[ y = \boldsymbol x^\mathsf{T} \boldsymbol w\]

для некоторого фиксированного вектора весов \(\boldsymbol w \in \mathbb R^d\). Правда, в таком случае \(y = 0\) при \(\boldsymbol x = \boldsymbol 0\), что может не соответствовать нашим данным. Поэтому к линейному функционалу добавляют ещё один параметр — свободный член (bias) \(w_0\), и тогда линейная модель (53) приобретает вид

\[ y = \boldsymbol x^\mathsf{T} \boldsymbol w + w_0. \]

Записывать в таком виде линейную регрессию не очень удобно, но свободный член можно учесть в первоначальной записи (53), если добавить ещё один (нулевой) признак, всегда равный единице:

\[\begin{split} \boldsymbol x = \begin{pmatrix} 1 \\ x_1 \\ \vdots \\ x_d\\ \end{pmatrix}, \quad \boldsymbol w = \begin{pmatrix} w_0 \\ w_1 \\ \vdots \\ w_d\\ \end{pmatrix}, \quad y = \boldsymbol x^\mathsf{T} \boldsymbol w. \end{split}\]

Далее будем считать, что этот фиктивный принак уже добавлен, и всякая линейная зависимость между признаками объекта \(\boldsymbol x\) и таргетом \(y\) имеет вид (53).

Для решения задачи регрессии (в том числе линейной) нам, разумеется, нужна обучающая выборка — датасет

\[ \mathcal D = (\boldsymbol x_i, y_i)_{i=1}^n, \]

состоящий из признаков \(\boldsymbol x_i \in \mathbb R^d\) и таргетов \(y_i\in \mathbb R\) \(i\)-го обучающего объекта, \(i=1, \ldots, n\). Такие числовые датасеты удобно записывать в матрично-векторной форме: построчно записанные признаки \(\boldsymbol x_i\) образуют матрицу объект-признак \(\boldsymbol X\) размера \(n\times d\), а таргеты — вектор \(\boldsymbol y\):

\[\begin{split} \boldsymbol X = \begin{pmatrix} \boldsymbol x_1^\mathsf{T} \\ \vdots \\ \boldsymbol x_n^\mathsf{T} \end{pmatrix}, \quad \boldsymbol y = \begin{pmatrix} y_1 \\ \vdots \\ y_n \end{pmatrix}. \end{split}\]

Такие обозначения позволяют линейную модель (53) записать единой формулой сразу для всего датасета \(\mathcal D\) как

\[ \boldsymbol y = \boldsymbol{Xw}. \]

Задача линейной регрессии состоит в подборе весов \(\boldsymbol w\) таким образом, чтобы \(\boldsymbol{Xw}\) был как можно ближе к вектору \(\boldsymbol y\). Для этого надо спроектировать вектор \(\boldsymbol y\) на \(C(\boldsymbol X)\). Согласно (51) оптимальный вектор весов \(\widehat {\boldsymbol w}\) равен

(54)\[ \widehat {\boldsymbol w} = (\boldsymbol X^\mathsf{T} \boldsymbol X)^{-1} \boldsymbol X^\mathsf{T} \boldsymbol y \]

Чтобы веса линейной регрессии можно было найти по этой формуле, матрица объект-признак \(\boldsymbol X\) должна иметь линейно независимые столбцы. Если это не так, то между признаками в датасете \(\mathcal D\) есть линейная зависимость (её также называют мультиколлинеарностью). Мультиколлинеарность ломает линейную регрессию, поэтому от неё следует избавляться, например, проредив количество признаков.

Orthogonal spaces

Subspaces \(U, V \subset \mathbb R^n\) are called orthogonal if

\[ \boldsymbol u^\mathsf{T}\boldsymbol v = 0 \text{ for all } \boldsymbol u, \boldsymbol v \in V. \]

For example, lines \(y = x\) and \(y = -x\) are orthogonal in \(\mathbb R^2\), and plane \(x + y + z = 0\) is orthogonal to line spanned by vector \((1, 1, 1)\).

Orthogonal complement of a subspace \(V\subset \mathbb R^n\) is a subspace of vectors perpendicular to all vectors from \(V\):

\[ V^\perp = \{ \boldsymbol x \in \mathbb R^n\colon \boldsymbol x^{\mathsf T} \boldsymbol v = 0 \text{ for all } \boldsymbol v \in V\}. \]

If \(V\) is a subspace of \(\mathbb R^n\), then \(\dim V + \dim V ^\perp = n\).

Fundamental theorem of linear algebra, part 2

If \(\boldsymbol A \in \mathbb R^{m\times n}\) then

\[ C(\boldsymbol A)^\perp = N(\boldsymbol A^\mathsf{T}), \quad C(\boldsymbol A^\mathsf{T})^\perp = N(\boldsymbol A). \]

Proof

Let \(\boldsymbol x \in N(\boldsymbol A)\), \(\boldsymbol y \in C(\boldsymbol A^\mathsf{T})\), then \(\boldsymbol{Ax} = \boldsymbol 0\) and \(\boldsymbol y = \boldsymbol A^\mathsf{T} \boldsymbol z\) for some \(\boldsymbol z \in \mathbb R^m\). Hence,

\[ \boldsymbol x^\mathsf{T}\boldsymbol y = \boldsymbol x^\mathsf{T} \boldsymbol A^\mathsf{T} \boldsymbol z = (\boldsymbol{Ax})^{\mathsf T} \boldsymbol z = \boldsymbol 0^\mathsf{T} \boldsymbol z = 0. \]

Exercises

1. Find the projection matrix onto the line \(x + y = 0\).

2. Prove that \(\boldsymbol P = \frac{\boldsymbol a \boldsymbol a^\mathsf{T}}{\boldsymbol a^\mathsf{T} \boldsymbol a}\), \(\boldsymbol a \ne \boldsymbol 0\), is a projection matrix, i.e., \(\boldsymbol P^2 = \boldsymbol P\).

3. Show that matrix (52) is a projection matrix.

4. Let \(\boldsymbol X \in \mathbb R^{n\times d}\). Estimate the complexity of calculations by formula (54) in terms of big-O.

5. Find the feature matrix \(\boldsymbol X\) for simple linear regression \(y = ax + b\). Applying (54) show that the equalities (11) hold.

6. Let \(\boldsymbol P\) be a projection matrix. Show that \(\boldsymbol I - \boldsymbol P\) is also a projection matrix.

7. Let \(\boldsymbol P\) be the projection matrix onto \(C(\boldsymbol A)\). On which subspace will project the matrix \(\boldsymbol I - \boldsymbol P\)?

   Answer

   Заметим, что

   \[ (\boldsymbol I - \boldsymbol P)^2 = \boldsymbol I - 2\boldsymbol P + \overbrace{\boldsymbol P^2}^{=\boldsymbol P} = \boldsymbol I - \boldsymbol P, \]

   так что \(\boldsymbol I - \boldsymbol P\) действительно матрица проекции. Любой вектор \(\boldsymbol x\) единственным образом представляется в виде суммы \(\boldsymbol x = \boldsymbol p + \boldsymbol e\), где \(\boldsymbol p = \boldsymbol{Px}\) — проекция на \(C(\boldsymbol A)\), \(\boldsymbol e = \boldsymbol x - \boldsymbol p\) — ортогональный ей вектор. Имеем

   \[ (\boldsymbol I - \boldsymbol P) \boldsymbol x = \boldsymbol x - \boldsymbol p = \boldsymbol e; \]

   таким образом, матрица \(\boldsymbol I - \boldsymbol P\) проектирует на ортогональное дополнение к \(C(\boldsymbol A)\), т.е. на левое ядро \(N(\boldsymbol A^\mathsf{T})\).