笔记：宾大《Algebra, Topology, Differential Calculus, and Optimization Theory For CS and ML》——第三章第一节

3.1 线性组合、线性独立、秩

在 $n$n 维中，我们可以这样定义线性组合(linear combination)：
${ x_1u+x_2v+x_3w+...+x_nz }$x1​u+x2​v+x3​w+...+xn​z
其中，$u$u , $v$v , $w$w … $z$z 均为 $n$n 维向量，即$\R^{n\times1}$Rn×1，$x_i (i = 1,2,3…,n)$xi​(i=1,2,3…,n) 均为在 $\R$R 上的变量（标量）。

基于上述定义，我们可以把下面的线性问题
$x_1u+x_2v+x_3w+...+x_nz = b$x1​u+x2​v+x3​w+...+xn​z=b
等价于判定是否 $b$b 可以表示为$u$u , $v$v , $w$w … $z$z 这组向量的线性组合。

考虑以下的情形，在 $n$n 维中，如果对于任何一组 $(x_1,x_2,x_3...x_n)\ne(0,0,0…0)$(x1​,x2​,x3​...xn​)​=(0,0,0…0) 都不能满足
$x_1u+x_2v+x_3w+...+x_nz = 0_n$x1​u+x2​v+x3​w+...+xn​z=0n​
那么，向量$u$u , $v$v , $w$w … $z$z 即为**线性独立（linearly independent）**的。

其中 $0_n$0n​ 表示 $n$n 维的零向量，例如 $n=3$n=3 :
$0_3 = \left(0,0,0\right)^T$03​=(0,0,0)T
不过我们通常将 $0_n$0n​ 写为 $0$0 ，原因在于，我们可以根据数据判断出此处的 $0$0 是向量还是标量。

实际上，在这组线性独立的向量$u$u , $v$v , $w$w … $z$z下，任意一个向量 $a \in \R^{n \times1}$a∈Rn×1 都可以唯一地表示如下的线性组合
$a = x_1u+x_2v+x_3w+...+x_nz$a=x1​u+x2​v+x3​w+...+xn​z
其唯一性证明如下：
$a = x_1u+x_2v+x_3w+...+x_nz = y_1u+y_2v+y_3w+...+y_nz$a=x1​u+x2​v+x3​w+...+xn​z=y1​u+y2​v+y3​w+...+yn​z
由基本向量运算可知
$（y_1-x_1）u+(y_2-x_2)v+(y_3-x_3)w+...+(y_n-x_n)z=0，$（y1​−x1​）u+(y2​−x2​)v+(y3​−x3​)w+...+(yn​−xn​)z=0，
即
$y_1-x_1=y_2-x_2=y_3-x_3=0，$y1​−x1​=y2​−x2​=y3​−x3​=0，
通过线性独立性，有
$y_1=x_1， y_2=x_2， y_3= x_3$y1​=x1​，y2​=x2​，y3​=x3​
所以，在线性独立的向量$u$u , $v$v , $w$w … $z$z下，任意一个向量 $a \in \R^{n \times1}$a∈Rn×1 都可以唯一地表示如下的线性组合
$a = x_1u+x_2v+x_3w+...+x_nz$a=x1​u+x2​v+x3​w+...+xn​z
现在我们可以根据定义来判断线性独立了，不过在定义中需要判断在 $n$n 维空间中，每一个$(x_1,x_2,x_3...x_n)\ne(0,0,0…0)$(x1​,x2​,x3​...xn​)​=(0,0,0…0) 的矩阵都不满足条件是不切实际的，所以我们需要使用其他方法来判断一组向量事都为线性独立的。

第一种方法，计算由$(u,v,w…z)$(u,v,w…z) 组成的矩阵的行列式结果是否非零，即$det(u,v,w,…z)\ne0$det(u,v,w,…z)​=0 。如果非零，则$(u,v,w…z)$(u,v,w…z) 为线性独立的。

第二种方法，计算由$(u,v,w…z)$(u,v,w…z) 组成的矩阵的LU分解或QR分解或SVD。这种方法在面对于具有大量的变量的问题时，效果更好。

这里我们在 $n=3$n=3 的条件下举例说明。

不妨有
$A=（u \quad v \quad w）=\left( \begin{matrix} 1 & 2 & -1\\ 2 & 1 & 1\\ 1 & -1 & -2 \end{matrix} \right)\\ x = (x_1,x_2,x_3)^T\\ b = (3,3,0)^T$A=（uvw）=⎝⎛​121​21−1​−11−2​⎠⎞​x=(x1​,x2​,x3​)Tb=(3,3,0)T
所以线性组合 $x_1u+x_2v+x_3w$x1​u+x2​v+x3​w 可以写为如下的矩阵形式
$Ax=x_1u+x_2v+x_3w = \left( \begin{matrix} 1 & 2 & -1\\ 2 & 1 & 1\\ 1 & -1 & -2 \end{matrix} \right)\left( \begin{matrix} x_1\\ x_2\\ x_3 \end{matrix} \right)=\left( \begin{matrix} 3\\ 3\\ 0 \end{matrix} \right) =b$Ax=x1​u+x2​v+x3​w=⎝⎛​121​21−1​−11−2​⎠⎞​⎝⎛​x1​x2​x3​​⎠⎞​=⎝⎛​330​⎠⎞​=b
上述结果可以简写为
$Ax=b$Ax=b
我们可以看到
$b = u+v\\ w=u-v$b=u+vw=u−v
所以上面的表达式可以化为
$（x_1+x_3）u+(x_2-x_3)v=b$（x1​+x3​）u+(x2​−x3​)v=b
同时，解为
$x_1=1，x_2=1,x_3=0.$x1​=1，x2​=1,x3​=0.
又因为 $u$u 和 $v$v 是线性独立的，所以对于 $x_1+x_3$x1​+x3​ 和 $x_2-x_3$x2​−x3​ 唯一解为
$x_1+x_3 = 1\\ x_2-x_3 = 1,$x1​+x3​=1x2​−x3​=1,
这就产生了基于参数 $x_3$x3​ 的无限解，即
$x_1 = 1-x_3\\ x_2 = 1+x_3.$x1​=1−x3​x2​=1+x3​.
综上所述，一个 $3\times3$3×3 的线性系统可能具有唯一的解、无解或有限解。解的数量，取决于线性独立性（和依赖性）或向量 $u,v,w,b$u,v,w,b 。 这种情况可以推广到任何 $n\times n$n×n 维的系统，甚至任何 $n\times m$n×m 维的系统，即 $m$m 个变量中的 $n$n 个方程，这个在后面将详细讨论。

我们可以将上面的向量 $u,v,w,b$u,v,w,b 视为矩阵的子向量，即
$A=\left( \begin{matrix} a_{11} & a_{12} & a_{13}\\ a_{21} & a_{22} & a_{23}\\ a_{31} & a_{32} & a_{33} \end{matrix}\right)$A=⎝⎛​a11​a21​a31​​a12​a22​a32​​a13​a23​a33​​⎠⎞​
所以我们可以定义矩阵下的线性组合，对于任意的向量 $x=(x_1,x_2,x_3)$x=(x1​,x2​,x3​) ，我们可以将其线性组合定义为 $Ax$Ax
$Ax = x_1A^1+x_2A^2+x_3A^3=\left( \begin{matrix} a_{11} & a_{12} & a_{13}\\ a_{21} & a_{22} & a_{23}\\ a_{31} & a_{32} & a_{33} \end{matrix}\right)$Ax=x1​A1+x2​A2+x3​A3=⎝⎛​a11​a21​a31​​a12​a22​a32​​a13​a23​a33​​⎠⎞​
也可以将其写为内积的形式：
$（a_{i1} \quad a_{i2} \quad a_{i3}）\cdot (x_1 \quad x_2 \quad x_3)^T = a_{i1}x_1+a_{i2}x_2+a_{i3}x_3$（ai1​ai2​ai3​）⋅(x1​x2​x3​)T=ai1​x1​+ai2​x2​+ai3​x3​
note：两个向量 $x=(x_1,…,x_n)$x=(x1​,…,xn​) 和 $y=(y_1,…,y_n) \in \R^n$y=(y1​,…,yn​)∈Rn 的内积通常写为 $x \cdot y$x⋅y 或 $<x,y>$<x,y> 。

下面我们继续在矩阵维度考虑线性方程组的解：

假设 $A$A 是一个 $n \times n$n×n 的矩阵，$b \in \R^n$b∈Rn ，对于线性方程组
$Ax = b$Ax=b
我们可以找到一个矩阵 $B \in \R ^ {n \times n}$B∈Rn×n 有
$BA^i=e_i ,\quad i=1,..n$BAi=ei​,i=1,..n
$e_i = (0,…,0,1,0,…,0)$ei​=(0,…,0,1,0,…,0) 在第 $i$i 处为1，其他位置为0。以此类推，我们可以得到
$BA = I_n$BA=In​
其中 $I_n$In​ 为单位矩阵
$I_n = \left ( \begin{matrix} 1 & 0 & \cdots & 0\\ 0 & 1 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & 1 \end{matrix} \right )$In​=⎝⎜⎜⎜⎛​10⋮0​01⋮0​⋯⋯⋱⋯​00⋮1​⎠⎟⎟⎟⎞​
我们在 $Ax=b$Ax=b 两侧同时左乘矩阵 $B$B
$B(Ax)=(BA)x=I_nx=x=Bb$B(Ax)=(BA)x=In​x=x=Bb
这里我们可以证明 $x = Bb$x=Bb 为$Ax=b$Ax=b 的解，我们将$x = Bb$x=Bb 带入
$A(Bb)=(AB)b=I_nb=b$A(Bb)=(AB)b=In​b=b
由于从 $BA = I_n$BA=In​ 可以得到 $AB = I_n$AB=In​（可以自己证明），所以我们通常用 $A^{-1}$A−1 （矩阵 $A$A 的逆）来代替矩阵 $B$B ，即
$AA^{-1}=A^{-1}A=I_n$AA−1=A−1A=In​
Note: 如果矩阵 $A$A 存在逆，那么我们称矩阵 $A$A 可逆矩阵或者非奇异矩阵(nonsingular) ，否则，我们称其为奇异矩阵。

综上，如果A是一个可逆的方阵，那么线性方程组 $AX=b$AX=b 的解为 $x=A^{-1}b$x=A−1b 。但是我们在真正使用的时候并不会直接计算 $A^{-1}$A−1 ，因为计算花销太大了。我们通常使用的方法为高斯消除(Gaussian elimination) (第8章会讨论)以及有关矩阵 $A$A 的因式分解(QR分解以及SVD分解)。

为了引出SVD分解，我们首先提出正交矩阵的概念

对于矩阵 $Q \in \R^{n \times n}$Q∈Rn×n ，如果存在
$QQ^T = Q^TQ = I_n$QQT=QTQ=In​
则称矩阵 $Q$Q 为正交矩阵（orthogonal matrix）

在几何上，正交矩阵代表着保留长度的线性变换，即在线性代数中每一个矩阵 $A \in \R^{m \times n}$A∈Rm×n 都可以写成
$A= V\Sigma U^T$A=VΣUT
其中， $V$V是一个 $m \times m$m×m 的正交矩阵， $U$U 是一个 $n \times n$n×n 的正交矩阵，$\Sigma$Σ 是 $m\times n$m×n 的矩阵，其所有的非零项都在对角线上，且为非负值，我们将其记做 $\sigma_1 \ge \sigma_2 \ge… \ge \sigma_p$σ1​≥σ2​≥…≥σp​ ，其中 $p = min(m,n)$p=min(m,n)，并将其定义为矩阵 $A$A 的奇异值，同时我们也将此因式分解称为矩阵 $A$A 的奇异值分解，即SVD（singular value decomposition）。

SVD可以用来求解大部分线性问题的精确解，不过面对于超定问题(overdetermined)时，即变量数大于方程数时，SVD方法不适用，即此线性系统无唯一确定解。

所以在此情况下，我们可以使用高精度的近似解来替代，即确定一个向量 $x$x 使其可以最小化误差 $Ax-b$Ax−b，这在工程领域中也是允许的。

数学家Gauss和Legendre提出使用误差的欧几里范数的平方来评价误差，即 $\left\|Ax-b\right\|^2_2$∥Ax−b∥22​ ，这样的好处是此误差可微，而且有且只有一个向量 $x^{+}$x+ 可以最小化此误差。

我们可以求得误差对应的解 $x^{+} = A^+b$x+=A+b ，这里的 $A^+$A+ 为矩阵 $A$A 的伪逆(pseudo-inverse)，同理 $A^+= V\Sigma^+ U^T$A+=VΣ+UT 中的 $\Sigma^+$Σ+ 为将 $\Sigma$Σ 中的每一个奇异值 $\sigma_i$σi​ 变为逆 $\sigma_i^{-1}$σi−1​ 。

除了上面介绍的使用欧几里范数的平方来评价误差，还可以在此基础上增加惩罚项 $K \left\|x\right\|^2_2$K∥x∥22​ ，即 $x$x 的 $l_2$l2​ 范数（二范数） ，其中 $K>0$K>0 ，然后再最小化$\left\|Ax-b\right\|^2_2+K \left\|x\right\|^2_2$∥Ax−b∥22​+K∥x∥22​ ，我们称这种方法为岭回归(ridge regression)。同样的对于岭回归有且只有一个向量 $x^{+}$x+ 可以使其达到最小。

除了欧几里范数的平方以及岭回归，我们还可以使用 $K \left\|x\right\|_1$K∥x∥1​ 来替代 $K \left\|x\right\|^2_2$K∥x∥22​

，其中 $ \left|x\right|_1 = |x_1|+…+|x_n|$ ，即 $x$x 的 $l_1$l1​ 范数（一范数） 。使用一范数可以使问题的解变得更加稀疏，即最优解 $x$x 的很多项为0，通常其被称为lasso。

SVD除了可以求解线性系统的解以及超定问题的最优近似解之外，另外一个重要应用就是主成分分析，即PCA(principal component analysis)，这将在后面的章节详细讨论。

另外，我们可以在可视化/几何视角来看线性方程组的解这个问题，类似于intersection problem。我们举例说明：

对于下面的线性问题
$x_1+2x_2-x_3 = 1\\ 2x_1+x_2+x_3 = 2\\ x_1-2x_2-2x_3 = 3$x1​+2x2​−x3​=12x1​+x2​+x3​=2x1​−2x2​−2x3​=3
其解为 $\R^3$R3 空间的一个子集，准确来说是一个$\R^3$R3 空间下的一个点。

对于第一个等式：
$x_1+2x_2-x_3 = 1$x1​+2x2​−x3​=1
实际上为一个$\R^3$R3 空间过 $(1,0,0),(0,1/2,0),(0,0,1)$(1,0,0),(0,1/2,0),(0,0,1) 三点的平面。

对于第二个等式：
$2x_1+x_2+x_3 = 2$2x1​+x2​+x3​=2
实际上为一个$\R^3$R3 空间过 $(1,0,0),(0,2,0),(0,0,2)$(1,0,0),(0,2,0),(0,0,2) 三点的平面。

对于第三个等式：
$x_1-2x_2-2x_3 = 3$x1​−2x2​−2x3​=3
实际上为一个$\R^3$R3 空间过 $(3,0,0),(0,-3/2,0),(0,0,-3/2)$(3,0,0),(0,−3/2,0),(0,0,−3/2) 三点的平面。

我们分别画出这三个平面，如下图

我们在一个坐标系下画出上述三个平面，两两平面的交集为之直线，三个平面的交集为点，所以此线性方程组的解为三个平面的交点，可以求解得到解为 $(1.4,-0.4,-0.4)$(1.4,−0.4,−0.4)。如下图

而对于下面这个线性方程组
$x_1+2x_2-x_3 = 1\\ 2x_1+x_2+x_3 = 2\\ x_1-x_2+2x_3 = 3$x1​+2x2​−x3​=12x1​+x2​+x3​=2x1​−x2​+2x3​=3
使用相同的方法在同一坐标系中画出每一个等式对应的平面，可以发现其没有交点，即此线性方程组没有解，如下图

而对于下面这个线性方程组
$x_1+2x_2-x_3 = 3\\ 2x_1+x_2+x_3 = 3\\ x_1-x_2+2x_3 = 0$x1​+2x2​−x3​=32x1​+x2​+x3​=3x1​−x2​+2x3​=0
使用相同的方法在同一坐标系中画出每一个等式对应的平面，可以发现他们所谓的交点为直线，即此线性方程组有无穷多解 $(1-x_3,1+x_3,x_3)$(1−x3​,1+x3​,x3​)，如下图

在几何角度考虑求解线性等式时，我们的视角与代数角度不同，几何角度下，我们都是在行考虑问题，在代数角度下我们是以列的基础考虑此问题。

另外，线性代数还可以帮助我们进行有效的数据压缩，即用更小的空间来保存更多的数据。所谓的数据压缩的原理是，在我们的大多数应用中数据的特征间不是完全独立的，即 $rank(A) \ll min\{m,n\}$rank(A)≪min{m,n} ，其中 $n$n 表示 $n$n 维的数据，共有 $m$m 组数据，通常 $m \ge n$m≥n。所以我们数据压缩的核心就是将矩阵 $A \in \R^{m \times n}$A∈Rm×n 分解为矩阵 $B \in \R^{m \times k}$B∈Rm×k 和矩阵 $C \in \R^{k \times n}$C∈Rk×n ，并保证 $k \ll min \{m,n\}$k≪min{m,n} 。

在上面我们也介绍过，直接对于原矩阵 $A$A ，进行因式分解的计算量是很大的，所以我们需要找到一个低阶（low-rank）的矩阵 $A’$A’ 来替代或近似原矩阵 $A$A 。这里我们使用矩阵范数 来计算矩阵 $A’$A’ ，即寻找一个低阶矩阵 $A’$A’ ，使其可以
$min\{\left\|A-A'\right\|^2 \}$min{∥A−A′∥2}
并且满足 $k \ll min\{m,n\}$k≪min{m,n}。

note：矩阵范数是非负实数，其代表的意义与实数的绝对值 $|x| $类似，它可以使得矩阵在低阶标量的角度进行比较和计算。

一些低阶近似的好处如下：

1. 表示矩阵 $A$A 所需的元素更少， 即用 $k(m+n)$k(m+n) 代替 $mn$mn。 所以重建 $A$A 需要更少的存储空间和更少的运算过程。

2. 在运算的过程会区别得到数据中的主要特征（有贡献的特征）和一般特征（无贡献的特征）。 因此可能会发现“大多数”的有效数据会在某些特征间集中。在今后的PCA等降维方法会用到这种思想。

   一组数据的低阶分解在工程中也有很多用处，例如在CS（computer science）、CV（computer vision）、统计学（statistics）以及机器学习（mechine learning）中。不过在实际应用中以上的方法仅仅可以得到一个比较好的初始解，还需要配合例如**随机化（randomization）**等操作来得到更满意的解决方案。

预告

向量空间