1. Gradient of $g(z)$ with respect to $z$

Given the function:

$g(z) = \frac{1}{2} \|Az - b\|^2_2 + \frac{1}{2} \|z\|^2_2$

where $A$ is an $n \times n$ matrix, $b$ is an $n$-dimensional vector, and $z$ is an $n$-dimensional vector, we want to find the gradient $\nabla g(z)$ with respect to $z$.

Step 1: Expand the terms

The first term $\|Az - b\|_2^2$ is the squared norm, which can be written as:

$\|Az - b\|^2_2 = (Az - b)^\top (Az - b)$

Expanding this:

$\|Az - b\|^2_2 = z^\top A^\top Az - 2b^\top Az + b^\top b$

The second term is:

$\|z\|^2_2 = z^\top z$

So, the function $g(z)$ becomes:

$g(z) = \frac{1}{2} \left( z^\top A^\top A z - 2b^\top A z + b^\top b \right) + \frac{1}{2} z^\top z$

Step 2: Differentiate with respect to $z$

Now, we differentiate each term with respect to $z$.

• The derivative of $\frac{1}{2} z^\top A^\top A z$ with respect to $z$ is $A^\top A z$.
• The derivative of $- b^\top A z$ with respect to $z$ is $- A^\top b$.
• The derivative of $\frac{1}{2} z^\top z$ with respect to $z$ is $z$.
• The term $\frac{1}{2} b^\top b$ is independent of $z$ and vanishes upon differentiation.

Therefore, the gradient $\nabla g(z)$ is:

$\nabla g(z) = A^\top A z - A^\top b + z$

This can be simplified to:

$\nabla g(z) = (A^\top A + I)z - A^\top b$

where $I$ is the identity matrix of appropriate dimensions.

2. Optimal Step Size $\alpha_k$ in Gradient Descent

In gradient descent, the update rule is:

$z_k = z_{k-1} - \alpha_k \nabla g(z_{k-1})$

where $\alpha_k$ is the step size to be determined.

To find the optimal step size $\alpha_k$, we want to minimize $g(z_k)$ with respect to $\alpha_k$. Substitute the update rule into $g(z_k)$:

$g(z_k) = \frac{1}{2} \|A(z_{k-1} - \alpha_k \nabla g(z_{k-1})) - b\|^2_2 + \frac{1}{2} \|z_{k-1} - \alpha_k \nabla g(z_{k-1})\|^2_2$

This expression is generally difficult to minimize directly. However, for quadratic functions like this one, the optimal step size can be obtained by differentiating $g(z_k)$ with respect to $\alpha_k$ and setting it to zero.

To derive the optimal step size $\alpha_k$, consider:

$\alpha_k = \frac{\nabla g(z_{k-1})^\top \nabla g(z_{k-1})}{\nabla g(z_{k-1})^\top (A^\top A + I)\nabla g(z_{k-1})}$

This choice of $\alpha_k$ ensures that the step size is optimal at each iteration, given the current gradient.

---

Do you want details or have any questions?

Here are some related questions:

1. What is the significance of the identity matrix $I$ in the gradient expression?
2. How does the condition number of $A$ affect the convergence of gradient descent in this scenario?
3. Can you apply gradient descent to a non-quadratic function? How would the step size change?
4. How would the gradient descent update rule change if $g(z)$ had an additional regularization term?
5. How does the choice of initial point $z_0$ impact the convergence of gradient descent?

Tip: When choosing a step size in gradient descent, it's often useful to perform a line search to find the optimal value, particularly when dealing with non-quadratic functions.