Прочтите мои доказательства для начинающих, чтобы изучить применение линейной алгебры

В последней статье этой серии нашей целью было сохранить всю вариативность пространства лица. В качестве компромисса нам по-прежнему нужно было включать измерения с относительно небольшими отклонениями, что увеличивало вычислительную сложность. Если мы готовы пожертвовать незначительной потерей дисперсии в обмен на значительный выигрыш в вычислительной эффективности, мы можем дополнительно уменьшить размерность подпространства собственной грани, выбрав только измерения с наибольшей дисперсией. Вышеупомянутый подход называется анализом главных компонентов (PCA).

Учитывая нормализованную матрицу A, мы определяем первое главное направление как то, в котором данные испытывают наибольшую дисперсию. Чтобы не мешать уже подтвержденному направлению максимальной дисперсии, мы определяем второе главное направление как направление с наибольшей дисперсией среди всех направлений, ортогональных первому главному направлению. Аналогичным образом определяются следующие основные направления.

Если мы сможем доказать, что основное направление jᵗʰ матрицы A является единичным собственным вектором матрицы C = α AᵗA, который соответствует jᵗʰ наибольшему собственному значению C, мы сможем уловить наибольшую дисперсию A, выбрав собственные векторы C которые соответствуют большим собственным значениям. В этом суть СПС, а также то, что мы собираемся доказать сегодня.

Прежде чем углубиться в доказательство, нам будет полезно сделать небольшую паузу и сравнить цель этой статьи с целью предыдущей. В последней статье нашей целью было найти ортогональный базис ковариационной матрицы C, поскольку ортогональный базис устранит ковариацию по измерениям и, следовательно, наиболее эффективно использует дисперсию. Для достижения этой цели мы сначала показали, что C имеет ортогональный базис, который оказывается собственным базисом. Затем мы показали, что в этом базисе собственных значений собственные векторы, соответствующие нулевому собственному значению, устранимы, так как существует нулевая дисперсия в размерах, которые они охватывают. Следуя этой логике, мы достигли нашей цели в последнем разделе без необходимости доказывать, что максимальная дисперсия лежит в направлении собственного вектора с наибольшим собственным значением. Вместо этого мы обосновали актуальность собственных векторов, показав, что ортогональный базис состоит из собственных векторов. Однако в этой статье мы хотим напрямую выбрать отдельные измерения с большими отклонениями. Следовательно, нам необходимо восстановить релевантность собственных векторов, обосновав более фундаментальный вопрос: Почему собственные векторы указывают на главные направления среди всех векторов? Имея это в виду, давайте погрузимся в доказательство:

Лемма 3. Главное направление jᵗʰ нормализованной матрицы A - это единичный собственный вектор матрицы C = α AᵗA (где α - обратное число строк в A), соответствующий jᵗʰ наибольшему собственному значению матрицы C. Дисперсия jᵗʰ главного direction - это jᵗʰ наибольшее собственное значение оператора C.

Чтобы доказать лемму 3, пусть u - любой единичный вектор. Пусть v_1 … v_n будет векторами-строками A. Пусть σᵤ² будет дисперсией v_1 … v_n в направлении u. Согласно четвертой строке уравнения 11 в последней статье, мы имеем:

Чтобы доказать по индукции, пусть P (k) будет утверждением, что: kᵗʰ главного направления a A является единичным собственным вектором C = α AᵗA, который соответствует kᵗʰ наибольшему собственному значению C. Дисперсия на kᵗʰ главном направлении равна kᵗʰ наибольшее собственное значение оператора C.

Базовый случай: когда k = 1, пусть λ₁ будет наибольшим собственным значением C. Поскольку C симметрично, согласно Спектральной теореме, мы можем записать C как:

где D - диагональная матрица, а Q - ортогональная матрица. Собственные значения C появляются на диагонали D, а соответствующие собственные векторы являются столбцами Q.

Объедините уравнения 13 и 14, мы получим:

Поскольку Q - ортогональная матрица и ортогональное преобразование сохраняет длину, y также является единичным вектором, т. Е.

Теперь, чтобы преобразовать yᵗDy в квадратичную форму, пусть λ₁ ≥ λ₂ ≥ ... ≥ λn - собственные значения C. Поскольку эти значения λ также являются диагональными элементами D, мы имеем:

Объедините уравнение 15 и 17, мы получим:

Максимальное значение достигается, когда u является единичным собственным вектором C с собственным значением λ₁. Следовательно, базовый случай P (1) верен.

Индуктивная гипотеза. Предположим, что P (1),…, P (j-1) верны для некоторого положительного целого числа j ≥ 2.

Индуктивный шаг: теперь мы покажем, что P (j) верен. Пусть λ₁ ≥… ≥ λⱼ - собственные значения оператора C с соответствующими ортогональными собственными векторами ω₁,…, ωⱼ (их ортогональность можно доказать с помощью спектральной теоремы). Поскольку все P (1),…, P (j-1) верны, мы знаем, что ω₁,…, ωⱼ⁻₁ указывают на первые j-1 главных направлений. Следовательно, чтобы найти главное направление jᵗʰ, нужно найти единичный вектор u, который максимизирует следующее выражение:

Требование после «|» добавляется, поскольку главное направление jᵗʰ должно быть ортогональным всем предыдущим основным направлениям.

Напомним, что ω₁,…, ωⱼ на самом деле являются столбцами Q, что делает их также строками Qᵗ. Без ограничения общности предположим, что ωₓ - строка xᵗʰ матрицы Qᵗ. Поскольку y = Qᵗu (определено в уравнении 15), мы можем сделать вывод, что yₓ = u ⋅ ωₓ. Следовательно, выражение 1 можно переписать следующим образом:

Теперь, когда y₁ = ... = yⱼ⁻₁ = 0, мы можем изменить уравнение 17:

Объедините уравнение 15 и 18, мы получим:

Максимальное значение достигается, когда u является единичным собственным вектором C с собственным значением λⱼ. Соответственно, индуктивный случай P (j) верен. Доказательство завершено.

В этой статье мы доказали, почему собственные векторы с большими собственными значениями всегда соответствуют размерам с большой дисперсией. Это открытие закладывает основу для PCA, который пригодится при распознавании лиц, когда нам нужно быстро уменьшить размеры изображений, сохраняя при этом большую часть их вариативности. В следующей статье я применим PCA к примеру распознавания лиц. Я также расскажу о том, как проецировать фотографии на подпространство eigenface. Будьте на связи!

[1] Питер Олвер и Чехерзад Шакибан. Прикладная линейная алгебра. Springer, 2018.

[2] Мэтью Терк и Алекс Пентланд. Собственные лица для узнавания. страницы 71–86. Журнал когнитивной нейробиологии, 1991 г.

[3] Фотография на обложке предоставлена ​​Махешу Кумару на https://www.maheshkumar.xyz/article/principal-component-analysis.html.