от arXiv
Петрос Дринеас, Майкл В. Махони
Сборник "Сердце машины"
Участие: Ли Цзэнань, Лю Сяокунь, Цзян Сыюань
Матричные вычисления играют ключевую роль в информатике и представляют собой математические знания, которыми должен овладеть каждый разработчик. Недавно Петрос Дринеас из Университета Пердью и Майкл Махони из Калифорнийского университета в Беркли представили обзорную статью «Лекции по рандомизированной числовой линейной алгебре», которую можно использовать в качестве справочного материала для изучения линейной алгебры (Глава: Линейная алгебра) для краткого введения.
Ссылка на бумагу:АР Вест V.org/PDF/1712.08…
Введение
Матрицы занимают уникальное место в информатике, статистике и прикладной математике. Матрица размера m × n может описывать информацию о дискретных дифференциальных операторах m объектов (каждый объект описывается n признаками) в сетке конечных элементов, а положительно определенная матрица размера n × n может кодировать все n пар объектов. между всеми парами n узлов в сети и т. д. Под влиянием достижений науки и компьютерных технологий в последние годы мы стали свидетелями захватывающих разработок в области теории и практики матричных алгоритмов. Наиболее заметным из них является использование рандомизации (часто предполагая, что входные данные зашумлены из-за механизма генерации), которую можно использовать в качестве алгоритма или вычислительного ресурса для разработки и улучшения фундаментальных матричных задач, таких как матричное умножение, метод наименьших квадратов ( LS ) аппроксимация, аппроксимация матриц низкого порядка и другие алгоритмы.
Случайная числовая линейная алгебра (RandNLA) — это междисциплинарная область исследований, которая использует рандомизацию в качестве вычислительного ресурса для разработки алгоритмов повышения для крупномасштабных задач линейной алгебры. С фундаментальной точки зрения, RandNLA является производным от теоретической информатики (TCS) и имеет тесные связи с математикой (выпуклый анализ, теория вероятностей, теория вложения метрик), а также с прикладной математикой (научные вычисления, обработка сигналов, численная линейная алгебра). . С точки зрения приложений RandNLA — важный новый инструмент для машинного обучения, статистики и анализа данных. Многие хорошо спроектированные реализации превзошли высокооптимизированные программные библиотеки в большом количестве задач, таких как регрессия методом наименьших квадратов, а также обладали значительной масштабируемостью, параллельными вычислениями и возможностями распространения. Кроме того, RandNLA обеспечивает надежную алгоритмическую и статистическую основу для современного крупномасштабного анализа данных.
Эта глава послужит отдельным введением в три основных алгоритма RandNLA, рандомизированное матричное умножение, рандомизированные решатели наименьших квадратов и вычисление матриц с помощью случайного алгоритма Низкоранговая аппроксимация . Поэтому эта глава имеет очень прочные связи со многими областями прикладной математики, особенно со многими другими главами этого тома. Наиболее важные из них включают работы Г. Мартинссона, который использовал эти методы для разработки улучшенных приближенных решателей для матриц низкого ранга [2], и работу Р. Вершинина, который разработал вероятностные инструменты для анализа алгоритмов RandNLA [3]; работу Дж. Дучи, который использовал стохастические методы в качестве дополнения для решения более общих задач оптимизации [4], и работу М. Маджиони, который использовал эти методы в качестве основы для более сложных многомасштабных методов [5].
В этой статье изложены базовые знания линейной алгебры в разделе 2, базовые знания о дискретной вероятности в разделе 3, стохастические алгоритмы для умножения матриц в разделе 4 и стохастические алгоритмы для задач регрессии методом наименьших квадратов в разделе 5. В разделе VI мы вводим случайные алгоритмы малоранговых аппроксимаций. Наконец, мы также представляем два других вводных ресурса по RandNLA [6,7] для заинтересованных читателей.
2 Линейная алгебра
В этом разделе мы дадим краткий обзор основных свойств линейной алгебры и математических обозначений, которые будут использоваться в этой главе. Мы предполагаем, что читатель имеет базовые знания линейной алгебры (например, внутренние и перекрестные произведения векторов, основные матричные операции, такие как сложение, скалярное умножение, транспонирование, верхние/нижние треугольные матрицы, умножение матрицы на вектор, умножение матриц, след матрицы и др.).
2.1 Основы
Мы полностью сосредоточимся на матрицах и векторах в линейном пространстве. Мы используем обозначение x ∈ R^n для обозначения n-мерных векторов, отмечая, что векторы пишутся жирными строчными буквами. Предполагается, что все векторы являются векторами-столбцами, если не указано иное. Векторы со всеми нулями представлены 0, а векторы со всеми единицами представлены 1 (аналогично вещанию); размеры неявно в контексте или явно индексируются.
Мы будем использовать жирные прописные буквы для обозначения матриц, таких как A ∈ R^mxn для матрицы порядка mxn, A_i* для вектора-строки i-й строки A и A_*i для вектор-столбца i-го столбца матрицы A. А. Единичная матрица представляется как I_n, где n — количество строк и столбцов матрицы. Наконец, мы обозначаем i-й столбец I_n через e_i, i-ю нормативную базу.
Обратная матрица. Матрица A ∈ R^mxn называется невырожденной или обратимой, если существует обратная матрица A^-1 ∈ R^mxn, удовлетворяющая следующим условиям:
A обратим, если все векторы-столбцы (или векторы-строки) A линейно независимы. Другими словами, не существует ненулевого вектора x ∈ R^n такого, что Ax=0. Стандартные свойства обратимых матриц: (A ^ −1 ) ^ ⊤ = (A ^ ⊤) ^ −1 = A ^ − ⊤ (обратная A равна обратной транспонированной A) и (AB) ^−1 = B^−1* A^−1 (Левое значение, умноженное на B обратное, равно B обратное левое, умноженное на A обратное. Примечание. Выражения Wechat неудобно отображать, пожалуйста, проверьте исходные материалы для получения точных выражений).
Ортогональная матрица: матрица называется ортогональной матрицей, если A ∈ R^n×n удовлетворяет A^⊤=A^−1. Эквивалентно, для всех i , j принадлежащих [1,n], ортогональная матрица удовлетворяет:
Для вектора-строки A вышеуказанные свойства также выполняются. То есть все векторы-столбцы (или строки) A являются попарно ортогональными или взаимно нормальными векторами.
QR-разложение: любую матрицу A ∈ R^n×n можно разложить на произведение ортогональной матрицы и верхней треугольной матрицы: A=QR
где Q ∈ R^n×n — ортогональная матрица, а R ∈ R^n×n — верхнетреугольная матрица. Разложение QR полезно при решении систем линейных уравнений, оно имеет вычислительную сложность O (n ^ 3) и численно устойчиво. Чтобы решить систему линейных уравнений Ax=b с QR-разложением, мы сначала умножаем обе части уравнения на Q^⊤, т. е. Q^⊤QRx = Rx = Q^⊤b. Затем находим Rx = Q^⊤b обратной подстановкой.
2.2 Норма
Нормы используются для измерения размера матрицы или, соответственно, длины вектора. Норма — это функция, которая отображает R^mxn (или R^n) в R. Формально:
Определение 1: Любая функция, удовлетворяющая || · ||: R^m×n → R, и следующие свойства, называется нормой:
- Неотрицательность: ||A||≥0;||A||=0 тогда и только тогда, когда A=0;
- Тригонометрическое неравенство: ||A+B ||≤||A ||+||B ||;
- Скалярный закон умножения: ||αA ||=|α|||A||, α∈R.
Легко доказываются следующие два свойства:
- || A ||=|| -A ||
- |||А ||-||В |||≤ ||А-В ||
Второе свойство называется неравенством перевернутого треугольника.
2.3 Векторная норма
Учитывая n-мерный вектор x и целое число p > 1, мы можем определить векторную p-норму как:
Наиболее распространенные векторные p-нормы:
- 1-норма:
- Евклидова (2) норма:
- Бесконечная (максимальная) норма:
Учитывая n-мерные векторы x, y, мы можем использовать p-норму как верхнюю грань скалярного произведения, то есть неравенство Коши-Шварца можно записать как:
В общем, это неравенство утверждает, что евклидову норму двух векторов можно использовать в качестве супремума для их скалярного произведения, а неравенство Гёльдера утверждает, что:
Легко доказываются следующие свойства неравенства векторной p-нормы:
2.4 Индуктивная матричная норма
Учитывая матрицу A порядка m × n и целое число p > 1, мы определяем p-норму матрицы как:
Как правило, наша наиболее часто используемая матричная p-норма:
- 1-норма, берущая максимум суммы столбцов матрицы и абсолютного значения:
- Бесконечная норма, берущая максимум суммы строк матрицы и абсолютного значения:
- 2-норма,
Этот ряд норм называется «индуцированным», потому что они достигаются ненулевым вектором x, не зависящим от A и p. Следовательно, вообще говоря, существует единичный вектор нормы (единичная норма в p-норме) x Пусть ||A||p = ||Ax||p. Индуктивная матричная p-норма подчиняется следующему закону субмультипликативности:
Кроме того, p-норма матрицы инвариантна к элементарным преобразованиям матриц, т.е. ||PAQ||p = ||A||p, где P и Q — матрицы элементарных преобразований соответствующих размерностей. Аналогично, если мы рассмотрим матричное разбиение:
Тогда норма подматрицы связана с нормой всей матрицы: т.е. ||B||p
Кроме того, ||A^T||1 = ||A||∞, ||A^T||∞ = ||A||1. Транспонирование влияет на бесконечную норму и 1-норму матрицы, но не на 2-норму, т.е. ||A^T||2 = ||A||2. Точно так же на 2-норму матрицы не влияет операция предварительного (после) умножения матрицы, где ее столбцы (или строки) являются ортонормированными векторами: ||UAV^T||2 = ||A||2 , где U и V — ортогональные матрицы соответствующих размерностей (U^T*U = I и V^T*V = I).
2.6 Разложение по сингулярным числам
Мы знаем, что квадратные матрицы можно разложить на собственные значения и собственные векторы, но неквадратные матрицы не могут добиться разложения по собственным значениям. Таким образом, разложение по сингулярным значениям (SVD) является наиболее важным методом факторизации матриц в каждой матрице, потому что не все матрицы могут быть собственными разложениями, но все матрицы могут быть разложением по сингулярным значениям.
Определение 6. Для матрицы A ∈ R^m×n мы определяем полное SVD как:
где U ∈ R^m×m и V ∈ R^n×n — ортогональные матрицы, содержащие левый и правый сингулярные векторы матрицы A соответственно, а Σ ∈ R^m×n — диагональная матрица, где сингулярные числа числа A в основном убывают по диагонали.
Мы часто используем u_i (или v_j), i=1,..., m (или j=1,..., n) для обозначения столбцов матрицы U (или V). Опять же, мы будем использовать σ_i, i = 1,..., min{m, n} для сингулярных значений:
Сингулярные значения A неотрицательны и их количество равно min{m, n}. Число ненулевых сингулярных значений A равно рангу A. В силу ортогональной инвариантности получаем:
где P и Q — ортогональные матрицы соответствующих размерностей (P^TP = I и Q^TQ = I). Другими словами, сингулярные значения PAQ такие же, как сингулярные значения A.
Очень важны следующие неравенства с участием сингулярных значений матриц A и B. Во-первых, если и A, и B находятся на R^m×n, для всех i = 1,..., min{m, n},
Во-вторых, если A ∈ R^p×m и B ∈ R^m×n, для всех i = 1, ..., min{m, n},
где σ_1(A) = ||A||_2. Нас часто интересует сохранение только ненулевых сингулярных значений и соответствующих левых и правых сингулярных векторов (матрицы A). Для матрицы A ∈ R^m×n и rank(A)=ρ мы можем определить ее разреженное SVD.
Определение 9. Для матрицы A ∈ R^m×n с рангом ρ ≤ min{m, n} определим разреженное SVD как:
где U ∈ R^m×ρ и V ∈ R^n×ρ — попарно ортогональные столбцы, содержащие левые и правые сингулярные векторы, соответствующие ненулевым сингулярным значениям (т. е. U^TU = I и V^TV = I). матрица ; Σ ∈ R^ρ×ρ — диагональная матрица, в которой ненулевые сингулярные числа A убывают по диагонали.
Если A неособое, мы можем вычислить его обратное с помощью SVD:
(Если A неособая, то она квадратная и имеет полный ранг, и в этом случае разреженная SVD и полная SVD совпадают). Как мы все знаем, SVD очень важна, и наилучшее приближение k-ранга любой матрицы может быть получается по СВД рассчитать.
Теорема 10. Пусть A = UΣV^⊤ ∈ R^m×n — разреженная SVD матрицы A, k
Впоследствии,
Другими словами, приведенная выше теорема утверждает, что если мы найдем k-ранговую аппроксимацию матрицы A, которая минимизирует 2-норму или норму Фробениуса матрицы «ошибок» (т. е. минимизирует разницу между A и ее аппроксимацией), то нам нужно сохранить верхние k сингулярных значений A и соответствующие левый и правый сингулярные векторы.
Мы будем часто использовать следующие обозначения: пусть U_k ∈ R^m×k (или V_k ∈ R^n×k) обозначает матрицу верхних k левых (или правых) сингулярных векторов матрицы A, пусть Σ_k ∈ R^k× k Представляет диагональную матрицу, содержащую k верхних сингулярных значений A . Аналогично, пусть U_k,⊥ ∈ R^m×(ρ−k) (или V_k,⊥ ∈ R^n×(ρ−k)) обозначает нижние ρ-k ненулевых левых (или правых) сингулярных векторов матрицы A. , то пусть Σ_k,⊥ ∈ R^(ρ−k)×(ρ−k) обозначает диагональную матрицу, содержащую нижние ρ-k сингулярных значений матрицы A. Потом,
2.9 Псевдообращение Мура-Пенроуза
Для неквадратных матриц обратная матрица не определена. Очень хорошо известный обобщенный метод обращения матриц, псевдообратный метод Мура-Пенроуза, добился определенного прогресса в таких задачах. Формально, для матрицы A порядка m × n матрица A † является псевдообратной Мура-Пенроуза матрицы A, если она удовлетворяет следующим свойствам:
Для матрицы A порядка m × n ранга ρ ее разреженное сингулярное разложение можно выразить как:
Разреженное сингулярное разложение его псевдоинверсии Мура-Пенроуза A† может быть выражено как:
Если A — матрица размера n на n полного ранга, то A† равна обратной матрице A. Если A представляет собой матрицу полного ранга столбца m × n, то A † A равна единичной матрице n-го порядка, а AA † является матрицей проекции на столбец A матрицы. Если A — матрица полного ранга строки, то AA† — единичная матрица порядка m, а A†A — матрица проекции на строку матрицы A.
Что касается псевдообратного произведения двух матриц, существуют следующие особенно важные свойства: для матрицы порядка m × p Y1 и матрицы порядка p × n Y2 и удовлетворяют Rank (Y1) = Rank (Y2), что то есть ранги равны, [9, теорема 2.2.3] показывает:
(Очень важно подчеркнуть условие равенства рангов: поскольку обратное умножение двух матриц всегда эквивалентно умножению обратных матриц, но этот вывод не выполняется для общего псевдообратного Мура-Пенроуза [9] ) Кроме того, базисное пространство псевдообратной матрицы Мура-Пенроуза связано со всеми реальными матрицами. Учитывая матрицу A и псевдообращение Мура-Пенроуза A† к A, пространство столбцов A† можно определить как:
Пространство столбца A† ортогонально нулевому пространству, а нулевое пространство A† можно определить как: