Signal Dequantization via Convex Optimization How could one prove the following problem?
Given a vector $\mathbf{y}=\left(y_{k}\right) \in \mathbb{R}^{n},$ we consider the energy function $E: \mathbb{R}^{n} \rightarrow \mathbb{R}$ defined by
$$
\forall \mathbf{x}=\left(x_{k}\right) \in \mathbb{R}^{n}, \quad E(\mathbf{x})=\sum_{i=1}^{n-1}\left(x_{k+1}+x_{k-1}-2 x_{k}\right)^{2}
$$
and the set
$$
C=\left\{\mathbf{x} \in \mathbb{R}^{n}, \forall k \in \mathbb{N}, 1 \leq k \leq n,\left|x_{k}-y_{k}\right| \leq q\right\}
$$
where $q$ is a fixed positive real number.


*

*Compute the gradient of $E$

*Show that $E$ is convex.

*Show that $C$ is convex.

*Give an explicit formula for $\pi_{C}(\mathbf{x}),$ the projection on $C$ of a vector $\mathbf{x} \in \mathbb{R}^{n}$.


Background:
In this project we are given a temperature signal $\mathbf{y}=\left(y_{k}\right) \in \mathbb{R}^{n},$ where $y_{1}, y_{2}, \ldots, y_{n}$ represent the temperature measured at different times. Due to the poor resolution of the measure, the signal is quantized, in the sense that all measured values $y_{k}$ are multiples of $1 / 2 .$ the aim of the project is to build a non-quantized signal $\mathbf{x}=\left(x_{k}\right) \in \mathbb{R}^{n}$ that is smoother than $\mathbf{y}$ and has the property that $\left|x_{k}-y_{k}\right| \leq 1 / 4$ for all $k$  (so that the quantized version of $ \mathbf{x} $ is $ \mathbf{y}$.
 A: Given the vector $ \boldsymbol{y} \in \mathbb{R}^{n} $ consider the Energy Function:
$$ E : \mathbb{R}^{n} \to \mathbb{R}, \; E \left( \boldsymbol{x} \right) = \sum_{k = 2}^{n} {\left( {x}_{k + 1} + {x}_{k - 1} - 2 {x}_{k} \right)}^{2} $$
And the set:
$$ \mathcal{C} = \left\{ \boldsymbol{x} \in \mathbb{R}^{n} \mid k \in \left\{ 1, 2, \ldots, n \right\}, \; \left| {x}_{k} - {y}_{k} \right| \leq q \right\} $$
The Gradient of $ E \left( \boldsymbol{x} \right) $
One could see that $ E \left( \boldsymbol{x} \right) $ could be written in Matrix Form:
$$ E \left( \boldsymbol{x} \right) = {\left\| A x \right\|}_{2}^{2} $$
Where the matrix $ A \in \mathbb{R}^{ \left( n - 2 \right) \times n } $ is given by:
$$ \begin{bmatrix}
1 & -2 & 1 & 0 & \ldots & 0 & 0\\ 
0 & 1 & -2 & 1 & 0 & \ldots & 0 \\ 
 &  & \vdots &  & \\ 
0 & 0 & \ldots & 0 & 1 & -2 & 1 
\end{bmatrix} $$
So the gradient is given by:
$$ \frac{\partial E }{\partial \boldsymbol{x}} = {A}^{T} A x $$
Convexity of $ E \left( \boldsymbol{x} \right) $
The function $ E \left( \boldsymbol{x} \right) $ is convex since it is a norm of a Linear Term of $ \boldsymbol{x} $ which means its Hessian Matrix (Which is given by $ {A}^{T} A $) is a Positive Semi Definite (PSD) Matrix.
Convexity of the Set $ \mathcal{C} $
The set $ \mathcal{C} $ is basically a shifted $ {L}_{\infty} $ ball. Since a shift in space doesn't affect convexity and it is known that the $ {L}_{\infty} $ Ball is convex (See How to Prove the $ {L}_{\infty} $ Ball Is Convex?) the set is convex.
Projection onto the Set $ \mathcal{C} $
Since the set is a shifted version of the $ {L}_{\infty} $ ball one could use the known projection - Orthogonal Projection onto the $ {L}_{\infty} $ Unit Ball.
Basically in this case it means the projection, component wise, is given by:
$$ {{\pi}_{ \mathcal{C} } \left( \boldsymbol{x} \right)}_{k} = \begin{cases}
{y}_{k} + q & \text{ if } {x}_{k} - {y}_{k} > q  \\ 
{y}_{k} - q & \text{ if } {x}_{k} - {y}_{k} < -q \\ 
{x}_{k} & \text{ if } \left| {x}_{k} - {y}_{k} \right| \leq q 
\end{cases} $$
