New form of matrix factorization เลยล่ะ
Theorem (Main Theorem)
Theorem: Any matrix can be factored as:
where:
- is orthogonal
- is orthogonal
- is diagonal with diagonal entries
Examples of :
Note: is always orthogonal.
Key Properties of SVD
- This is called the singular value decomposition (SVD) of
- The sequence are the singular values of and are uniquely determined by
- Any matrix can be decomposed this way - no other factorization has this property
Analogy: Think of SVD as decomposing any transformation into three steps: rotate (by ), stretch/compress along axes (by ), then rotate again (by ). It's like finding the "principal directions" of how a matrix transforms space.
Applications of SVD
SVD สามารถใช้หาอะไรได้อย่างเลยล่ะ
1. Matrix 2-Norm
SVD provides an elegant way to compute the matrix 2-norm.
Lemma 1
Let and be orthogonal. Then:
Proof:
- Recall: for orthogonal
- Therefore:
Lemma 2
Let and be orthogonal. Then:
Proof:
- Let , so
- Therefore:
Lemma 3
Let be diagonal. Then:
Proof: Left as exercise. #FinalExam ออกสอบแน่เลยอะ
Theorem
If (SVD of ), then:
Proof:
by the previous three lemmas.
Note: In general, calculating is more expensive than or . 3 - Norms
Analogy: The largest singular value tells you the maximum "stretching factor" of the matrix - how much it can amplify a vector at most.
Example 1
The singular value decomposition of:
is given by:
- อันนี้หา SVD มาให้แล้ว ใน Course นี้จะไม่สอนนะว่าทำยังไง ดังนั้นก็ไม่ต้องกังวลเรื่องข้อสอบ5555
Question: What is ?
Solution: , the largest singular value.
Solving Least-Squares Problems with SVD
- SVD can be used to solve linear least squares, including when the matrix is not full rank or
Case 1: and Full Rank
Problem: Find that minimizes where , , .
Approach:
- Suppose is the SVD of
- Let be the first columns of
Then:
Note: as the columns of are orthonormal.
Claim:
is the solution to the normal equations .
Proof of the claim:
A^T Ax &= (U_1 \Sigma_1 V^T)^T (U_1 \Sigma_1 V^T)(V\Sigma_1^{-1} U_1^T b) \\ &= V\Sigma_1^T \cancel{U_1^T U_1} \Sigma_1 \cancel{V^T V} \Sigma_1^{-1} U_1^T b \\ &= V\Sigma_1^T \cancel{\Sigma_1 \Sigma_1^{-1}} U_1^T b \\ &= V\Sigma_1^T U_1^T b \\ &= (U_1 \Sigma_1 V^T)^T b = A^T b \end{align}$$ >ทำได้ แต่ไม่แนะนำ ไปใช้วิธีของมันที่ถูกต้องใน [[10 - Linear Least Squares]] จะ efficient กว่า --- ### Case 2: General Case (Any Shape or Rank) For $A$ of any shape or rank, the least squares solution to $Ax \cong b$ is: $$\boxed{x = \sum_{\sigma_i \neq 0} \frac{u_i^T b}{\sigma_i} v_i}$$ where: - $u_i$ is the $i$-th column of $U$ - $v_i$ is the $i$-th column of $V$ > **Analogy:** This formula "inverts" only the non-zero singular values, effectively finding the best solution even when the matrix doesn't have full rank - like trying to reverse a transformation that lost some information. --- ### Example 2 Solve the least-squares problem: $$\begin{bmatrix} 0 & 1.6 \\ 0 & 0 \\ 0 & -1.2 \end{bmatrix} x \cong \begin{bmatrix} -1 \\ 0 \\ 1 \end{bmatrix}$$ The SVD is: $$U\Sigma V^T = \begin{bmatrix} 0.8000 & 0 & 0.6000 \\ 0 & 1.0000 & 0 \\ -0.6000 & 0 & 0.8000 \end{bmatrix} \begin{bmatrix} 2 & 0 \\ 0 & 0 \\ 0 & 0 \end{bmatrix} \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}^T$$ **Solution:** Since only $\sigma_1 \neq 0$: $$x = \frac{u_1^T b}{\sigma_1} v_1 = \frac{\begin{bmatrix} 0.8 & 0 & -0.6 \end{bmatrix} \begin{bmatrix} -1 \\ 0 \\ 1 \end{bmatrix}}{2} \begin{bmatrix} 0 \\ 1 \end{bmatrix} = \begin{bmatrix} 0 \\ -0.7 \end{bmatrix}$$ ![[CSS322_Doable_L14_Ex2.pdf]] --- ## Condition Number from SVD > [!NOTE] Theorem > If $\sigma_1, \ldots, \sigma_n$ are singular values of $A \in \mathbb{R}^{n \times n}$ and $A$ is invertible, then: $$\boxed{\|A^{-1}\|_2 = \frac{1}{\sigma_n}}$$ **Proof:** From the SVD $A = U\Sigma V^T$: $$A^{-1} = (U\Sigma V^T)^{-1} = V^{-T} \Sigma^{-1} U^{-1} = V\Sigma^{-1} U^T$$ Note that: $$\Sigma^{-1} = \begin{bmatrix} \frac{1}{\sigma_1} & 0 & \cdots & 0 \\ 0 & \frac{1}{\sigma_2} & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & \frac{1}{\sigma_n} \end{bmatrix}$$ However, $A^{-1} = V\Sigma^{-1} U^T$ is **not** an SVD of $A^{-1}$ because the diagonal entries of $\Sigma^{-1}$ are not in the correct order! Consider the permutation matrix: $$P = \begin{bmatrix} & & 1 \\ & \ddots & \\ 1 & & \end{bmatrix}$$ Then: $$P\Sigma^{-1} P = \begin{bmatrix} \frac{1}{\sigma_n} & \cdots & 0 \\ \vdots & \ddots & \vdots \\ 0 & \cdots & \frac{1}{\sigma_1} \end{bmatrix}$$ has diagonal entries in non-increasing order. **Note:** $PP = I$, $VP$ is orthogonal, and $PU^T$ is orthogonal. Therefore: $$A^{-1} = V\Sigma^{-1} U^T = (VP)(P\Sigma^{-1} P)(PU^T)$$ is the SVD of $A^{-1}$. Thus: $$\|A^{-1}\|_2 = \frac{1}{\sigma_n}$$ as $1/\sigma_n$ is the largest singular value of $A^{-1}$. --- ### Condition Number in 2-Norm [[5 - Conditioning and Stability]] So the condition number (in 2-norm) is: $$\boxed{\text{cond}_2(A) = \frac{\sigma_1}{\sigma_n}}$$ For **rectangular matrices** $A \in \mathbb{R}^{m \times n}$: $$\boxed{\text{cond}_2(A) = \frac{\sigma_1}{\sigma_{\min(m,n)}}}$$ > **Analogy:** The condition number is the ratio of maximum to minimum stretching - it tells you how "unbalanced" the transformation is. A high condition number means the matrix stretches very differently in different directions, making it sensitive to errors. --- ### Example 3 **Question:** What are the condition numbers in 2-norm for the matrices in Examples 1 and 2? **Solution:** For Example 1: $$\text{cond}_2(A) = \frac{\sigma_1}{\sigma_n} = \frac{2.3028}{1.3028} = 1.7676$$ For Example 2: The condition number is **infinity** because $\sigma_n = \sigma_2 = 0$. ![[CSS322_Doable_L14_Ex3.pdf]] --- > [!NOTE] Theorem > Suppose $A \in \mathbb{R}^{m \times n}$ with $\text{rank}(A) = n$. Then: $$\boxed{\text{cond}_2(A^T A) = \text{cond}_2(A)^2}$$ **Proof:** Left as exercise. > This theorem gives intuition why the **method of normal equations** is only conditionally stable (and not backward stable) - it squares the condition number! --- ## Rank Determination **Theorem:** If $A = U\Sigma V^T$, then: $$\boxed{\text{rank}(A) = \text{number of nonzero singular values}}$$ - SVD is considered to be the **most reliable rank-determination algorithm** **Example:** - อันนี้ Rank 2 $$A = \begin{bmatrix} 2 & 1 & 3 \\ 0 & 1 & 2 \\ 2 & 2 & 5 \end{bmatrix}$$ Its SVD is: $$A = \begin{bmatrix} -0.5158 & 0.6330 & -0.5774 \\ -0.2903 & -0.7632 & -0.5774 \\ -0.8061 & -0.1302 & 0.5774 \end{bmatrix} \begin{bmatrix} 7.1245 & 0 & 0 \\ 0 & 1.1141 & 0 \\ 0 & 0 & 0 \end{bmatrix} \begin{bmatrix} -0.3711 & 0.9026 & -0.2182 \\ -0.3394 & -0.3506 & -0.8729 \\ -0.8644 & -0.2498 & 0.4364 \end{bmatrix}$$ So $\text{rank}(A) = 2$ (two nonzero singular values). --- ### Example 4 **Question:** What are the ranks of the matrices in Examples 1 and 2? **Solution:** - Matrix in Example 1: rank = 2 - Matrix in Example 2: rank = 1 ![[CSS322_Doable_L14_Ex4.pdf]] ## Low-Rank Approximation > [!NOTE] Theorem > Let $A \in \mathbb{R}^{m \times n}$ whose SVD is $A = U\Sigma V^T$. Note that: $$A = \sum_{i=1}^{\min(m,n)} \sigma_i u_i v_i^T$$ where $u_i$ is the $i$-th column of $U$, $v_i$ is the $i$-th column of $V$. Let: $$A_k = \sum_{i=1}^{k} \sigma_i u_i v_i^T$$ **Then:** 1. $\text{rank}(A_k) \leq k$ 2. $A_k$ is the **best approximation** to $A$ in the Frobenius norm among matrices whose rank is $\leq k$: $$\boxed{\|A - A_k\|_F = \min\{\|A - B\|_F : B \in \mathbb{R}^{m \times n} \text{ satisfying } \text{rank}(B) \leq k\}}$$ **Storage Benefits:** - By working with $A_k$, we only need to store: - First $k$ columns of $U$ - First $k$ singular values - First $k$ columns of $V$ - Use them to compute entries of $A_k$ as needed **Applications:** - Information retrieval - Web searching - Data compression > **Analogy:** Low-rank approximation is like creating a "compressed" version of a matrix that captures the most important patterns while discarding noise. It's similar to how JPEG compression keeps important image features while removing fine details. ### Example 5 Consider: >คิดว่าไม่ต้องทำเป็นหรอกแต่ว่า `ex5.py` >เราอยากได้ Matrix ที่เล็กกว่า แต่ใกล้เคียงต้นฉบับมากที่สุด >**Image Compression (JPEG, AI image formats)** $$A = \begin{bmatrix} 9 & 3 & 4 & 1 & 0 & 2 & 5 \\ 1 & 0 & 0 & 4 & 5 & 9 & 1 \\ 12 & 0 & 4 & 1 & 2 & 0 & 0 \\ 1 & 4 & 2 & 1 & 9 & 2 & 1 \\ 0 & 0 & 5 & 2 & 2 & 8 & 4 \end{bmatrix}$$ Its SVD is $A = U\Sigma V^T$ where: $$\Sigma = \begin{bmatrix} 18.9385 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 13.4871 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 8.1289 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 5.4722 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 3.0672 & 0 & 0 \end{bmatrix}$$ ($U$ and $V$ are omitted) The rank-2 approximation $A_2$ is: $$A_2 = \begin{bmatrix} 9.5405 & 1.5514 & 4.0262 & 1.1641 & 1.9063 & 1.6309 & 2.3872 \\ -0.2316 & 1.2427 & 2.2209 & 2.7946 & 5.5117 & 7.7769 & 2.3836 \\ 11.3902 & 1.5228 & 4.2103 & 0.6635 & 0.8461 & -0.0638 & 2.2219 \\ 1.4843 & 1.0788 & 2.1430 & 2.0275 & 3.9319 & 5.3663 & 1.9684 \\ 0.8863 & 1.2391 & 2.3571 & 2.5224 & 4.9305 & 6.8365 & 2.3099 \end{bmatrix}$$ Compared to the original: $$A = \begin{bmatrix} 9 & 3 & 4 & 1 & 0 & 2 & 5 \\ 1 & 0 & 0 & 4 & 5 & 9 & 1 \\ 12 & 0 & 4 & 1 & 2 & 0 & 0 \\ 1 & 4 & 2 & 1 & 9 & 2 & 1 \\ 0 & 0 & 5 & 2 & 2 & 8 & 4 \end{bmatrix}$$ Notice how $A_2$ captures the general structure of $A$ while using only 2 components instead of 5! --- ## Summary of Key Formulas ### SVD Decomposition $$\boxed{A = U\Sigma V^T}$$ ### Matrix 2-Norm $$\boxed{\|A\|_2 = \sigma_1}$$ ### Condition Number $$\boxed{\text{cond}_2(A) = \frac{\sigma_1}{\sigma_n}}$$ ### Rank Determination $$\boxed{\text{rank}(A) = \text{number of nonzero singular values}}$$ ### Least Squares Solution (General) $$\boxed{x = \sum_{\sigma_i \neq 0} \frac{u_i^T b}{\sigma_i} v_i}$$ ### Low-Rank Approximation $$\boxed{A_k = \sum_{i=1}^{k} \sigma_i u_i v_i^T}$$ --- ## Important Notes - SVD works for **any matrix** (not just square or full rank) - Singular values are **uniquely determined** - SVD is the most **numerically stable** method for many matrix problems - Computing SVD is expensive but provides rich information about the matrix - Applications include: compression, noise reduction, dimensionality reduction, recommendation systems --- ## Moore-Penrose Pseudoinverse ### Pseudoinverse of a Scalar The pseudoinverse of a scalar $\sigma$ is: $$\boxed{\sigma^+ = \begin{cases} \frac{1}{\sigma} & \text{if } \sigma \neq 0, \\ 0 & \text{otherwise.} \end{cases}}$$ ### Pseudoinverse of a Matrix The pseudoinverse of a matrix $A \in \mathbb{R}^{m \times n}$ is given by: - Matrix doesn’t have to be square! $$\boxed{A^+ = V\Sigma^+ U^T}$$ where: - $A = U\Sigma V^T$ is the SVD of $A$ - $\Sigma^+$ is the $n \times m$ matrix with diagonal entries $\sigma_1^+, \sigma_2^+, \ldots$ (from top-left to bottom-right) > **Analogy:** The pseudoinverse is like a "generalized inverse" that works even when the regular inverse doesn't exist. It's like finding the best way to "undo" a transformation, even if some information was lost - you recover what you can and ignore what's impossible. ### Key Properties of Pseudoinverse - The pseudoinverse **exists for all matrices** (even non-square or rank-deficient) - $A^+ b$ is the **least-squares solution** to $Ax \cong b$ - If $A$ is square and nonsingular, then $\boxed{A^+ = A^{-1}}$ (reduces to regular inverse) **Why is this useful?** (Not in lecture) - Provides a unified approach to solving linear systems - Works for overdetermined systems ($m > n$) - Works for underdetermined systems ($m < n$) - Works for rank-deficient systems - Always gives the minimum-norm solution when multiple solutions exist > **Analogy:** Think of the pseudoinverse as a "smart inverse" - if a regular inverse exists, it acts like one. If not, it finds the best approximate solution possible, like trying to reverse a one-way street by finding the closest point you can get to your destination. --- ## How to Find SVD Decomposition ### The Basic Idea Find eigenvalues and eigenvectors of $A^T A$ and $AA^T$ **without actually computing** $A^T A$ and $AA^T$. ### The Connection to Eigendecomposition - The **eigenvectors of $A^T A$** make up the columns of $V$ - The **eigenvectors of $AA^T$** make up the columns of $U$ - The **square roots of eigenvalues** of $AA^T$ (and of $A^T A$) are the singular values $$\boxed{\sigma_i = \sqrt{\lambda_i(A^T A)} = \sqrt{\lambda_i(AA^T)}}$$ ### Computational Notes - Many algorithms exist to compute SVD - **All are iterative** (no closed-form solution for general matrices) - Common algorithms include: (Not in lecture) - QR algorithm - Divide-and-conquer method - Jacobi method - Power iteration methods > **Analogy:** Computing SVD is like finding the principal axes of an ellipsoid - you're looking for the natural coordinate system where the transformation is simplest (just stretching along axes). The algorithms iteratively rotate and refine until they find these special directions. --- ## Complete Summary: SVD Workflow ### 1. Decomposition $$A = U\Sigma V^T$$ ### 2. Extract Information - **Singular values:** $\sigma_1, \sigma_2, \ldots, \sigma_p$ (diagonal of $\Sigma$) - **Left singular vectors:** columns of $U$ (eigenvectors of $AA^T$) - **Right singular vectors:** columns of $V$ (eigenvectors of $A^T A$) ### 3. Applications | Task | Formula | Usage | |------|---------|-------| | **Matrix norm** | $\\|A\\|_2 = \sigma_1$ | Measure matrix size | | **Condition number** | $\text{cond}_2(A) = \frac{\sigma_1}{\sigma_n}$ | Measure sensitivity | | **Rank** | # of nonzero $\sigma_i$ | Determine independence | | **Least squares** | $x = \sum_{\sigma_i \neq 0} \frac{u_i^T b}{\sigma_i} v_i$ | Solve $Ax \cong b$ | | **Pseudoinverse** | $A^+ = V\Sigma^+ U^T$ | Generalized inverse | | **Low-rank approx** | $A_k = \sum_{i=1}^k \sigma_i u_i v_i^T$ | Compress data | --- ## Quick Reference: When to Use SVD ✅ **Use SVD when you need:** - To solve least-squares problems (especially rank-deficient) - To determine matrix rank reliably - To compute condition numbers - To find low-rank approximations - To compress data or reduce noise - To compute pseudoinverses ⚠️ **SVD is expensive:** - Computational cost: $O(mn^2)$ for $m \times n$ matrix with $m \geq n$ - Use faster methods (QR, LU) when possible for simpler tasks --- ## Mathematical Relationships ### Between Singular Values and Eigenvalues **For symmetric positive definite $A$:** - Singular values = eigenvalues - $V = U$ (left and right singular vectors are the same) **For general $A$:** - $\sigma_i^2 = \lambda_i(A^T A) = \lambda_i(AA^T)$ - $\sigma_i = |\lambda_i(A)|$ only if $A$ is normal ($A^T A = AA^T$) ### Spectral Theorem Connection SVD generalizes the spectral theorem: - **Spectral theorem:** Symmetric $A = Q\Lambda Q^T$ (eigendecomposition) - **SVD:** General $A = U\Sigma V^T$ (singular value decomposition) > **Analogy:** The spectral theorem works for symmetric matrices (like perfect circles). SVD works for all matrices (including ellipses) - it's a more general tool that handles asymmetry. --- ## Final Remarks ### Why SVD is Fundamental 1. **Universality:** Works for any matrix 2. **Stability:** Numerically reliable 3. **Rich information:** Provides norm, rank, condition number, and best approximations 4. **Theoretical importance:** Connects linear algebra, optimization, and statistics ### Practical Considerations - **In practice:** Use library functions (NumPy, MATLAB, etc.) - don't implement yourself - **For large matrices:** Consider iterative methods or randomized SVD - **For sparse matrices:** Specialized algorithms exist (ARPACK, etc.) ### Historical Note - Developed independently by several mathematicians in the 1870s - Named after Moore (1920) and Penrose (1955) for the pseudoinverse - Became computationally practical with Golub-Kahan algorithm (1965) - Now fundamental in data science, machine learning, and scientific computing