Справочник по математике
Изучите векторы, матрицы, аффинную и пространственную геометрию, решетки, линейные системы, преобразования, разложения, метод наименьших квадратов и PCA с помощью примеров.
Кратчайшее смещение от точки до плоскости параллельно нормальному вектору плоскости.
Целочисленные комбинации двух базисных векторов покрывают плоскость фундаментальными параллелограммами равной площади.
97 терминов
Объекты и формы
Scalar
aОдиночное числовое значение, используемое для масштабирования векторов или матриц.
Используйте скаляры для весов, коэффициентов, скоростей обучения, температур и величин.
3[2, -1] = [6, -3].Объекты и формы
Vector
v ∈ ℝⁿУпорядоченный список компонентов, который может представлять направление, положение, характеристики или состояние.
Используйте векторы для представления координат, сигналов, признаков, вложений и параметров модели.
v = [3, 4] has two components.Объекты и формы
Matrix
A ∈ ℝᵐˣⁿПрямоугольный массив чисел, расположенных в строках и столбцах.
Используйте матрицы для хранения наборов данных, линейных систем, преобразований, изображений и весов.
A = [[1, 2], [3, 4]].Объекты и формы
Tensor
T ∈ ℝᵈ¹ˣ⋯ˣᵈᵏМногомерный массив, который обобщает скаляры, векторы и матрицы.
Используйте тензоры для пакетов, изображений, видео, активаций модели и многомерных научных данных.
Пакет из 32 изображений RGB размером 224×224 имеет форму 32×3×224×224.Объекты и формы
Shape
m × nУпорядоченные размеры осей массива.
Проверяйте формы перед сложением, умножением, расширением, изменением формы и вводом данных в модель.
Большинство ошибок при умножении матриц возникают из-за несовместимых внутренних размеров.
Матрица 3×4 имеет 3 строки и 4 столбца.Операции с векторами
Vector addition
u + vПокомпонентное сложение векторов с одинаковой размерностью.
Используйте это для объединения смещений, сил, сигналов, обновлений или вкладов признаков.
[1, 2] + [3, -1] = [4, 1].Операции с векторами
Scalar multiplication
cvУмножение каждого компонента вектора на один и тот же скаляр.
Используйте это для масштабирования величины, изменения направления или применения взвешенного обновления.
-2[3, 1] = [-6, -2].Операции с векторами
Dot product
u · vСумма произведений соответствующих компонент векторов, дающая скаляр.
Используйте это для подобия, проекций, работы, оценок внимания и выходных данных линейной модели.
[1, 2, 3] · [4, 0, -1] = 1.Операции с векторами
Cross product
u × vТрехмерный вектор, перпендикулярный двум входным векторам, с величиной, равной площади параллелограмма, образованного ими.
Используйте это для нормалей к поверхности, крутящего момента, ориентации и 3D-геометрии.
Стандартное векторное произведение определено только для трех измерений, за исключением менее распространенного семимерного аналога.
[1,0,0] × [0,1,0] = [0,0,1].Операции с векторами
Vector norm
‖v‖Неотрицательная мера размера вектора, удовлетворяющая аксиомам нормы.
Используйте норму для измерения величины, расстояния, ошибки, регуляризации и сходимости.
For v=[3,4], ‖v‖₂=5.Операции с векторами
Unit vector
v/‖v‖Вектор, норма которого равна 1.
Используйте это для сохранения направления при удалении величины и для построения ортонормированных базисов.
[3,4]/5 = [0.6,0.8].Операции с векторами
Euclidean distance
‖u-v‖₂Прямолинейное расстояние между двумя точками, представленными в виде векторов.
Используйте это для геометрии, поиска ближайших соседей, кластеризации и измерения ошибок, когда масштабы сопоставимы.
Расстояние от [1,1] до [4,5] равно 5.Операции с векторами
Cosine similarity
u·v/(‖u‖‖v‖)Косинус угла между двумя ненулевыми векторами, измеряющий направленность.
Используйте это для сравнения векторных представлений текста или признаков высокой размерности, когда важно, чтобы величина имела меньшее значение.
Косинусное сходство не определено для нулевого вектора и может скрывать значительные различия в величине.
[1,0] and [2,0] have cosine similarity 1.Операции с векторами
Orthogonal vectors
u·v=0Векторы с нулевым скалярным произведением.
Используйте ортогональность для разделения независимых направлений, упрощения проекций и построения устойчивых базисов.
[1,2] · [2,-1] = 0, следовательно, векторы ортогональны.Операции с векторами
Vector projection
projᵤ(v)Компонента одного вектора, лежащая в направлении другого вектора или подпространства.
Используйте это для разложения, метода наименьших квадратов, теней и удаления компонент в определенном направлении.
proj_[1,0]([3,4]) = [3,0].Операции с матрицами
Matrix addition
A+BПокомпонентное сложение матриц с одинаковой формой.
Используйте это для объединения линейных эффектов, обновлений остатков, изображений или накопленных данных.
[[1,2],[3,4]] + [[5,6],[7,8]] = [[6,8],[10,12]].Операции с матрицами
Matrix multiplication
ABОперация над строками и столбцами, которая комбинирует линейные преобразования, когда внутренние размеры совпадают.
Используйте это для преобразований координат, слоев нейронных сетей, распространения по графам и решения систем уравнений.
Умножение матриц, как правило, не коммутативно: AB может отличаться от BA, или один из порядков может быть неопределен.
A₂ˣ₃B₃ˣ₄ дает C₂ˣ₄.Операции с матрицами
Transpose
AᵀМатрица, образованная путем обмена строками и столбцами.
Используйте это для скалярных произведений, ковариации, нормальных уравнений, проверки симметрии и изменения ориентации.
If A=[[1,2,3],[4,5,6]], then Aᵀ=[[1,4],[2,5],[3,6]].Операции с матрицами
Identity matrix
IКвадратная матрица с единицами на главной диагонали и нулями в остальных местах.
Используйте это как мультипликативную единицу и для описания неизменных координат.
AI = IA = A.Операции с матрицами
Inverse matrix
A⁻¹Матрица, удовлетворяющая условию AA⁻¹=A⁻¹A=I для обратимой квадратной матрицы A.
Используйте это концептуально для обратного преобразования и решения уравнения Ax=b.
Программное обеспечение для численных расчетов обычно должно решать Ax=b напрямую, а не явно вычислять A⁻¹.
For A=[[2,0],[0,4]], A⁻¹=[[1/2,0],[0,1/4]].Операции с матрицами
Determinant
det(A)Скаляр для квадратной матрицы, который измеряет изменение объема со знаком и указывает на обратимость.
Используйте это для проверки сингулярности и анализа ориентации или изменения объема под преобразованием.
det([[a,b],[c,d]]) = ad - bc.Операции с матрицами
Trace
tr(A)Сумма элементов главной диагонали квадратной матрицы.
Используйте это для тождеств, связанных с собственными значениями, анализа ковариации, матричного исчисления и оптимизации.
tr([[2,1],[3,4]]) = 6.Операции с матрицами
Matrix rank
rank(A)Количество линейно независимых строк или столбцов в матрице.
Используйте это для измерения размерности информации, определения структуры решения и обнаружения избыточных признаков.
rank([[1,2],[2,4]]) = 1.Операции с матрицами
Symmetric matrix
A=AᵀКвадратная матрица, равная своей транспонированной матрице.
Используйте это для ковариации, квадратичных форм, неориентированных графов и вещественной ортогональной разложения.
[[2,3],[3,5]] is symmetric.Операции с матрицами
Orthogonal matrix
QᵀQ=IРеальная квадратная матрица, столбцы и строки которой образуют ортонормированные множества.
Используйте это для вращений, отражений, устойчивых факторизаций и преобразований, сохраняющих норму.
Q⁻¹ = Qᵀ для ортогональной матрицы.Операции с матрицами
Diagonal matrix
DМатрица, у которой все элементы вне главной диагонали равны нулю.
Используйте это для независимого масштабирования и эффективных вычислений степеней, обратных величин и преобразований.
diag(2,3)^4 = diag(16,81).Линейные системы
System of linear equations
Ax=bНабор линейных уравнений, которые должны быть выполнены одновременно.
Используйте это для балансировки, подгонки, сетей, цепей, ограничений и восстановления.
x+y=5 and 2x-y=1 give x=2, y=3.Линейные системы
Augmented matrix
[A|b]Компактное представление матрицы, которое добавляет правую часть к матрице коэффициентов линейной системы.
Используйте это для приведения матрицы к ступенчатому виду без повторного написания переменных.
x+2y=5, 3x-y=4 becomes [[1,2|5],[3,-1|4]].Линейные системы
Elementary row operation
Перестановка строк, умножение строки на ненулевое значение или добавление кратного одной строки к другой.
Используйте эти операции, сохраняющие решение, для упрощения линейной системы.
R₂ ← R₂ - 3R₁.Линейные системы
Row echelon form
REFФорма матрицы с опорными элементами, движущимися вправо, и нулями ниже каждого опорного элемента.
Используйте это для обратной подстановки, вычисления ранга и определения свободных переменных.
[[1,2,3],[0,1,4],[0,0,0]] находится в ступенчатой форме.Линейные системы
Reduced row echelon form
RREFФорма ступенчатого преобразования, в которой каждый опорный элемент равен 1 и является единственным ненулевым элементом в своем столбце.
Используйте это для получения уникальных решений, свободных переменных, ранга и базисов нулевого пространства непосредственно.
RREF([[1,2],[2,4]]) = [[1,2],[0,0]].Линейные системы
Gaussian elimination
Операции над строками, которые преобразуют систему в эшелонированную форму, с последующей обратной подстановкой.
Используйте это как общий метод решения умеренно сложных линейных систем вручную или в программном обеспечении.
Устраните x из нижних строк, затем решайте уравнение, начиная с последнего опорного элемента и двигаясь вверх.Линейные системы
Gauss-Jordan elimination
Операции над строками выполняются до тех пор, пока расширенная матрица не примет эшелонированную форму.
Используйте это, когда требуется явное полное решение или обратная матрица.
Приведите [A|I] к виду [I|A⁻¹], когда A обратима.Линейные системы
Consistent system
Линейная система, которая имеет хотя бы одно решение.
Используйте ранг или приведение к ступенчатому виду для различения уникальных, бесконечных и не существующих решений.
Строка [0 0 | 1] доказывает, что система несовместна.Векторные пространства
Vector space
VМножество, элементы которого можно складывать и умножать на скаляр, удовлетворяя аксиомам векторного пространства.
Используйте это для обработки координат, многочленов, функций, сигналов и матриц в рамках одной системы.
ℝ³ и множество полиномов степени не более 2 являются векторными пространствами.Векторные пространства
Subspace
W ⊆ VПодмножество векторного пространства, которое само замкнуто относительно векторного сложения и скалярного умножения.
Используйте это для описания ограниченных направлений, множеств решений, пространств признаков и инвариантной структуры.
Плоскость x+y+z=0, проходящая через начало координат, является подпространством ℝ³.Векторные пространства
Span
span{v₁,…,vₖ}Множество всех линейных комбинаций заданного набора векторов.
Используйте это для описания всех направлений или выходных данных, доступных из генераторов.
span{[1,0],[0,1]} = ℝ².Векторные пространства
Linear independence
Набор векторов является линейно независимым, когда только нулевые коэффициенты приводят к нулевому вектору.
Используйте это для обнаружения избыточных направлений и выбора базиса.
[1,0] и [0,1] линейно независимы.Векторные пространства
Basis
Линейно независимый набор, охватывающий векторное пространство.
Используйте это для присвоения координат и представления каждого вектора однозначно.
{[1,0],[0,1]} является стандартным базисом ℝ².Векторные пространства
Dimension
dim(V)Количество векторов в любом базисе векторного пространства конечной размерности.
Используйте это для измерения независимых степеней свободы.
dim(ℝ⁴)=4.Векторные пространства
Column space
Col(A)Линейная оболочка столбцов матрицы, равная всем выходным данным Ax.
Используйте это для определения, решаемо ли уравнение Ax=b, и какие выходные данные может произвести преобразование.
Ax=b is solvable exactly when b belongs to Col(A).Векторные пространства
Null space
Null(A)Множество векторов x, удовлетворяющих Ax=0.
Используйте это для описания недоступных направлений, однородных решений, избыточности параметров и ограничений.
Если A=[1 2], то Null(A)=span{[-2,1]}.Векторные пространства
Rank-nullity theorem
rank(A)+nullity(A)=nДля матрицы с n столбцами, размерность столбцового пространства плюс размерность нулевого пространства равны n.
Используйте это для связи независимых выходных данных с потерянными степенями свободы входных данных.
Матрица 3×5 с рангом 3 имеет нулевую размерность 2.Линейные преобразования
Linear transformation
T(u+v)=T(u)+T(v)Отображение, сохраняющее векторное сложение и скалярное умножение.
Используйте это для моделирования вращения, масштабирования, проекции, фильтрации и линейных слоев.
T([x,y])=[2x,y] масштабирует направление x в 2 раза.Линейные преобразования
Kernel
ker(T)Множество входных данных, которые отображаются в нулевой вектор линейным преобразованием.
Используйте это для обнаружения информации, потерянной в результате преобразования, и проверки инъективности.
T является взаимно однозначным отображением тогда и только тогда, когда ker(T)={0}.Линейные преобразования
Image
im(T)Множество всех выходных значений, полученных в результате преобразования.
Используйте это для описания доступных выходных данных и проверки сюръективности.
Для матричного преобразования T(x)=Ax, im(T)=Col(A).Линейные преобразования
Change of basis
Повторное представление того же вектора или преобразования с использованием другой координатной системы.
Используйте это для выравнивания координат с геометрией, упрощения оператора или перехода между локальными и глобальными системами координат.
If P contains new basis vectors as columns, then [v]new=P⁻¹v.Пространственная и аффинная геометрия
Point
PМестоположение в аффинном пространстве, которое само по себе не имеет величины или направления.
Используйте точки для обозначения позиций, и вычитайте две точки, чтобы получить вектор смещения.
Сложение двух точек не определено однозначно без выбора начала координат или аффинной комбинации.
Для P=(1,2) и Q=(4,6), смещение Q-P=[3,4].Пространственная и аффинная геометрия
Position vector
OPВектор от выбранного начала координат O к точке P.
Используйте ее для представления точек с координатами после фиксации начала координат и базиса.
If O=(0,0,0) and P=(2,-1,3), then OP=[2,-1,3].Пространственная и аффинная геометрия
Affine space
Пространство точек, в котором разности точек являются векторами, но не существует предпочтительного начала координат.
Используйте ее для моделирования геометрии независимо от произвольного начала координат.
Плоскость, сдвинутая в аффинное пространство, даже если она не проходит через начало координат.Пространственная и аффинная геометрия
Affine combination
ΣαᵢPᵢ, Σαᵢ=1Взвешенная комбинация точек, коэффициенты которой в сумме дают 1.
Используйте ее для интерполяции, центроидов, барицентрических координат и аффинных преобразований.
Середина отрезка, соединяющего точки P и Q, равна 0.5P + 0.5Q.Пространственная и аффинная геометрия
Parametric equation of a line
x=p+tvЛиния, представленная точкой p и ненулевым направляющим вектором v.
Используйте ее для генерации точек на прямой и решения задач пересечения с плоскостями или другими прямыми.
Through p=(1,2) with v=[3,-1]: x(t)=(1+3t,2-t).Пространственная и аффинная геометрия
Equation of a plane
n·(x-p)=0Плоскость, описанная точкой p и ненулевым нормальным вектором n.
Используйте ее для границ классификации, обрезки, тестов на столкновения и геометрических ограничений.
Если n=[1,2,3] и p=(1,0,0), то уравнение плоскости: x+2y+3z=1.Пространственная и аффинная геометрия
Hyperplane
w·x=bАффинное подпространство размерности n-1 в пространстве n-мерном.
Используйте ее в качестве границы принятия решений, ограничивающей поверхности или плоскости более высокой размерности.
В ℝ⁴, w·x=b определяет трехмерную гиперплоскость.Пространственная и аффинная геометрия
Normal vector
nВектор, перпендикулярный линии, плоскости, касательной поверхности или гиперплоскости.
Используйте ее для определения плоскостей, вычисления расстояний, отражения векторов и определения ориентации поверхности.
Для 2x-y+3z=4, нормальный вектор равен [2,-1,3].Пространственная и аффинная геометрия
Line-plane intersection
Точка, найденная путем подстановки параметрической прямой в уравнение плоскости и решения относительно ее параметра.
Используйте ее для трассировки лучей, рендеринга, обнаружения столкновений и геометрического построения.
Если n·v=0, то прямая параллельна плоскости или полностью лежит в ней.
Substitute x=p+tv into n·x=d, then solve t=(d-n·p)/(n·v).Пространственная и аффинная геометрия
Distance from a point to a line
Длина кратчайшего перпендикулярного отрезка от точки до прямой.
Используйте ее для запросов на ближайший путь, подгонки, полей обнаружения столкновений и геометрических ошибок.
Для прямой p+tv, расстояние(P,прямая)=‖(P-p)-projᵥ(P-p)‖.Пространственная и аффинная геометрия
Distance from a point to a plane
|n·P-d|/‖n‖Абсолютное знаковое уравнение плоскости в точке, нормализованное длиной нормального вектора.
Используйте ее для полей, обрезки, обнаружения столкновений и обработки облаков точек.
Расстояние от (1,2,3) до z=0 равно 3.Пространственная и аффинная геометрия
Projection onto a plane
Ближайшая точка на плоскости, полученная путем удаления нормальной компоненты смещения.
Используйте ее для привязки точек к поверхностям, разрешения ограничений и разложения движения.
For plane n·x=d, Pproj=P-((n·P-d)/‖n‖²)n.Пространственная и аффинная геометрия
Reflection across a plane
Преобразование, которое инвертирует нормальную компоненту, сохраняя компоненты, параллельные плоскости.
Используйте ее для геометрии отражений, направлений отскока, симметрии и графики.
Для плоскости, проходящей через начало координат, отражение равно v - 2projₙ(v).Пространственная и аффинная геометрия
Barycentric coordinates
α+β+γ=1Веса, которые выражают точку как аффинную комбинацию вершин симплекса.
Используйте их для триангуляционной интерполяции, проверки принадлежности точки треугольнику, мешей и конечных элементов.
P=αA+βB+γC with α+β+γ=1.Пространственная и аффинная геометрия
Area from a determinant
|det([u v])|Абсолютный определитель двух векторных ребер плоскости, равный площади их параллелограмма.
Используйте ее для площади многоугольника, тестов на ориентацию, якобианов и преобразований координат.
u=[3,0], v=[1,2] give area |3×2-0×1|=6.Пространственная и аффинная геометрия
Scalar triple product
u·(v×w)Мера объема со знаком для параллелепипеда, образованного тремя трехмерными векторами.
Используйте ее для объема, копланарности и тестов ориентации в трехмерном пространстве.
Объем равен |u·(v×w)|.Пространственная и аффинная геометрия
Orientation
sign(det)Знак, указывающий ориентацию или порядок по часовой стрелке или против часовой стрелки последовательности базиса или точки.
Используйте ее для алгоритмов построения многоугольников, определения закрученности, нормалей и согласованности системы координат.
В ℝ², det([B-A,C-A])>0 означает, что точки A, B, C расположены в порядке против часовой стрелки.Пространственная и аффинная геометрия
Homogeneous coordinates
[x,y,z,w]Координаты с дополнительной компонент масштаба, которые представляют аффинные точки и проективные направления единообразно.
Используйте их для объединения преобразований: трансляции, вращения, масштабирования, перспективы и проекции в матричной форме.
Однородный вектор должен быть нормализован тщательно, когда его последний компонент не равен нулю; нулевой последний компонент представляет направление в бесконечности.
Точка (x,y) в ℝ² становится [x,y,1], в то время как направление становится [vx,vy,0].Геометрия решеток
Lattice
L=BℤᵏДискретный набор точек, образованный всеми целыми комбинациями линейно независимых базисных векторов.
Используйте решетки в дискретной геометрии, кодировании, криптографии, оптимизации и кристаллографии.
For b₁=[2,0], b₂=[1,3], L={z₁b₁+z₂b₂ | z₁,z₂∈ℤ}.Геометрия решеток
Integer lattice
ℤⁿРешетка всех n-мерных векторов с целыми координатами.
Используйте ее в качестве стандартной координатной решетки и в качестве справочной для подрешеток и целочисленной оптимизации.
ℤ² содержит каждую точку (m,n), где m,n∈ℤ.Геометрия решеток
Lattice basis
B=[b₁ … bₖ]Линейно независимый набор, чьи целые комбинации генерируют решетку.
Используйте ее для кодирования, перечисления, преобразования и вычисления свойств решетки.
Решетка имеет бесконечно много возможных базисов, часто с очень разными длинами векторов и углами.
Столбцы [2,0] и [1,3] образуют базис двумерной решетки.Геометрия решеток
Lattice rank
rank(L)Количество векторов в базисе решетки, равное размерности ее вещественного линейного охвата.
Используйте ее для различения решеток полного ранга и решеток меньшей размерности в окружающем пространстве.
Решетка, порожденная векторами [1,0,0] и [0,1,0], имеет ранг 2 в ℝ³.Геометрия решеток
Lattice point
BzТочка, полученная путем умножения матрицы базиса решетки на целочисленный вектор.
Используйте ее в качестве дискретного кандидата в задачах поиска ближайшей точки, упаковки, кодирования и задач с целочисленными ограничениями.
Если B=[[2,1],[0,3]] и z=[2,-1], то Bz=[3,-3].Геометрия решеток
Fundamental parallelepiped
P(B)Полуоткрытый регион, образованный коэффициентами базиса между 0 (включительно) и 1 (исключительно).
Используйте ее в качестве повторяющейся ячейки, содержащей один представитель каждого смежного класса по модулю решетки.
P(B)={Bt | 0≤tᵢ<1}.Геометрия решеток
Lattice determinant
det(L)Объем фундаментальной области, также называемый объемом решетки.
Используйте ее для измерения плотности решетки и сравнения расстояний между решетками полного ранга.
For square basis B, det(L)=|det(B)|; B=[[2,1],[0,3]] gives 6.Геометрия решеток
Sublattice
L'⊆LПодгруппа решетки, которая сама является решеткой в том же вещественном пространстве или в пространстве меньшей размерности.
Используйте ее для наложения дополнительных условий сравнения или сравнения вложенных дискретных структур.
2ℤ² - подрешетка ℤ².Геометрия решеток
Lattice index
[L:L']Количество смежных классов подрешетки L' полного ранга в решетке L.
Используйте ее для измерения степени разреженности подрешетки и установления связи между определителями вложенных решеток.
[ℤ²:2ℤ²]=4 and det(2ℤ²)=4det(ℤ²).Геометрия решеток
Unimodular matrix
U∈GLₙ(ℤ)Целочисленная квадратная матрица с определителем 1 или -1, обратная которой также является целочисленной.
Используйте ее для изменения базиса решетки без изменения самой решетки.
Если B'=BU с det(U)=±1, то B и B' порождают одну и ту же решетку.Геометрия решеток
Equivalent lattice bases
B'=BUДве базы, связанные унимодулярной целочисленной матрицей, которые порождают одну и ту же решетку.
Используйте ее для замены длинного, смещенного базиса более коротким и более ортогональным.
B и B'=B[[1,1],[0,1]] являются эквивалентными базисами.Геометрия решеток
Gram matrix of a lattice basis
G=BᵀBМатрица, содержащая все парные скалярные произведения базисных векторов.
Используйте ее для вычисления длин, углов, объемов и квадратичных форм в координатах базиса.
Для целочисленного вектора z, ‖Bz‖²=zᵀGz.Геометрия решеток
Gram-Schmidt for lattice bases
bᵢ*Ортогонализация, используемая для анализа базиса решетки без создания другого базиса решетки.
Используйте ее для вычисления коэффициентов проекции, качества базиса и шагов сокращения LLL.
Векторы Грама-Шмидта являются аналитическими вспомогательными величинами и не обязательно должны быть точками решетки.
b₂*=b₂-μ₂₁b₁* , где μ₂₁=⟨b₂,b₁*⟩/‖b₁*‖².Геометрия решеток
Orthogonality defect
∏‖bᵢ‖/det(L)Мера того, насколько полноранговый базис отличается от ортогональности.
Используйте ее для сравнения качества базиса и прогнозирования вычислительной или перечислительной сложности.
Дефект равен 1 для ортогональной базы и больше или равен 1 в противном случае.Геометрия решеток
Dual lattice
L*Множество векторов, имеющих целые скалярные произведения с каждым вектором в L.
Используйте ее в анализе Фурье, теории кодирования, реципрочной геометрии и оценках переноса.
Для полнорангового базиса B, двойной базис - B⁻ᵀ.Геометрия решеток
Shortest vector problem
SVPПоиск кратчайшего ненулевого вектора в решетке при выбранной норме.
Используйте ее для понимания геометрии решеток, качества сокращения и криптографической стойкости на основе решеток.
Find z≠0 minimizing ‖Bz‖.Геометрия решеток
Closest vector problem
CVPПоиск точки решетки, ближайшей к целевой точке.
Используйте ее для декодирования, квантования, решения целочисленных систем линейных уравнений и анализа безопасности на основе решеток.
Найдите z, минимизирующий ‖Bz-t‖.Геометрия решеток
Successive minima
λᵢ(L)Радиусы, необходимые для охвата возрастающего числа линейно независимых векторов решетки.
Используйте их для описания формы решетки, выходящей за рамки только самого короткого вектора.
λ₁(L) – длина самого короткого вектора, в то время как λₖ(L) достигает k линейно независимых векторов.Геометрия решеток
Minkowski's convex body theorem
Условие объема, обеспечивающее, что выпуклое тело, симметричное относительно начала координат, содержит ненулевую точку решетки.
Используйте ее для доказательства оценок для коротких векторов решетки и результатов в теории алгебраических чисел.
Достаточно большое выпуклое тело, симметричное относительно начала координат, должно содержать ненулевую точку L.Геометрия решеток
Lattice sphere packing
Размещение равных непересекающихся сфер в точках решетки и измерение доли занимаемого пространства.
Используйте ее в теории кодирования, связи, дискретной геометрии и оптимизации в пространствах высокой размерности.
Радиус упаковки равен половине длины кратчайшего ненулевого вектора решетки.Геометрия решеток
Voronoi cell of a lattice
Регион точек, находящихся как минимум на таком же расстоянии от одной точки решетки, как и от любой другой точки решетки.
Используйте это для понимания декодирования с использованием ближайшей точки решетки и геометрической формы областей CVP.
Ячейка Вороного вокруг 0 покрывает пространство сдвигами решетки.Геометрия решеток
Lattice basis reduction
Замена базиса решетки на эквивалентный базис с более короткими и более близкими к ортогональным векторами.
Используйте ее для улучшения перечисления, поиска целочисленных соотношений, криптоанализа и численного поведения.
Уменьшенный базис генерирует ту же решетку, но более четко отображает ее геометрию.Геометрия решеток
LLL algorithm
LLLАлгоритм, работающий за полиномиальное время, который генерирует базис, удовлетворяющий условиям уменьшения размера и условиям Ловаша.
Используйте ее для практического приближенного поиска коротких векторов, факторизации многочленов, криптоанализа и целочисленных соотношений.
LLL дает гарантию качества для приближенного короткого вектора, но не обязательно является точным решением задачи SVP.
Алгоритм LLL многократно уменьшает размер коэффициентов Грама-Шмидта и меняет базисные векторы, когда выполняется условие Ловаша.Собственные значения и разложения
Eigenvalue
Av=λvСкаляр λ, на который линейное преобразование масштабирует ненулевой собственный вектор, не изменяя его направление.
Используйте собственные значения для изучения устойчивости, долгосрочной динамики, ковариации, графов и дифференциальных уравнений.
Для A=diag(2,3), собственные значения равны 2 и 3.Собственные значения и разложения
Eigenvector
Av=λv, v≠0Не нулевое направление, сохраняемое линейным преобразованием с учетом скалярного масштабирования.
Используйте это для идентификации естественных осей, доминирующих мод, стационарных состояний и главных направлений.
Для A=diag(2,3), [1,0] является собственным вектором для λ=2.Собственные значения и разложения
Characteristic polynomial
det(A-λI)Многочлен, корни которого являются собственными значениями квадратной матрицы.
Используйте это для символьных вычислений собственных значений и теоретического анализа матриц малого размера.
Для A=[[2,0],[0,3]], det(A-λI)=(2-λ)(3-λ).Собственные значения и разложения
Diagonalization
A=PDP⁻¹Представление матрицы с использованием диагональной матрицы собственных значений и базиса собственных векторов.
Используйте это для упрощения степеней матриц, рекуррентных соотношений и линейных динамических систем.
Не у каждой квадратной матрицы достаточно независимых собственных векторов, чтобы ее можно было диагонализовать.
A^k=PD^kP⁻¹ при диагонализуемой матрице A.Собственные значения и разложения
LU decomposition
PA=LUРазложение матрицы на нижне- и верхнетреугольные множители, иногда с перестановкой строк.
Используйте это для решения нескольких систем с одной и той же матрицей коэффициентов эффективно.
Factor PA=LU, then solve Ly=Pb and Ux=y.Собственные значения и разложения
QR decomposition
A=QRРазложение матрицы на ортогональную матрицу Q и верхнетреугольную матрицу R.
Используйте это для численных методов наименьших квадратов, ортонормированных базисов и алгоритмов вычисления собственных значений.
Решите задачу методом наименьших квадратов, используя Rx=Qᵀb после A=QR.Собственные значения и разложения
Singular value decomposition
A=UΣVᵀРазложение любой матрицы на матрицы ортогональных сингулярных векторов и неотрицательных сингулярных значений.
Используйте это для сжатия, шумоподавления, псевдообратных матриц, приближения с низким рангом и скрытой структуры.
Малые сингулярные значения могут усиливать шум при использовании в обратной или псевдообратной матрице.
Сохранение k наибольших сингулярных значений дает наилучшее приближение ранга k в 2-норме и норме Фробениуса.Собственные значения и разложения
Least squares
min ‖Ax-b‖₂Поиск параметров, которые минимизируют сумму квадратов остатков, когда линейная система не имеет точного решения или является переопределенной.
Используйте это для регрессии, калибровки, восстановления и подгонки зашумленных измерений.
Подгонка функции y≈mx+c путем минимизации суммы квадратов вертикальных остатков.Собственные значения и разложения
Principal component analysis
X≈UₖΣₖVₖᵀМетод снижения размерности, который находит ортогональные направления наибольшей дисперсии в центрированных данных.
Используйте это для визуализации, сжатия, шумоподавления или обобщения коррелированных числовых признаков.
PCA чувствителен к масштабу признаков, выбросам и предположению, что высокая дисперсия является информативной.
Центр X, вычислите его SVD, и спроецируйте на первые k правых сингулярных векторов.