A Short Note on SOE-Based Toeplitz Matrix Approximation
Lemma
\[\|A\|_2 \leq n \,\|A\|_{\max}.\]Approximation of a Toeplitz Matrix
Let a Toeplitz matrix $A=\left[a_{ij}\right]{n \times n}, \qquad a{ij}=f(i-j)$.
Suppose $f$ admits a sum-of-exponentials (SOE) approximation such that
\[\bigl|f(i-j) - \sum_{l=1}^k w_l e^{-s_l (\,i-j\,)}\bigr| < \epsilon \quad \text{for all}\; i,j.\]Define a matrix $ B = [b_{ij}]$ by \(b_{ij} = \sum_{l=1}^k w_l \, e^{-s_l (\,i-j\,)}.\) Then $B$ serves as an approximation to $ A$.
Factorization of $B$
Observe that $B$ can be factorized as
\[B = \underbrace{ \begin{pmatrix} w_1 e^{-s_1 \cdot 1} & \cdots & w_k e^{-s_k \cdot 1}\\ \vdots & \ddots & \vdots \\ w_1 e^{-s_1 \cdot n} & \cdots & w_k e^{-s_k \cdot n} \end{pmatrix}_{n \times k} }_{\displaystyle \text{Call this }U} \; \underbrace{ \begin{pmatrix} e^{-s_1 \cdot 1} & \cdots & e^{-s_1 \cdot n}\\ \vdots & \ddots & \vdots \\ e^{-s_k \cdot 1} & \cdots & e^{-s_k \cdot n} \end{pmatrix}_{k \times n} }_{\displaystyle \text{Call this }V}\]which immediately implies \(\mathrm{rank}(B) \;\leq\; k.\)
Low-Rank Approximation Error
Because $\mathrm{rank}(B) \leq k$, we have \(\sigma_k \;=\; \min_{\mathrm{rank}(X)\,\leq\,k} \|A - X\|_2 \;\leq\; \|A - B\|_2 \;\leq\; n \,\|A - B\|_{\max} \;\leq\; n\,\epsilon.\)
Thus, $B$ provides a rank-$k$ approximation to $A$ with spectral norm error at most $n\,\epsilon$.
Convolution Viewpoint
A Toeplitz matrix can be viewed as a discrete version of an integral convolution. In continuous form, one might approximate \(\int_{a}^b f(t-\tau)\,u(\tau)\,d\tau\) by an SOE representation: \(f(t - \tau) \;\approx\; \sum_{l=1}^{k} w_l \, e^{-s_l (\,t - \tau\,)}.\) Hence, \(\int_{a}^b f(t-\tau)\,u(\tau)\,d\tau \;\approx\; \int_{a}^b \sum_{l=1}^{k} w_l \, e^{-s_l (\,t-\tau\,)}\,u(\tau)\,d\tau \;=\; \sum_{l=1}^{k} \Bigl(\int_{a}^{b} w_l\,e^{\,s_l \tau}\,u(\tau)\,d\tau\Bigr) \,e^{-s_l t}.\)
This continuous analogy mirrors the construction of low-rank approximations for Toeplitz matrices via sum-of-exponentials.
