对于任一给定的矩阵 A m × n \boldsymbol{A}_{m\times n} Am×n​，都存在这样的分解： A = U D V T \boldsymbol{A}=\boldsymbol{U}\boldsymbol{D}\boldsymbol{V}^T A=UDVT 这里: U \boldsymbol{U} U是一个 ( m × m ) (m\times m) (m×m)的正交矩阵， D \boldsymbol{D} D是一个 ( m × n ) (m\times n) (m×n)的对角矩阵， V \boldsymbol{V} V是一个 ( n × n ) (n\times n) (n×n)的正交矩阵。

D \boldsymbol{D} D中的对角元叫做 A \boldsymbol{A} A的奇异值， U \boldsymbol{U} U中的列向量叫做 A \boldsymbol{A} A的左奇异向量， V \boldsymbol{V} V中的列向量叫做 A \boldsymbol{A} A的右奇异向量。

问题等价于 min ⁡ ∥ A x − b ∥ 2 \min\parallel \boldsymbol{Ax}-\boldsymbol{b}\parallel^2 min∥Ax−b∥2，是一个非线性优化问题。 对A进行SVD分解 min ⁡ ∥ A x − b ∥ 2 = min ⁡ ∥ U D V T x − b ∥ 2 = min ⁡ ∥ D V T x − U T b ∥ 2 \min\parallel \boldsymbol{Ax}-\boldsymbol{b}\parallel^2 \\ = \min \parallel \boldsymbol{U}\boldsymbol{D}\boldsymbol{V}^T \boldsymbol{x}-\boldsymbol{b}\parallel^2 \\ = \min \parallel \boldsymbol{D}\boldsymbol{V}^T \boldsymbol{x}- \boldsymbol{U}^T\boldsymbol{b}\parallel^2 min∥Ax−b∥2=min∥UDVTx−b∥2=min∥DVTx−UTb∥2 设 y = V T x \boldsymbol{y}=\boldsymbol{V}^T\boldsymbol{x} y=VTx, c = U T b \boldsymbol{c} = \boldsymbol{U}^T \boldsymbol{b} c=UTb，则 min ⁡ ∥ D V T x − U T b ∥ 2 \min \parallel \boldsymbol{D}\boldsymbol{V}^T \boldsymbol{x}- \boldsymbol{U}^T\boldsymbol{b}\parallel^2 min∥DVTx−UTb∥2可以表述为 D y = c \boldsymbol{D}\boldsymbol{y}= \boldsymbol{c} Dy=c，方程组的解为 y i = c i / d i \boldsymbol{y}_i=\boldsymbol{c}_i/\boldsymbol{d}_i yi​=ci​/di​

问题等价于 min ⁡ ∥ A x ∥ 2 \min\parallel \boldsymbol{Ax}\parallel^2 min∥Ax∥2 上式转化为： min ⁡ ∥ A x ∥ 2 = min ⁡ ∥ U D V T x ∥ 2 \min\parallel \boldsymbol{Ax}\parallel^2 \\=\min \parallel \boldsymbol{U}\boldsymbol{D}\boldsymbol{V}^T \boldsymbol{x}\parallel^2 min∥Ax∥2=min∥UDVTx∥2 令 y = V T x \boldsymbol{y} = \boldsymbol{V}^T\boldsymbol{x} y=VTx，则上式变为 min ⁡ ∥ D y ∥ 2 \min \parallel \boldsymbol{Dy}\parallel^2 min∥Dy∥2 D是一个对角矩阵，且对角元素按照递减的顺序排列，所以最小值即最优解在 y = ( 0 , 0 , . . . , 1 ) T \boldsymbol{y}=(0,0,...,1)^T y=(0,0,...,1)T时取得，此时 x = V y \boldsymbol{x}=\boldsymbol{V}\boldsymbol{y} x=Vy，所以最优解就是 V \boldsymbol{V} V的最小奇异值对应的列向量。比如，最小奇异值在第10行10列，那么解向量 x \boldsymbol{x} x就等于 V \boldsymbol{V} V的第10个列向量.

参考链接: link.