The set of $n \times n$ symmetric Toeplitz matrices is

$$\left\{ x_1 \mathrm M_1 + x_2 \mathrm M_2 + \cdots + x_n \mathrm M_n  \mid x_1, x_2, \dots, x_n \in \mathbb R \right\}$$

where $\mathrm M_1, \mathrm M_2, \dots, \mathrm M_n$ are $n \times n$ symmetric Toeplitz **basis** matrices. Let $\mathrm M_1 = \mathrm I_n$ correspond to the main diagonal, whereas the remaining basis matrices correspond to super and sub diagonals.

Let $\mathrm M : \mathbb R^n \to \mbox{Sym}_n (\mathbb R)$ be defined by

$$\mathrm M (\mathrm x) := x_1 \mathrm M_1 + x_2 \mathrm M_2 + \cdots + x_n \mathrm M_n$$

----------

###Spectral norm

To complement Suvrit's comment, using the **spectral** norm, we obtain the following unconstrained optimization problem in $\mathrm x \in \mathbb R^n$

$$\begin{array}{ll} \text{minimize} & \| \mathrm M (\mathrm x) - \mathrm A \|_2\end{array}$$

which can be rewritten as the following [semidefinite program][1] (SDP) in $\mathrm x \in \mathbb R^n$ and $t \geq 0$

$$\boxed{\begin{array}{ll} \text{minimize} & t\\ \text{subject to} & - t \,\mathrm I_n \preceq - \mathrm A + x_1 \mathrm M_1 + x_2 \mathrm M_2 + \cdots + x_n \mathrm M_n \preceq t \,\mathrm I_n\end{array}}$$

----------

###Frobenius norm

To complement Federico's comment, using the *squared* **Frobenius** norm, we obtain the following unconstrained quadratic program (QP) in $\mathrm x \in \mathbb R^n$

$$\begin{array}{ll} \text{minimize} & \| \mathrm M (\mathrm x) - \mathrm A \|_{\text{F}}^2\end{array}$$

where the objective function is

$$\begin{bmatrix} x_1\\ x_2\\ \vdots \\ x_n\end{bmatrix}^\top \begin{bmatrix} \langle \mathrm M_1, \mathrm M_1 \rangle & \langle \mathrm M_1, \mathrm M_2 \rangle & \cdots & \langle \mathrm M_1, \mathrm M_n \rangle\\ \langle \mathrm M_2, \mathrm M_1 \rangle & \langle \mathrm M_2, \mathrm M_2 \rangle & \cdots & \langle \mathrm M_2, \mathrm M_n \rangle\\ \vdots & \vdots & \ddots & \vdots\\ \langle \mathrm M_n, \mathrm M_1 \rangle & \langle \mathrm M_n, \mathrm M_2 \rangle & \cdots & \langle \mathrm M_n, \mathrm M_n \rangle\\ \end{bmatrix} \begin{bmatrix} x_1\\ x_2\\ \vdots \\ x_n\end{bmatrix} - 2 \,\begin{bmatrix} \langle \mathrm A, \mathrm M_1 \rangle\\ \langle \mathrm A, \mathrm M_2 \rangle\\ \vdots \\ \langle \mathrm A, \mathrm M_n \rangle\end{bmatrix}^\top \begin{bmatrix} x_1\\ x_2\\ \vdots \\ x_n\end{bmatrix} + \| \mathrm A \|_{\text{F}}^2$$

where $\langle \mathrm M_i, \mathrm M_j \rangle$ denotes the [Frobenius inner product][2] of (symmetric) basis matrices $\mathrm M_i$ and $\mathrm M_j$. 

Computing the gradient of the objective function and finding where it does vanish, we obtain the following linear system

$$\begin{bmatrix} \langle \mathrm M_1, \mathrm M_1 \rangle & \langle \mathrm M_1, \mathrm M_2 \rangle & \cdots & \langle \mathrm M_1, \mathrm M_n \rangle\\ \langle \mathrm M_2, \mathrm M_1 \rangle & \langle \mathrm M_2, \mathrm M_2 \rangle & \cdots & \langle \mathrm M_2, \mathrm M_n \rangle\\ \vdots & \vdots & \ddots & \vdots\\ \langle \mathrm M_n, \mathrm M_1 \rangle & \langle \mathrm M_n, \mathrm M_2 \rangle & \cdots & \langle \mathrm M_n, \mathrm M_n \rangle\\ \end{bmatrix} \begin{bmatrix} x_1\\ x_2\\ \vdots \\ x_n\end{bmatrix} = \,\begin{bmatrix} \langle \mathrm A, \mathrm M_1 \rangle\\ \langle \mathrm A, \mathrm M_2 \rangle\\ \vdots \\ \langle \mathrm A, \mathrm M_n \rangle\end{bmatrix}$$

Fortunately, the basis matrices are *orthogonal* and, thus, the matrix above is diagonal. Hence,

$$\begin{bmatrix} n & 0 & \cdots & 0\\ 0 & 2(n-1) & \cdots & 0\\ \vdots & \vdots & \ddots & \vdots\\ 0 & 0 & \cdots & 2 \end{bmatrix} \begin{bmatrix} x_1\\ x_2\\ \vdots \\ x_n\end{bmatrix} = \begin{bmatrix} \sum_{i=1}^n a_{i,i}\\ 2 \sum_{i=1}^{n-1} a_{i,i+1}\\ \vdots \\ 2 a_{n,n}\end{bmatrix}$$

and, thus, the solution are the **arithmetic means** of the $n$ diagonals of $\rm A$

$$\boxed{\begin{array}{rl} x_1 &= \dfrac 1n \displaystyle\sum_{i=1}^n a_{i,i}\\ x_2 &= \dfrac 1{n-1} \displaystyle\sum_{i=1}^{n-1} a_{i,i+1}\\ x_3 &= \dfrac 1{n-2} \displaystyle\sum_{i=1}^{n-2} a_{i,i+2}\\ & \vdots\\ x_n &= a_{n,n}\end{array}}$$


  [1]: https://en.wikipedia.org/wiki/Semidefinite_programming
  [2]: https://en.wikipedia.org/wiki/Frobenius_inner_product