hw6_532_fall21_solutions E C E 532|VERY HELPFUL

CS/ECE/ME 532 Homework 6: Iterative Algorithms for Regularized LS 1. Gradient Descent Convergence. Consider the Gradient Descent iteration for solving a standard least-squares problem with A ∈ R m×n , b ∈ R m, and A has full column rank. Recall that this iteration begins with some initial x0 and then: xk+1 = xk − µAT (Axk − b) for k = 0, 1, . . . (1) a) We expect the algorithm to converge to x? = (ATA) −1ATb. Define the error as ek := xk − x?. Show how to rewrite (1) in the form ek+1 = P ek. What is the matrix P ? SOLUTION: Substitute xk 7→ ek + x? and xk+1 7→ ek+1 + x? and obtain: ek+1 = ek − µAT (Aek + Ax? − b) Then, using the fact that ATAx? = ATb, the expression simplifies to: ek+1 = (I − µATA)ek Therefore P = I − µATA. b) Define the residual rk := Axk − b. Show how to rewrite (1) in the form rk+1 = Qrk. What is the matrix Q? SOLUTION: Compute the residual at time k + 1 and obtain: rk+1 = Axk+1 − b = A(xk − µAT (Axk − b)) − b = (I − µAAT )(Axk − b) = (I − µAAT )rk Therefore Q = I − µAAT. c) Let {σi} be the singular values of A. Prove that when 0 µ 2 σ 2 1 , we have limk→∞ ek = 0. Hint: substitute the SVD of A into your expression for P . SOLUTION: Let UΣV T = A be the full SVD of A. The expression for ek+1 becomes: ek+1 = (I − µV ΣTΣV T )ek Multiply by V T on both sides and define V Tek = qk and rewrite as: qk+1 = (I − µΣTΣ)qk Since V T is orthogonal, ek → 0 if and only if qk → 0. And this, in turn, is equivalent to each component of qk going to zero separately (because I − µΣTΣ is diagonal). Moreover, A has full column rank, so ΣTΣ is invertible—it is diagonal with entries σ1 ≥ · · · ≥ σn 0. The equations corresponding to individual components of qk look like: qk+1 = (1 − µσ2 )qk. We have convergence to zero if and only if |1 − µσ2 i |