Unique solution of linear system involving hessian and gradient

Question

Consider the following problem: $$ f(x) = \frac{1}{2}x^T Hx + b^T x. $$

In this case, ($f''(x) = H$) with $H \in \mathbb{R^{n \times n}}$, and hence:

$$ f''(x^{k+1})(x^{k+1} - x^k) = H (x^{k+1} - x^k) = \nabla f( x^{k+1}) - \nabla f( x^k), \quad k = 0, \ldots n-1 $$

If $H$ is unknown and we only know the gradients of (f) as well as the vectors $$x^0, \ldots, x^{n-1}$$, we obtain (n) linear systems:

$$ H (x^{k+1} - x^k) = \nabla f(x^{k+1}) - \nabla f (x^k), \quad k = 0, \ldots, n - 1 $$

Why is $H$ uniquely determined if $(x^{k+1} - x^k)$ are linear independent for $k=0, \cdots n-1$

Answer 1

Let's define a matrix $X$ such that its general term is given by:

$$\boxed{X_{ik} = \left[x^{k+1}-x^{k}\right]_i}$$

So, each $x^{k+1} -x^k$ defines a column of $X$.

(the subscript $i$ denotes the $i$-th term of the vector)

---

Moreover, let's define a matrix $F$ such that its general term is given by:

$$\boxed{F_{ik} = \left[\nabla f(x^{k+1})-\nabla f(x^{k}) \right]_i}$$

So, each $\nabla f(x^{k+1})-\nabla f(x^{k})$ defines a column of $F$.

(the subscript $i$ denotes the $i$-th term of the vector)

---

Thus, all matrices $H$, $X$ and $F$ have dimensions $n\times n$. And we have the following equation:

$$\boxed{H\,X = F}$$

---

$X$ is invertible if, and only if, all its columns are linearly independent. Moreover, if $X$ is invertible, the system has a unique solution given by:

$$\boxed{H = F\,X^{-1}}$$

---

• [Proof-1] If $X$ is invertible, then, a solution exists.

$$H\,X = F \Rightarrow H\,X\,X^{-1} = F\,X^{-1} \Rightarrow H = F\,X^{-1}$$

• [Proof-2] If $X$ is invertible and $H_1$ and $H_2$ are solutions of the system, then, $H_1 = H_2$ (solution is unique).

$$H_1\,X = F$$

$$H_2\,X = F$$

$$[H_1-H_2]\,X = O \Rightarrow [H_1-H_2]\,X\,X^{-1} = O\,X^{-1} \Rightarrow H_1-H_2 = O \Rightarrow H_1 = H_2$$

• [Proof-3] If there is a solution but $X$ is not invertible, there are infinite solutions (solution is not unique).

If $X$ is not invertible, it has at least one zero-valued eigenvalue. So, there is a matrix $V\neq O$ such that $V\,X = O$.

If $H_s$ is a solution of the system, then $H_s + \alpha\,V$ is also a solution, for any $\alpha\in\mathbb{R}$.

$$V\,X = O$$

$$H_s\,X = F$$

$$[H_s + \alpha\,V]\,X = H_s\,X + \alpha\,V\,X = F + O = F$$

($O$ corresponds to the $n\times n$ matrix filled with zeroes)

Answer 2

If $H\delta_k = b_k$ with $\delta_k,\ \ k = 1,\cdots,n$ with $n=\text{rank}(H)$ are linear independent, then making $D = (\delta_1',\cdots,\delta_k')'$ and $B =(b_1',\cdots,b_k')'$ we have

$$ H D = B $$

and $D$ is invertible.

Answer 3

Here is the full solution to the problem using the Laplace transform:

\begin{align*} \mathcal{L}{f''(x)} &= s^2 F(s) - sf(0) - f'(0) \ \mathcal{L}{H (x_k - x_{k-1})} &= H (x_k - x_{k-1}) \ \Rightarrow \mathcal{L}{f''(x_k) (x_{k+1} - x_k)} &= H (x_{k+1} - x_k) \ \Rightarrow s^2 F_k(s) - sf(x_k) - f'(x_k) &= H (x_{k+1} - x_k) \end{align*}

Therefore, we have the following system of equations:

\begin{bmatrix} s^2 & -s & -1 \\ s^2 & -s-1 & -1 \\ \vdots & \vdots & \vdots \\ s^2 & -s-(n-1) & -1 \end{bmatrix} \begin{bmatrix} F_0(s) \\ F_1(s) \\ \vdots \\ F_{n-1}(s) \end{bmatrix}

\begin{bmatrix} H(x_1 - x_0) \\ H(x_2 - x_1) \\ \vdots \\ H(x_n - x_{n-1}) \end{bmatrix}

This system of equations can be written in the following form:

$A \mathbf{F} = \mathbf{B}$

where $A$ is the matrix whose rows are the vectors $(s^2, -s, -1)$ and $B$ is the matrix whose rows are the vectors $H(x_1 - x_0)$, $H(x_2 - x_1)$, $\cdots$, $H(x_n - x_{n-1})$.

Since the vectors $x_{k+1} - x_k$ are linearly independent, the matrix $A$ is invertible. Therefore, we can solve the system of equations to uniquely determine the matrix $H$:

$H = A^{-1} \mathbf{B}$

Therefore, the Laplace transform can be used to uniquely determine the matrix $H$ given the gradients of $f$ and the vectors $x_0, \cdots, x_{n-1}$ under the condition that the vectors $x_{k+1} - x_k$ are linearly independent for $k=0, \cdots, n-1$.