Homework 4

Theory

You can either write your answers to theoretical questions on paper or (preferably) edit them in the file hw4/paper.tex. Please show all the mathematical derivations that you perform.

1. The conjugate gradient algorithm is applied to iteratively optimizing $\Vert\mathbf{A x-b}\Vert^2$ for $\mathbf{x}$ starting with $\mathbf{x}_0=\mathbf{0}$ . Prove that, after $N$ -th iteration, the solution is given by $\mathbf{x}_N = \mathbf{F}_N \mathbf{b}$ , where

   $$\mathbf{F}_N = \sum\limits_{n=1}^{N} \frac{\mathbf{s}_n \mathbf{s}_n^T}{\mathbf{s}_n^T \mathbf{A}^T \mathbf{A} \mathbf{s}_n} \mathbf{A}^T$$ (1)

   
   
   and $\mathbf{s}_n$ is the model step at $n$ -th iteration.
2. If the model shaping operator $\mathbf{S}_m$ admits a symmetric splitting $\mathbf{S}_m=\mathbf{H}_m \mathbf{H}_m^T$ with square and invertable $\mathbf{H}_m$ , the model shaping equation can be rewritten in a symmetric form

   $$\left[\mathbf{I} + \mathbf{S}_m (\mathbf{B F - I})\right]^{-1}\... ...(\mathbf{B F - I}) \mathbf{H}_m\right]^{-1} \mathbf{H}_m^T \mathbf{B d}\;.$$ (2)

   
   
   1. Prove equation (10).
   2. Assuming a symmetric splitting for the data shaping operator $\mathbf{S}_d=\mathbf{H}_d^T \mathbf{H}_d$ , find a symmetric form of the data shaping equation

      $$\mathbf{B} \left[\mathbf{I} + \mathbf{S}_d (\mathbf{F B - I})\right]^{-1} \mathbf{S}_d \mathbf{d} =$$ (3)

      
      

Homework 4