Trong học máy và khoa học dữ liệu hiện đại, ta thường xuyên đối mặt với các bài toán có số lượng lớn hơn rất nhiều so với số lượng điểm dữ liệu quan sát ($n>m$). Khi đó, hệ phương trình điều kiện $Ax=b$ trở thành hệ thiếu xác định (Underdetermined Linear System). Hệ này sở hữu vô số nghiệm khả dĩ tạo thành một không gian afin. Thách thức đặt ra là: Trong vô số nghiệm đó, nghiệm nào mang cấu trúc tối ưu về mặt hình học, có chuẩn nhỏ nhất, hoặc có tính thưa cao nhất?

Bên cạnh đó, để tối ưu hóa các mô hình xác suất và mạng nơ-ron, việc thao tác với các hàm (như hàm vết, định thức logarit, dạng toàn phương) đòi hỏi công cụ vi tích phân ma trận chuẩn xác. Bài học này hệ thống hóa toàn diện phương pháp giải hệ thiếu xác định và các bổ đề giải tích ma trận cốt lõi trong tối ưu hóa lồi.

---

1. Hệ Phương Trình Tuyến Tính Thiếu Xác Định

Xét hệ phương trình tuyến tính:

$$Ax=b,$$

trong đó $A\in {\mathbb{R}}^{m\times n}$ là kích thước "béo" (fat matrix) với $m<n$, và ma trận có hạng hàng đủ $\mathrm{rank}(A)=m$. vế phải $b\in {\mathbb{R}}^m$.

Vì $\mathrm{rank}(A)=m$, không gian cột của $A$ phủ kín toàn bộ không gian đích ${\mathbb{R}}^m$, do đó hệ luôn có nghiệm với mọi $b$. Không gian nghiệm của hệ là tập afin:

$$\mathcal{S}=\{x\in {\mathbb{R}}^n\mid Ax=b\}.$$

Nếu $x_0$ là một nghiệm riêng bất kỳ, thì toàn bộ tập nghiệm có dạng:

$$\mathcal{S}=x_0+\ker (A)=\{x_0+z\mid z\in {\mathbb{R}}^n,Az=0\}.$$

Vì số chiều của không gian hạt nhân $\dim (\ker (A))=n-m>0$, hệ có vô số nghiệm.

---

2. Nghiệm Chuẩn $L_2$ Nhỏ Nhất (Least-Norm Solution)

Trong số vô vàn nghiệm của $\mathcal{S}$, nghiệm tự nhiên nhất là nghiệm nằm gần gốc tọa độ nhất theo :

$$\begin{array}{rl}& \underset{x}{min}\frac{1}{2}\parallel x{\parallel }_2^2\\ & \text{s.t.}Ax=b.\end{array}$$

Đây là bài toán quy hoạch toàn phương lồi nghiêm ngặt có ràng buộc đẳng thức.

Thiết lập hàm Lagrange và nghiệm giải tích

Hàm Lagrange của bài toán với nhân tử $\nu \in {\mathbb{R}}^m$:

$$L(x,\nu )=\frac{1}{2}{x}^{T}x+{\nu }^T(Ax-b).$$

Điều kiện tối ưu KKT bậc nhất:

$$\begin{array}{rl}{\mathrm{\nabla }}_{x}L(x^{\ast },{\nu }^{\ast })& =x^{\ast }+A^T{\nu }^{\ast }=0⟹x^{\ast }=-A^T{\nu }^{\ast },\\ {\mathrm{\nabla }}_{\nu }L(x^{\ast },{\nu }^{\ast })& =A{x}^{\ast }-b=0.\end{array}$$

Thế biểu thức $x^{\ast }=-A^T{\nu }^{\ast }$ vào ràng buộc đẳng thức:

$$A(-A^T{\nu }^{\ast })=b⟹(A{A}^T)(-{\nu }^{\ast })=b.$$

Vì $A$ có hạng hàng đủ $\mathrm{rank}(A)=m$, ma trận Gram $A{A}^T\in {\mathbb{R}}^{m\times m}$ đối xứng và xác định dương nghiêm ngặt ($A{A}^T\succ 0$), do đó khả nghịch hoàn toàn. Ta suy ra:

$$-{\nu }^{\ast }=(A{A}^T{)}^{-1}b.$$

Thế ngược lại, ta thu được nghiệm chuẩn nhỏ nhất duy nhất $x_{\text{ln}}$ (Least-):

$$x_{\text{ln}}=A^T(A{A}^T{)}^{-1}b.$$

Trực giác hình học và Định lý Pythagoras

Từ công thức trên, ta thấy $x_{\text{ln}}\in \mathrm{range}(A^T)$. Mặt khác, theo định lý cơ bản của đại số tuyến tính, không gian ${\mathbb{R}}^n$ được phân rã trực giao thành:

$${\mathbb{R}}^n=\mathrm{range}(A^T)\oplus \ker (A).$$

Nghiệm $x_{\text{ln}}$ chính là hình chiếu trực giao của gốc tọa độ lên đa diện afin $\mathcal{S}$.

Với mọi nghiệm khả dĩ khác $x\in \mathcal{S}$, ta luôn có thể biểu diễn $x=x_{\text{ln}}+z$ với $z\in \ker (A)$. Khi đó, giữa hai thành phần:

$$x_{\text{ln}}^{T}z={(A^T(A{A}^T{)}^{-1}b)}^{T}z=b^T(A{A}^T{)}^{-1}(Az)=0,$$

bởi vì $Az=0$. Theo định lý Pythagoras:

$$\parallel x{\parallel }_2^2=\parallel x_{\text{ln}}+z{\parallel }_2^2=\parallel x_{\text{ln}}{\parallel }_2^2+\parallel z{\parallel }_2^2\ge \parallel x_{\text{ln}}{\parallel }_2^2.$$

Đẳng thức xảy ra khi và chỉ khi $z=0$, khẳng định tính duy nhất và tính tối tiểu của $x_{\text{ln}}$.

---

3. Thuật Toán Số Học Hiệu Năng Cao Qua Phân Tích $LQ$

Việc tính toán trực tiếp tích $A{A}^T$ rồi đảo ma trận $(A{A}^T{)}^{-1}$ rất dễ gặp mất ổn định số học khi ma trận có điều kiện xấu, đồng thời làm tăng bình phương số điều kiện: $\kappa (A{A}^T)=(\kappa (A){)}^2$.

Trong thực tế, ta sử dụng phân tích $LQ$ của $A$ (tương đương với phân tích $QR$ của ma trận chuyển vị $A^T$).

Thuật toán phân tích $LQ$

Phân tích $A\in {\mathbb{R}}^{m\times n}$ thành:

$$A=LQ=\left[\begin{array}{cc}{L}_1& 0\end{array}\right]\left[\begin{array}{c}{Q}_1^T\\ Q_2^T\end{array}\right]=L_1{Q}_1^T,$$

trong đó:

• $L_1\in {\mathbb{R}}^{m\times m}$ là tam giác dưới khả nghịch với các phần tử đường chéo khác không.
• $Q_1\in {\mathbb{R}}^{n\times m}$ có các cột trực chuẩn: $Q_1^T{Q}_1=I_m$.
• $Q_2\in {\mathbb{R}}^{n\times (n-m)}$ có các cột tạo thành cơ sở trực chuẩn cho $\ker (A)$.

Quy trình giải 3 bước ổn định số học

Thế phân tích $A=L_1{Q}_1^T$ vào công thức nghiệm chuẩn nhỏ nhất:

$$\begin{array}{rl}{x}_{\text{ln}}& =A^T(A{A}^T{)}^{-1}b\\ & =(Q_1{L}_1^T){((L_1{Q}_1^T)(Q_1{L}_1^T))}^{-1}b\\ & =Q_1{L}_1^T(L_1{L}_1^T{)}^{-1}b\\ & =Q_1{L}_1^T(L_1^T{)}^{-1}{L}_1^{-1}b\\ & =Q_1{L}_1^{-1}b.\end{array}$$

Thuật toán gồm ba bước:

1. Phân tích $LQ$: Thực hiện phân tích $A=L_1{Q}_1^T$ với chi phí $O(m^{2}n)$.
2. Giải thế tiến (Forward substitution): Giải hệ tam giác dưới $L_{1}y=b$ để tìm trung gian $y\in {\mathbb{R}}^m$ với chi phí $O(m^2)$.
3. Phép nhân : Tính nghiệm $x_{\text{ln}}=Q_{1}y$ với chi phí $O(mn)$.

Quy trình này hoàn toàn không cần nghịch đảo , đảm bảo độ chính xác số học cao nhất.

---

4. Nghiệm Chuẩn $L_1$ Nhỏ Nhất và Tính Thưa (Sparse Recovery)

Nếu ta thay chuẩn $L_2$ bằng chuẩn $L_1$, bài toán tìm nghiệm trở thành:

$$\begin{array}{rl}& \underset{x}{min}\parallel x{\parallel }_1=\sum _{j=1}^n|x_j|\\ & \text{s.t.}Ax=b.\end{array}$$

Bài toán này được gọi là Basis Pursuit trong lĩnh vực Nén cảm biến (Compressed Sensing).

Đưa về Quy hoạch Tuyến tính (LP)

Ta phân rã mỗi biến $x_j$ thành hiệu của hai biến không âm: Biểu thức $x_j=u_j-v_j$ với $u_j\ge 0,v_j\ge 0$. Khi đó $|x_j|=u_j+v_j$, và bài toán trở thành LP dạng chuẩn:

$$\begin{array}{rl}& \underset{u,v}{min}{\mathbf{1}}^{T}u+{\mathbf{1}}^{T}v\\ & \text{s.t.}Au-Av=b,\\ & u\ge 0,v\ge 0.\end{array}$$

Khác với nghiệm $L_2$ thường làm dàn đều các trọng số ra toàn bộ các tọa độ, nghiệm chuẩn $L_1$ có xu hướng ép rất nhiều tọa độ về đúng giá trị 0, tạo ra một nghiệm thưa (Sparse solution). Đây là nền tảng toán học của việc phục hồi tín hiệu kích thước lớn chỉ từ một số lượng nhỏ các phép đo cảm biến.

---

5. Bổ Trợ Giải Tích Ma Trận Cốt Lõi

Nghịch đảo giả Moore-Penrose ($A^{+}$)

Nghịch đảo giả Moore-Penrose $A^{+}\in {\mathbb{R}}^{n\times m}$ của một $A\in {\mathbb{R}}^{m\times n}$ là ma trận duy nhất thỏa mãn bốn điều kiện Penrose:

1. $A{A}^{+}A=A$.
2. $A^{+}A{A}^{+}=A^{+}$.
3. $(A{A}^{+}{)}^T=A{A}^{+}$.
4. $(A^{+}A{)}^T=A^{+}A$.

Các trường hợp đặc biệt quan trọng:

• Khi $\mathrm{rank}(A)=m<n$ (hạng hàng đủ, hệ thiếu xác định):
  $$A^{+}=A^T(A{A}^T{)}^{-1}.$$
  Khi đó $A{A}^{+}=I_m$, và nghiệm chuẩn nhỏ nhất viết gọn là $x_{\text{ln}}=A^{+}b$.
• Khi $\mathrm{rank}(A)=n<m$ (hạng cột đủ, hệ thừa xác định / ):
  $$A^{+}=(A^{T}A{)}^{-1}{A}^T.$$
• Qua phân tích SVD $A=U\mathrm{\Sigma }{V}^T$:
  $$A^{+}=V{\mathrm{\Sigma }}^{+}{U}^T,$$
  trong đó ${\mathrm{\Sigma }}^{+}$ thu được bằng cách nghịch đảo các giá trị kỳ dị khác không và giữ nguyên các giá trị bằng không.

Bổ đề Nghịch Đảo Ma Trận Woodbury (Sherman-Morrison-Woodbury)

Khi cần cập nhật nghịch đảo của một sau khi bị biến đổi bởi một số hạng hạng thấp (Low-rank perturbation), công thức Woodbury là công cụ thiết yếu:

$$(A+UCV{)}^{-1}=A^{-1}-A^{-1}U(C^{-1}+V{A}^{-1}U{)}^{-1}V{A}^{-1},$$

trong đó $A\in {\mathbb{R}}^{n\times n}$, $C\in {\mathbb{R}}^{k\times k}$, $U\in {\mathbb{R}}^{n\times k}$, $V\in {\mathbb{R}}^{k\times n}$.

Trường hợp riêng cập nhật hạng 1 ($k=1$, $U=u,V=v^T,C=1$) là công thức Sherman-Morrison:

$$(A+u{v}^T{)}^{-1}=A^{-1}-\frac{A^{-1}u{v}^T{A}^{-1}}{1+v^T{A}^{-1}u}.$$

Công thức này giảm chi phí tính toán cập nhật từ $O(n^3)$ xuống chỉ còn $O(n^2)$, đóng vai trò then chốt trong thuật toán lọc Kalman và hồi quy trực tuyến.

Vi phân Các Hàm Ma Trận Tiêu Biểu

Bảng dưới đây tổng hợp và gradient của các phổ biến trong tối ưu hóa:

$f(X)$	Miền xác định	Gradient ${\mathrm{\nabla }}_{X}f(X)$
$\mathrm{tr}(AXB)$	$X\in {\mathbb{R}}^{m\times n}$	$A^T{B}^T$
$\mathrm{tr}(X^{T}AX)$	$X\in {\mathbb{R}}^{n\times p}$	$(A+A^T)X$
$\frac{1}{2}{x}^{T}Xx$	$X\in {\mathbb{S}}^n$	$\frac{1}{2}x{x}^T$
$\log det(X)$	$X\in {\mathbb{S}}_{++}^n$	$X^{-1}$
$\mathrm{tr}(X^{-1})$	$X\in {\mathbb{S}}_{++}^n$	$-X^{-2}$

---

6. Bài Tập Tự Luyện Kèm Lời Giải Chi Tiết

Bài tập 1: Tính Nghiệm Chuẩn Nhỏ Nhất và Kiểm Tra Tính Trực Giao

Cho $A\in {\mathbb{R}}^{2\times 3}$ và $b\in {\mathbb{R}}^2$:

$$A=\left[\begin{array}{ccc}1& 1& 0\\ 0& 1& 1\end{array}\right],b=\left[\begin{array}{c}2\\ 4\end{array}\right].$$

1. Tính Gram $A{A}^T$ và nghịch đảo của nó.
2. Xác định nghiệm chuẩn nhỏ nhất $x_{\text{ln}}=A^T(A{A}^T{)}^{-1}b$.
3. Tìm cơ sở của không gian hạt nhân $\ker (A)$ và kiểm tra tính trực giao $x_{\text{ln}}\perp \ker (A)$.

Lời giải chi tiết:

1. Tính tích $A{A}^T$:

   $$A{A}^T=\left[\begin{array}{ccc}1& 1& 0\\ 0& 1& 1\end{array}\right]\left[\begin{array}{cc}1& 0\\ 1& 1\\ 0& 1\end{array}\right]=\left[\begin{array}{cc}1+1+0& 0+1+0\\ 0+1+0& 0+1+1\end{array}\right]=\left[\begin{array}{cc}2& 1\\ 1& 2\end{array}\right].$$

   Định thức: $det(A{A}^T)=2\times 2-1\times 1=3\ne 0$.

   Nghịch đảo của $2\times 2$:

   $$(A{A}^T{)}^{-1}=\frac{1}{3}\left[\begin{array}{cc}2& -1\\ -1& 2\end{array}\right].$$

2. Tính trung gian $w=(A{A}^T{)}^{-1}b$:

   $$w=\frac{1}{3}\left[\begin{array}{cc}2& -1\\ -1& 2\end{array}\right]\left[\begin{array}{c}2\\ 4\end{array}\right]=\frac{1}{3}\left[\begin{array}{c}4-4\\ -2+8\end{array}\right]=\frac{1}{3}\left[\begin{array}{c}0\\ 6\end{array}\right]=\left[\begin{array}{c}0\\ 2\end{array}\right].$$

   Nghiệm chuẩn nhỏ nhất:

   $$x_{\text{ln}}=A^{T}w=\left[\begin{array}{cc}1& 0\\ 1& 1\\ 0& 1\end{array}\right]\left[\begin{array}{c}0\\ 2\end{array}\right]=\left[\begin{array}{c}0\\ 2\\ 2\end{array}\right].$$

   Thử lại nghiệm:

   $$A{x}_{\text{ln}}=\left[\begin{array}{ccc}1& 1& 0\\ 0& 1& 1\end{array}\right]\left[\begin{array}{c}0\\ 2\\ 2\end{array}\right]=\left[\begin{array}{c}2\\ 4\end{array}\right]=b.$$

   Chuẩn bình phương: $\parallel x_{\text{ln}}{\parallel }_2^2=0^2+2^2+2^2=8$.

3. Tìm hạt nhân $\ker (A)$:

   $$Az=0⟺\{\begin{array}{l}{z}_1+z_2=0\\ z_2+z_3=0\end{array}⟺z_1=-z_2=z_3.$$

   Chọn $z_2=-1⟹z_1=1,z_3=1$. Cơ sở của $\ker (A)$ là $v=(1,-1,1{)}^T$.

   Kiểm tra :

   $$x_{\text{ln}}^{T}v=0(1)+2(-1)+2(1)=0-2+2=0.$$

   Điều này khẳng định $x_{\text{ln}}$ vuông góc với toàn bộ không gian hạt nhân $\ker (A)$.

---

Bài tập 2: Cập Nhật Nghịch Đảo Ma Trận Bằng Công Thức Sherman-Morrison

Trong mô hình hồi quy tuyến tính trực tuyến (Online Ridge Regression), mẫu được cập nhật sau khi nhận thêm một điểm dữ liệu mới $a\in {\mathbb{R}}^n$:

$$V_{\text{new}}=V+a{a}^T,$$

với $V\succ 0$ là khả nghịch đã biết trước nghịch đảo $V^{-1}$.

1. Áp dụng công thức Sherman-Morrison để biểu diễn $V_{\text{new}}^{-1}$ theo $V^{-1}$ và $a$.
2. Giả sử $V=I_2$ và điểm dữ liệu mới là $a=\left[\begin{array}{c}1\\ 2\end{array}\right]$. Tính giá trị giải tích của $V_{\text{new}}^{-1}$.

Lời giải chi tiết:

1. Đặt $u=a$ và $v=a$. Áp dụng trực tiếp công thức Sherman-Morrison:

   $$V_{\text{new}}^{-1}=(V+a{a}^T{)}^{-1}=V^{-1}-\frac{V^{-1}a{a}^T{V}^{-1}}{1+a^T{V}^{-1}a}.$$

   Đặt $q=V^{-1}a\in {\mathbb{R}}^n$ và số thực vô hướng $\gamma =1+a^{T}q=1+a^T{V}^{-1}a$. Biểu thức viết gọn:

   $$V_{\text{new}}^{-1}=V^{-1}-\frac{1}{\gamma }q{q}^T.$$

   Phép tính này chỉ đòi hỏi một phép nhân - ($V^{-1}a$) và một phép nhân ngoài vector ($q{q}^T$), tiêu tốn tổng cộng $O(n^2)$ phép tính thay vì $O(n^3)$ khi đảo ma trận từ đầu.

2. Áp dụng với dữ liệu cụ thể: $V=I_2⟹V^{-1}=I_2$.

   $q=I_{2}a=\left[\begin{array}{c}1\\ 2\end{array}\right]$.

   Đại lượng vô hướng $\gamma$:

   $$\gamma =1+a^T{I}_{2}a=1+(1^2+2^2)=1+5=6.$$

   Tích ngoài $q{q}^T$:

   $$q{q}^T=\left[\begin{array}{c}1\\ 2\end{array}\right]\left[\begin{array}{cc}1& 2\end{array}\right]=\left[\begin{array}{cc}1& 2\\ 2& 4\end{array}\right].$$

   Tính nghịch đảo mới:

   $$V_{\text{new}}^{-1}=\left[\begin{array}{cc}1& 0\\ 0& 1\end{array}\right]-\frac{1}{6}\left[\begin{array}{cc}1& 2\\ 2& 4\end{array}\right]=\left[\begin{array}{cc}1-1/6& -2/6\\ -2/6& 1-4/6\end{array}\right]=\left[\begin{array}{cc}5/6& -1/3\\ -1/3& 1/3\end{array}\right].$$

   Kiểm tra lại bằng phép nhân trực tiếp:

   $$V_{\text{new}}=I_2+a{a}^T=\left[\begin{array}{cc}1& 0\\ 0& 1\end{array}\right]+\left[\begin{array}{cc}1& 2\\ 2& 4\end{array}\right]=\left[\begin{array}{cc}2& 2\\ 2& 5\end{array}\right].$$

   Tích của hai :

   $$\left[\begin{array}{cc}2& 2\\ 2& 5\end{array}\right]\left[\begin{array}{cc}5/6& -1/3\\ -1/3& 1/3\end{array}\right]=\left[\begin{array}{cc}10/6-2/3& -2/3+2/3\\ 10/6-5/3& -2/3+5/3\end{array}\right]=\left[\begin{array}{cc}1& 0\\ 0& 1\end{array}\right]=I_2.$$

---

Bài tập 3: Tối Đa Hóa Entropy Ma Trận Hiệp Phương Sai (Maximum Entropy Covariance)

Xét bài toán ước lượng xác định dương $X\in {\mathbb{S}}_{++}^n$ tối đa hóa entropy thông tin chuẩn tắc Gauss có ràng buộc về vết:

$$\begin{array}{rl}& \underset{X}{max}\log det(X)\\ & \text{s.t.}\mathrm{tr}(SX)=n,X\succ 0,\end{array}$$

trong đó $S\in {\mathbb{S}}_{++}^n$ là đối xứng xác định dương đã cho trước.

1. Chuyển bài toán về dạng cực tiểu lồi chuẩn tắc và thiết lập hàm Lagrange.
2. Áp dụng công thức vi phân để tìm điều kiện KKT.
3. Tìm nghiệm tối ưu giải tích $X^{\ast }$.

Lời giải chi tiết:

1. Bài toán tương đương với:

   $$\begin{array}{rl}& \underset{X}{min}-\log det(X)\\ & \text{s.t.}\mathrm{tr}(SX)-n=0,X\succ 0.\end{array}$$

   Vì hàm $-\log det(X)$ lồi nghiêm ngặt trên nón đối xứng xác định dương ${\mathbb{S}}_{++}^n$ và ràng buộc là tuyến tính theo $X$, đây là bài toán tối ưu lồi nghiêm ngặt có nghiệm tối ưu duy nhất.

   Hàm Lagrange với nhân tử đối ngẫu vô hướng $\nu \in \mathbb{R}$:

   $$L(X,\nu )=-\log det(X)+\nu (\mathrm{tr}(SX)-n).$$

2. Lấy vi phân của hàm Lagrange theo đối xứng $X$:

   • Ta đã biết ${\mathrm{\nabla }}_X(-\log det(X))=-X^{-1}$.
   • Với số hạng tuyến tính: ${\mathrm{\nabla }}_X\mathrm{tr}(SX)=S$ (do $S$ đối xứng).

   Điều kiện KKT triệt tiêu gradient :

   $${\mathrm{\nabla }}_{X}L(X^{\ast },{\nu }^{\ast })=-(X^{\ast }{)}^{-1}+{\nu }^{\ast }S=0⟹(X^{\ast }{)}^{-1}={\nu }^{\ast }S.$$

   Nghịch đảo cả hai vế (với điều kiện ${\nu }^{\ast }>0$):

   $$X^{\ast }=\frac{1}{{\nu }^{\ast }}{S}^{-1}.$$

3. Xác định nhân tử ${\nu }^{\ast }$ bằng cách thế $X^{\ast }$ vào ràng buộc đẳng thức $\mathrm{tr}(S{X}^{\ast })=n$:

   $$\mathrm{tr}\left(S\left(\frac{1}{{\nu }^{\ast }}{S}^{-1}\right)\right)=n⟹\frac{1}{{\nu }^{\ast }}\mathrm{tr}(I_n)=n.$$

   Vì $\mathrm{tr}(I_n)=n$, ta có:

   $$\frac{n}{{\nu }^{\ast }}=n⟹{\nu }^{\ast }=1.$$

   Thế ${\nu }^{\ast }=1$ trở lại, ta tìm được nghiệm tối ưu duy nhất:

   $$X^{\ast }=S^{-1}.$$

   Nghiệm này hoàn toàn thỏa mãn điều kiện xác định dương $X^{\ast }\succ 0$ do $S\succ 0$.

---

Tài liệu tham khảo

• Stephen Boyd, Lieven Vandenberghe, Convex Optimization, Phụ lục A & C, Cambridge University Press.
• Gene H. Golub, Charles F. Van Loan, Computations, Johns Hopkins University Press.