For an arbitrary $N\times N$ Hermitian matrix $A$, I want to derive a Toeplitz matrix from $A$ such that the eigenvectors of both matrices have minimal change. 


Specifically I want find the Toeplitz matrix such that the $L^2$ norm between the eigenvectors of the Toeplitz matrix and eigenvectors of the matrix $A$ is minimal. Is there any alternative method other than searching numerically for the matrix? What is the computational cost of such such search?


I am aware of some work done related to perturbations of Toeplitz matrices, in addition eigenvectors of banded toeplitz matrix is studied, but the matrix I want in my application is not banded. I would appreciate any suggestion.


Edit: Is the problem tractable/solvable/realistic if we are given a sequence of matrices $A^n$ instead of $A$?



Finding Toeplitz matrix nearest to a given matrix
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](https://en.wikipedia.org/wiki/Semidefinite_programming) (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}}$$


whose solution can be found numerically.




---


### 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](https://en.wikipedia.org/wiki/Frobenius_inner_product) 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 solutions $x\_1, x\_2, \dots, x\_n$ are the **arithmetic means** of the $n$ (distinct) diagonals of $\rm A$


$$\begin{array}{rl} x\_1 &= \dfrac{\langle \mathrm A, \mathrm M\_1 \rangle}{\langle \mathrm M\_1, \mathrm M\_1 \rangle} = \dfrac 1n \displaystyle\sum\_{i=1}^n a\_{i,i}\\ x\_2 &= \dfrac{\langle \mathrm A, \mathrm M\_2 \rangle}{\langle \mathrm M\_2, \mathrm M\_2 \rangle} = \dfrac 1{n-1} \displaystyle\sum\_{i=1}^{n-1} a\_{i,i+1}\\ x\_3 &= \dfrac{\langle \mathrm A, \mathrm M\_3 \rangle}{\langle \mathrm M\_3, \mathrm M\_3 \rangle} = \dfrac 1{n-2} \displaystyle\sum\_{i=1}^{n-2} a\_{i,i+2}\\ & \qquad\qquad\quad\vdots\\ x\_n &= \dfrac{\langle \mathrm A, \mathrm M\_n \rangle}{\langle \mathrm M\_n, \mathrm M\_n \rangle} = \displaystyle\sum\_{i=1}^1 a\_{i,i+n-1} = a\_{1,n}\end{array}$$


Lastly, the Toeplitz matrix nearest to the given symmetric matrix $\rm A$ is


$$\boxed{\hat{\mathrm X} := \left( \dfrac 1n \displaystyle\sum\_{i=1}^n a\_{i,i} \right) \mathrm I\_n + \left( \dfrac 1{n-1} \displaystyle\sum\_{i=1}^{n-1} a\_{i,i+1} \right) \mathrm M\_2 + \left( \dfrac 1{n-2} \displaystyle\sum\_{i=1}^{n-2} a\_{i,i+2} \right) \mathrm M\_3 + \cdots + a\_{1,n} \mathrm M\_n}$$


