选自arXiv

作者：PetrosDrineas、MichaelW.Mahoney

机器之心编译

参与：李泽南、刘晓坤、蒋思源

矩阵计算在计算机科学中占有举足轻重的地位，是每个开发者都需要掌握的数学知识。近日，来自普渡大学的PetrosDrineas与UCBerkeley的MichaelMahoney提交了一篇概述论文《LecturesonRandomizedNumericalLinearAlgebra》可以作为线性代数知识的参考资料，本文将对其中的部分内容（主要为第二章：线性代数）进行简单介绍。

论文链接：

简介

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

随机数值线性代数（RandNLA）是一个跨学科的研究领域，利用随机化作为计算资源来开发用于大规模线性代数问题的提升算法。从基础的角度来看，RandNLA源自理论计算机科学（TCS），并与数学有着很深的联系（凸面分析、概率论、度量嵌入理论），也与应用数学相关（科学计算、信号处理、数值线性代数）。从应用层面来看，RandNLA是机器学习、统计和数据分析的重要新工具。很多精心设计的实现已经在大量问题上超越了高度优化的软件库，如最小二乘回归，同时也具有相当的扩展性、平行计算和分布能力。此外，RandNLA为现代大规模数据分析提供了良好的算法和统计基础。

这一章将作为对三种基本RandNLA算法的独立的入门介绍，分别是随机矩阵乘法（randomizedmatrixmultiplication）、随机最小二乘解算器（randomizedleast-squaressolvers），以及用一个随机算法计算矩阵的低秩近似。因此，这一章和很多应用数学的领域有非常强的联系，特别是它和这一卷的其它许多章节都有很强的联系。最重要的是，其中分别包含了G.Martinsson的工作，他利用这些方法开发了改进的低秩矩阵近似解算器[2]；R.Vershynin的工作，他开发了概率论工具用于分析RandNLA算法[3]；J.Duchi的工作，他以互补的方式利用随机方法求解更通用的优化问题[4]；以及M.Maggioni的工作，他以这些方法作为更复杂的多尺度方法的基础模块[5]。

本论文将在第二节中概述基本的线性代数知识；在第三节概述离散概率的基本知识；在第四节介绍矩阵乘法的随机算法；在第五节介绍最小二乘回归问题的随机算法；在第六节介绍低秩近似的随机算法。最后我们还介绍了两个其它关于RandNLA的导论资源[6,7]，供感兴趣的读者参考。

2线性代数

在这一节，我们将简要概述基本的线性代数属性和在这一章中将用到的数学符号。我们假定读者具备线性代数的基础（例如，向量的内积和叉积，基本矩阵运算如加法、标量乘法、转置、上/下三角矩阵，矩阵-向量乘法，矩阵乘法，矩阵的迹等）。

2.1基础

我们将完全聚焦于线性空间中的矩阵和向量。我们使用符号x∈R^n表示n维向量，注意向量都是以粗体小写字母书写。这里假定所有的向量都是列向量，除非特别说明。所有元素为零的向量用0表示，所有元素为1的向量用1表示（类似Broadcasting）；维度会隐含在上下文中或显式地用下标表示。

我们将使用粗体大写字母表示矩阵，例如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是可逆的。换句话说，不存在一个非零向量x∈R^n使得Ax=0。可逆矩阵的标准性质有：(A^1)^=(A^)^1=A^（A逆的转置等于A转置的逆）和(AB)^1=B^1*A^1（A左乘B的逆等于B逆左乘A逆。注：

转载请注明:http://www.aideyishus.com/lktp/4965.html