Logo

AskSia

Plus

Problem 2 (13 points). Least Squares Without Full Column Rank Consider the leas...
Sep 26, 2024
Solution by Steps
step 1
To derive the expression of the infinitely many solutions based on singular value decomposition (SVD), we start with the SVD of the matrix X \boldsymbol{X} :
X=VΣ1U1⊤ \boldsymbol{X} = \boldsymbol{V} \boldsymbol{\Sigma}_{1} \boldsymbol{U}_{1}^{\top} where V \boldsymbol{V} is an orthogonal matrix, Σ1 \boldsymbol{\Sigma}_{1} is a diagonal matrix, and U1 \boldsymbol{U}_{1} is a semi-orthogonal matrix.
step 2
We define A:=VΣ1 \boldsymbol{A} := \boldsymbol{V} \boldsymbol{\Sigma}_{1} , which is a square matrix of full rank. We let z=U1⊤θ \boldsymbol{z} = \boldsymbol{U}_{1}^{\top} \boldsymbol{\theta} and set up the optimization problem:
min⁡z∥Az−y∥22 \min_{\boldsymbol{z}} \|\boldsymbol{A} \boldsymbol{z} - \boldsymbol{y}\|_{2}^{2}
step 3
Applying the first-order optimality condition, we find the optimal z \boldsymbol{z} such that:
A⊤(Az−y)=0 \boldsymbol{A}^{\top}(\boldsymbol{A} \boldsymbol{z} - \boldsymbol{y}) = 0
step 4
Solving for z \boldsymbol{z} , we get:
z=Σ1−1V⊤y \boldsymbol{z} = \boldsymbol{\Sigma}_{1}^{-1} \boldsymbol{V}^{\top} \boldsymbol{y}
step 5
The general solution for θ \boldsymbol{\theta} can be expressed as:
θ=U1z+U2s \boldsymbol{\theta} = \boldsymbol{U}_{1} \boldsymbol{z} + \boldsymbol{U}_{2} s where s s is a vector in Rd−n \mathbb{R}^{d-n} .
step 6
Therefore, the solution set is given by:
{U1Σ1−1V⊤y+U2s∣s∈Rd−n} \left\{ \boldsymbol{U}_{1} \boldsymbol{\Sigma}_{1}^{-1} \boldsymbol{V}^{\top} \boldsymbol{y} + \boldsymbol{U}_{2} s \mid s \in \mathbb{R}^{d-n} \right\}
step 7
The optimal function value is obtained by substituting θ \boldsymbol{\theta} back into the original least squares problem, yielding:
min⁡θ∥Xθ−y∥22=∥y−XU1Σ1−1V⊤y∥22 \min_{\boldsymbol{\theta}} \|\boldsymbol{X} \boldsymbol{\theta} - \boldsymbol{y}\|_{2}^{2} = \|\boldsymbol{y} - \boldsymbol{X} \boldsymbol{U}_{1} \boldsymbol{\Sigma}_{1}^{-1} \boldsymbol{V}^{\top} \boldsymbol{y}\|_{2}^{2}
Answer
The expression of the infinitely many solutions is {U1Σ1−1V⊤y+U2s∣s∈Rd−n} \left\{ \boldsymbol{U}_{1} \boldsymbol{\Sigma}_{1}^{-1} \boldsymbol{V}^{\top} \boldsymbol{y} + \boldsymbol{U}_{2} s \mid s \in \mathbb{R}^{d-n} \right\} and the optimal function value is ∥y−XU1Σ1−1V⊤y∥22 \|\boldsymbol{y} - \boldsymbol{X} \boldsymbol{U}_{1} \boldsymbol{\Sigma}_{1}^{-1} \boldsymbol{V}^{\top} \boldsymbol{y}\|_{2}^{2} .
Key Concept
The least squares problem without full column rank leads to infinitely many solutions due to the rank deficiency of the matrix X \boldsymbol{X} .
Explanation
The SVD provides a structured way to express the solutions, highlighting the role of the orthogonal matrices U1 \boldsymbol{U}_{1} and U2 \boldsymbol{U}_{2} in forming the general solution set.
© 2023 AskSia.AI all rights reserved