计算机科学中的线性代数——软件开发人员必学

矩阵在计算机科学、统计学和应用数学中占有独特的地位。一个m×n矩阵可以描述有限元网格中m个对象（每个对象由n个特征描述）的离散微分算子信息；一个 n × n 正定矩阵可以编码所有 n 对对象之间的关系。网络中所有n对节点之间的相关性或边连接等。近年来，随着科学和计算机技术的发展，我们目睹了矩阵算法的理论和实践取得了令人兴奋的发展。其中最值得注意的是随机化的使用——通常假设输入数据由于生成机制而存在噪声——可以用作算法或计算资源来开发和改进基本矩阵问题，例如矩阵乘法、最小二乘法（LS )近似、低阶矩阵近似等算法。

随机数值线性代数 (RandNLA) 是一个跨学科研究领域，利用随机化作为计算资源来开发大规模线性代数问题的增强算法。基本上，RandNLA 来自理论计算（TCS），与数学（凸性分析、概率微积分、度量嵌入理论）以及应用数学（科学计算、信号处理、数值线性）密切相关。代数）。从应用角度来看，RandNLA 是机器学习、统计和数据分析的重要新工具。一些精心设计的实现在许多问题上都优于高度优化的软件库，例如最小二乘回归，同时还具有显着的可扩展性、并行计算和分发功能。此外，RandNLA为现代大规模数据分析提供了良好的算法和统计基础。

本章是对三种基本 RandNLA 算法的独立介绍：随机矩阵乘法、随机最小二乘求解器和使用随机。该算法计算矩阵的低秩近似。因此，本章与应用数学的许多领域，特别是与本书的许多其他章节密切相关。最重要的是，其中包括 G. Martinsson 的工作，他使用这些方法开发了一种改进的低秩矩阵近似求解器 [2]；以及 R. Vershynin 的工作，他开发了用于分析 RandNLA 的概率工具。算法[3]； J. Duchi 的工作，他以互补的方式使用随机方法来解决更一般的优化问题 [4]；以及 M. Maggioni 的工作，他使用这些方法作为更复杂、多尺度方法的构建块 [5]。

论文第二部分概述了线性代数的基础知识；第三部分概述离散概率的基础知识；第四部分介绍了矩阵乘法的随机算法；第五节介绍了最小二乘回归问题。第 6 章介绍了低秩近似的随机算法。最后，我们为感兴趣的读者提供了关于 RandNLA [6,7] 的另外两个介绍性资源。

2 线性代数

在本节中，我们简要概述本章中使用的线性代数的基本属性和数学符号。假设读者对线性代数有基本的了解（例如向量的内积和叉积、基本矩阵运算，例如加法、标量乘法、转置、上/下三角矩阵、矩阵向量乘法、矩阵乘法、矩阵、 ETC。）。

2.1 基础知识

我们完全关注线性空间中的矩阵和向量。我们使用符号 x ∈ R^n 来表示 n 维向量，注意向量以粗体小写字母书写。除非另有说明，所有向量均假定为列向量。所有具有 0 个元素的向量都用 0 表示，所有具有 1 个元素的向量都用 1 表示（类似于广播）；维度可以隐含在上下文中，也可以通过下标显式表示。

我们将使用粗体大写字母来表示矩阵。例如，A ∈ R^mxn 表示 mxn 阶矩阵； A_i*表示A的第i行的行向量，A_*i表示A的第i列。列向量。单位矩阵用I_n表示，其中n是矩阵的行数和列数。最后，e_i 表示 I_n 的第 i 列，即第 i 个规范基。

逆矩阵：如果存在满足以下条件的逆矩阵 A^-1 ∈ R^mxn，则矩阵 A ∈ R^mxn 被称为非奇异或可逆：

如果 A 都是列向量 (或行向量）是线性无关的，则 A 是可逆的。换句话说，不存在 Ax=0 的非零向量 x ∈ R^n。可逆矩阵的标准属性： (A^−1 )^⊤ = (A^⊤)^−1 = A^−⊤ （A 的逆矩阵的转置等于 A 的逆矩阵）和 ( AB)^−1 = B^−1* A^−1 （A的倒数乘以B等于B的倒数乘以A。注：微信表达式不方便显示，具体请查看原材料表达式）。

正交矩阵：如果矩阵 A ∈ R^n×n 满足 A^⊤=A^−1，则 A 称为正交矩阵。等价地讲，正交矩阵对于属于[1,n]的所有i,j满足：

对于行向量A也满足上述性质。也就是说，A 的每个列（或行）向量都是两两正交或相互正交的。

QR 分解：任意矩阵 A ∈ R^n×n 都可以分解为正交矩阵和上三角矩阵的乘积： A=QR

其中 Q ∈ R^n×n 正交矩阵 R ∈ R ^n×n 是上三角矩阵。 QR 分辨率对于求解线性方程组很有用，其计算复杂度为 O(n^3)，并且数值稳定。要通过 QR 分解求解线性方程组 Ax=b，首先将方程左边乘以 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 ||≤|| ||+|| B ||;
• 标量乘法定律： || αA ||=|α| || A||，αεR。

可以轻松证明以下两个性质：

• || ||=|| -A ||
• | || ||-||乙|| | ≤|| A-B ||

第二个性质称为倒三角不等式。

2.3 向量范数

如果给定一个n维向量x和一个整数p > 1，那么p范数向量可以定义如下：

最常见的向量p范数：

1-范数：

欧几里得 (2) 范数：

无限（最大）范数：

如果给定 n 维向量 x、y，则 p-范数可以用作优越性，即柯西-施瓦茨不等式可以写成如下：

一般来说，这个不等式意味着两个向量的欧几里得范数可以作为它们内积的优越性。 Holder 不等式显示如下：

p 范数向量的以下不等式属性可以轻松验证：

2.4 归纳矩阵范数

给定 m×n 矩阵 A 和整数 p > 1 可以为定义的。矩阵 p-范数：

一般来说，我们最常用的矩阵 p-范数：

• 1-范数，取矩阵列和的绝对值的最大值：

• 无穷范数，取矩阵行的绝对值之和的最大值：

• 2-范数，

这一系列范数称为“诱导”，因为它是由不依赖于 A 的非零向量 x 给出的，并且p。他意识到。因此，一般来说，存在一个单位范数向量（p-范数中的单位范数）x let ||A||p = ||Ax||p。归纳矩阵的 p 范数遵循以下次重数定律：

此外，矩阵的 p 范数对于矩阵的初等变换是不变的，即 ||PAQ||p = ||A|| p，其中 P 和 Q 是相应维度变换矩阵的初等。类似地，如果我们考虑矩阵划分：

，那么子矩阵的范数与整个矩阵的范数相关：即||B||p